Comprender los ordinales contables hasta $\epsilon_{0}$

Question

En una pregunta reciente de MO, enlace Al hablar de los fundamentos actuales de las matemáticas, el autor enlazó una conferencia en vídeo del profesor Voevodsky, que argumenta contra el principio de $\epsilon_{0}$ -inducción utilizada en la prueba de Gentzen de la consistencia de PA.

En las discusiones derivadas de la pregunta, algunas personas comentaron que imaginar una cadena descendente infinita en $\epsilon_{0}$ es una "locura".

Me gustaría entender mejor este ordinal, ya que en realidad no sé exactamente cómo representarlo en mi mente.

Tengo claro en mi mente el orden asociado a los ordinales finitos. Utilizo en mi mente una notación del tipo siguiente:

$1 = I$

$2= II$

$3= III$

$4= IIII$

$\omega = (III\dots)$

$\omega+1= (III\dots)I$

$\omega +2 = (III\dots)II$

$\omega + \omega= \omega \cdot 2= (III\dots)(III\dots)$

En general, entiendo $\alpha + \beta$ como la yuxtaposición de las dos representaciones.

$\omega\cdot 3 = (III\dots)(III\dots)(III\dots)$

$\omega\cdot \omega = \omega^{2} = \big( (III\dots)(III\dots)(III\dots)\dots\big)$

En general, entiendo $\alpha \cdot \beta$ sustituyendo cada $I$ símbolo en $\beta$ con la representación de $\alpha$ . Así que

$\omega^{3}=\omega^{2}\cdot \omega = \big( \omega^{2} \omega^{2} \omega^{2} \dots \big)$

Esto me permite visualizar todo ordinal de la forma $\omega^{n}\cdot m + k$ con $n,m,k$ naturales (es decir, ordinales finitos). Hasta ahora no tengo ninguna duda de que no hay ninguna cadena descendente infinita en los ordinales de la forma $\omega^{n}\cdot m + k$ .

Sin embargo, empiezo a tener problemas con el ordinal $\omega^{\omega}= \bigsqcup_{n<\omega}\omega^{n}$ . ¿Tiene alguna idea de cómo visualizar $\omega^{\omega}$ es una forma coherente con la representación utilizada anteriormente (que en realidad encontré aquí ) ?

De todos modos, mirando wikipedia Todavía me las arreglo para visualizar $\omega^{\omega}$ como el conjunto de cadenas infinitas de números naturales, que sólo tienen un número finito de dígitos diferentes de $0$ .

Aún así, no tengo ninguna duda de que no hay una cadena descendente infinita en $\omega^{\omega}$ .

Tal vez pueda entender $\omega^{\omega^{\omega}}$ , es decir, el conjunto de cadenas infinitas etiquetadas con elementos de $\omega^{\omega}$ que sólo tiene un número finito de elementos diferentes de $0$ . O (supongo) de forma equivalente un $\omega\times\omega$ cuadrado etiquetado con naturales, donde sólo finitamente muchas columnas son diferentes de $0^{\omega}$ y todos estos no constantes $0$ columnas, sólo contiene un número finito de dígitos diferentes de $0$ .

Sin embargo, no sé cómo visualizar $\epsilon_{0}$ . Quiero decir que sé que los elementos de $\epsilon_{0}$ puede ser representado por árboles finitos de ramas finitas etiquetados con números naturales, pero eso no me da una fuerte intuición sobre el hecho de que no existe ninguna cadena infinita, así que supongo que no es una gran imagen (o al menos no lo entiendo correctamente, todavía).

Preguntas

A) ¿Podría sugerir una forma de visualizar $\omega^{\omega^{\omega}}$ ? Debe ser de tal manera que me convenza sobre el hecho de que no hay una cadena descendente infinita.

B) ¿Podría sugerir una forma de visualizar $\epsilon_{0}$ , argumentando de nuevo que debe quedar muy claro que no hay infinitas cadenas descendentes.

C) ¿Podría exponer su opinión sobre el profesor Voevodsky, que argumenta contra el principio de $\epsilon_{0}$ -inducción utilizada en Gentzen's? Esto no debería ser un duplicado del hilo anterior, más amplio enlace Sólo me interesa esta pequeña parte de la charla de Voevodsky.

Gracias de antemano,

