Ah, conque ensartándome mi propio puñal... jaja.
Pues aquí tienes un ejemplo de cómo se te puede ensartar tu puñal. Precisamente me pareció interesante hablar de esto para casos como éste. Tú dices:
Creo que como matemático, muchas veces lo que necesito es saber "qué me dejan usar",
y qué cosas "no me dejan usar". Ambas.
Y ahora puedo recordarte que en este hilo nadie te ha dicho qué te dejan usar o qué no te dejan usar, pero que, a pesar de ello, tú viste la primera "prueba" de Gentzen sobre la buena ordenación de \( \epsilon_0 \) y dijiste esto:
Este argumento, así como se muestra ahí, no me parece válido.
Lo cual es una cosa distinta a si ayuda a "convencer" de la accesibilidad de \(\epsilon_0\).
Da la sensación de que hay una estructura en los ordinales que permite afirmar que son todos accesibles,
pero que el "argumentador" no es capaz de poner de manifiesto cuál es esa estructura de una forma creíble.
La "lógica" que aparece allí me parece insuficiente.
Y yo estoy de acuerdo contigo: tú juzgaste (sin que nadie te dijera qué puedes usar y qué no) que dar eso por un argumento convincente no era aceptable, y seguiría sin serlo si alguien te dijera que puedes usar eso como argumento.
Por el contrario, viste la prueba de Takeuti y dijiste esto otro:
El argumento de Takeuti parece simple y mucho más creíble.
De modo que, aunque nadie te hubiera dicho que podías usarlo, te pareció usable, según tu propio criterio. Más aún, tú mismo has dado un argumento que —supongo— te parecerá aceptable, y a mí también me lo parece, aunque tal vez algún finitista radical podría decir que no le convence (no me preguntes por qué, porque no he conocido nunca a ningún finitista radical para entender cómo piensan). Así pues, si tu propio argumento te convence —a mí me convence— tú mismo has decidido qué podías usar en un argumento que te convenciera de que los ordinales menores que \( \epsilon_0 \) están bien ordenados.
Aquí tiene la moraleja de esta historia: no necesitas limitarte a decir: uso esto porque (me dicen que o se ha establecido que) aquí está permitido y no uso aquello porque aquí no está permitido, sino que tú mismo puedes decidir qué te parece admisible y qué no a la hora de concluir que un hecho es cierto.
Me llama la atención que con los Axiomas de AP sea posible construir una estructura más compleja que los naturales dentro de los mismos naturales, como los ordinales hasta \(\epsilon_0\).
Bueno, no sé qué le exigirás exactamente a una estructura para que la podamos considerar "más compleja" que los naturales, así que no sé si esto serán otros ejemplos: en AP puedes construir los números enteros, los números racionales, los enteros de Gauss, los enteros ciclotómicos, etc. Si consideras esas estructuras más complejas, entonces ves que los ordinales hasta \( \epsilon_0 \) son un caso más entre muchos, y si no las consideras más complejas, entonces lo que sucede es que los ordinales hasta \( \epsilon_0 \) sólo son aparentemente más complejos que los números naturales, pero en realidad no.
He estado buscando otras formas de construir las tuplas de Gentzen, pero la termino complicando demasiado en algún punto.
Me he quedado estancado en \(\omega^2\), o luego en \(\omega^\omega\) por ejemplo.
Haciendo modificaciones menos ambiciosas se pueden obtener desarrollos alternativos.
Es decir, obviamente, cualquier biyección de \(\mathbb N\) a \(\mathbb N^2\) debiera servir para obtener la construcción de las tuplas, hasta obtener la forma normal de Cantor, y desde ahí ya no importa cómo se llegó a ese punto.
Pero yo pretendía lograr, por ejemplo, que el conjunto \(E\) me coincidiera con todos los naturales. Mmmm....
Como sea, intentar formas alternativas me ayudó a valorar la construcción de Gentzen con ese método.
Pues no sé. Nunca me he puesto a pensar qué variantes se pueden hacer y qué ventajas tendrían. Eso sí, yo no aseguraría que la codificación de los ordinales como n-tuplas que he puesto en el hilo sea tal cual atribuible a Gentzen. Sospecho que es más moderna.
Creo que una de las cosas que me molesta es la necesidad de codificar la longitud de las tuplas como una información que forma parte de ellas.
Pensaba por ejemplo que se podría especificar algo más directo,
como \(2^\ell(2x+1)\), donde \(\ell\) sería la longitud de la tupla, y \(x\) se usaría para representar la codificación de una tupla de longitud \(\ell\),
con cualquier estrategia que biyecte \(\mathbb N\) en \(\mathbb N^\ell\).
¿Y no es lo mismo en el fondo? En realidad usar exponentes para codificar sucesiones es más complicado que lo que hacemos en el hilo. Si quieres usar eso sistemáticamente, puedes usar el sistema que uso Gödel cuando definió sus "números de Gödel": puedes codificar la sucesión \( s_1, \ldots, s_n \) con el número \( 2^{s_1}\cdot 3^{s_1}\cdots p_n^{s_n} \), donde \( p_n \) es el n-simo primo. Así no necesitas incluir la longitud de ningún modo como parte de la sucesión. Ésta queda "almacenada" en el orden del mayor primo que divide al código.
Otra pregunta que se me ocurre plantear es si puede demostrarse en general la capacidad de un sistema de producir ordinales hasta cierto valor, de la siguiente manera:
Si un sistema axiomático de \(\mathbb N\) permite construir ordinales hasta cierto \(\alpha\), entonces permite construir ordinales hasta \(\epsilon_0\).
Por ejemplo, ¿es ciero que si un sistema axiomático permite construir ordinales hasta \(\alpha=\omega^\omega\), entonces permite también llegar hasta \(\epsilon_0\)?
Y la misma pregunta para \(\alpha=\omega^2\), o para \(\alpha=\omega\cdot 2\).
Es fundamental distinguir entre los ordinales que pueden construirse en una teoría y los ordinales que puede probarse que están bien ordenados.
Por ejemplo, en AP podemos definir un "superordinal" como un par de ordinales (de los que hemos definido en el hilo) \( \left<\alpha, \beta\right> \), y considerar el orden lexicográfico en los superordinales. Con eso has definido en AP todos los ordinales menores que \( \epsilon_0+\epsilon_0 \), y tienes un nombre para cada uno de ellos. Por ejemplo, uno concreto sería \( \left<\omega^3\cdot 5+\omega+7, \omega^2+\omega\cdot 4\right> \). Todo "superordinal" tiene un nombre concreto de este estilo. En particular, \( \epsilon_0 = \left<1, 0\right> \), \( \epsilon_0+1 = \left<1, 1\right> \), etc.
Si interpretas estos "superordinales" y su relación de orden en el modelo natural de AP, resulta que están bien ordenados, pero en AP no se puede demostrar que lo estén a partir de \( \epsilon_0 \). Similarmente puedes definir en AP ordinales mucho mayores que \( \epsilon_0 \), que estarán bien ordenados (en el sentido de que lo están en el modelo natural), pero que no se puede demostrar en AP que lo están.
Así pues, lo que importa no es qué ordinales se pueden construir (con definiciones correctas, en el sentido de que en el modelo natural se interpreten como conjuntos bien ordenados), sino qué ordinales se puede demostrar que están bien ordenados en una teoría dada.
Eso ha dado lugar a una rama de la teoría de la demostración que se conoce como
análisis ordinal, de la que no sé nada de nada, más allá de que el mínimo ordinal que no puede probarse que está bien ordenado en AP es \( \epsilon_0 \). En la página de wikipedia puedes ver otras teorías para las que se conoce cuál es ese mínimo ordinal.
Cabe señalar que el sentido de la pregunta (encontrar el mínimo ordinal que no se puede probar que está bien ordenado en una teoría dada) no es trivial, pues presupone que hay que elegir una forma de codificar los ordinales en la teoría en cuestión (ya que no vale la definición conjuntista). Por ejemplo, en AP hemos codificado los ordinales usando la expresión en forma normal de Cantor para reducirlos a sucesiones finitas, pero codificar ordinales mayores requiere usar otras funciones más allá de la suma, el producto y la exponenciación de ordinales.
Carlos, creo que dijiste que con Axiomas más débiles que AP todo esto funcionaba.
¿En qué sistemas axiomáticos más débiles se puede elaborar toda esta construcción de ordinales?
Teorías aritméticas (unas más fuertes y otras más débiles que AP) hay montones. En la página de wikipedia que he citado antes puedes ver unas cuantas.
Una familia de teorías más débiles que AP son las que resultan de debilitar el principio de inducción. Por ejemplo, el caso más drástico es eliminarlo por completo, y entonces tienes la llamada
Aritmética de Robinson, que es la que tiene por axiomas los axiomas de Peano menos la inducción (añadiendo un axioma que dice que todo número natural es el 0 o el siguiente de otro, pues eso se prueba en AP por inducción). Su interés reside, entre otras cosas, en que el primer teorema de incompletitud de Gödel es válido para la aritmética de Robinson (y, por lo tanto, para cualquier teoría que la extienda), con lo que "la culpa" de la incompletitud no es atribuible al axioma de inducción, ya que sigue estando ahí sin él.
Otros casos menos drásticos son los que resultan de restringir el axioma de inducción, por ejemplo, a fórmulas de tipo \( \exists x\, \alpha \) o \( \forall x,\alpha \), donde la fórmula \( \alpha \) sólo tiene cuantificadores acotados, del tipo \( \forall x<y \) o \( \exists x<y \). Esta subteoría de AP se conoce como \( \rm I\Sigma_1 \).
En cuanto a lo que dije yo sobre teorías más débiles, no sé si te refieres a esto:
No necesitamos considerar propiedades arbitrarias (con toda la vaguedad que ello conlleva), sino que a efectos de lo que nos ocupa basta considerar una propiedad en concreto: la de no ser el ordinal de la prueba de una contradicción en AP, que se corresponde con la no existencia de sucesiones decrecientes de ordinales de pruebas de contradicciones en AP (y estas afirmaciones son formalizables en AP, e incluso en teorías mucho más débiles, porque estamos hablando de conceptos recursivos, calculables por ordenadores, y no de afirmaciones aritméticas arbitrarias).
Me refería que la prueba de Gentzen de que si \( \epsilon_0 \) está bien ordenado entonces AP es consistente es formalizable en AP y en teorías más débiles. La teoría más natural entre las subteorías de AP en las que se puede demostrar el teorema de Gentzen es la Aritmética Recursiva Primitiva (aunque no podría asegurar que sea la más débil posible), la cual se considera que formaliza ni más ni menos que lo que consideraría aceptable un finitista puro y ortodoxo, que desconfíe de cualquier abuso de objetos numerables (como sucesiones infinitas) o incluso de pruebas de existencia no constructivas.
Según dice la página de wikipedia anterior (no conozco la prueba) el mínimo ordinal que no puede probarse en ARP que está bien ordenado es \( \omega^\omega \).
Esto nos lleva a esto otro:
Me ha gustado mucho seguir el hilo, he aprendido mucho con él y solo espero que no sea el último que hagas porque realmente se disfrutan mucho y son más llevaderos cuando uno no tiene mucho tiempo que el ponerse a leer un libro sobre el tema sin saber muy bien por donde empezar.
Hace unos días que estaba pensando que podría ser interesante un hilo que presentara la Aritmética Recursiva Primitiva, porque no es muy popular, en el sentido de que es difícil encontrarla con detalle salvo en libros y artículos técnicos, y no me parece que sea "una más en el zoo de subteorías de AP". De hecho, si me planteaba presentarla es porque basta para formalizar la lógica matemática básica (es decir, no el teorema de completitud, por ejemplo, pero sí lo necesario para construir ZFC y, a partir de ahí, usarlo para hacer matemática formal, aunque sin entrar en las garantías de que su lógica es la que debe ser) y requiere aceptar muy pocos hechos intuitivamente ciertos sobre los números naturales (los demás se pueden demostrar formalmente en ella misma).
Ahora, la verdad es que no sé lo largo que se podría hacer un hilo sobre ARP, pero si os interesa, podríamos meternos en harina a ver hasta dónde llegamos.
