La paradoja de Skolem no - Parte 2

Question

Esta es la continuación de una pregunta anterior: No es la paradoja de Skolem .

Supongamos que tenemos un modelo contable, no estándar de la aritmética de Peano en ZFC.

Dejemos que $N^*$ sea el universo de este modelo y que $p \in N^*$ sea un número natural no estándar mayor que cualquier número natural estándar. En ZFC podemos definir el conjunto $X = \{x : x \in N^* \land x < p\}$ . Sea $Y = X \cup \{p\}$ . $X$ y $Y$ son ambos conjuntos contablemente infinitos y podemos definir fácilmente una biyección entre $X$ y $Y$ en ZFC. Por ejemplo, podemos definir el conjunto de pares ordenados:

$F = \{(0,p), (1,0), (2,1), (3,2), ...\}$ .

Mi pregunta es por qué la biyección no $F$ existen dentro del modelo?

En mi pregunta anterior había cierta confusión sobre cómo estaba definiendo los conjuntos dentro del modelo. Podemos codificar cualquier conjunto "finito" de números naturales como un número natural utilizando potencias de 2. Por ejemplo, podemos codificar el conjunto $\{1,2,3\}$ como $2^1+2^2+2^3=14$ . Del mismo modo, podemos codificar una biyección como un número natural. En primer lugar, definimos un método para codificar un par ordenado como un número natural. Codificar $(a,a)$ como $2^a$ . Codificar $(a,b)$ como $2^{a+1} + 2^{b+1}$ si $a<b$ . Si $b<a$ codificar $(a,b)$ como $2^{a+1} + 2^{b+1} + 1$ . Ahora que podemos codificar pares ordenados, podemos definir una biyección entre dos conjuntos de números naturales utilizando La función beta de Godel .

Mi pregunta es por qué algún número natural en nuestro modelo no codifica una función tal que $F$ es un segmento inicial de esta función?

Editar:

Quiero agradecer a Andrés Caicedo que haya corregido mi pregunta. Quiero definir mi biyección como él sugiere:

$F = \{(0,p)\} \cup \{(t+1,t) | t \in \aleph \} \cup \{ (s,s) | s \in X \backslash \aleph \}$

Como señala, no puedo definir $\aleph$ el conjunto de números naturales estándar, dentro del modelo. Sin embargo, puedo definir $\aleph$ en mi metateoría. Puedo llegar a una con función beta para $F$ dentro de ZFC? Si es así, ¿existe la codificación de esta función beta en mi modelo? Si no es así, existe un número natural de la forma $2^{a+1} + 2^{b+1} + 1$ que falta en el modelo donde $(a,b)$ es mi función beta. Si la codificación existe en el modelo tenemos una violación definible de la inducción. Considerando las alternativas, supongo que hay alguna razón por la que no puedo definir una función beta para $F$ en ZFC.

Answer 1

Antes de continuar, tenga en cuenta que $F$ Tal y como está escrito, lo más probable es que no sea lo que pretendías. Parece como si $F$ es una biyección entre la parte estándar $\mathbb N$ de $N^*$ y el conjunto $\mathbb N\cup\{p\}$ . Obsérvese que se trata de una biyección, y es el segmento inicial de alguna biyección entre $X$ y $Y$ (por ejemplo, la del apartado 3). Esto no es un problema. La cuestión es que el segmento inicial que codifica $F$ no es definible en el modelo, no está codificado. La cuestión es que si $G$ es una función codificada en $N^*$ con el dominio de un segmento inicial de $N^*$ entonces para cualquier segmento inicial $I$ que es definible en $N^*$ tenemos que en $N^*$ hay un código para $G\upharpoonright I$ . Pero $I$ en este caso es $\mathbb N$ y esto no es definible en $N^*$ . De hecho, los únicos segmentos iniciales definibles son los de la forma $\{y\mid y<t\}$ para algunos $t$ y $\mathbb N$ definitivamente no tiene esta forma. (Esto se demuestra por inducción: "Para cualquier segmento inicial adecuado hay un menor número que no está en él". El problema es que no hay un menor número entero no estándar: SI $K$ es infinito, también lo es $K-1$ .) El obstáculo aquí es la restricción a los segmentos iniciales definibles, pero esto es inevitable: Si $G\upharpoonright I$ está codificado en $N^*$ Ciertamente $I$ es definible en $N^*$ .

Me imagino que esto $F$ no es lo que pretendías. Más bien, probablemente querías decir algo como $F=\{(0,p)\}\cup\{(t+1,t)\mid t<p\}$ . Pero tenga en cuenta que $(p,p-1)\in F$ Así que $F$ es una biyección, y ciertamente una codificada dentro de $N^*$ pero es sólo una biyección de $Y$ a sí mismo, que de nuevo no es lo que pretendía.

O tal vez querías decir $F=\{(0,p)\}\cup\{(t+1,t)\mid t\in\mathbb N\}\cup\{(s,s)\mid s\in X\setminus\mathbb N\}$ . Esto es definitivamente una biyección entre $X$ y $Y$ pero no es definible en $N^*$ No está codificado allí. Si lo estuviera, podríamos a partir de él definir $\mathbb N$ y obtener una violación definible de la inducción.

De hecho, por mucho que lo intentemos, cualquier biyección entre $X$ y $Y$ no se puede codificar dentro del modelo. Esto se debe a que $N^*$ siendo un modelo de $\mathsf{PA}$ demuestra los hechos apropiados sobre los conjuntos finitos codificados, tales como que no hay una biyección de un conjunto finito a un superconjunto apropiado. (Esto se demuestra por inducción, por supuesto).

(Si estas explicaciones no le parecen satisfactorias, y si indica cualquier problema que pueda tener, intentaré aclarar/ampliar/añadir lo que proceda).

---

Permítame abordar su edición. La función $F$ en el párrafo 3 es definitivamente un objeto en $\mathsf{ZFC}$ . Es contable, por lo que se puede codificar como un conjunto de números. Sin embargo, no podemos codificarla dentro del modelo. Como señala Andreas Blass, cada valor $(a,F(a))$ es ciertamente codificable, pero por supuesto esto no es suficiente. Para tener una codificación de $F$ en $N^*$ por medio del enfoque de Gödel o de otro modo, necesitaríamos la definibilidad de $F$ . Como se ha explicado anteriormente, esto nos da la posibilidad de definir $\mathbb N$ dentro de $N^*$ . Pero esto es imposible. En cierto sentido, esto está relacionado con su pregunta anterior: $N^*$ sólo puede referirse (mediante códigos) a conjuntos que se presentan de forma bastante explícita, y la mayoría de los conjuntos no lo son. Aunque "desde fuera" tengamos una buena comprensión de $F$ , esto es simplemente un objeto externo a nuestro modelo $N^*$ es "invisible" para ella, y no es posible cambiar esto, porque el esquema de inducción impide la presencia de "enteros infinitos Dedekind".

Answer 2

Dirigiéndose a la versión editada de la pregunta, con la versión corregida de $F$ : La función $F$ existe en el universo ZFC, y (por lo tanto) también lo hace el correspondiente conjunto de códigos en $N^*$ de los pares ordenados en $F$ . Pero este subconjunto de $N^*$ no está codificado por ningún miembro de $N^*$ por la razón de la respuesta de Andrés Caicedo: Si fuera codificable, entonces habría una violación definible de la inducción, lo que significa que $N^*$ no es realmente un modelo de Aritmética de Peano.