bye

matteo

Answer 1

La forma estándar de visualizar $\epsilon_0$ es por el Juego de la Hidra . Aquí los elementos de $\epsilon_0$ se visualizan como clases de isomorfismo de árboles finitos enraizados. La desigualdad puede describirse mediante la regla de "cortar cabezas": El árbol $T_1$ es mayor que $T_2$ es que hay una serie de cortes de cabeza que reduce $T_1$ a $T_2$ . Escribir la relación de desigualdad entre los árboles directamente es un dolor, ver mi blogpost . Si conviertes esos conjuntos anidados en árboles de la manera obvia, obtienes el juego de la Hidra.

Me han dicho que a la mayoría de la gente no le parece intuitivo que el juego de Hydra termine. A mí me parece que, una vez que he jugado unas cuantas rondas (prueba esta applet ) Me parece "obvio", aunque escribir una prueba real sigue siendo doloroso.

En cuanto a una prueba real, debería mostrar directamente lo siguiente: Dejemos que $X$ sea un conjunto totalmente ordenado. Sea $\omega^X$ sea el conjunto de funciones $X \to \omega$ que son $0$ para casi todos los $x \in X$ ordenados de la siguiente manera: Sea $f$ y $g$ sean elementos distintos de $\omega^X$ y que $x$ sea el mayor elemento de $x$ para lo cual $f(x)\neq g(x)$ . Entonces $f<g$ si y sólo si $f(x) < g(x)$ . Entonces $\omega^X$ está bien ordenado. Así que cada torre de $\omega$ 's está bien ordenado y, $\epsilon_0$ siendo la unión de todas esas torres, también está bien ordenada.

---

Por cierto, no se pregunta esto, pero podría ser curioso lo que sucede cuando se trata de escribir esta prueba dentro de PA. Recuerda que PA no puede hablar directamente de subconjuntos de $\omega$ . La afirmación de que $\omega$ está bien ordenado se codifica como un esquema de axiomas. Sea $\phi(x, y_1, y_2, \ldots, y_N)$ sea cualquier declaración con variables $x$ y $y_i$ que se ejecuta a través de $\omega$ . Entonces PA tiene el siguiente axioma: $$\forall y_1, y_2, \ldots, y_n \in \omega: \left( \exists x \in \omega : \phi(x, y_{\bullet}) \implies \exists x' \in \omega : \left( \phi(x', y_{\bullet}) \wedge \forall x \in \omega \left( \phi(x, y_{\bullet}) \implies x \geq x' \right) \right) \right).$$ Por favor, lea este axioma hasta que entienda que, en inglés, dice "For all $y$ 's, si hay algún $x$ obedeciendo a $\phi$ entonces hay un mínimo de $x$ obedeciendo a $\phi$ ."

Llamemos a este axioma $W(\phi, \omega)$ . Utilizaremos una notación similar con $\omega$ sustituido por otros conjuntos. Este es un ejercicio desafiante e importante: Dejemos que $X$ sea un conjunto ordenado. Sea $\phi$ ser una declaración sobre $\omega^X$ que puede tener otras variables $y_i$ en ella. Construir una declaración específica $\sigma(\phi)$ sobre $X$ con otras variables $z_i$ que se ejecuta a través de $X$ , de tal manera que $$ W(\sigma(\phi), X) \implies W(\phi, \omega^X) \quad (*).$$

Para cada $\phi$ La declaración $(*)$ se puede demostrar en PA. Dado que $W(\psi, \omega)$ es un axioma de PA para cada $\psi$ podemos demostrar $W(\phi, \omega^{\omega^{\ldots^{\omega}}})$ en PA para cualquier $\phi$ y cualquier altura específica de la torre.

Pero, para demostrar que $\epsilon_0$ está bien ordenado, tenemos que demostrar que $W(\phi, \omega^{\omega^{\ldots^{\omega}}})$ simultáneamente para cada altura de la torre. Siguiendo los argumentos aquí expuestos, habría que saber $W(\phi, \omega)$ , $W(\sigma(\phi), \omega)$ , $W(\sigma(\sigma(\phi)), \omega)$ , $W(\sigma^3(\phi), \omega)$ y así sucesivamente. Como matemático humano, eso probablemente no le moleste en absoluto. Pero, en el sistema formal PA, cualquier prueba sólo puede utilizar un número finito de axiomas. Así que no hay manera de escribir una prueba que utiliza todos los axiomas $W(\sigma^k(\phi), X)$ para todos $k$ .

Por supuesto, esto no demuestra que algún argumento más inteligente no pueda demostrar que $\epsilon_0$ está bien ordenado mientras se trabaja con PA; para ello se necesita el teorema de Kirby-Paris. (Más precisamente Kirby-Paris más Godel muestra que, si PA demuestra $\epsilon_0$ está bien ordenado, entonces PA es inconsistente). Pero encuentro que ver este obstáculo, la necesidad de usar infinitas versiones del axioma de buen orden, aclara mi comprensión de lo que está pasando.

Answer 2

En el transcurso de la redacción de un artículo expositivo sobre la consistencia de la aritmética, me llevó a tratar de explicar $\epsilon_0$ de la manera más fina posible. Esto es lo que se me ocurrió, inspirado en gran medida por el relato del libro de Torkel Franzen Inagotabilidad: Un relato no exhaustivo así como el lenguaje de programación LISP.

Definir un lista sea una secuencia vacía -denotada por ( ) y referida como la lista vacía-o, recursivamente, una secuencia finita no vacía de listas. Si escribimos una lista separando los elementos constitutivos por comas y encerrando la secuencia completa con paréntesis, entonces, por ejemplo, (( ), ( ), ( )) y (( ), ( )), (( ), (( ), ( ))), ( ))) son listas. El número de listas constituyentes se llama longitud (es cero para la lista vacía). Si $a$ es una lista no vacía, entonces escribimos $a[i]$ para el $i$ La lista de constituyentes de $a$ , donde $i$ rangos desde 1 hasta la longitud de $a$ .

