Autor Tema: Comentarios a "Ordinales menores que \(\epsilon_0\)"

0 Usuarios y 1 Visitante están viendo este tema.

02 Mayo, 2023, 11:44 pm
Respuesta #10

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Iba a empezar a exponer los argumentos de Gentzen y Takeuti sobre la buena ordenación de \( \epsilon_0 \), pero me he entreteniendo añadiendo en la respuesta #5 algunos ejemplos y resultados sobre aritmética ordinal que iba a necesitar.

No estoy muy contento con mi respuesta #5, porque creo que tiene demasiada información demasiado condensada. Sería necesario analizar mucho más despacio la aritmética ordinal, pero me parece que, en lugar de tratar de anticiparme a ciegas a todas las dudas, ejemplos y aclaraciones que podrían hacer falta, será más práctico que cualquiera que se atasque me pregunte por lo que necesite.

07 Mayo, 2023, 04:32 pm
Respuesta #11

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 982
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos.

Perdón por no contestar antes, pero desde el miércoles estuve muy liado y, aunque a ratos e ido leyendo el post, quería esperarme a tener todo leído y tiempo para responder bien.

Las dudas anteriores todo aclarado aunque en esto creo que no me expliqué bien:

Y, por cierto, al menos para valores grandes (y en Maple, que es donde estoy programando las cosas), mi ordenador tarda menos tiempo en calcular el conjunto \( R_n \) necesario (y, a partir de este, calcular los ordinales y comprobar el orden) que haciéndolo todo directamente tal y como has mostrado en tus programas. La diferencia para \( n=5000 \) es de un par de segundos y me parece muy curioso la verdad ???

Bueno, mis programas van calculando ordinales cuando lo necesitan, pero nada te impide usarlos calculando todo al principio. Sólo tienes que poner calcula(5000) y te calculará \( R_{5000} \), y a partir de ahí ya no necesitará calcular nada mientras no te pases de ese rango. Acabo de probar y el tiempo que tarda mi ordenador en calcular (e imprimir) los ordinales menores que 5000 es de 0.84 segundos. En cambio, con el último módulo que he adjuntado tarda 1.33 segundos, pero sabe trabajar fácilmente con ordinales mucho más grandes, representados por números astronómicos.

Quería decir que, mientras he ido leyendo el hilo siempre me he ido haciendo mis propios programas y después he comparado con los tuyos y, en la parte de la construcción recursiva de los ordinales, yo cree tres programas distintos. Uno que imita el paso recursivo en la construcción de los \( R_n \), uno que repite esta recursión partiendo de \( R_0=\{0\} \) y con el que calcula todos los elementos de \( R_n \) hasta cierto natural \( n \) y, a partir de este, otro que te calcula todos los ordinales hasta \( n \) simplemente comprobando si \( \langle x,x \rangle_2 \in R_x \) para cada \( x \leq n \).

Después, al ver tus programas también los adapte a Maple y, lo que me parecía curioso es que, aunque tu programa "calcula de golpe" tanto el conjunto \( R_n \) (al que llamas pares), como el conjunto \( E \) (al que llamas ordinales), resulta que es un poco más lento que mis programas que hacen las cosas "por pasos". Tal vez haya hecho algo mal al traducir tu programa y por eso resulte ser algo más lento, pero me parecía curioso que fuera así.

Como sea, tampoco era algo realmente importante ::)

Ahora sí, voy con las cosas nuevas y, como la última vez, pongo primero las errorcillos que he encontrado y después ya las dudas y comentarios.

ERRATAS

Toda la construcción del mensaje precedente sólo tiene dos finalidades:

1) Justificar que esta definición no es circular y
2) Poner en evidencia que los ordinales no son "unas cosas raras que a saber si existen", sino que son simplemente números naturales, de modo que un ordenador siempre puede decidir si un número natural es o no un ordinal y si un ordinal es o no menor que otro.

Supongo que aquí, donde ponía "recursiva" querías decir "circular", ¿no?

Por ejemplo, si queremos comparar los ordinales

\( \alpha =\omega^{\omega^{\color{blue}4}\cdot 3}\cdot 5+
\omega^{\omega^3 \color{black} \cdot 5+\omega^2\cdot 7+\omega+3}\cdot 7+
\omega^{\omega+2}+\omega^5\cdot 8+\omega\cdot 3+10 \)

\( \beta =\omega^{\omega^{\color{blue}4}\cdot 3}\cdot 5+
\omega^{\omega^3\cdot 5+\omega^2+\omega\cdot 8+9}\cdot 3+
\omega^{\omega+2}+\omega^5\cdot 8+\omega\cdot 3+10 \)

Aquí supongo que querías poner algo del estilo de lo que he puesto en azul (antes ponía un \( 3 \)), porque si no, las expresiones dadas no son ordinales.

Relación con los ordinales de la teoría de conjuntos
En ZF se pueden definir los ordinales de una forma muy distinta a como los hemos definido aquí (y, de hecho, obtenemos muchos más ordinales que los que nosotros hemos definido). Con la construcción conjuntista, cada ordinal es el conjunto de todos los ordinales menores que él. Por ejemplo:

\( 0 = \emptyset, \quad 1 = \{0\}, \quad 2 = \{0, 1\},\quad \ldots, \omega = \{0, 1, 2, \ldots\},\quad \omega+1 = \{0, 1, 2, \ldots, \omega\},\quad \ldots \)

También se define de forma natural una suma, un producto y una exponenciación de ordinales, que nosotros introduciremos en el mensaje siguiente. Cantor demostró que todo ordinal \( \alpha\neq 0 \) se expresa de forma única en lo que ahora se llama forma normal de Cantor:

\( \alpha = \omega^{\beta_1}\cdot k_1+\cdots + \omega^{\beta_n}\cdot k_n \),   \( \alpha\geq \beta_1\geq \cdots \geq \beta_n,\qquad   k_1, \ldots, k_n < \omega. \)

El ordinal \( \epsilon_0 \) se define como el supremo de los ordinales:

\( \omega< \omega^\omega <\omega^{\omega^\omega}<\omega^{\omega^{\omega^\omega}}<\cdots <\epsilon_0 \)

y es el menor ordinal con la propiedad de que \( \omega^{\epsilon_0}= \color{blue} \epsilon_0 \) (los números con esta propiedad se llaman numeros \( \epsilon \)). Esto hace que su forma normal de Cantor sea simplemente \( \epsilon_0 = \omega^{\epsilon_0} \). Sin embargo, los números \( \alpha<\epsilon_0 \) tienen todos forma normal con \( \alpha>\beta_1>\cdots >\beta_n \), por lo que, a través de su forma normal de Cantor, cada ordinal menor que \( \epsilon_0 \) está determinado por una sucesión decreciente de ordinales menores.

Esto hace que si en ZF construimos el conjunto \( E \) de los números naturales a los que hemos llamado "ordinales", la aplicación \( E\longrightarrow \epsilon_0 \) que a cada ordinal de los nuestros le hace corresponder el ordinal usual con la misma forma normal es biyectiva y conserva el orden, por lo que los ordinales que hemos construido forman un conjunto ordenado isomorfo a \( \epsilon_0 \).

En el mensaje siguiente definiremos la suma y el producto de ordinales (menores que \( \epsilon_0 \)) de modo que este isomorfismo de conjuntos ordenados conserve también la suma y el producto.
[cerrar]