A continuación, defina recursivamente una ordenación total $\le$ en las listas como siguiente (es esencialmente una ordenación lexicográfica). Sea $a$ y $b$ sean listas, con longitudes $m$ y $n$ respectivamente. Si $m\le n$ y $a[i] = b[i]$ para todos $1\le i \le m$ (esta condición se satisface vacuamente se satisface si $m=0$ ), entonces $a\le b$ . En caso contrario, existe algún $i$ tal que $a[i] \ne b[i]$ ; deja que $i_0$ sea el menor de dichos números, y declarar $a< b$ si $a[i_0] < b[i_0]$ .

Por último, defina recursivamente una lista $a$ para ser un ordinal (o más exactamente, un ordinal inferior $\epsilon_0$ pero me limitaré a decir ordinal para abreviar) si todas sus listas constitutivas son ordinales y $a[i] \ge a[j]$ siempre que $i<j$ . (En particular, la lista vacía es un ordinal, ya que la condición se satisface vacuamente).

Como ejercicio, puedes comprobar que los ordinales ((( ))) y ((( ), ( ))) y ((( )), (( ))) son, en notación estándar, lo mismo que $\omega$ , $\omega^2$ y $\omega \cdot 2$ respectivamente.

Mi opinión personal es que las formas habituales de definir $\epsilon_0$ lo hacen parecer alucinantemente infinito, pero la definición anterior deja claro que cualquier ordinal particular es sólo un tipo especial de lista finita de listas finitas de listas finitas de de listas finitas. No es muy infinito en absoluto.

La prueba de que no existe una secuencia descendente infinita tampoco es especialmente alucinante, en este lenguaje. En lugar de escribirla aquí, te remito a la prueba del Teorema 1 en mi artículo expositivo.

Me parece que después de entender esta prueba, lo difícil de entender es cómo puede ser verdad que la AP hace no demostrar que no existe una secuencia descendente infinita. Mi intuición actual es que PA parece extrañamente débil, porque ni siquiera puede formalizar una prueba tan simple como ésta.

Answer 3

David Speyer entrada del blog inspirado en la pregunta del modus operandi a la que hace referencia François Dorais en los comentarios, contiene una respuesta detallada a esta cuestión.

Answer 4

Se trata de una respuesta sencilla, pero quizá un poco alternativa. Defina dos funciones $V_1:\epsilon_0 \rightarrow \epsilon_0$ y $V_2:\epsilon_0 \rightarrow \epsilon_0$ .

Para cualquier $x$ , defina $\gamma$ como el ordinal más pequeño tal que $\gamma \cdot \omega > x$ . Y ahora define:

$V_1(x)=0 \qquad \qquad \qquad \qquad \qquad when\; x<\omega$

$V_1(x)=\alpha \;such\; that\; \omega^\alpha=\gamma \qquad \quad when\; x \geq\omega$

$V_2(x)=Pre(x) \qquad \qquad \quad when\; x<\omega$

$V_2(x)=Lsub(\gamma,x) \qquad \qquad when \; x \geq\omega $

Aquí $Pre$ representa la función predecesora habitual (con salida $0$ en $0$ ). Y $Lsub:\epsilon_0 \times \epsilon_0 \rightarrow \epsilon_0$ se define como: $$Lsub(\alpha,\beta)=0 \qquad if \, \alpha > \beta$$ $$Lsub(\alpha,\beta)=\{\,y\in \epsilon_0\,|\,\alpha+y=\beta\,\} \qquad if \, \alpha \le \beta$$

Obsérvese que para todos los valores del dominio (excepto $x=0$ ), tenemos $V_1(x)<x$ y $V_2(x)<x$ . Además, podemos observar que para cualquier ordinal no nulo $\alpha_1,\alpha_2<\epsilon_0$ (donde $\alpha_1 \neq \alpha_2$ ) no es el caso que $V_1(\alpha_1)=V_1(\alpha_2)$ y $V_2(\alpha_1)=V_2(\alpha_2)$ .

Y con esto podemos asociar a todo ordinal menor que $\epsilon_0$ un árbol finito "único". Cada nodo tendrá "dos" o "ningún" nodos hijos. Además, cada nodo está completamente desmarcado (sin número/etiqueta, etc., asociados a él).

Por ejemplo, para cualquier $\alpha<\epsilon_0$ podemos definir el subárbol izquierdo como el árbol de $V_1(\alpha)$ y el subárbol derecho como el árbol de $V_2(\alpha)$ . Además, el árbol de $0$ puede definirse como un único nodo (no marcado). Creo que se puede utilizar la inducción (transfinita) para demostrar que para cualquier ordinal no nulo $\alpha_1,\alpha_2<\epsilon_0$ (donde $\alpha_1 \neq \alpha_2$ ), sus representaciones como árboles serán diferentes.

Tal vez para alguien que es "muy escéptico" que $\epsilon_0$ pueden estar bien ordenados en absoluto (en términos de objetos finitos) se podría intentar convencerles de que las funciones $V_1$ y $V_2$ son lo suficientemente simples como para que la aplicación de cualquier combinación posible de ellos (como composición) en un $\alpha<\epsilon_0$ volvería a $0$ en intentos finitos.

Para sólo aplicar $V_1$ es muy fácil de ver. Por ejemplo, $V_1(\omega^{\omega^\omega})=\omega^\omega$ , $V_1(\omega^\omega)=\omega$ , $V_1(\omega)=1$ , $V_1(1)=0$ . Del mismo modo, $V_1(\omega^{\omega^2})=\omega^2$ . Así que me parece que la aplicación $V_1$ puede pensarse que simplemente "se come" las torres (y un número finito de torres se comerá con un número finito de intentos).

Pero la situación parece más compleja para una combinación y convencer a alguien "muy escéptico" podría requerir una explicación más intuitiva/visible que cualquier combinación (de $V_1$ y $V_2$ aplicado como composición) también volvería siempre a $0$ en intentos finitos.

---

Pero parece que una buena manera de ver si no hay una cadena descendente infinita es escribir un juego complejo en el que la persona que reclama la cadena debe proporcionar un nuevo número (natural) en cada etapa. Y eventualmente mostrar que no importa qué números se proporcionen, el juego tiene que terminar.

Editar: Me he dado cuenta del razonamiento erróneo en mi anterior post. Lo he eliminado.

P.D. Me he dado cuenta de que esta pregunta está en la lista de "Relacionadas". Espero que esté bien que se haga un bump de una pregunta antigua (especialmente si tiene una respuesta aceptada) para un tipo de respuesta ligeramente diferente.

Answer 5

La ausencia de una secuencia descendente infinita se debe a que todo ordinal está bien ordenado; tal cosa debe y no puede contener simultáneamente un elemento mínimo.