Erratilla con el ordinal \( \epsilon_0 \).

  • Para todo ordinal \( \alpha \) existe un \( n\prec \omega \) tal que \( \alpha\prec \omega^{(n)} \). En otras palabras, la sucesión \( \{\omega^{(n)}\}_{n=0}^\infty \) no está acotada.

Vamos a probarlo por inducción sobre \( \alpha \) (por la inducción usual en los números naturales, es decir, vamos a ver que si todos los números naturales \( \beta<\alpha \) que son ordinales cumplen la afirmación, lo mismo le sucede a \( \alpha \)).

Si \( \alpha = 0 \) es trivial. Pongamos que \( \alpha = (\beta_1, \ldots, \beta_n) \), y hemos visto al final de la respuesta #2 que \( \beta_1<\alpha \) (en el orden de los números naturales), luego por hipótesis de inducción existe un \( n \) tal que \( \beta_1\prec \omega^{(n)} \), y entonces

\( \alpha = \omega^{\beta_1}+\cdots + \omega^{\beta_n}\prec \omega^{\omega^{(n)}}=\omega^{(n+1)} \).

Erratillas con un paréntesis y una letra. También, es en la respuesta #2 donde se ve que si \( x=\langle x_1, \cdots, x_n \rangle_\infty \) entonces \( x_i <x \) para cada \( i \).

  • Si \( \lambda \) es el supremo de una sucesión creciente
    \( \delta_0\prec \delta_1\prec \delta_2\prec \cdots \prec \lambda \)
    de ordinales accesibles, entonces \( \lambda \) también es accesible.

Esto es trivial: si una sucesión decreciente empieza en un \( \color{red}\alpha_0 \color{black}\prec \lambda \), por definición de supremo existirá un \( n \) tal que \( \alpha_0\prec \delta_n \), luego en realidad sería

\( \delta_n\succ \alpha_0\succ \alpha_1\succ \alpha_2\succ \cdots \),

lo cual contradiría la accesibilidad de \( \delta_n \).

Pequeña errata marcada en rojo.

Para empezar, podemos razonar que, del mismo modo que hemos pasado de la accesibilidad de \( \omega^\omega \) a la de \( \omega^{\omega^2} \) a base de multiplicar por \( \omega \) (sumando 1 al exponente) y tomar supremos, exactamente el mismo argumento nos permite pasar de la accesibilidad de  \( \omega^{\omega^2} \) a la de  \( \omega^{\omega^2+\omega^2}= \omega^{\omega^2 \color{blue} \cdot 2} \), y no es necesario que repitamos todo el proceso de nuevo, y el mismo bloque de razonamientos nos permite ir probando la accesibilidad de

\( \omega^{\omega^2}\prec \omega^{\omega^2\cdot 2}\prec \omega^{\omega^2\cdot 3}\prec \omega^{\omega^2\cdot 4}\prec \cdots \prec \omega^{\omega^2\cdot \omega} = \omega^{\omega^3} \).

En lo marcado en azul, el "\( 2 \)" no aparecía en el exponente.

DUDAS

Dedicaré el mensaje siguiente a empezar a exponer los argumentos en favor de la buena ordenación de \( \epsilon_0 \) (de los ordinales que hemos definido aquí), pero antes merece la pena observar nuestro problema desde un ángulo distinto:

¿Es válida la inducción hasta \( \epsilon_0 \)?, es decir, si, bajo la hipótesis de que todos los ordinales \( \beta\prec \alpha \) cumplen una propiedad \( P(\beta) \), demostramos \( P(\alpha) \), ¿podemos asegurar que todos los ordinales cumplen dicha propiedad?

Esto es equivalente a la no existencia de sucesiones decrecientes de ordinales. Consideremos, concretamente, la propiedad

\( P(\alpha)\equiv \alpha  \) no es el ordinal asociado a la prueba de una contradicción en AP.

Gentzen demostró que si un ordinal no cumple \( P(\alpha) \), es decir, si se trata del ordinal asociado a una prueba de una contradicción en AP, entonces existe otro ordinal \( \beta\prec \alpha \) que tampoco cumple \( P(\beta) \) (hay una prueba de una contradicción con ordinal menor). Dicho al revés: si todos los ordinales \( \beta\prec \alpha \) cumplen \( P(\beta) \), podemos asegurar \( P(\alpha) \).

Si es válido el principio de inducción que acabo de enunciar, de aquí se puede deducir que todos los ordinales cumplen \( P(\alpha) \), es decir, que ninguno está asociado a la prueba de una contradicción en AP, luego no existe tal prueba (toda prueba tiene un ordinal asociado) y AP es consistente.

Aquí no veo del todo claro. Entiendo que el argumento que das prueba que si la inducción hasta \( \epsilon_0 \) es válida, entonces AP es consistente. Ahora, si entendí bien lo que expones en mensajes anteriores, lo que Gentzen probó es que si AP no es consistente, entonces existe una sucesión decreciente de ordinales. Por tanto, me da la impresión de que tenemos implicaciones que van en sentido contrario. Quiero decir, tenemos las implicaciones:

AP no es consistente \( \longrightarrow{} \) Existe una sucesión decreciente de ordinales
La inducción hasta \( \epsilon_0 \) es válida \( \longrightarrow{} \) AP es consistente

Pero, para probar la equivalencia

La inducción hasta \( \epsilon_0 \) es válida \( \longleftrightarrow{} \) No existe una sucesión decreciente de ordinales

parece que necesitaríamos

AP no es consistente \( \color{red} \longleftrightarrow{} \) Existe una sucesión decreciente de ordinales
La inducción hasta \( \epsilon_0 \) es válida \( \color{red} \longleftrightarrow{} \) AP es consistente

¿Qué estoy entendiendo mal?

La ventaja de este enfoque es que este principio de inducción puede formalizarse en AP. Todas las definiciones que hemos dado en este hilo son puramente aritméticas y son formalizables en AP. Igual que podemos definir aritméticamente la propiedad "n es un número primo", también podemos definir \( n\in E \), y del mismo modo que podemos definir "m divide a n", podemos definir \( \alpha\prec \beta \). Por lo tanto, para cada propiedad expresable aritméticamente \( \phi(x) \), podemos formular este principio de inducción:

\( \phi-\text{IND}(\epsilon_0)\equiv \forall \alpha\in E\ \forall \beta((\beta\prec \alpha\land \phi(\beta))\rightarrow \phi(\alpha))\rightarrow \forall \alpha\in E\,\phi(\alpha). \)

Aquí mi duda se debe a que, como sabes, me quedé justamente al principio del capítulo 5 de tu libro de lógica donde supongo que se explica todo esto en detalle, pero aún así la comento por si podrías darme un esbozo preliminar de las ideas involucradas.

Básicamente, mi dudas es sobre como se pueden definir (formalmente) conjuntos obtenidos de manera recursiva, como es el caso de \( E \), en AP. Es decir, como se puede formalizar la fórmula \( n \in E \).

COMENTARIOS

No recuerdo quién fue el matemático mordaz que señaló que Gentzen había demostrado la consistencia de la inducción hasta \( \omega \) suponiendo la inducción hasta \( \epsilon_0 \).

Justamente leí hace muy poco esta misma cita, pero no recuerdo donde la leí y no he podido encontrar de que matemático se trata.

Lo dejo aquí de momento. La cuestión sobre la que el lector debería meditar es si lo dicho le convence de que no hay sucesiones decrecientes de ordinales, o si no, o si, en caso de que esto no le parezca concluyente, se le ocurre un razonamiento alternativo que lo sea.

A mi me ha convencido en el sentido siguiente:

Si tu me das cualquier ordinal \( \alpha \) (de los definidos en el post claro), tengo hecho un pequeño programa que calcula el menor natural \( n \) para el cual se cumple \( \alpha \prec \omega^{(n)} \). Una vez tienes esto con dicho \( n \) ya fijo, se puede seguir el argumento que se da en la Respuesta #8 que, aunque implique usar un "y así sucesivamente" unas pocas veces, creo que está claro que cada afirmación que se hace es perfectamente válida. Así pruebas que \( w^(n) \) es accesible y con ello lo era el \( \alpha \) de partida.

Ahora bien, si es cierto que dejaría mucho mejor sabor de boca algún argumento como los utilizados para probar las afirmaciones en azul de dicha respuesta. Pero, como he dicho, Gentzen me convence (al menos a la espera de algo mejor) :aplauso:

Por último, respecto a la parte computacional, me ha parecido muy compacto y bien hecho el módulo que has hecho para tratar los ordinales  :aplauso:

Yo he programado algo parecido, pero muchísimo menos elegante y muchísimo más engorroso (aunque da los mismos resultados  ::))

Lo que hice es básicamente lo mismo que has hecho en tu módulo, pero en lugar de utilizar sucesiones de la cadena vacía [], he tratado con expresiones en "forma normal". Es decir, de forma teórica definiría recurrentemente, partiendo de los naturales, los conjuntos de "sucesiones finitas de naturales", "sucesiones finitas de sucesiones finitas de naturales", etc. Después utilizaría la "forma normal" para expresar de forma compacta cualquier elemento de estos conjuntos (identificando \( \omega=[1] \)) y, una vez hecho esto, el orden, decidir que elementos son ordinales y las operaciones aritméticas ya son exactamente iguales a lo visto en tus mensajes. La única dificultad ha sido hacer un programa que, dada una cadena de texto, te diga si es una "forma normal" y la exprese en una forma cómoda para trabajar con ella. Después es todo "coser y cantar".

Dejo aquí el archivo de Maple por si a alguien le apetece echarle un vistazo (aunque no incluye ninguna novedad a lo hecho por Carlos), pero aviso que los programa que permiten tratar con las cadenas de texto en "forma normal" son horrorosos :P

Un saludo.

AÑADIDO: Acabo de ver que que has publicado un nuevo mensaje, pero aún no he podido leerlo, por si algo de lo que he dicho aquí queda obsoleto

07 Mayo, 2023, 05:55 pm
Respuesta #12

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hola Carlos.

Perdón por no contestar antes, pero desde el miércoles estuve muy liado y, aunque a ratos e ido leyendo el post, quería esperarme a tener todo leído y tiempo para responder bien.

No, si yo también estoy muy atareado estos días. No obstante, he tenido ratillos para ir modificando el mensaje sobre aritmética ordinal, añadiendo algunos resultados que faltaban y otros que me han hecho falta para el mensaje que he publicado hoy.

Quería decir que, mientras he ido leyendo el hilo siempre me he ido haciendo mis propios programas y después he comparado con los tuyos y, en la parte de la construcción recursiva de los ordinales, yo cree tres programas distintos. Uno que imita el paso recursivo en la construcción de los \( R_n \), uno que repite esta recursión partiendo de \( R_0=\{0\} \) y con el que calcula todos los elementos de \( R_n \) hasta cierto natural \( n \) y, a partir de este, otro que te calcula todos los ordinales hasta \( n \) simplemente comprobando si \( \langle x,x \rangle_2 \in R_x \) para cada \( x \leq n \).

Después, al ver tus programas también los adapte a Maple y, lo que me parecía curioso es que, aunque tu programa "calcula de golpe" tanto el conjunto \( R_n \) (al que llamas pares), como el conjunto \( E \) (al que llamas ordinales), resulta que es un poco más lento que mis programas que hacen las cosas "por pasos". Tal vez haya hecho algo mal al traducir tu programa y por eso resulte ser algo más lento, pero me parecía curioso que fuera así.

Como sea, tampoco era algo realmente importante ::)

Ya veo. Pues no sé. Aprendí algo de Python aprovechando el confinamiento por la covid, pero sé lo justito, y desde luego, no tengo ninguna práctica buscando la forma más eficiente de calcular algo.

Ahora sí, voy con las cosas nuevas y, como la última vez, pongo primero las errorcillos que he encontrado y después ya las dudas y comentarios.

Ya he corregido todas las erratas que señalas. No se te pasa ni una (espero).  :aplauso:

Dedicaré el mensaje siguiente a empezar a exponer los argumentos en favor de la buena ordenación de \( \epsilon_0 \) (de los ordinales que hemos definido aquí), pero antes merece la pena observar nuestro problema desde un ángulo distinto:

¿Es válida la inducción hasta \( \epsilon_0 \)?, es decir, si, bajo la hipótesis de que todos los ordinales \( \beta\prec \alpha \) cumplen una propiedad \( P(\beta) \), demostramos \( P(\alpha) \), ¿podemos asegurar que todos los ordinales cumplen dicha propiedad?

Esto es equivalente a la no existencia de sucesiones decrecientes de ordinales. Consideremos, concretamente, la propiedad

\( P(\alpha)\equiv \alpha  \) no es el ordinal asociado a la prueba de una contradicción en AP.

Gentzen demostró que si un ordinal no cumple \( P(\alpha) \), es decir, si se trata del ordinal asociado a una prueba de una contradicción en AP, entonces existe otro ordinal \( \beta\prec \alpha \) que tampoco cumple \( P(\beta) \) (hay una prueba de una contradicción con ordinal menor). Dicho al revés: si todos los ordinales \( \beta\prec \alpha \) cumplen \( P(\beta) \), podemos asegurar \( P(\alpha) \).

Si es válido el principio de inducción que acabo de enunciar, de aquí se puede deducir que todos los ordinales cumplen \( P(\alpha) \), es decir, que ninguno está asociado a la prueba de una contradicción en AP, luego no existe tal prueba (toda prueba tiene un ordinal asociado) y AP es consistente.

Aquí no veo del todo claro.

Es que dices que he dicho que la inducción hasta \( \epsilon_0 \) es equivalente a la consistencia de AP, cuando sólo he afirmado que si la inducción hasta \( \epsilon_0 \) es válida entonces AP es consistente. (Supongo que la implicación contraria también será cierta, pero tendría que pensarlo.) Pero no veo en el texto que citas qué te ha hecho pensar que afirmaba también la implicación contraria.

Lo que digo es que la validez de la inducción hasta \( \epsilon_0 \) equivale a la no existencia de sucesiones decrecientes de ordinales. Eso sí que es una equivalencia:

Si tienes una sucesión decreciente de ordinales, no se cumple la inducción respecto de la propiedad \( P(\alpha)\equiv  \) \( \alpha \) no aparece en la sucesión, pues si todos los ordinales menores que \( \alpha \) no aparecen en la sucesión, seguro que \( \alpha \) tampoco aparece, y no por ello podemos concluir que ningún ordinal aparece en la sucesión.

Recíprocamente, si no hay sucesiones decrecientes de ordinales, se cumple el principio de inducción, pues si supones que si todo ordinal menor que \( \alpha \) cumple \( P \), también \( \alpha \) cumple \( P \), es necesario que todos los ordinales cumplan \( P \), ya que si hubiera un \( \alpha_0 \) que no cumpliera \( P \), por la hipótesis tendría que haber otro \( \alpha_1\prec \alpha_0 \) que tampoco cumpliera \( P \), y así podríamos continuar construyendo una sucesión de ordinales que no cumplen \( P \).

Luego explico cómo se puede reformular el argumento de Gentzen para usar como hipótesis la inducción hasta \( \epsilon_0 \) en lugar de la no existencia de sucesiones decrecientes de ordinales.

Cuando tenga un rato retocaré el texto para aclarar este punto.

La ventaja de este enfoque es que este principio de inducción puede formalizarse en AP. Todas las definiciones que hemos dado en este hilo son puramente aritméticas y son formalizables en AP. Igual que podemos definir aritméticamente la propiedad "n es un número primo", también podemos definir \( n\in E \), y del mismo modo que podemos definir "m divide a n", podemos definir \( \alpha\prec \beta \). Por lo tanto, para cada propiedad expresable aritméticamente \( \phi(x) \), podemos formular este principio de inducción:

\( \phi-\text{IND}(\epsilon_0)\equiv \forall \alpha\in E\ \forall \beta((\beta\prec \alpha\land \phi(\beta))\rightarrow \phi(\alpha))\rightarrow \forall \alpha\in E\,\phi(\alpha). \)

Aquí mi duda se debe a que, como sabes, me quedé justamente al principio del capítulo 5 de tu libro de lógica donde supongo que se explica todo esto en detalle, pero aún así la comento por si podrías darme un esbozo preliminar de las ideas involucradas.

Básicamente, mi dudas es sobre como se pueden definir (formalmente) conjuntos obtenidos de manera recursiva, como es el caso de \( E \), en AP. Es decir, como se puede formalizar la fórmula \( n \in E \).

Como norma general (para hacerte una idea de qué se puede probar en AP y qué no), conviene que tengas en cuenta que en AP se puede definir y demostrar exactamente lo mismo que en ZFC sin el axioma de infinitud más el axioma que afirma que todo conjunto es finito. Eso te permite hablar también de conjuntos infinitos (definibles explícitamente por fórmulas) en el mismo sentido en que en ZFC se habla de clases propias, es decir, que en AP "conjuntos" como \( E \) son clases propias.

Hay varias formas de hacer estas cosas en AP, unas más elegantes y largas, y otras más directas. La idea de fondo es usar de un modo u otro lo que se conoce como función \( \beta \) de Gödel, que permite codificar de forma un tanto rudimentaria cualquier sucesión finita de números naturales en términos de una expresión aritmética con dos parámetros.

Más concretamente, para cada sucesión finita \( s_1,\ldots, s_n \) de números naturales existen números \( c, d \) tales que \( \beta(c, d, i)= s_i \) para \( i = 1,\ldots, n \).

No es que puedas demostrar esto en AP, literalmente, porque para ello tendrías que tener ya formalizado el concepto de sucesión finita, sino que, cuando necesitas una sucesión finita, en lugar de decir "existen s_1, \ldots, s_n", puedes decir "existen \( c, d \) tales que..." y luego, donde dirías \( s_i \), dices \( \beta(c, d, i) \), y puedes contar con que eso va a funcionar bien.

Una vez puedes asociar a cada dos números naturales una sucesión finita de números naturales, puedes depurar eso de varias formas. Si quieres ir directo al grano, puedes usar la función \( \beta \) para dar definiciones recurrentes. Por ejemplo, si quieres definir la sucesión de Fibonacci, puedes hacerlo así:

\( \mbox{Fib}(n) = x \) si y sólo si existen \( c, d \) tales que \( \beta(c, d, 0) = 1 \) y \( \beta(c, d, 1) = 1 \) y para todo \( 1<i<i+1< n \) se cumple que \( \beta(c, d, i+2)=\beta(c, d, i)+\beta(c, d, i+1) \) y \( \beta(c, d, n) = x \).

Y ahí tienes una definición recurrente expresada en términos aritméticos.

Pero todo se puede hacer más fino si estás dispuesto a gastar tiempo. Por ejemplo, se puede usar \( \beta \) para definir la codificación de sucesiones que hemos introducido en este hilo, de modo que acabamos teniendo definidas aritméticamente las funciones \( \mbox{log}(s) \) y \( p(i, s) =s_i \) que determinan la longitud de un número natural visto como sucesión y sus componentes, para \( i<\mbox{long}(s) \), y a partir de ese momento trabajar con esta condificación más fina.

Pero, más aún, puedes definir, \( m\in n \) como "el dígito \( m \)-simo de la expresión de \( n \) en base \( 2 \) es igual a \( 1 \), y con eso tienes una relación de pertenencia que cumple los axiomas de ZFC menos el axioma de infinitud, y a partir de ahí puedes trabajar en AP como en ZFC sin infinitud (y con el axioma que afirma que todo conjunto es finito).

Una forma concreta de hacerlo la tienes en la sección 5.5 de mi libro de lógica, que diría así a ojo que no depende de nada anterior si pasas por alto algunos comentarios sobre la jerarquía de Kleene y donde leas I\( \Sigma_1 \) piensas simplemente en AP.

A mi me ha convencido en el sentido siguiente:

Si tu me das cualquier ordinal \( \alpha \) (de los definidos en el post claro), tengo hecho un pequeño programa que calcula el menor natural \( n \) para el cual se cumple \( \alpha \prec \omega^{(n)} \).

Sí, justo hasta ahí, no hay problema. Todo se reduce a probar que cada \( \omega^{(n)} \) es accesible.

Una vez tienes esto con dicho \( n \) ya fijo, se puede seguir el argumento que se da en la Respuesta #8 que, aunque implique usar un "y así sucesivamente" unas pocas veces, creo que está claro que cada afirmación que se hace es perfectamente válida. Así pruebas que \( \omega^{(n)} \) es accesible y con ello lo era el \( \alpha \) de partida.

Yo creo que no hay duda de que en ese mensaje se demuestra que \( \omega^{(3)} \) es accesible (o se puede extender la prueba hasta que no quede ningún paso en el aire), pero, ¿cuál sería el argumento que prueba que si \( \omega^{(n)} \) es accesible también lo es \( \omega^{(n+1)} \)? Lo único que hemos visto es que "razonando, razonando", se puede pasar de \( \omega^{(1)} \) a \( \omega^{(2)} \) y de \( \omega^{(2)} \) a \( \omega^{(3)} \), y nada parece indicar que haya nada de especial en el 3 que no permita pasar al 4, etc., pero los razonamientos necesarios necesitan cada vez más pasos y más casos, y no tenemos una descripción general del argumento que es necesario para pasar de \( n \) a \( n+1 \), sino un mero "si te pones a razonar (a trepar por los ordinales), seguro que vas a poder llegar a \( \omega^{(n+1)} \), ¿por qué no ibas a poder?"

Y una cosa es que los razonamientos que hemos dado sean sin duda razonamientos convincentes, y otra distinta que el "¿por qué no iba a poder continuar de esta misma manera?" cuele como "razonamiento", si no está claro qué queremos decir exactamente por "de esta misma manera".

De todos modos, quizá sea mejor posponer esta discusión para añadir como ingredientes lo que he contado en el mensaje de hoy (la respuesta #9, por si alguien lee esto más adelante) y lo que contaré en los siguientes.

Por último, respecto a la parte computacional, me ha parecido muy compacto y bien hecho el módulo que has hecho para tratar los ordinales  :aplauso:

Yo he programado algo parecido, pero muchísimo menos elegante y muchísimo más engorroso (aunque da los mismos resultados  ::))

Lo que hice es básicamente lo mismo que has hecho en tu módulo, pero en lugar de utilizar sucesiones de la cadena vacía [], he tratado con expresiones en "forma normal". Es decir, de forma teórica definiría recurrentemente, partiendo de los naturales, los conjuntos de "sucesiones finitas de naturales", "sucesiones finitas de sucesiones finitas de naturales", etc. Después utilizaría la "forma normal" para expresar de forma compacta cualquier elemento de estos conjuntos (identificando \( \omega=[1] \)) y, una vez hecho esto, el orden, decidir que elementos son ordinales y las operaciones aritméticas ya son exactamente iguales a lo visto en tus mensajes. La única dificultad ha sido hacer un programa que, dada una cadena de texto, te diga si es una "forma normal" y la exprese en una forma cómoda para trabajar con ella. Después es todo "coser y cantar".

Dejo aquí el archivo de Maple por si a alguien le apetece echarle un vistazo (aunque no incluye ninguna novedad a lo hecho por Carlos), pero aviso que los programa que permiten tratar con las cadenas de texto en "forma normal" son horrorosos :P

No conozco Maple. Cuando necesito cálculo simbólico uso Mathematica, y no veo muy práctico meterme ahora mismo en otro software distinto. A decir verdad, usé Maple hará más de 20 años, cuando debía de estar en mantillas respecto de lo que será ahora. Pero bueno, el único interés de los programas es, por una parte, dejar claro que estamos hablando de cosas tangibles y por otra también es útil programar para fijar ideas. No me cabe duda de que tú has aprovechado los programas en ambos sentidos y con eso ya han cumplido su función.

07 Mayo, 2023, 06:44 pm
Respuesta #13

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 982
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola de nuevo.

Es que dices que he dicho que la inducción hasta \( \epsilon_0 \) es equivalente a la consistencia de AP, cuando sólo he afirmado que si la inducción hasta \( \epsilon_0 \) es válida entonces AP es consistente. (Supongo que la implicación contraria también será cierta, pero tendría que pensarlo.) Pero no veo en el texto que citas qué te ha hecho pensar que afirmaba también la implicación contraria.

Lo que digo es que la validez de la inducción hasta \( \epsilon_0 \) equivale a la no existencia de sucesiones decrecientes de ordinales. Eso sí que es una equivalencia:

Si tienes una sucesión decreciente de ordinales, no se cumple la inducción respecto de la propiedad \( P(\alpha)\equiv  \) \( \alpha \) no aparece en la sucesión, pues si todos los ordinales menores que \( \alpha \) no aparecen en la sucesión, seguro que \( \alpha \) tampoco aparece, y no por ello podemos concluir que ningún ordinal aparece en la sucesión.

Recíprocamente, si no hay sucesiones decrecientes de ordinales, se cumple el principio de inducción, pues si supones que si todo ordinal menor que \( \alpha \) cumple \( P \), también \( \alpha \) cumple \( P \), es necesario que todos los ordinales cumplan \( P \), ya que si hubiera un \( \alpha_0 \) que no cumpliera \( P \), por la hipótesis tendría que haber otro \( \alpha_1\prec \alpha_0 \) que tampoco cumpliera \( P \), y así podríamos continuar construyendo una sucesión de ordinales que no cumplen \( P \).

Luego explico cómo se puede reformular el argumento de Gentzen para usar como hipótesis la inducción hasta \( \epsilon_0 \) en lugar de la no existencia de sucesiones decrecientes de ordinales.

Cuando tenga un rato retocaré el texto para aclarar este punto.

No, no. No afirmaba que habías dicho que la consistencia de AP fuera equivalente a la inducción hasta \( \epsilon_0 \), era solo que no había entendido a que te referías y me parecía que era eso lo que querías decir. Era porque pensaba que lo que escribías tras afirmar que la inducción hasta \( \epsilon_0 \) y la no existencia de sucesiones decrecientes de ordinales son equivalentes era una prueba de esto mismo. Pero ahora veo que realmente estabas queriendo mostrar otra cosa. Todo aclarado pues.

También tengo más claro, con lo que comentas, que se puede demostrar en AP, pero aún así cuando tenga tiempo y lea las secciones correspondientes de tu libro ya podré asegurarlo o preguntar dudas más concretas. Aún así, con lo dicho creo que si pillo por donde van los tiros.

Yo creo que no hay duda de que en ese mensaje se demuestra que \( \omega^{(3)} \) es accesible (o se puede extender la prueba hasta que no quede ningún paso en el aire), pero, ¿cuál sería el argumento que prueba que si \( \omega^{(n)} \) es accesible también lo es \( \omega^{(n+1)} \)? Lo único que hemos visto es que "razonando, razonando", se puede pasar de \( \omega^{(1)} \) a \( \omega^{(2)} \) y de \( \omega^{(2)} \) a \( \omega^{(3)} \), y nada parece indicar que haya nada de especial en el 3 que no permita pasar al 4, etc., pero los razonamientos necesarios necesitan cada vez más pasos y más casos, y no tenemos una descripción general del argumento que es necesario para pasar de \( n \) a \( n+1 \), sino un mero "si te pones a razonar (a trepar por los ordinales), seguro que vas a poder llegar a \( \omega^{(n+1)} \), ¿por qué no ibas a poder?"

Y una cosa es que los razonamientos que hemos dado sean sin duda razonamientos convincentes, y otra distinta que el "¿por qué no iba a poder continuar de esta misma manera?" cuele como "razonamiento", si no está claro qué queremos decir exactamente por "de esta misma manera".

Toda la razón sí. Por eso digo que me convence como argumento, pero no me deja todo el buen sabor de boca que me gustaría, por no tener precisamente un argumento general (como si lo teníamos para pasar, por ejemplo, de \( \omega^n \) a \( \omega^{n+1} \)) para pasar de la accesibilidad de \( \omega^(n) \) a \( \omega^{(n+1)} \).

De todos modos, quizá sea mejor posponer esta discusión para añadir como ingredientes lo que he contado en el mensaje de hoy (la respuesta #9, por si alguien lee esto más adelante) y lo que contaré en los siguientes.

La aplazamos entonces pues ;D

Ahora, respecto a la Respuesta #9, nuevo mensaje, nuevas erratas :laugh:

Notemos que, si la propiedad \( P(\alpha) \) puede definirse aritméticamente (recordemos que los ordinales no son más que números naturales, luego \( P(\alpha) \) podría ser cualquier propiedad del estilo "\( \alpha \) es múltiplo de 5" etc.) este principio de inducción puede formalizarse en el lenguaje de la aritmética, mediante la fórmula que en la respuesta #7 hemos llamado

\( P-\mbox{IND}(\epsilon_0)\equiv \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha))\rightarrow \forall \alpha\in E\,P(\alpha) \).

Para probar esto definimos dos propiedades a partir de \( P(\alpha) \):

\( P^*(\alpha) \) significará que todos los ordinales \( \beta\preceq \alpha \) tienen la propiedad \( P(\beta) \). Formalmente:

\( P^*(\color{red}\alpha\color{black})\equiv \forall \beta\in E(\beta\preceq \alpha\rightarrow P(\beta)) \).

Pequeña errata con las aes (latinas y griegas :laugh:)

A su vez, \( P'(\eta) \) significará que si un ordinal \( \alpha \) cumple \( P^*(\alpha) \), entonces también se cumple \( P^*(\alpha+\omega^\eta) \). Formalmente:

\( P'(\eta)\equiv \forall \alpha(\color{blue}( \color{black}\alpha\in E\land P^*(\alpha) \color{blue}) \color{black}\rightarrow P^*(\alpha+\omega^\eta)) \).

Aquí supongo que debería haber unos paréntesis como los que he puesto en azul, ¿no? Porque si no, nunca se cumplirá dicha propiedad.

Distinguimos tres casos, según si \( \eta=0 \), \( \eta \) es un ordinal sucesor o bien es un ordinal límite.

Si \( \eta=0 \) tenemos que probar \( P^*(\alpha+1) \), pero la hipótesis \( P^*(\alpha) \) equivale a que \( \forall \beta\in E(\beta\prec \alpha+1\rightarrow P(\beta)) \), y entonces podemos aplicar (B), que nos da \( P^*(\alpha+1) \), como queríamos.

Creo que se aplica la propiedad (B) probada a partir de (A).

Suponemos \( P^*(\alpha+\omega^\delta\cdot k) \) y, como \( \delta\prec \eta \), por (E) tenemos \( P'(\delta) \) que, por definición de \( P' \), implica

\( P^*(\alpha+\omega^\delta\cdot k)\rightarrow P^*(\color{red}\alpha+\omega\color{black}^\delta\cdot k+\omega^\delta) \)

y lo segundo es precisamente \( P^*(\alpha+\omega^\delta\cdot (k+1)) \), lo que completa la inducción, la prueba de (G) y, por lo tanto, la de (F).

Habías intercambiado \( \alpha \) y \( \omega \) en lo corregido en rojo.

Ahora podemos aplicar repetidamente (2) (ya que contamos con \( P''(0), P'(0), P(0) \)), lo que nos da:

\( \forall \alpha\in E(\alpha\preceq \omega^{(2)}\rightarrow P''(\alpha)) \)

\( \forall \alpha\in E(\alpha\preceq \omega^{(3)}\rightarrow P'(\alpha)) \)

\( \forall \alpha\in E(\alpha\preceq \omega^{(4)}\rightarrow P(\alpha)) \)

Aquí falta un paréntesis que he marcado en azul.

Por último, respecto al mensaje en sí, diría que la parte que no puede formalizarse en AP empieza aquí:

Aplicando repetidamente (1), tenemos:

Porque una demostración formal es una sucesión finita de fórmulas, pero con este "aplicamos repetidamente (1)", el número de fórmulas en la "demostración" dependerá del \( n \) para el cual se cumpla que \( \alpha \prec w^{(n)} \). Es decir, creo que para cualquier \( n \) fijo es posible demostrar en AP la inducción hasta cualquier \( \omega^(n) \) siguiendo el argumento que has dado, pero no es posible demostrarla hasta \( \epsilon_0 \) pues precisaríamos de una infinitud de demostraciones concatenadas y eso no es una demostración formal pues, por definición, deben tener una longitud finita. Vamos, que el problema creo que está siempre en el "repetimos una cantidad arbitraria de veces" que es válido intuitivamente (pues queda perfectamente especificado como deberíamos repetir el proceso independientemente del \( n \), no como en lo discutido sobre la Respuesta #8), pero no es posible formalizarlo en una teoría axiomática débil como es AP que no permite con sus axiomas hablar de conjuntos infinitos.

Tampoco afirmo nada de lo anterior con una convicción férrea, pero creo que la idea va por ahí, ¿no? ¿O estoy completamente equivocado y con un buen lío en la cabeza? ::)

Un saludo.

07 Mayo, 2023, 06:59 pm
Respuesta #14

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ahora, respecto a la Respuesta #9, nuevo mensaje, nuevas erratas :laugh:

Las ratas son siempre las primeras en abandonar el barco, y las erratas las últimas.   ::)

Ya las he corregido, gracias una vez más.

Tampoco afirmo nada de lo anterior con una convicción férrea, pero creo que la idea va por ahí, ¿no? ¿O estoy completamente equivocado y con un buen lío en la cabeza? ::)

 :aplauso:

Ya lo comentaré con detalle en el próximo mensaje del hilo principal, pero, en efecto, el problema está ahí.

08 Mayo, 2023, 01:18 am
Respuesta #15

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Partimos de \( R_0 = \{0\} \). Como \( 0 = \left<0, 0\right>_2 \), con esto estamos diciendo que \( 0\in E \) y que \( 0\preceq 0 \).

Supongamos ahora que ya tenemos definido \( R_n \), es decir, que para todo número \( x\leq n \) ya está decidido si \( x \) está o no en \( E \) (según si se cumple \( x\preceq x \) o, equivalentemente si \( \left<x, x\right>_2\in R_n \) o no) y para todo par de números \( x, y\leq n \) ya está decicido si cumplen o no \( x\preceq y \).

Para definir \( R_{n+1} \) en primer lugar tenemos que decidir si \( n+1\in E \). En caso negativo será \( R_{n+1}= R_n \).

Para ello expresamos \( n+1 = \left<s_1, \ldots, s_l\right>_\infty \) como sucesión de números naturales. Hemos visto que entonces \( s_i\leq n \) para todo \( i \), y la condición para incluir \( n+1\in E \) es que se cumpla que todos los \( s_i \) estén en \( E \) (es decir, que \( \left<s_i, s_i\right>_2\in R_n \)) y que además la sucesión sea decreciente: \( s_1\succeq s_2\succeq \cdots \succeq s_l \).

Si esto es así establecemos, por definición, que \( \left<n+1, n+1\right>_2\in R_{n+1} \) y ahora tenemos que decidir, para cada \( x\leq n \), si añadimos a \( R_{n+1} \) el par \( \left<x, n+1\right>_2 \) o el par \( \left<n+1,x\right>_2 \).

Si no se cumple que \( \left<x, x\right>_2\in R_n \) (es decir, si no hemos metido a \( x \) en \( E \)), no incluimos ninguno de los dos pares, mientras que si \( \left<x, x\right>_2\in R_n \), expresamos

\( n+1 = \left<s_1, \ldots, s_l\right>_\infty \),     \( x= \left<t_1,\ldots, t_r\right>_\infty \)

y consideramos las posibilidades siguientes:

a) Si la sucesión de \( n+1 \) se prolonga hasta la de \( x \) (Aclaro: si \( \color{red}x = \left<s_1,\ldots, s_l, t_{l+1},\ldots, t_r\right>_\infty \)), entonces metemos \( \left<n+1, x\right>_2 \) en \( R_{n+1} \).

b) Si la sucesión de \( x \) se prolonga hasta la de \( n+1 \), entonces metemos \( \left<x, n+1\right>_2 \) en \( R_{n+1} \).

c) Si ninguna sucesión extiende a la otra, podemos fijar el mínimo número natural en el que difieren, es decir, el mínimo \( i \) tal que \( s_j = t_j \) para \( j<i \), pero \( s_i\neq t_i \) (notemos que las sucesiones no pueden ser iguales, porque \( x<n+1 \)).

En tal caso, si \( s_i\preceq t_i \) metemos \( \left<n+1, x\right>_2 \) en \( R_{n+1} \), y si \( t_i\preceq s_i \) metemos el par opuesto \( \left<x, n+1\right>_2 \).

Esto completa la definición recurrente de los conjuntos \( R_n \), con lo que tenemos definido el conjunto \( E \) de todos los números naturales \( n \) que cumplen que \( \left<n, n\right>_2 \) esta en \( R_n \) y, para números en \( E \), la relación \( x\preceq y \) dada por \( \left<x, y\right>_2\in R_n \), donde \( n= \max\{x, y\} \).

Para mi gusto personal, esta exposición es algo engorrosa.

Dado que para cada \(n\in\mathbb N\) se establece si \(x\preceq y\) cuando \(x,y\leq n\),
podría definirse una relación \(\preceq_n\) con dominio el segmento inicial \([0,n]=\{0,1,2,...,n\}\).

Luego se haría:
\[
  \preceq \quad := \quad \bigcup_{n=0}^\infty \mathbb N^n.
\]

Yo dejaría la definición de los conjuntos \(R_n\) para el final,
enfocándome en definir \(\preceq_n\).

Las condiciones para establecer \(x\preceq y\) en \([0,n]\) me parecen escritas de una forma extensa.
Intentaré ser más sintético, separando con más claridad los casos posibles:

Supogamos definida \(\preceq_n\subset [0,n]\times[0,n]\).

Dados \(a,b\in[0,n]\), si \(a\preceq_n b\), entonces establecemos:
\[a\preceq_{n+1} b.\]
Por lo tanto, \(\preceq_{n+1}\) extiende \(\preceq_n\).

Denotar \(n+1=\langle s_1,\ldots,s_l\rangle_\infty\).
Si para todo \(j,k, 1\leq j\leq k\leq l\),
vale que \(s_j\succeq_n s_k\).
Se establece que:
\[n+1\;\preceq_{n+1}\;n+1.\]

A continuación, si eso ocurre, continuamos agregando más elementos:

Sea \(x\leq n\).
Si no cumple que \(x\preceq_n x\), no hacemos nada con  \(x\).

En cambio, si \(x\preceq_n x\), avanzamos un poco más, y denotamos:


\[x=\langle t_1,...,t_r\rangle_\infty.\]

Sea \(q\) el mínimo número natural tal que:
\(s_j=t_j\) para \(j < q, j \leq l, j \leq r\).

Si \(q = l+1\leq r\), ó bien \(q\leq l,r\) y \(s_q\preceq_n t_q\), establecemos:
\[n+1\preceq_{n+1} x.\]

En caso contrario, vale que
\(q=r+1\leq l\), ó bien \(q\leq l,r\) y \(t_q\preceq_n s_q\),
en cuyo caso establecemos:
\[x\preceq_{n+1} n+1.\]

La manera en que se define \(\preceq_{n+1}\)
indica que es un subconjunto de \([0,n+1]^2\).

Luego, se definiría:
\[\preceq_\infty \; = \; \bigcup_{n=0}^\infty \preceq_n.\]

Ahora recién definiría los conjuntos \(R_n\) y \(E\):

\[R_n = \{\langle a,b\rangle_2: a\preceq_n b\}.\]

\[R_\infty=\bigcup_{n=0}^\infty R_n.\]

\[E=\{x\in R_\infty: x\preceq_\infty x\}.\]

Y finalmente defino \(\preceq\) como la restricción de \(\preceq_\infty\) a \(E\).

Aún así, la exposición tal como está en la cita,
tendría que estar de algún modo u otro,
porque es más pedagógica.


08 Mayo, 2023, 02:38 am
Respuesta #16

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Para mi gusto personal, esta exposición es algo engorrosa.

Aún así, la exposición tal como está en la cita,
tendría que estar de algún modo u otro,
porque es más pedagógica.

Bueno, mi intención era que se entendiera a qué llamamos "ordinal" y cómo están ordenados los ordinales. Lo que podríamos llamar "ser pedagógico", pero algo debe de fallar en mi exposición porque cada lector se redacta su versión (primero Eparoh y ahora tú). Por cierto, que te has dejado el mismo punto importante que se había dejado Eparoh en su momento:

A continuación, si eso ocurre, continuamos agregando más elementos:

Sea \(x\leq n\), y denotar:
\[x=\langle t_1,...,t_r\rangle_\infty.\]

¡Ojo! Una condición necesaria para que se cumpla \( x\preceq_{n+1} n+1 \) (que has pasado por alto) es que tiene que cumplirse \( t_1\succeq \cdots \succeq t_r \).

Ahora recién definiría los conjuntos \(R_n\) y \(E\):

\[R_n = \{\langle a,b\rangle_2: a\preceq_n b\}.\]

\[R_\infty=\bigcup_{n=0}^\infty R_n.\]

En realidad ahora los conjuntos \( R_n \) y \( R_\infty \) ya no hacen falta para nada. Si vas a trabajar con pares ordenados "de verdad", no es necesario recurrir a los pares \( \left<a, b\right>_2 \). No los vamos a usar para nada. En cambio, el conjunto de ordinales \( E \) sí que va a ser esencial.

Mi intención era que la exposición quedara más cerca de la aritmética de Peano que de la teoría de conjuntos, y por eso evité los pares ordenados "de verdad", pero esos detalles son irrelevantes. Quiero decir, que si te gusta más como lo estás haciendo, bien está (siempre y cuando no te dejes la condición que te he señalado antes) y no les hagas caso a los conjuntos \( R_n \), que con tu enfoque no hacen falta.

Pues... no sé. Si os parece bien, añadiré en ese mensaje un par de spoilers con tu exposición de la definición y la de Eparoh, para que cada lector se quede con la que más le guste (y confiando en que, entre la mía y las vuestras, todo futuro lector se quede satisfecho con alguna y no venga a sugerir una cuarta  ;D ).

08 Mayo, 2023, 08:41 am
Respuesta #17

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 982
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola de nuevo.

Ya lo comentaré con detalle en el próximo mensaje del hilo principal, pero, en efecto, el problema está ahí.

Leída la Respuesta #10 veo claro que si era lo que pensaba, pero ahora me surge una duda: ¿En ZFC es posible formalizar el argumento anterior?

No me refiero a si es posible probar la inducción hasta el ordinal \( \epsilon_0 \) (que eso se que en ZF es casi trivial por las propiedades de los ordinales), sino si el argumento dado en la Respuesta #9 podría formalizarse en ZFC. A simple vista, me parece que se tiene el mismo problema aunque trabajemos en una teoría axiomática más potente: conocer pruebas individuales de la inducción hasta \( w^(n) \) para cada natural \( n \) no te da inmediatamente una prueba de \( \forall n\ P-\mbox{IND}(\omega^{(n)}) \) por el requerimiento de finitud de las demostraciones formales. Ahora bien, igual me equivoco y alguno de los axiomas de ZFC si permite dar dicho paso. ¿Cuál es el caso?

Pues... no sé. Si os parece bien, añadiré en ese mensaje un par de spoilers con tu exposición de la definición y la de Eparoh, para que cada lector se quede con la que más le guste (y confiando en que, entre la mía y las vuestras, todo futuro lector se quede satisfecho con alguna y no venga a sugerir una cuarta  ;D ).

Por mi perfecto. Entre las tres explicaciones creo que lo dejan todo más que claro  ;D

Quedo espectante por ver la demostración de Takeuti. A ver si esta pasa de "muy convincente" a "razonamiento" :laugh:

Un saludo.

08 Mayo, 2023, 01:43 pm
Respuesta #18

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Leída la Respuesta #10 veo claro que si era lo que pensaba, pero ahora me surge una duda: ¿En ZFC es posible formalizar el argumento anterior?

No me refiero a si es posible probar la inducción hasta el ordinal \( \epsilon_0 \) (que eso se que en ZF es casi trivial por las propiedades de los ordinales), sino si el argumento dado en la Respuesta #9 podría formalizarse en ZFC. A simple vista, me parece que se tiene el mismo problema aunque trabajemos en una teoría axiomática más potente: conocer pruebas individuales de la inducción hasta \( w^(n) \) para cada natural \( n \) no te da inmediatamente una prueba de \( \forall n\ P-\mbox{IND}(\omega^{(n)}) \) por el requerimiento de finitud de las demostraciones formales. Ahora bien, igual me equivoco y alguno de los axiomas de ZFC si permite dar dicho paso. ¿Cuál es el caso?

Pues... según lo mires. En cierto sentido, tienes razón cuando dices que en ZF tendrías igualmente una sucesión de infinitas demostraciones que no hacen una demostración, pero eso tiene remedio sin que podamos decir que estamos cambiando de argumento.

La idea básica es que en ZFC se puede formalizar todo (bueno, todo no. Eso es esencialmente cierto pero tiene algo de "letra pequeña" que comento un poco más abajo).

En ZF (y de hecho en AP) se puede demostrar que, para cada número natural \( n \), existe una demostración de que \( \omega^{(n)} \) es accesible.

Observa que, si identificamos con números naturales los signos de un lenguaje formal, una fórmula no es más que una sucesión de números naturales, que en AP puede verse como un único número natural, y a su vez una demostración es una sucesión de fórmulas, que también puede verse como un número natural. Igual que puede definirse en AP cuándo un número natural es un ordinal, se puede definir cuándo es una demostración de tal o cual fórmula. Así, podemos construir una fórmula aritmética \( \phi(n) \) que signifique "\( \omega^{(n)} \) es accesible", y también otra que diga que, para cada \( n \) existe una demostración de la fórmula \( \phi(n) \).

Todo esto es lo que Gödel hizo codificando fórmulas y demostraciones con "números de Gödel", y probó que, en efecto, todo los conceptos lógicos "fórmula, demostración, etc." son definibles a partir de los axiomas de Peano.

Por supuesto, en ZF todo esto se puede hacer de forma mucho más fácil. En resumen, tanto en ZF como en AP podemos demostrar la fórmula que dice:

Para cada número natural \( n \) existe una demostración en AP de que el ordinal \( \omega^{(n)} \) es accesible.

La diferencia es que en AP no podemos ir más lejos, mientras que en ZF podemos probar que si existe una demostración de la fórmula \( \omega^{(n)} \) es accesible, dicha fórmula será verdadera en el modelo natural definido por los números naturales, y el hecho de que la fórmula "\( \omega^{(n)} \) es accesible" sea verdadera en el modelo natural implica que \( \omega^{(n)} \) es accesible. Por lo tanto, en ZF podemos demostrar que todos los \( \omega^{(n)} \) son accesibles y, por consiguiente, que todo ordinal (menor que \( \epsilon_0 \)) es accesible.

En cambio, en AP no podemos pasar de "se puede demostrar que \( \omega^{(n)} \) es accesible" a "\( \omega^{(n)} \) es accesible". Para ello habría que definir una función que a cada número natural que codifique una fórmula le asigne un valor 0 o 1 según que la fórmula correspondiente sea verdadera o falsa en los números naturales, para luego probar que los axiomas de Peano son verdaderos y todas sus consecuencias también, por lo que si una fórmula es demostrable, entonces es verdadera.

Esto se puede hacer sin problemas en ZF, pero en AP falla justo lo primero: no es posible definir en AP si un número natural que codifica una fórmula, codifica una fórmula verdadera o falsa (con su interpretación natural), pues eso es precisamente lo que afirma el teorema de Tarski sobre indefinibilidad de la verdad. En una teoría aritmética se puede definir el concepto de fórmula de dicha teoría aritmética, incluso el concepto de fórmula demostrable, pero no el concepto de fórmula verdadera, en el sentido de que si un número \( n \) codifica una sentencia \( \alpha \), se cumpla

\( n \) es verdadera \( \leftrightarrow \alpha \)

En ZF se puede definir una fórmula que diga si un número que codifica una fórmula aritmética codifica una fórmula aritmética verdadera en el modelo \( \mathbb N \) y eso nos permite terminar de formalizar el argumento de Gentzen. Lo que prohíbe el teorema de Tarski para ZF es definir qué significa que una fórmula del lenguaje de ZF sea verdadera  de modo que si \( n \) codifica una sentencia \( \alpha \) (del lenguaje de ZF, no del lenguaje de la aritmética) se cumpla

\( n \) es verdadera \( \leftrightarrow \alpha \)

Vamos, que una teoría aritmética no puede definir qué significa que una fórmula de su propio lenguaje (no de otro más pequeño) sea verdadera.

Esto es un ejemplo de que en ZF no se puede formalizar "todo, todo". Uno podría esbozar una demostración de "fórmula verdadera" que "debería" funcionar en ZF, pero que no funciona porque involucra clases propias de una forma que ZF no es capaz de gestionar. Hay resultados que en ZF sólo se pueden probar para conjuntos, pero no para clases propias.

Pero las clases propias de ZF están a años luz de distancia de los conceptos intuitivamente bien definidos, por lo que estas limitaciones de ZF no impiden formalizar ningún argumento que sea intuitivamente convincente.

08 Mayo, 2023, 02:26 pm
Respuesta #19

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
A continuación, si eso ocurre, continuamos agregando más elementos:

Sea \(x\leq n\), y denotar:
\[x=\langle t_1,...,t_r\rangle_\infty.\]

¡Ojo! Una condición necesaria para que se cumpla \( x\preceq_{n+1} n+1 \) (que has pasado por alto) es que tiene que cumplirse \( t_1\succeq \cdots \succeq t_r \).

Entiendo que eso es lo mismo que pedir que \(x\preceq_n x\).
¿Correcto?

Si es así, agrego ese detalle a mi exposición anterior.