[Carlos Ivorra]

Un tema recurrente en este foro a lo largo de los años es si existe o no una matemática intuitiva —en el sentido de matemática no concebida como un mero deducir lógicamente sentencias de unos axiomas prefijados sin tener en cuenta su significado— rigurosa, fiable e incluso necesaria.

Las contradicciones que se encontraron los matemáticos a principios del siglo XX hicieron que se extendiera en la comunidad matemática un formalismo radical que, naturalmente, sólo afectó a quienes no se enfrentaron realmente al problema, es decir, a los expertos y no expertos en otras áreas de la matemática distintas de la lógica en general y de la teoría de la demostración en particular. Éstos se convencieron de que todo lo que no sea fijar unos axiomas y deducir a partir de ellos no es matemática seria, sin ser conscientes de que con esa concepción es imposible estudiar la corrección y adecuación de unos axiomas y reglas de razonamiento para decidir si son admisibles o no, o si unos son preferibles a otros en uno u otro sentido, etc.

Y, al margen de que razonar intuitivamente (con todo rigor) pueda ser imprescindible en ciertos contextos, el hecho es que es posible, tanto si es necesario como si no (y así, uno podría estudiar con todo rigor la aritmética elemental, buena parte de la teoría de grupos finitos, grafos, etc. sin necesidad alguna de ZFC o equivalentes). Sin embargo, parece que filosofar sobre este tema no sirve de nada a la hora de que un formalista radical deje de serlo, sino que la única forma en la que parece posible que alguien abandone sus prejuicios formalistas consiste en que se enfrente a la necesidad de razonar intuitivamente (por ejemplo, a la hora de fundamentar la matemática formal) y sólo entonces uno empieza a darse cuenta por sí mismo del dilema "intuición o estamos perdidos" y que la primera opción no tiene realmente nada de malo (pero he dicho "empieza a", no "termina por").

En este foro se han expuesto opiniones que se extienden por todo el espectro del formalismo radical, que, enunciadas familiarmente, podríamos expresar como que "eso de las matemáticas intuitivas son paparruchas" o "la matemática intuitiva no es más que matemática formal disfrazada", o incluso que los autores de libros de lógica y teoría de la demostración ocultan (o debería decir ocultamos) al mundo que todo eso que dicen (decimos) es un engaño.

Quiero dejar claro que no insinúo ni por asomo que los formalistas radicales sean algo así como terraplanistas o chalados de los que demuestran el Último Teorema de Fermat en diez líneas y dicen que los matemáticos tratan de ocultar que hay pruebas sencillas, etc. Al contrario, entiendo que el problema de la fundamentación de la matemática es delicado y que no se le puede pedir a nadie que diga: "acepto que existe una matemática intuitiva rigurosa aunque no entiendo cómo es esto posible", y que parece difícil que alguien, pese a su mejor voluntad, pueda llegar a entender esto "filosofando en el aire" sin meterse a fondo en harina y preocuparse de ver cómo se puede fundamentar satisfactoriamente la matemática formal, pero eso es algo que lleva mucho tiempo. De hecho, si yo tengo claras estas ideas, no es por ninguna genialidad por mi parte, sino porque dediqué muchos años hace tiempo en estudiar a fondo la fundamentación de la matemática, y este tiempo no es algo de lo que cualquiera pueda disponer en cualquier momento.

Anécdota sobre la genialidad

En cierta ocasión un crítico calificó de genio al violinista Pablo Sarasate, y él respondió: ¡Un genio! He practicado catorce horas diarias durante treinta y siete años, y ahora me llaman genio.

Igualmente estoy convencido de que entender lo que es la matemática intuitiva no es cuestión de ninguna genialidad, sino de haber dedicado tiempo suficiente a tratar de entender otras cosas más concretas que, para que tengan sentido, requiren, quieras o no, razonar intuitivamente.

[cerrar]

Por ello, el propósito de este hilo es suministrar un "material didáctico" adicional, unas ideas que tal vez puedan contribuir a quien reflexione sobre ellas a formarse una idea más adecuada del problema (no trivial) que supone razonar de forma rigurosa y fiable en términos intuitivos, es decir, atendiendo a que lo que se diga sea verdad y no una mera consecuencia formal de unos axiomas.

La popularización de los teoremas de incompletitud de Gödel ha contribuido notablemente a que muchos matemáticos empiecen a entender que la matemática informal (pero rigurosa, porque el formalismo radical llega a identificar "informal", "intuitivo" con "no riguroso" o "poco serio", y no tiene nada que ver lo uno con lo otro) es viable, e incluso necesaria para entender plenamente algunos resultados. En este hilo me propongo exponer unas ideas que son relativamente sencillas pero que, a diferencia de los teoremas de incompletitud, no se han popularizado y, como están relacionadas con otras ideas mucho más técnicas, permanecen profundamente enterradas en los libros de teoría de la demostración en los que pocos se adentran.

He pensado en ello a raíz de un comentario que hice de pasada en este hilo, en el que mencioné lo que quiero exponer aquí como ejemplo extremo de lo que supone razonar intuitivamente.

Por si lee esto alguien que ya conoce estas ideas, las resumo aquí en pocas palabras para no tenerlo en ascuas:

No leer, peligro de susto

Voy a plantear el problema de si podemos dar por intuitivamente cierto (ojo, no como evidentemente cierto, sino como algo demostrable en términos intuitivos) que el el ordinal \( \epsilon_0 \) está bien ordenado, cuando éste se define convenientemente a partir de los números naturales a través del hecho de que todo ordinal menor que \( \epsilon_0 \) está determinado por un número finito de ordinales menores por su forma normal de Cantor.

Pero si algún infractor del aviso no ha entendido nada de lo anterior, no debe preocuparse por ello. No voy a hablar ni de teoría de conjuntos, ni de "forma normal de Cantor", ni siquiera de lógica matemática. Sólo de la aritmética de los números naturales, y no voy a necesitar nada más que las propiedades elementales de la suma, el producto, etc. de números naturales.

[cerrar]

Sin tecnicismos, lo que voy a hacer es definir una afirmación sobre números naturales (lo cual requiere introducir algunos conceptos y demostrar algunos hechos previos) y plantear la pregunta: ¿podemos afirmar que esto es verdad?

Superficialmente, la afirmación en cuestión se parece a la conjetura de Collatz. La recuerdo por si alguien no la conoce:

La conjetura de Collatz

Partimos de un número natural arbitrario \( x_0 \) y definimos una sucesión recurrentemente mediante:

\( x_{n+1}=\begin{cases}{x_n/2}&\text{si}& n \text{ es par,}\\ 3x_n+1 & \text{si}& n \text{ es impar.}\end{cases} \)

La conjetura de Collatz afirma que toda sucesión construida de este modo llega al 1 tras un número finito de pasos, pero nadie ha conseguido demostrarlo hasta ahora.

[cerrar]

Concretamente, vamos a definir una clase de sucesiones de números naturales que, de momento, podemos llamar "de tipo S", y la afirmación en cuestión, que podemos llamar BO, es que todas las sucesiones de tipo S acaban llegando al 0.

Por ejemplo, ésta es una sucesión de tipo S:

29, 37, 4, 7, 17, 31, 8, 2, 6, 3, 1, 0.

Pero hay una diferencia sustancial entre la conjetura de Collatz y la afirmación BO, y es que, mientras no se conoce ninguna demostración de la primera, es relativamente fácil probar BO en la teoría de conjuntos ZF (la prueba requiere algunos resultados sobre ordinales, en especial el teorema de la forma normal de Cantor, pero aquí no vamos a hablar de nada de eso). Sin embargo, hay una razón por la cual el hecho de que BO sea demostrable en ZF no hace que deje de tener interés la pregunta de si BO es o no verdadera. Normalmente, la diferencia entre "X es verdad" y "X es demostrable en ZF" es despreciable para un formalista, no sin parte de razón, pero en este caso no es así. Veamos por qué:

Una de las consecuencias de los teoremas de incompletitud de Gödel es que, si una teoría de conjuntos como ZF es consistente, es imposible demostrar que lo es. Esto es algo que los formalistas saben y tienen asumido: pueden decir "para mí la matemática seria no es más que demostrar teoremas en ZFC" o, un poco más en general: "si me demuestras algo, dime cuáles son tus axiomas y yo comprobaré que lo que dices se deduce lógicamente de ellos y, si es así, te diré que está bien, sin cuestionarte tus axiomas, y sin cuestionarme si son consistentes o no (porque sé que es inútil intentarlo)".

Pero, sabiendo que no es posible probar la consistencia de ZF, un formalista debería admitir que es natural plantearse si es posible demostrar la consistencia de otras teorías axiomáticas más débiles, y un buen candidato a conejillo de indias es la aritmética de Peano (AP).

La aritmética de Peano

Aunque en este hilo no vamos a hablar para nada de axiomas ni de tecnicismos lógicos, recuerdo lo que es AP como parte de estos comentarios marginales para entender el valor de la afirmación BO:

La aritmética de Peano es la teoría axiomática que consta de estos axiomas:

• \( \forall x\ x' \neq 0 \)   (El 0 no es el siguiente de ningún número natural.)
• \( \forall xy (x' = y'\rightarrow x = y) \)   (Si dos números naturales tienen el mismo siguiente, son iguales).
• \( \forall x\ x+0 = x \)
• \( \forall xy (x+y' = (x+y)') \)  (Definición recurrente de la suma)
• \( \forall x\ x\cdot 0 = 0 \)
• \( \forall xy(x\cdot y' = x\cdot y +x) \) (Definición recurrente del producto)
• \( P(0)\land \forall x(P(x)\rightarrow P(x'))\rightarrow \forall x\ P(x) \) (Principio de inducción)

En ellos hay que entender que todas las variables hacen referencia exclusivamente a números naturales.

[cerrar]

Pues bien, alguien para quien no suponga ningún trauma reconocer que los números naturales son "algo concreto" de lo que podemos hablar intuitivamente sabiendo lo que decimos, dirá que AP es obviamente consistente, porque los axiomas de Peano son verdaderos cuando se interpretan como afirmaciones sobre los números naturales, y las leyes de la lógica están diseñadas para que, cuando partimos de premisas verdaderas, llegamos necesariamente a conclusiones verdaderas, luego todos los teoremas que podemos deducir de los axiomas de Peano tienen que ser afirmaciones verdaderas sobre los números naturales, y por consiguiente es imposible demostrar cosas como que \( 0\neq 0 \) a partir de los axiomas de Peano, porque eso es falso, y si AP fuera contradictorio, se podría demostrar cualquier cosa a partir de sus axiomas, incluso \( 0\neq 0 \).

Un formalista radical, que considere que son los axiomas de Peano los que definen los números naturales y no los números naturales los que nos llevan a elegir los axiomas de Peano de forma que sean verdaderos, dirá que ese razonamiento es circular o, pasando al contraataque, dirá que si yo puedo decir que AP es consistente porque los números naturales satisfacen sus axiomas, él puede decir que ZF es consistente porque los conjuntos satisfacen sus axiomas, y entonces acabamos en la clásica palestra sobre si los números naturales tienen un sentido intuitivo objetivo mientras que los "conjuntos" no lo tienen, y de ahí no se sale filosofando.

Pues bien, en 1936, Gehrard Gentzen presentó una prueba de la consistencia de AP que era "casi" absolutamente finitista, en el sentido siguiente: Gentzen probó que es posible programar un ordenador de forma que si le damos como input la prueba de una contradicción en AP, el ordenador nos genera una sucesión de tipo S que, por más que se prolongue, nunca llegará a 0.

Obviamente, Gentzen no hablaba de ordenadores, pero lo he expresado así para enfatizar que es totalmente constructiva: igual que analizando un programa podemos concluir que genera la sucesión de los números primos, analizando el programa que Gentzen podría haber programado podemos concluir que genera una sucesión de tipo S que no llega nunca a 0, siempre y cuando le hayamos proporcionado una prueba de una contradicción en AP.

Por lo tanto, si podemos asegurar BO, es decir, que es imposible que una sucesión de tipo S se prolongue indefinidamente sin llegar al 0, podemos asegurar que AP es consistente.

La prueba de Gentzen es muy técnica, requiere saber bastante teoría de la demostración y, personalmente (después de haberla estudiado con detalle), me atrevería a decir que es bastante aburrida, pues obliga a distinguir casos y más casos. Pero no vamos a hablar de ella aquí. Lo que nos interesa es su hipótesis BO.

No creo descabellado afirmar que esta prueba de Gentzen no convence a nadie, pero no porque no sea concluyente, sino porque cualquiera que esté dispuesto a reconocer que es concluyente también reconocerá de antemano que AP es consistente (porque sus axiomas los cumplen los números naturales), por lo que la prueba de Gentzen demuestra (rigurosamente) lo que uno ya sabe. No obstante, tiene el interés técnico de que es "casi" finitista (el "casi" es porque requiere convencerse de que BO es cierta) y además puede ser interesante para un formalista que —quiero pensar— no objetará nada a la parte finitista de la prueba —la posibilidad de programar un ordenador como he dicho— y así puede concentrarse en algo mucho más concreto como si realmente podemos afirmar BO.

Con esto ya podemos entender la peculiaridad sobre lo que podemos exigir a una demostración de BO. Si nuestro propósito es convencernos de que AP es consistente probando BO, el hecho de que BO es demostrable en ZF no nos aporta nada.

En general, si demostramos que \( 2+2=4 \) en ZF, no hemos probado realmente que \( 2+2=4 \). Sólo hemos demostrado que si ZF es consistente entonces \( 2+2=4 \), porque si ZF fuera contradictorio podríamos demostrar también que \( 2+2=372 \), luego una prueba en ZF no nos garantizaría nada. Normalmente un formalista radical no le presta atención a este detalle y, dado que está dispuesto a trabajar en ZF y a suponer que es consistente para que tenga sentido su trabajo, y dado que necesita ZFC para probar cosas como el teorema de Alaoglu-Bourbaki (por decir algo), pues, de perdidos al río, lo aceptamos para todo, incluso para probar que \( 2+2=4 \). Bien, se podría objetar alguna cosa, pero eso nos llevaría a las eternas discusiones filosóficas. Pero el caso es que en el caso concreto de BO ese planteamiento es inadmisible:

Si un formalista concede que, dado que no es posible probar la consistencia de ZF, es razonable investigar si podemos probar la consistencia de AP (y que ésta se reduce a probar BO), tiene que reconocer que es ridículo afirmar que AP es consistente por el hecho de que BO es demostrable en ZF, porque con ello sólo está probando que si ZF es consistente, también lo es AP, ¡pero eso es trivial!  Como en ZF se pueden demostrar los axiomas de Peano, si se pudiera probar alguna contradicción a partir de ellos, también podríamos probar esa misma contradicción en ZF: primero probamos los axiomas de Peano en ZF, y prolongamos la demostración hasta llegar a la contradicción que se deduce de estos.

Así pues, lo que tiene interés no es la trivialidad de que AP es consistente si lo es ZF, sino llegar a convencernos de que AP es consistente sin apoyarnos en la consistencia indemostrable de ZF. Gentzen dio un argumento absolutamente hipermegafinitista que ningún formalista debería objetar en virtud del cual todo se reduce a probar BO, pero si acabamos probando BO en ZF ¡estamos haciendo el tonto!

Por ello tiene sentido plantearse: vale, de los axiomas de ZF se deduce BO, pero, si no nos fiamos de los axiomas de ZF (no por vicio, sino porque aspiramos a probar la consistencia de AP y sería absurdo apoyarnos en algo más fuerte que lo que queremos probar) ¿podemos asegurar que BO es verdad? ¿Podemos asegurar que es inconcebible que exista un criterio que permita construir una sucesión de tipo S que nunca llegue al 0?

No se trata de dar un argumento para que venga un formalista y diga: a ver, en tu prueba estás suponiendo tales y tales axiomas. Suponiendo eso, la conclusión es correcta. Se trata de probar que no hay sucesiones de tipo S que no llegan al 0 si se prolongan lo suficiente sin fiar la conclusión a que tales o cuales axiomas sean ciertos o no. Se trata de demostrarlo a partir de hechos cuya certeza sea indudable. Se trata de convencerse de que es así, que no puede ser que exista una sucesión de tipo S que no llega al 0 igual que no puede ser que dos números naturales den una suma distinta según en qué orden se sumen.

Y si el formalista llega y dice: "pues tu prueba de BO se parece a una prueba en ZF como se parecen dos gotas de agua", en este contexto podemos decirle claramente que el parecido es irrelevante. Sí, la prueba tal cual se podrá formalizar en ZF, pero eso es ridículo, porque para demostrar así BO en ZF hay argumentos mucho más simples y directos (usando ordinales y la forma normal de Cantor). Independientemente de que la prueba se pueda formalizar en ZF, su interés reside en que pueda darse por válida sin interpretarla como una prueba en ZF, no porque sus afirmaciones se deducen lógicamente de teoremas de ZF, sino porque cada cosa que se dice es verdad, se pruebe o no en ZF. En este caso la diferencia es crucial. No importa si la prueba tiene una hermana gemela en ZF, importa que puede respirar fuera de ZF.

Nota: Tiene cierta importancia "filosófica" observar que la prueba de Gentzen no sólo afirma que si AP fuera contradictoria habría una sucesión de tipo S que nunca llegaría al 0, sino que dicha sucesión sería recursiva, es decir, calculable explícitamente por un ordenador.

Gentzen no dijo mucho sobre cómo justificar BO (entre otras cosas porque los nazis lo mataron a los 35 años), pero, al discutir su prueba de consistencia, analizando BO vino a decir que era claro que tenía que ser cierta por una serie de observaciones que, en esencia, contenían un "y así sucesivamente" un tanto cuestionable.

De hecho, Gödel lo cuestionó abiertamente y afirmó que, al margen de que podemos dar por hecho que BO es cierta igual que lo damos por hecho de cualquier teorema de ZF, prescindiendo de ello, no veía como algo intuitivamente justificado que BO tuviera que ser cierta, que la afirmación era demasiado compleja para que se pudiera dar por cierta a la ligera.

Más adelante, un matemático japonés, Gaisi Takeuti (que había estudiado con Gödel) presentó una prueba que ha dado mucho que hablar sobre si es intuitivamente aceptable o no (él mismo debatió mucho con Gödel acerca de su demostración). Nuevamente, la prueba de Takeuti no hace sino razonar sobre números naturales (no tiene nada que ver con la lógica ni con la teoría de conjuntos), eso sí, definiendo unos conceptos "sospechosamente abstractos". Según decía un profesor mío, es una de esas pruebas que les gustan a los lógicos que un día te levantas y la ves concluyente y otro día te parece que no vale.

En principio mi intención en este hilo es exponer lo necesario para definir BO y el argumento de Takeuti sin hacer referencia a nada que no sea aritmética pura y básica, por una parte para desenterrarlos de los libros de Teoría de la demostración y que estén accesibles para quien quiera interesarse por esto sin necesidad de digerir libros un tanto técnicos y, también, naturalmente, por si algún usuario del foro quiere seguir el desarrollo y plantear cualquier clase de duda u observación.

Justo ahora no dispongo de mucho tiempo, pero iré añadiendo mensajes a este hilo poco a poco. Cualquier comentario o participación será bienvenida, naturalmente, pero si nadie tiene ahora tiempo o interés, iré publicando igualmente para cualquier lector potencial presente o futuro, que alguno habrá por el mundo.

Para cualquier observación, pregunta o comentario sobre este hilo usar mejor el hilo Comentarios a "Ordinales menores que \(\epsilon_0\)

[Carlos Ivorra]

Es bien conocido que \( \mathbb N\times \mathbb N \) es biyectable con \( \mathbb N \), y que una biyección explícita viene dada por una de las dos cosas distintas que se llaman "método diagonal de Cantor" (la otra es la que prueba la no numerabilidad de \( \mathbb R \)):

\( \begin{array}{lllll}
\vdots\\
(0,4)\rightarrow 10\\
(0,3)\rightarrow 6&(1,3)\rightarrow 11\\
(0,2)\rightarrow 3&(1,2)\rightarrow 7&(2,2)\rightarrow 12\\
(0,1)\rightarrow 1&(1,1)\rightarrow 4&(2,1)\rightarrow 8&(3,1)\rightarrow 13\\
(0, 0)\rightarrow 0&(1,0)\rightarrow 2&(2,0)\rightarrow 5&(3,0)\rightarrow 9&(4,0)\rightarrow 14\ldots
\end{array} \)

Lo que no es tan conocido es que esta biyección \( \mathbb N\times \mathbb N\longrightarrow \mathbb N \) se puede expresar con fórmulas aritméticas. Por ejemplo, para calcular el número que corresponde al par \( (3, 1) \) vemos que, para llegar hasta él contando como muestra la figura, primero hemos de recorrer la diagonal formada por los números que cumplen \( x+y=0 \), que sólo tiene \( 1 \) par (el \( (0,0) \)), luego la diagonal formada por los números que cumplen \( x+y = 1 \), que tiene \( 2 \) pares, luego la diagonal de los números que cumplen \( x+y=2 \), que tiene \( 3 \) pares, y así, tenemos que contar en total

\( 1+2+3+4=10 \)

pares antes de entrar en la diagonal \( x+y=4 \), que es la que contiene a nuestro par \( (x, y) = (3, 1) \). En general, antes de llegar a la diagonal de los pares que suman \( x+y \) hemos de recorrer \( x+y \) diagonales, con lo que habremos contado hasta

\( 1+2+3+\cdots +(x+y) =  \dfrac{(x+y)(x+y+1)}2 \)

Volviendo a nuestro ejemplo concreto, como empezamos a contar en el 0, para contar \( 10 \) pares empleamos los números del 0 al 9, por lo que el par número 10 es el primero de la diagonal \( x+y=4 \). En general, el par \( (x+y)(x+y+1)/2 \) es el primero de la diagonal de los pares cuyas coordenadas suman \( x+y \), es decir, ese número corresponde al par \( (0, x+y) \). Para llegar al par \( (x, y) \) tenemos que avanzar \( x \) posiciones más, luego el par \( (x,y) \) recibe el número

\( \left<x, y\right>_2 = \dfrac{(x+y)(x+y+1)}2+x \).

Por ejemplo, \( \left<3, 1\right>_2 =\dfrac{4\cdot 5}2+3= 13 \), como muestra la figura.

Así pues, la correspondencia

\( (x, y)\mapsto\left<x, y\right>_2 = \dfrac{(x+y)(x+y+1)}2+x  \)

determina una biyección entre los pares de números naturales y los números naturales. Llamaremos \( p_2(z)=(x, y) \) a la biyección inversa.

Para calcular explícitamente \( p_2 \) observamos que si \( z = \left<x, y\right>_2 \), entonces

\( \dfrac{(x+y)(x+y+1)}2\leq z<\dfrac{(x+y+1)(x+y+2)}2 \),

pues el término de la derecha es el número que corresponde al primer par de la diagonal siguiente, la de los pares cuyas coordenadas suman \( x+y+1 \), luego

\( (x+y)^2\leq (x+y)(x+y+1)\leq 2z< (x+y+1)(x+y+2)\leq (x+y+2)^2 \),

luego

\( x+y\leq \sqrt{2z}<x+y+2 \).

Esto nos deja sólo dos posibilidades para \( x+y \), que tiene que ser \( n=E[\sqrt{2z}] \) o bien \( n=E[\sqrt{2z}]-1 \). Sólo hay que ver cuál de estos dos números cumple

\( \dfrac{n(n+1)}2\leq  z<\dfrac{(n+1)(n+2)}2 \)

y entonces

(*)   \( x = z-\dfrac{n(n+1)}2 \),     \( y = n-x \).

Conviene observar que \( x+y = n \leq 1+2+\cdots + n = n(n+1)/2\leq \left<x, y\right>_2 \). Así pues, se cumple

\( x, y \leq\left<x, y\right>_2 \).

Si el lector está familiarizado con algún lenguaje de programación o con alguna aplicación de cálculo simbólico, sería interesante que programara estas funciones para jugar con los conceptos que vamos a ir definiendo (todos ellos computables). Por ejemplo, yo he programado así estas funciones en Python:

Código: [Seleccionar]

def isqrt(n):
    """Parte entera de la raíz cuadrada de un entero"""
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def par(x,y):
    """Par ordenado de dos números naturales"""
    u = (x+y) * (x+y+1) // 2 + x
    return u

def p2(z):
    """Coordenadas de z visto como par ordenado"""
    zz = 2*z
    n = isqrt(zz)
    while n * (n+1) > zz:
        n -= 1
    u= z - n * (n+1) // 2
    v = n-u
    return (u,v)
La primera función me la he copiado de internet, y sirve para calcular la parte entera de la raíz cuadrada de un número entero. La segunda es obvia. La tercera calcula \( n=E(\sqrt{2z}) \) y va restando 1 a \( n \) hasta que \( n(n+1)\leq 2z \). Entonces \( n = x+y \) y podemos aplicar (*) para calcular \( x, y \).

Nota: Disto mucho de ser un experto en Phyton, así que cualquier mejora a los programas que ponga será bien recibida.

De este modo tenemos un criterio explícito para asociar biunívocamente a cada número natural \( z \) un par de números naturales \( (x, y) \) y viceversa. Desde un punto de vista psicológico conviene pensar más bien que cada número natural \( z \) tiene dos coordenadas asociadas \( z_1, z_2 \), es decir, que, por ejemplo, el número natural \( 230\,054 \) es o se descompone en el par \( (551, 126) \), exactamente igual que decimos que se descompone en el producto de primos  \( 230\,054 = 2\cdot 11\cdot 10\,457 \).

[Carlos Ivorra]

En el mensaje anterior hemos visto que cada número natural \( n \) está determinado por dos coordenadas, de modo que dos números son iguales si y sólo si lo son sus coordenadas, sy todo par de números son las coordenadas de un (único) número. Ahora bien, también podemos descomponer cada número en ternas de coordenadas si definimos

\( \left<x, y, z\right>_3 = \left<\left<x, y\right>_2,z\right>_2 \)

La aplicación \( (x, y, z) \mapsto \left<x, y, z\right>_3 \) biyecta las ternas ordenadas de números naturales con los números naturales.

Por ejemplo: \( \left<3, 5, 0\right>_3 = \left<\left<3, 5\right>_2, 0\right>_2 = \left<39,0\right>_2=819 \).

Recíprocamente, si partimos de \( 819 \), podemos calcular \( p_2(819)= (39, 0) \) y, a su vez, \( p_2(39)= (3, 5) \), con lo que obtenemos la descomposición \( 389 = \left<3, 5, 0\right>_3 \).

La tabla siguiente contiene la descomposición en ternas de los primeros números naturales:

\( \begin{array}{cccccccccc}
0&1&2&3&4&5&6&7&8&9\\
(0, 0, 0)&(0, 0, 1)&(0, 1, 0)&(0, 0, 2)&(0, 1, 1)&(1, 0, 0)&(0, 0, 3)&(0, 1, 2)&(1, 0, 1)&(0, 2, 0)
\end{array} \)

Más en general, si definimos \( \left<x\right>_1 = x \) y \( \left<x, y\right>_2 \) la aplicación que hemos estudiado en el mensaje anterior, podemos definir \( n \)-tuplas de cualquier longitud:

\( \left<x_1, x_2, x_3\right>_3 = \left<\left<x_1, x_2\right>_2,x_3\right>_2 \),   \( \left<x_1, x_2, x_3, x_4\right>_4 = \left<\left<x_1, x_2, x_3\right>_3, x_4\right>_2 \),    \( \left<x_1, x_2, x_3, x_4, x_5\right>_5 = \left<\left<x_1, x_2, x_3, x_4\right>_4, x_5\right>_2 \), etc.

y de este modo podemos determinar cada número natural por una única coordenada (él mismo) o por dos coordenadas, o por tres, etc. Más precisamente, tenemos biyecciones que a cada \( n \)-tupla de números naturales le asignan un número natural, y podemos considerar sus inversas: \( p_n:\mathbb N\longrightarrow \mathbb N^n \).

He aquí una implementación en Python:

Código: [Seleccionar]

def tupla(*l):
    """tupla de una sucesión"""
    long = len(l)
    if long == 1:
        u = l[0]
    else:
        u = par(tupla(*l[:long-1]),l[long-1])
    return u

def pn(n,z):
    """"Coordenadas de z visto como n-tupla"""
    u=[]
    for i in range(0,n-1):
        p = p2(z)
        u.append(p[1])
        z = p[0]
    u.append(z)
    u.reverse()
    u = tuple(u)
    return u
La primera función calcula recursivamente \( \text{tupla}(x_1,\ldots, x_l) =\text{par}(\text{tupla}(x_1, \ldots, x_{l-1}), x_l) \), mientras que la segunda parte de un número \( z \) y va descomponiendo: \( z = \left<z', x\right> \), va añadiendo los valores  \( x \) en una lista \( u \) y pasa a hacer lo mismo con \( z' \), así \( n-1 \) veces, hasta que finalmente añade a la lista \( u \) el último valor \( z \) obtenido, con lo que \( u \) es la \( n \)-tupla asociada a \( z \) salvo que está ordenada al revés, así que hay que darle la vuelta antes de devolver el resultado. (Insisto en que cualquier idea para hacer los algoritmos más eficientes será bienvenida.)

Así, un mismo número natural puede descomponerse —de forma única— en un par, en una terna, en una cuádrupla, etc. Por ejemplo, las descomposiciones del número \( 123\,456\,789 \) son:

\( (123456789),\  (15461, 251),\  (61, 114, 251), \ (6, 4, 114, 251), \ (0, 3, 4, 114, 251),\ (0, 0, 3, 4, 114, 251)\ldots \)

Pero necesitamos refinar estas técnicas para que cada número natural se identifique con una única descomposición de una longitud determinada, es decir, no queremos que el par \( (15461, 251) \) y la terna \( (61, 114, 251) \) se tengan que identificar con un mismo número natural. Más precisamente, vamos a definir una biyección \( s\mapsto \left<s\right>_\infty \) que a cada sucesión finita de números naturales (de cualquier longitud) le asigne un único número natural. La definición es sencilla, pero hay un tecnicismo en ella para hacerle un hueco a la sucesión vacía de longitud \( 0 \), para la que será \( \left<\ \right>_\infty = 0 \).

La definición es:

\( \left<x_1, \ldots, x_n\right>_\infty=\begin{cases}{0}&\text{si}& n=0,\\ \left<n-1,\left<x_1,\ldots, x_n\right>_n\right>_2+1 & \text{si}& n>0.\end{cases} \)

De este modo, a la única sucesión vacía (de longitud \( n=0 \)) le asignamos el número \( 0 \), mientras que a una sucesión no vacía, como \( (3, 0, 4, 4) \), de longitud \( 4 \) le asignamos el par:

\( \left<3, 0, 4, 4\right>_\infty = \left<3,\left<3, 0, 4, 4\right>_4\right>_2+1 = \left<3, 5\,560\right>_2 +1= 15\,476\,269+1 = 15\,476\,270. \)

Así, cada número natural se descompone de forma única en una sucesión finita de números naturales. Por ejemplo, si nos dan el \( 15\,476\,270 \), como no es \( 0 \) ya sabemos que se corresponde con una sucesión no vacía, le restamos \( 1 \) y descomponemos:

\( 15\,476\,270-1 = \left<3, 5\,560\right>_2 \),

y la primera coordenada nos dice que la sucesión que buscamos tiene longitud \( 3+1=4 \). Entonces reinterpretamos la segunda coordenada como \( 5\,560 = \left<3, 0, 4, 4\right>_4 \) y ya tenemos la sucesión buscada. He aquí dos funciones en Python para calcular esta función y su inversa, así como la longitud de la sucesión codificada por un número:

Código: [Seleccionar]

def s(*l):
    """Número correspondiente a una sucesión dada"""
    if l == ():
        u = 0
    else:
        u = par(len(l) - 1,tupla(*l)) + 1
    return(u)

def long(s):
    """Longitud de una sucesión"""
    if s == 0:
        u = 0
    else:
        u = p2(s-1)[0]+1
    return(u)

def term(s):
    """Términos de un número"""
    if s == 0:
        u = ()
    else:
        z = p2(s-1)
        u = pn(z[0] + 1,z[1])
    return u
La función s implementa de forma obvia la función \( \left<s\right>_\infty \), la función long(s) distingue si \( s = 0 \), en cuyo caso codifica la sucesión vacía de longitud \( 0 \), o si \( s>0 \), en cuyo caso la longitud de la sucesión que codifica se obtiene sumando 1 a la primera coordenada de \( s-1 \) visto como par. Finalmente, la función term, tras distinguir el caso \( s=0 \), descompone \( s-1 = \left<z_0, z_1\right>_2 \) y luego descompone \( z_1 \) en sucesión de longitud \( z_0+1 \).

Con esto hemos conseguido nuestro primer objetivo: probar que cada número natural puede descomponerse de forma única en una sucesión finita de números naturales. Por ejemplo, \( \left<0, 1, 2, 3, 4, 5\right>_\infty = 3\,374\,956\,582\,776 \). La tabla siguiente muestra las primeras descomposiciones:

\( \begin{array}{cccccccccc}
0&1&2&3&4&5&6&7&8&9\\
()&(0)&(1)&(0, 0)&(2)&(0, 1)&(0, 0, 0)&(3)&(1, 0)&(0, 0, 1)\\
\hline
10&11&12&13&14&15&16&17&18&19\\
(0, 0, 0, 0)&(4)&(0, 2)&(0, 1, 0)&(0, 0, 0, 1)&(0, 0, 0, 0, 0)&(5)&(1, 1)&(0, 0, 2)&(0, 0, 1, 0)\\
\hline
20&21&22&23&24&25&26&27&28&29\\
(0, 0, 0, 0, 1)&(0, 0, 0, 0, 0, 0)&(6)&(2, 0)&(0, 1, 1)&(0, 0, 0, 2)&(0, 0, 0, 1, 0)&(0, 0, 0, 0, 0, 1)&(0, 0, 0, 0, 0, 0, 0)&(7)\\
\hline
\end{array} \)

En lo sucesivo usaremos únicamente las funciones \( \left<x, y\right>_2 \), \( \left<x_1, \ldots, x_n\right>_\infty \) y sus inversas.

En el mensaje anterior hemos probado que \( x, y \leq \left<x, y\right>_2 \), de donde se sigue fácilmente que \( x_i \leq \left<x_1, \ldots, x_n\right>_n \), de donde a su vez,

\( x_i \leq \left<n-1, \left<x_1, \ldots, x_n\right>_n\right>_2<\left<x_1,\ldots, x_n\right>_\infty \).

El lector debería asimilar todo esto hasta que vea natural que digamos, por ejemplo, que \( 28 \) tiene longitud \( 7 \), mientras que \( 29 \) tiene longitud \( 1 \). Así, esta sucesión, que en otro contexto parecería bastante vulgar y caprichosa:

\( 0, \quad 1, \quad 3, \quad 6, \quad 10, \quad 15, \quad 21, \quad 28, \quad 36, \quad 45, \quad 55\ldots \)

aquí resulta bastante natural.

Si algún lector está dispuesto a seguir este hilo programando, se puede plantear cómo determinar si un número natural extiende a otro (en el sentido de que la sucesión que determina extiende a la del otro), como 24, que extiende a 5, y, en caso negativo, cómo determinar el primer término en el que ambos difieren.

[Carlos Ivorra]

Ya podemos entrar en el meollo de este hilo. Vamos a definir una relación \( \preceq \) en un subconjunto \( E \) de \( \mathbb N \) que, como el nombre sugiere, será una relación de orden, pero eso lo probaremos más tarde. La definiremos recurrentemente, definiendo conjuntos finitos \( R_n \), de modo que \( R_n \) será el conjunto de todos los números naturales \( z \) que, vistos como pares \( z=\left<x, y\right>_2 \) con \( x, y\leq n \), cumplen \( x\preceq y \).

La relación en \( E \) será reflexiva, de modo que un número natural \( n \) estará en \( E \) si y sólo si el par \( \left<n, n\right>_2 \) está en \( R_n \) (es decir, si y sólo si \( n\preceq n \)).

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\} \).

Copio aquí (desde el hilo de comentarios) dos exposiciones alternativas de esta misma construcción que Eparoh y argentinator han considerado preferibles para sí mismos, por si a alguien más le resultan esclarecedoras:

 Versión de Eparoh

• Definimos \( R_0=\{0\} \).
• De forma recursiva se define \( R_{n+1} \) siguiendo estos pasos:
  
  • Expresamos \( n+1=\langle s_1, \cdots, s_l \rangle_\infty \) (donde cada \( s_i \leq n \)) y comprobamos si se cumplen:
    
    • \( \langle s_i, s_i \rangle_2 \in R_{\color{blue} n} \) para cada \( i=1, \cdots, l \)
    • \( \langle s_{i+1}, s_i \rangle_2 \in R_{\color{blue} n} \) para cada \( i=1, \cdots, l-1 \)
  • Si no se cumplen los dos puntos anteriores, entonces \( R_{n+1}=R_n \).
  • En caso contrario, definimos \( R_{n+1} \) como el conjunto de naturales que resulta de añadir a \( R_n \) los siguientes números:
    
    • \( \langle n+1, n+1 \rangle_2 \)
    • Para cada \( x \leq n \):
      
      • Si \( \color{blue} \langle x, x \rangle_2 \not \in R_n \), entonces no añadimos ni \( \langle n+1, x \rangle_2 \) ni \( \langle x, n+1 \rangle_2 \).
      • En caso contrario expresamos \( x=\langle t_1, \cdots, t_r \rangle_\infty \) (donde cada \( t_i <x \leq n \)) y comprobamos:
        
        • Si \( x \) extiende a \( n+1 \), añadimos \( \langle n+1, x \rangle_2 \)
        • Si \( n+1 \) extiende a \( x \), añadimos \( \langle x, n+1 \rangle_2 \)
        • Si no se da ninguno de los casos anteriores y es \( i \) el menor índice para el cual es \( s_i \not = t_i \), entonces:
          
          • Si \( \langle s_i, t_i \rangle_2 \in R_{\color{blue} n} \), añadimos \( \langle n+1, x \rangle_2 \)
          • Si \( \langle t_i, s_i \rangle_2 \in R_{\color{blue} n} \), añadimos \( \langle x, n+1 \rangle_2 \)

Tras esta gran recursión, dados dos naturales \( x, y \) definimos la relación

\( x \preceq y \longleftrightarrow \langle x, y \rangle_2 \in R_{\max\{x,y\}} \)

y el conjunto \( E \) formado por todos los naturales \( n \) que cumplen que \( \langle n, n \rangle_2 \in R_n \).

[cerrar]

Versión de argentinator

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\).

[cerrar]

De esta construcción se siguen algunas consecuencias sencillas. Dejo los detalles como ejercicio para el lector, porque demostrarlas es una buena forma de familiarizarse con la definición:

• \( n\in E \) si y sólo si \( n\preceq n \) (por definición de \( E \)).
• Si \( x\preceq y \), entonces \( x, y\in E \).
  
  Por inducción sobre \( n=\max\{x, y\} \). Para \( n=0 \) es trivial y, si vale para \( n \), la construcción muestra que vale para \( n+1 \).
  
  
• \( n\in E \) si y sólo si es una sucesión decreciente de elementos de \( E \).
  
  En efecto, esto vale trivialmente para \( 0 \) (que es la sucesión vacía, luego sus términos inexistentes están todos en \( E \)) y, si vale para números \( x\leq n \), también vale para \( n+1 \) por la construcción.
  
  
• Si \( x, y\in E \), o bien \( x\preceq y \), o bien \( y\preceq x \)
  
  Por inducción sobre \( n = \max\{x, y\} \), pues para \( n=0 \) es trivial y, si vale para \( n \), no perdemos generalidad si suponemos que \( y = n+1 \), y entonces, por construcción, si una sucesión prolonga a la otra, se cumple \( x\preceq n+1 \) o bien \( n+1\preceq x \), y en caso contrario ambas tienen que diferir en un primer término \( i \). Por hipótesis de inducción se cumple \( s_i\preceq t_i \) o bien \( t_i\preceq s_i \) y, por construcción, esto implica que \( x\preceq n+1 \) o bien \( n+1\preceq x \).
  
  
• Si \( x\preceq y, y\preceq x \), entonces \( x=y \).
  
  Similar al caso anterior.
  
  
• Si \( x\preceq y\preceq z \), entonces \( x\preceq z \).
  
  Ésta la dejo entera como ejercicio.

Acabamos de definir una joya de la metamatemática. A los elementos de \( E \) los llamaremos ordinales (deberíamos decir "ordinales menores que \( \epsilon_0 \)", pero resulta un poco largo), y lo que hemos probado es que los ordinales son un conjunto de números naturales en los que tenemos definida una relación de orden total \( \preceq \), que no hay que confundir con el orden usual \( \leq \) definido sobre todos los números naturales. Además:

• Un número natural es un ordinal si y sólo si es una sucesión decreciente de ordinales.
• Dos ordinales cumplen \( x\preceq y \) si y sólo si, vistos como sucesiones de ordinales,
  
  
  \( x= \left<s_1,\ldots, s_l\right>_\infty \),  \( y= \left<t_1,\ldots, t_r\right>_\infty \)
  
  se cumple que \( x \) se extiende hasta \( y \) (Aclaro: si \( y = \left<s_1,\ldots, s_l, t_{l+1},\ldots, t_r\right>_\infty \)) o bien ambas sucesiones difieren en un mínimo índice \( i \) tal que \( s_i\preceq t_i \).
  

Estas dos últimas afirmaciones parecen circulares, pero toda la construcción técnica precedente sirve para justificar que no hay circularidad, sino recurrencia.

En este punto, lo más saludable que puede hacer un lector que quiera seguir el hilo es programarse estas definiciones y jugar con los ordinales a ver si conjetura algunas cosas básicas sobre su ordenación. En los mensajes siguientes la estudiaremos con detalle. Pongo aquí mis programas en Python:

Para que no haga falta repetir una y otra vez los mismos cálculos recurrentes, he creado unas variables globales que guarden el máximo \( n \) para el que hemos calculado \( R_n \) así como el conjunto \( R_n \) y el conjunto de los ordinales menores o iguales que \( n \).

Código: [Seleccionar]

pares ={0}          #Tupla de pares de ordinales crecientes calculados
ordinales = [0]     #Lista de ordinales calculados
puntero = 0         #Máximo número natural que hemos visto si es un ordinal

def calcula(n):
    """Calcula la relación de orden entre ordinales hasta
    los pares de coordenadas menores o iguales que n"""
    global puntero, ordinales, pares
    while puntero < n:
        puntero += 1
        s = term(puntero)
        ls = len(s)
        i = 0
        while i < ls-1 and par(s[i+1],s[i]) in pares:
                i += 1
#Aquí hemos comprobado que la sucesión s es decreciente hasta i.
#Si i = sl-1, es que es toda decreciente, pero comprobamos
#que su último término s[ls-1] sea tambien un ordinal por si la
#longitud es 1 y no se ha comparado ningún par.
        if i == ls-1 and s[i] in ordinales:
            pares.add(par(puntero,puntero))
            ordinales.append(puntero)
#Ahora comparamos puntero con todos los ordinales menores
            for x in range(0,puntero):
                if x in ordinales:
                    t = term(x)
                    lt = len(t)
                    m = min(ls,lt)
                    j = 0
                    while(j < m and s[j] == t[j]):
                        j += 1
#Aquí j es el menor ordinal en el que s y t difieren, salvo si j = m.
                    if j == m:
                        if ls <= lt:
                            pares.add(par(puntero,x))
#En este caso s se prolonga hasta t.
                        else:
                            pares.add(par(x, puntero))
#En este caso t se prolonga hasta s.
                    else:
                        if par(s[j],t[j]) in pares:
                            pares.add(par(puntero,x))
                        else:
                            pares.add(par(x, puntero))
#Añadimos un par u otro según si el primer término en el que difieren
#es menor en uno o en otro.

def ord(a):
    """Determina si a es un ordinal"""
    calcula(a)
    return (a in ordinales)

def comp(a, b):
    """Determina si a ≤ b como ordinales"""
    calcula(max(a,b))
    return (par(a, b) in pares)
Por ejemplo, si ejecutamos el código:

Código: [Seleccionar]

ord(100)
print(len(ordinales))
print(ordinales)
Veremos que hay \( 30 \) ordinales menores que \( 100 \), que son:

\( 0, 1, 2, 3, 4, 6, 7, 8, 10, 11, 15, 17, 21, 22, 23, 28, 29, 31, 36, 37, 45, 47, 55, 56, 57, 66, 67, 78, 91, 93. \)

Para entender por qué estos números son ordinales y otros no, conviene ordenarlos respecto de orden \( \preceq \), para lo cual he usado un algoritmo copiado de internet (adaptado ligeramente para que use la función "comp" para comparar):

Código: [Seleccionar]

def ordena(array):
    n = len(array)
    for i in range(n):
        # Create a flag that will allow the function to
        # terminate early if there's nothing left to sort
        already_sorted = True
        # Start looking at each item of the list one by one,
        # comparing it with its adjacent value. With each
        # iteration, the portion of the array that you look at
        # shrinks because the remaining items have already been
        # sorted.
        for j in range(n - i - 1):
            #if array[j] > array[j + 1]:
            if (par(array[j + 1], array[j]) in pares) and array[j] != array[j+1]:
                # If the item you're looking at is greater than its
                # adjacent value, then swap them
                array[j], array[j + 1] = array[j + 1], array[j]
                # Since you had to swap two elements,
                # set the `already_sorted` flag to `False` so the
                # algorithm doesn't finish prematurely
                already_sorted = False
        # If there were no swaps during the last iteration,
        # the array is already sorted, and you can terminate
        if already_sorted:
            break
    return array
Si ahora ejecutamos:

Código: [Seleccionar]

ord(100)
ordena(ordinales)
print(len(ordinales))
for a in ordinales:
    print(a, term(a))
obtenemos que los primeros \( 30 \) ordinales (ordenados según \( \preceq \)) son:

\( \begin{array}{|rl|rl|rl|}
\hline
0&()&55&(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)&22&(6)\\
1&(0)&66&(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)&56&(10)\\
3&(0, 0)&78&(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)&4&(2)\\
6&(0, 0, 0)&91&(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)&23&(2, 0)\\
10&(0, 0, 0, 0)&2&(1)&47&(2, 1)\\
15&(0, 0, 0, 0, 0)&8&(1, 0)&93&(2, 2)\\
21&(0, 0, 0, 0, 0, 0)&31&(1, 0, 0)&37&(8)\\
28&(0, 0, 0, 0, 0, 0, 0)&17&(1, 1)&29&(7)\\
36&(0, 0, 0, 0, 0, 0, 0, 0)&7&(3)&11&(4)\\
45&(0, 0, 0, 0, 0, 0, 0, 0, 0)&57&(3, 0)&67&(11)\\
\hline
\end{array} \)

Por ejemplo:

• \( 0 \) es un ordinal porque, al ser la sucesión vacía, es trivialmente una sucesión decreciente de ordinales.
• \( 1 = \left<0\right>_\infty \) es un ordinal porque es una sucesión de ordinales, trivialmente decreciente, ya que tiene longitud 1. Además \( 0\preceq 1 \) porque la sucesión vacía se extiende a cualquier otra sucesión
• \( 2=\left<1\right>_\infty \) es un ordinal por el mismo motivo que \( 1 \) y además \( 1 =(0)\preceq (1)=2 \) porque ambas sucesiones tienen longitud 1, luego difieren en su primer término y \( 0\prec 1 \).
• \( 23 = \left<2, 0\right>_\infty \) y \( 47 = \left<2, 1\right>_\infty \) son ordinales porque son sucesiones decrecientes de ordinales (por los puntos precedentes) y \( 23\preceq 47 \) porque difieren en su segundo término y \( 0\prec 1 \).
• \( 5 = \left<0,1\right>_\infty \) no es un ordinal porque, aunque es una sucesión de ordinales, no es decreciente.
• \( 16 = \left<5\right>_\infty \) no es un ordinal porque no es una sucesión de ordinales.

Conviene señalar que los \( 30 \) ordinales anteriores son los \( 30 \) primeros ordinales respecto del orden usual de los números naturales, pero no son los \( 30 \) primeros ordinales respecto de \( \preceq \). Si calculamos más ordinales, muchos ordinales nuevos tendrán que intercalarse en la sucesión anterior.

Como decíamos, en los mensajes siguientes estudiaremos los ordinales y su relación de orden, pero de momento ya podemos explicar a qué llamábamos sucesiones de tipo S en el primer mensaje y qué dice la afirmación BO. Las sucesiones de tipo S son simplemente las sucesiones decrecientes de ordinales, y BO afirma, pues, que toda sucesión decreciente de ordinales, si se prolonga lo suficiente, llega al \( 0 \).

Dejo aquí algunas cuestiones que el lector puede plantearse como ejercicios y que trataré con detalle en el mensaje siguiente:

• Probar que el \( 0 \) es el mínimo ordinal.
  
  
• Probar que todo ordinal \( \alpha \) tiene un siguiente \( \alpha' \), es decir, que \( \alpha\prec \alpha' \) y que \( \alpha'\preceq \beta \), para todo ordinal \( \beta \succ \alpha \). Concretamente, si \( \alpha = \left<s_1,\ldots, s_l\right>_\infty \), probar que \( \alpha ' =  \left<s_1,\ldots, s_l,0\right>_\infty \) es un ordinal y cumple lo requerido.
  
  De este modo, los menores ordinales son
  
  
  \( 0 = \left<\right>_\infty = 0,\quad 0' = \left<0\right>_\infty = 1, \quad0'' = \left<0, 0\right>_\infty = 3, \quad0''' = \left<0, 0, 0\right>_\infty = 6,\quad \ldots \)
  
  Estos ordinales se llaman ordinales finitos, porque son los que se obtienen del \( 0 \) en un número finito de pasos. Los demás son los ordinales infinitos.
  
  
• Probar que \( \omega = \left<1\right>_\infty = 2 \) es el menor ordinal infinito, es decir, que es mayor que todo ordinal finito y menor o igual que todo ordinal infinito.
  
  Por lo tanto, los menores ordinales son:
  
  
  \( 0 = \left<\right>_\infty = 0,\quad 0' = \left<0\right>_\infty = 1, \quad0'' = \left<0, 0\right>_\infty = 3, \quad \ldots\quad \omega =  \left<1\right>_\infty = 2,\quad \omega' = \left<1,0\right>_\infty =8,\quad \omega'' = \left<1,0, 0\right>_\infty =31,\quad \ldots \)
  
  
• Probar que existe un mínimo ordinal mayor que \( \omega, \omega', \omega'', \ldots \) ¿qué número natural es? (está en la tabla anterior).

[Carlos Ivorra]

En este mensaje veremos cómo expresar los ordinales de forma natural, de modo que a simple vista se vea cuándo un ordinal es mayor o menor que otro (si no son muy complicados). Recordemos lo básico (a partir de aquí omitiré el subíndice \( \infty \) en las expresiones como sucesiones):

• Un ordinal es un número natural \( \alpha = \left<\delta_1,\ldots, \delta_m\right> \) que (como sucesión) es una sucesión decreciente de ordinales: \( \delta_1\succeq \ldots \succeq \delta_m \).
  
  
• Dados dos ordinales \( \alpha = \left<\delta_1,\ldots, \delta_m\right> \),    \( \beta = \left<\epsilon_1, \ldots, \epsilon_n\right> \), se cumple \( \alpha\preceq \beta \) si y sólo si \( \alpha \) se puede prolongar hasta \( \beta \) o si el mínimo índice tal que \( \delta_i\neq \epsilon_i \) cumple, de hecho, que \( \delta_i\preceq \epsilon_i \).

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.

Pero si aceptamos que la definición anterior es correcta, de ella se deducen todas las propiedades de los ordinales. Por ejemplo:

• \( 0 \) es el mínimo ordinal.
  
  Esto se debe a que \( 0 = \left<\right> \) es la sucesión vacía, luego trivialmente es un ordinal y se extiende a cualquier otro, luego \( 0\preceq \alpha \) para todo ordinal \( \alpha \).
  
  
• Todo ordinal \( \alpha = \left<\beta_1,\ldots, \beta_m\right> \) tiene un siguiente, concretamente \( \alpha' =  \left<\beta_1,\ldots, \beta_m, 0\right> \), de modo que \( \alpha\prec \alpha' \) y si \( \alpha\prec \gamma \), entonces \( \alpha'\preceq \gamma \).
  
  En efecto, como \( 0 \) es el mínimo ordinal, se cumple que \( \beta_m\succeq 0 \), luego \( \alpha' \) es una sucesión decreciente de ordinales y es, por lo tanto, un ordinal. Obviamente \( \alpha\prec \alpha' \) y, si \( \alpha \prec \gamma = \left<\delta_1,\ldots, \delta_n\right> \), hay dos posibilidades:
  
  1) Si \( \gamma = \left<\beta_1,\ldots, \beta _m, \delta_{m+1},\ldots, \delta_n\right> \) extiende a \( \alpha \), o bien \( \delta_{m+1}=0 \) y entonces también extiende a \( \alpha' \), o bien \( 0\prec \delta_{m+1} \), en cuyo caso \( \alpha' \) y \( \gamma \) difieren precisamente en el término \( m+1 \), de modo que \( \alpha'\prec \gamma \).
  
  2) Si \( \alpha \) y \( \gamma \) difieren por primera vez en \( \delta_i\prec \gamma_i \), entonces \( \alpha' \) y \( \gamma \) difieren en el mismo término, luego \( \alpha'\prec \gamma \).
  

Con esto ya podemos asegurar que los primeros ordinales son

\( 0 = \left<\ \right>, \quad 0'=\left<0\right>, \quad 0''=\left<0,0\right>, \quad 0''' = \left<0,0,0\right>, \quad 0''''= \left<0,0,0,0\right>, \quad \ldots \)

A estos ordinales los llamaremos ordinales finitos, pues son los que se obtienen de \( 0 \) aplicando un número finito de veces la operación "siguiente". Los demás ordinales son los ordinales infinitos.

A partir de aquí usaremos la notación:

\( 1 = 0', \quad 2 = 0'', \quad 3 = 0''',\quad \ldots \)

Esto entra en conflicto con la notación usual para los números naturales y, para evitarlo, a partir de ahora llamaré

\( \bar 0, \quad \bar 1, \quad \bar 2, \quad \bar 3, \quad \ldots \)

a los números naturales. Así podemos afirmar que

\( 0 = \bar 0, \quad 1 = 0' = \bar 1, \quad 2 = 1' =\bar 3,\quad 3 = 2' = \bar 6,\quad 4 = 3' = \overline{10},\quad \cdots  \)

pero en realidad el número natural que es cada ordinal será irrelevante en la práctica.

• \( \omega = \left<1\right> = \bar 2 \) es el menor ordinal infinito.
  
  En efecto, como \( 1 \) es un ordinal, tenemos que \( \omega \) es una sucesión decreciente de ordinales, luego es un ordinal, ciertamente infinito (pues no consta de ceros) y si \( \alpha = \left<\beta_1,\ldots, \beta_n\right> \) es un ordinal infinito, alguno de sus términos tiene que ser no nulo, pero como la sucesión tiene que ser decreciente, necesariamente \( \beta_1\neq 0 \), luego \( 1\preceq \beta_1 \), luego \( \omega\preceq \alpha \).

Por lo tanto, los primeros ordinales son:

\( 0\prec 1\prec 2\prec \cdots \omega\prec \omega'\prec \omega''\prec \cdots \)

Añadido: En particular, \( \omega \) es el menor ordinal límite, donde un ordinal límite se define como un ordinal no nulo que no sea el sucesor de otro ordinal (lo que, visto como sucesión decreciente de ordinales, equivale a que no sea la sucesión vacía y que su último término no sea un 0).

Si \( \alpha = \left<\beta_1,\ldots, \beta_n\right> \) es un ordinal no nulo (de modo que \( n\geq 1 \)), en lo sucesivo lo representaremos así:

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

OJO: Más adelante definiremos una suma de ordinales, de modo que esta expresión podrá verse como la suma de los ordinales \( \omega^{\beta_1} = \left<\beta_1\right>, \ldots,  \omega^{\beta_n} = \left<\beta_n\right> \), pero aquí debemos destacar que NO tenemos definida una suma de ordinales y que esta expresión hay que verla como una mera notación que sustituye a \( \left<\beta_1,\ldots, \beta_n\right> \). En particular, para que tenga sentido (de momento) la sucesión de exponentes tiene que ser decreciente.

Por ejemplo, tenemos definido

\( \omega^3+\omega^3+\omega^2+\omega^1+\omega^1+\omega^0+\omega^0+\omega^0 = \left<3, 3, 2, 1, 1, 0, 0, 0\right> \)

pero no tenemos definido \( \omega^2 +\omega^5 \), ya que \( \left<2, 5\right> \) no es un ordinal.

Adoptaremos también los convenios siguientes:

• Como \( \omega^0 = \left<0\right>= 1 \), en lugar de \( \omega^0 \) escribiremos \( 1 \) y, en lugar de \( 1+1+1 \) escribiremos \( 3 \).
  
  
• Además, \( \omega^1 = \left<1\right> = \omega \), por lo que en lugar de \( \omega^1 \) escribiremos simplemente \( \omega \).
  
  
• Cuando se repitan "sumandos", como en \( \omega^3+\omega^3 \), escribiremos \( \omega^3\cdot 2 \).
  

Con estos convenios:

\( \left<3, 3, 2, 1, 1, 0, 0, 0\right> = \omega^3\cdot 2 + \omega^2+\omega\cdot 2+3 \).

Por ejemplo:

\( \omega' = \left<1, 0\right> = \omega+1, \quad \omega'' = \left<1, 0, 0\right> = \omega+2, \quad \omega''' = \left<1, 0, 0, 0\right> = \omega+3, \quad \ldots \)

En estos términos, los primeros ordinales son:

\( 0, \quad 1, \quad 2, \quad 3, \quad \ldots \quad \omega, \quad \omega+1,\quad \omega+2, \quad \ldots \)

Ahora es fácil ver que el menor ordinal mayor que todos éstos es \( \left<1, 1\right> = \omega+\omega = \omega\cdot 2 \), luego los primeros ordinales son:

\( 0,\quad 1, \quad 2, \quad \ldots, \quad \omega, \quad \omega+1, \quad\omega+2,\quad \ldots, \quad \omega\cdot 2,\quad \omega\cdot 2+1,\quad \ldots \)

Esta forma de expresar los ordinales (como sumas de potencias de \( \omega \) con exponentes decrecientes) se llama forma normal de Cantor. Pongo aquí dos funciones en Python que calculan la forma normal de Cantor de un ordinal (dado como número natural) en forma de cadena imprimible por Python y en LaTeX:

Código: [Seleccionar]

def fnc(n):
    """Expresa el ordinal n en forma normal de Cantor"""
    if n == 0:
        u = "(0)"  #u contendrá la fnc de n
    else:
        u = ""
        s = term(n)
        l = len(s)
        i=0
        while i<l:
            j = i   #Fijamos un término y contamos todos los siguientes iguales.
            t = s[i]
            while j< l and s[j] == t:
                j += 1
            if t == 0:
                #Si el término repetido es 0, suma k = j-i.
                u = u + str(j-i) + " + "
            else:
                if j-i == 1:
                    c = ""   #Si el término repetido es 1, no se pone el coeficiente.
                else:
                    #En otro caso el coeficiente es k = j-i
                    c = "\u00b7" + str(j-i)
                exp = fnc(t)    #fnc del exponente de omega.
                if exp == "(1)":
                    exp = ""    #Si el exponente es 1, no se pone.
                else:
                    exp = "^" + exp  #En caso contrario, elevamos al exponente.
                u = u + "\u03c9" + exp + c + " + "
            i = j
        u = "(" + u[:-3] + ")"   #Quita el último + y añade paréntesis.
    return u

def latex(n):
    """Expresa el ordinal n en forma normal de Cantor en LaTeX"""
    if n == 0:
        u = "0" #u contendrá la expresión en LaTeX
    else:
        u = ""
        s = term(n)
        l = len(s)
        i=0
        while i<l:
            j = i     #Fijamos un término y contamos todos los siguientes iguales.
            t = s[i]
            while j< l and s[j] == t:
                j += 1
            if t == 0:
                #Si el término repetido es 0, suma k = j-i.
                u = u + str(j-i) + " + "
            else:
                if j-i == 1:
                    c = ""  #Si el término repetido es 1, no se pone el coeficiente.
                else:
                    #En otro caso el coeficiente es k = j-i
                    c = "\cdot" + str(j-i)
                exp = latex(t)  #Expresión en LaTeX del exponente de omega.
                if exp == "1":
                    exp = ""    #Si el exponente es 1, no se pone.
                else:
                    exp = "^{" + exp + "}"  #En caso contrario, elevamos al exponente.
                #Añadimos a u omega elevado al exponente por el coeficiente.
                u = u+ "\omega" + exp + c + " + "
            i = j
        u = u[:-3]  #Quita el último +
    return u
Con la función latex he calculado la tabla siguiente, que contiene todos los ordinales menores que 200 (he omitido las sucesiones de ceros correspondientes a los ordinales finitos, que ocupan mucho espacio para nada):

\( \begin{array}{|rll|rll|rll|}
\hline
\bar 0 &()& 0&\overline{105}& -& 14&\overline{22}& (\bar 6)& \omega^{3}\\
\bar 1& (\bar 0)& 1&\overline{120}&-&15&\overline{56}& (\overline{10})& \omega^{4}\\
\bar 3& (\bar 0,\bar  0)& 2&\overline{136}& -& 16&\overline{121}& (\overline{15})& \omega^{5}\\
\bar 6 &(\bar 0,\bar  0,\bar  0)& 3&\overline{153}& -& 17&\bar 4& (\bar 2)& \omega^{\omega}\\
\overline{10}& -& 4&\overline{171}& -& 18&\overline{23}& (\bar 2, \bar 0)& \omega^{\omega} + 1\\
\overline{15}&-& 5&\overline{190}& -& 19&\overline{47}& (\bar 2, \bar 1)& \omega^{\omega} + \omega\\
\overline{21}& -& 6&\bar 2& (\bar 1)& \omega&\overline{173}& (\bar 2, \bar 3)& \omega^{\omega} + \omega^{2}\\
\overline{28}& -& 7&\bar 8& (\bar 1, \bar 0)& \omega + 1&\overline{93}& (\bar 2, \bar 2)& \omega^{\omega}\cdot2\\
\overline{36}& -& 8&\overline{31}& (\bar 1,\bar  0,\bar  0)& \omega + 2&\overline{37}& (\bar 8)& \omega^{\omega + 1}\\
\overline{45}& -&9&\overline{17}& (\bar 1,\bar  1)& \omega\cdot2&\overline{154}& (\overline{17})& \omega^{\omega\cdot2}\\
\overline{55}& -& 10&\overline{139}& (\bar 1, \bar 1, \bar 0)& \omega\cdot2 + 1&\overline{29}& (\bar 7)& \omega^{\omega^{2}}\\
\overline{66}& -& 11&\bar 7& (\bar 3)& \omega^{2}&\overline{11}& (\bar 4)& \omega^{\omega^{\omega}}\\
\overline{78}& -&12& \overline{57}& (\bar 3,\bar  0)& \omega^{2} + 1&\overline{122}& (\bar 4,\bar  0)& \omega^{\omega^{\omega}} + 1\\
\overline{91} &-&13&\overline{107}& (\bar 3, \bar 1)& \omega^{2} + \omega&\overline{67}& (\overline{11})& \omega^{\omega^{\omega^{\omega}}}\\
\hline
\end{array} \)

Ahora es fácil comparar dos ordinales a simple vista: Hay que comparar el término \( \omega^\beta\cdot k \) en el que difieren situado más hacia la izquierda. Será menor el ordinal que tenga menor exponente \( \beta \) y, en caso de igualdad, el que tenga el menor coeficiente \( k \).

Por ejemplo, si queremos comparar los ordinales

\( \alpha =\omega^{\omega^{\color{red}4}\cdot 3}\cdot 5+
\omega^{\omega^3\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{red}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 \)

vemos que difieren en su segundo término, por lo que tenemos que comparar sus exponentes, que son

\( \omega^3\cdot 5+\omega^2\cdot 7+\omega+3,\qquad \omega^3\cdot 5+\omega^2+\omega\cdot 8+9 \)

También difieren en su segundo término, y ahora los exponentes son ambos iguales a \( 2 \), por lo que comparamos los coeficientes, que son \( 7\succ 1 \), luego \( \alpha\succ \beta \).

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{red}\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]

Podemos definir:

\( \omega^{(0)}= 1, \quad \omega^{(1)}= \omega, \quad \omega^{(2)}= \omega^\omega,  \)

y, en general: \( \omega^{(n+1)}=\omega^{\omega^{(n)}} = \left<\omega^{(n)}\right> \).

Por ejemplo, la tabla anterior muestra que

\( \omega^{(0)}= \bar 1,\quad \omega^{(1)}= \bar 2,\quad \omega^{(2)}= \bar 4,\quad \omega^{(3)}= \overline{11},\quad \omega^{(4)}= \overline{67},\quad\ldots \)

Terminamos este mensaje con la observación siguiente:

• 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_{\color{red}m}) \), 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_{\color{red} m}}\prec \omega^{\omega^{(n)}}=\omega^{(n+1)} \).

Un ejercicio interesante es programar una función que a cada ordinal \( \alpha \) le calcule un \( n \) que cumpla el teorema.

[Carlos Ivorra]

Para terminar la presentación de los ordinales voy a definir la suma y el producto de ordinales. Las definiciones pueden parecer caprichosas, pero son las necesarias para que las operaciones se correspondan con las que se definen en teoría de conjuntos de forma natural.

En el mensaje anterior hemos visto que todo ordinal no nulo se puede expresar de forma única como

\( \alpha = \omega^{\delta_1}+\cdots + \omega^{\delta_n}, \)

donde \( \delta_1\succeq \cdots \succeq \delta_n \), o bien de la forma

\( \alpha = \omega^{\delta_1}\cdot k_1+\cdots + \omega^{\delta_n}\cdot k_n, \)

donde \( \delta_1\succ \cdots \succ \delta_n \) (la \( n \) no es la misma en los dos casos, sino que la segunda expresión es más corta, porque resulta de agrupar todos los términos consecutivos iguales).

Suma de ordinales Definimos \( \alpha + 0 = \alpha \), \( 0+\beta = \beta \) y, para ordinales no nulos

\( \alpha = \omega^{\delta_1}+\cdots + \omega^{\delta_m}, \quad \beta = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n} \),

definimos la suma como

\( \alpha + \beta = \omega^{\delta_1}+\cdots + \omega^{\delta_r}+\omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n}, \)

donde hemos suprimido todos los términos \( \omega^{\delta_i} \) con \( \delta_i\prec \epsilon_1 \) (en particular, si \( \delta_1\prec \epsilon_1 \) es \( \alpha+\beta = \beta \)).

Por ejemplo:

\( (\omega^{\omega^3}+ \omega^{\omega^2+\omega}+ \omega^4+\omega^2+5) + (\omega^4+\omega^3+\omega^2+3) = \omega^{\omega^3}+ \omega^{\omega^2+\omega}+ \omega^4+\omega^4+\omega^3+\omega^2+3. \)

La suma de ordinales es una de las pocas operaciones que los matemáticos consienten en llamar "suma" a pesar de que no es conmutativa. Por ejemplo:

\( (\omega^5+\omega^2+7)+(\omega^5+\omega+2) = \omega^5\cdot 2+\omega+2  \)

\( (\omega^5+\omega+2) + (\omega^5+\omega^2+7) = \omega^5\cdot 2+\omega^2+7 \).

En cambio, no es difícil probar que la suma es asociativa. Observemos que las expresiones en forma normal que hasta ahora eran una mera notación ahora pueden verse como sumas de sus términos, es decir, un ordinal como \( \omega^{\omega^2} + \omega^{\omega+3}+\omega^5+8 \) es la suma de sus cuatro términos en el sentido que acabamos de definir.

En particular, \( \alpha+1 \) se obtiene añadiendo un sumando \( 1 = \omega^0 \) a la expresión de \( \alpha \), que nunca cancela a ningún otro sumando, y ya sabemos que el ordinal que resulta de añadir un exponente \( 0 \) a otro \( \alpha \) es el ordinal siguiente (el menor ordinal mayor que \( \alpha \)).

• La suma de ordinales finitos coincide con la suma usual de números naturales. Por ejemplo:

\( 2+3 = (\omega^0+\omega^0)+ (\omega^0+\omega^0+\omega^0) = 5  \)

• Si \( \lambda \) es un ordinal límite, entonces \( \alpha+\lambda \) es el supremo de los ordinales \( \alpha+\beta \) con \( \beta\prec\lambda \).

En efecto, pongamos que \( \alpha = \omega^{\delta_1}+\cdots + \omega^{\delta_m} \) y \( \lambda = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n} \), donde \( \epsilon_n\succ 0 \), ya que \( \lambda \) es un ordinal límite. Entonces

\( \alpha+\lambda = \omega^{\delta_1}+\cdots + \omega^{\delta_k}+\omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n} \),

donde \( k \) es el mayor índice que cumple \( \delta_k\succeq \epsilon_1 \) (con la posibilidad de que \( k=0 \) y no esté la primera parte). Es fácil ver que si \( \beta\prec \lambda \), entonces \( \alpha+\beta\prec \alpha+\lambda \). Por otra parte, tomemos \( \eta\prec \alpha+\lambda \) y vamos a ver que existe un \( \beta\prec \lambda \) tal que \( \eta\prec \alpha+\beta \). Distingamos varios casos:

Puede ser que la expresión de \( \eta \) se prolongue hasta la de \( \alpha+\lambda \), en cuyo caso hay dos posibilidades:

Si \( \eta = \omega^{\delta_1}+\cdots + \omega^{\delta_j} \), con \( j\leq k \), entonces \( \eta\preceq \alpha= \alpha+0 \), con \( 0\prec \lambda \), y se cumple lo que queremos probar.

Si \( \eta = \omega^{\delta_1}+\cdots + \omega^{\delta_k}+\omega^{\epsilon_1}+\cdots + \omega^{\epsilon_j} \), con \( j <n \), entonces tomamos \( \beta = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_j}\prec \lambda \) y se cumple que \( \eta\prec\alpha+\color{red}\beta \).

La alternativa es que un (mínimo) exponente de \( \eta \) sea menor que el correspondiente de \( \alpha+\lambda \), y también hay dos casos:

Si \( \eta = \omega^{\delta_1}+\cdots + \omega^{\delta_j}+\omega^{\delta'_{j+1}}+\cdots \), con \( \delta'_{j+1}\prec \delta_{j+1} \), entonces \( \eta\prec \alpha= \alpha+0 \), como antes.

Si \( \eta = \omega^{\delta_1}+\cdots + \omega^{\color{red}\delta_k}+\omega^{\epsilon_1}+\cdots + \omega^{\color{red}\epsilon_j}+\omega^{\epsilon'_{j+1}}+\cdots \), con \( \epsilon'_{j+1}\prec \epsilon_{j+1} \), distinguimos dos casos:

Si \( j+1<n \), tomamos  \( \beta = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_j}+\omega^{\epsilon_{j+1}}\prec \lambda \) y \( \eta \prec \alpha+\beta \).

Si  \( j+1=n \) tomamos \( \beta = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_{n-1}}+\omega^{\epsilon'_n} + 1 \prec \lambda \) y \( \eta \prec \alpha+\beta \).

En particular, si partimos de un ordinal, \( \alpha \), podemos construir la sucesión creciente

\( \alpha\prec \alpha+1\prec \alpha+2\prec \alpha+3\prec \cdots \prec \alpha +\omega \)

y tenemos que \( \alpha+\omega \) es precisamente el supremo de esta sucesión. En otras palabras, \( \alpha+\omega \) es el menor ordinal límite mayor que \( \alpha \).

• Si \( \alpha\preceq \beta \), existe un único ordinal \( \gamma \) tal que \( \alpha+\gamma =\beta \).

En efecto, podemos suponer que ambos ordinales son no nulos, digamos

\( \alpha = \omega^{\delta_1}+\cdots + \omega^{\delta_m}, \quad \beta = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n} \).

Puesto que \( \alpha\preceq \beta \), hay dos posibilidades:

1) Si \( \beta \) extiende a \( \alpha \), entonces \( \gamma \) es necesariamente la suma de los términos que le faltan a \( \alpha \) para llegar a \( \beta \).

2) Si existe un mínimo \( i \) tal que \( \delta_i\prec \epsilon_i \), entonces tiene que ser \( \gamma = \omega^{\epsilon_i}+\cdots +\omega^{\epsilon_n} \).

• \( \alpha\preceq \alpha+\beta \), y la desigualdad es estricta si \( \beta \neq 0 \).

En efecto, podemos suponer que \( \beta\neq 0 \). Pongamos que \( \alpha = \omega^{\delta_1}+\cdots + \omega^{\delta_m} \), \( \beta = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n} \). Si \( \delta_m\succeq \epsilon_1 \) entonces

\( \alpha+\beta =  \omega^{\delta_1}+\cdots + \omega^{\delta_m}+\omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n} \),

que claramente es mayor que \( \alpha \). En caso contrario, si \( i \) es el mínimo índice tal que \( \delta_i\prec \epsilon_1 \), tenemos que

\( \alpha+\beta =  \omega^{\delta_1}+\cdots + \omega^{\delta_{i-1}}+\omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n} \),

y para comparar la suma con \( \alpha \) tenemos que comparar los exponentes \( \delta_i\prec \epsilon_1 \), luego la suma es mayor.

A su vez:

• Si \( \beta\prec \gamma \) si y sólo si \( \alpha+\beta\prec \alpha+\gamma \).

En efecto, hemos visto que \( \gamma = \beta+\delta \), para cierto \( \delta \succ 0 \), luego, por la propiedad precedente, \( \alpha+\beta\prec \alpha+\beta +\delta = \alpha+\gamma \).

Recíprocamente, si \( \alpha+\beta\prec \alpha+\gamma \) tiene que ser \( \beta\prec \gamma \), porque en caso contrario sería \( \gamma\preceq \beta \) y, por la parte ya probada, \( \alpha+\gamma\preceq \alpha+\beta \), contradicción.

Producto de ordinales La definición del producto de dos ordinales parece más caprichosa aún. Ante todo, definimos \( \alpha\cdot 0 = 0\cdot \alpha = 0 \) y \( \alpha\cdot 1 = \alpha \).

En segundo lugar, si \( \alpha = \omega^{\delta_1}+\cdots + \omega^{\delta_m} \) y \( \beta = \omega^\epsilon \), con \( \epsilon>0 \), definimos \( \alpha\cdot \omega^{\epsilon} = \omega^{\delta_1+\epsilon} \), de modo que el producto sólo depende del primer término de \( \alpha \).

Por último, si \( \beta =  \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n} \), definimos \( \alpha\cdot \beta = \alpha\cdot \omega^{\epsilon_1}+\cdots + \alpha\cdot \omega^{\epsilon_n}, \) donde los productos del miembro izquierdo están en uno de los dos casos anteriores, según si \( \epsilon_i \) es nulo o no.

Por ejemplo:

\( (\omega^5+\omega^5+\omega^2+\omega)(\omega^2+1+1)=\omega^7+ (\omega^5+\omega^5+\omega^2+\omega)+(\omega^5+\omega^5+\omega^2+\omega)=\omega^7+\omega^5\cdot 4+\omega^2+\omega \).

El producto de ordinales tampoco es conmutativo. Por ejemplo:

\( 3\cdot \omega = (\omega^0+\omega^0+\omega^0)\cdot \omega^1 = \omega^1 = \omega \)

mientras que \( \omega\cdot 3 = \omega+\omega+\omega \). En general, los productos —hasta ahora formales— \( \omega^\delta\cdot n \) que aparecen en las expresiones en forma normal son productos en el sentido que acabamos de definir. En efecto:

• Si \( n \) es un ordinal finito no nulo, según la definición de producto:

\( \alpha\cdot n = \alpha\cdot (1+\cdots + 1) = \alpha+\cdots +\alpha \).

En particular, esto implica que el producto de ordinales finitos se corresponde con el producto usual de números naturales.

Por ejemplo, si \( \alpha = \omega^\omega\cdot 3+\omega^4\cdot 5+\omega+3 \), entonces

\( \alpha\cdot 4 = (\omega^\omega\cdot 3+\omega^4\cdot 5+\omega+3)+(\omega^\omega\cdot 3+\omega^4\cdot 5+\omega+3)+(\omega^\omega\cdot 3+\omega^4\cdot 5+\omega+3)+(\omega^\omega\cdot 3+\omega^4\cdot 5+\omega+3) \)

\( =\omega^\omega\cdot 12+\omega^4\cdot 5+\omega+3 \),

pues \( \omega^\omega \) cancela los términos intermedios.

• Veamos ahora que \( \alpha\cdot \omega \) es el supremo de la sucesión

\( \alpha\prec \alpha\cdot 2\prec \alpha\cdot 3\prec \alpha\cdot 4\prec \cdots \)

En el ejemplo que hemos puesto, por definición, \( \alpha \cdot \omega = \omega^{\omega+1} = \left<\omega+1\right> \), mientras que

\( \alpha = \omega^\omega\cdot 3+\omega^4\cdot 5+\omega+3\prec \omega^\omega\cdot 6\preceq \alpha\cdot 2 =\omega^\omega\cdot 6+\omega^4\cdot 5+\omega+3\prec \omega^{\omega}\cdot 9\preceq \alpha\cdot 3 = \omega^\omega\cdot 9+\omega^4\cdot 5+\omega+3\prec \cdots \)

es decir:

\( \alpha\prec \omega^\omega\cdot 6\preceq \alpha\cdot 2 \prec \omega^\omega\cdot 9\preceq \alpha\cdot 3\prec \omega^\omega\cdot 12\preceq \alpha\cdot 4\prec\cdots  \),

luego el supremo de la sucesión \( \alpha\cdot n \) coincide con el de la sucesión \( \omega^\omega\cdot n \), es decir, el supremo de la sucesión \( \left<\omega, \ldots ,\omega\right> \) (\( n \) veces), y dicho supremo (teniendo en cuenta que el orden es el lexicográfico) es precisamente \( \left<\omega+1\right> = \omega^{\omega+1} = \alpha\cdot \omega \).

En el caso general, si \( \alpha = \omega^{\delta_1}\cdot k_1+\cdots + \omega^{\delta_l}\cdot k_l \), tenemos que \( \alpha\cdot n =  \omega^{\delta_1}\cdot k_1\cdot n+\cdots + \omega^{\delta_l}\cdot k_l \) y que el supremo de esta sucesión coincide con el de \( \omega^{\delta_1}\cdot k_1\cdot n \), o también con el de la sucesión \( \omega^{\delta_1}\cdot n = \left<\delta_1,\ldots, \delta_1\right> \) (\( n \) veces), que, como el orden es el lexicográfico, es \( \left<\delta_1+1\right> = \omega^{\delta_1+1} =\alpha\cdot \omega \).

Las funciones siguientes calculan la suma y el producto de ordinales:

Código: [Seleccionar]

def suma(m,n):
    """Calcula la suma de dos ordinales."""
    ss = term(m)
    tt = term(n)
    if n == 0:
        u = m
    else:
        i = len(ss)-1
        while i >= 0 and comp(ss[i],tt[0]) and ss[i] != tt[0]:
            i -= 1
        ss = list(ss)[0:i+1]
        ss.extend(tt)
        u = s(*ss)
    return u

def prod(m,n):
    """Calcula el producto de dos ordinales."""
    if m == 0 or n == 0:
        u = 0
    else:
        ss = term(m)
        tt = term(n)
        i = len(tt)
        while i>0 and tt[i-1] == 0:
            i -=1
        u = list(tt[:i])
        for j in range(0, len(u)):
            u[j] = suma(ss[0], u[j])
        u = s(*u)
        for j in range(i, len(tt)):
            u = suma(u, m)
    return u
Exponenciación de ordinales  No vamos a definir en general la exponenciación de ordinales, pero lo ciero es que tenemos definidas las potencias \( \omega^\delta \), para todo ordinal \( \delta \), y la definición de producto hace ahora que \( \omega^\delta \cdot \omega^\epsilon = \omega^{\delta+\epsilon} \). Esto implica a su vez que si \( k \) es finito, entonces \( (\omega^\delta)^k = \omega^{\delta \cdot k} \).

Observemos que si \( \lambda \) es un ordinal límite, entonces \( \omega^\lambda \) es el supremo de los ordinales \( \omega^\alpha \), con \( \alpha\prec \lambda \).

En efecto, es inmediato que \( \omega^\alpha\prec \omega^\lambda \) y, si \( 0\prec \beta\prec \omega^{\lambda} \), entonces \( \beta = \omega^{\epsilon_1}+\cdots + \omega^{\epsilon_n} \), donde necesariamente \( \epsilon_1\prec \lambda \), y así \( \beta\prec \omega^{\epsilon_1+1} \), con \( \alpha = \epsilon_1+1\prec \lambda \).

En particular, si

\( \alpha_0\prec \alpha_1\prec \alpha_2\prec \cdots \prec \alpha \)

es una sucesión estrictamente creciente de ordinales con supremo \( \alpha \), se cumple que \( \omega^\alpha \) es el supremo de la sucesión

\( \omega^{\alpha_0}\prec \omega^{\alpha_1}\prec \omega^{\alpha_2}\prec \cdots \)

Con esto ya estamos en condiciones de "filosofar" sobre los ordinales y su buena ordenación, pero eso será en la entrega siguiente.


En lo que sigue necesitaré algunas propiedades de la aritmética ordinal, pero, como aún no sé cuáles exactamente, ya iré añadiendo aquí los resultados que vaya necesitando.

[Carlos Ivorra]

Los programas en Python que he puesto en los mensajes anteriores estaban pensados para reproducir las definiciones y mostrar que todas ellas son computables en la práctica, pero codificar los ordinales finitos como números naturales no es nada eficiente.

Por ejemplo, un ordinal con el que se puede operar fácilmente a mano como \( \omega^{\omega \cdot 3 + 1} + \omega^{2} + \omega \cdot 4 + 1 \) resulta ser el número natural

1153066699115034244899462638892188551800591125593489414047473296179179108366071291272275420771
0772336335609569692792059293609963027611102766335087874358734282151769355786319873274935895672
6551071491763302814868162613291498344373915457802258208960598042833560240411485760741431029924
9691217246398946116363281696121017299010290942193612248392071840333708926980788461421721760496
3460544524700882832518963416772805594543681582089563819264722096297437202698199136694274793031
16934578132085998690913800009744511929255709788007

Y a poco que aumentemos la complejidad del ordinal los números naturales se vuelven astronómicos y Python no puede con ellos. Esto se resuelve codificando los ordinales de otra forma. Adjunto aquí un módulo Python que he programado para ello.

Se carga con

Código: [Seleccionar]

from ordinales import *
y para ver su contenido basta teclear

Código: [Seleccionar]

help(ordinales)
Permite operar con ordinales de forma natural, identificando los números naturales con los ordinales finitos. He aquí un ejemplo de código:

Código: [Seleccionar]

u = []
for i in range(0, 100):
    a =OdC(i)
    if a != -1:
        u.append(a)
ordena(u)

for i in range(0, len(u)):
    print(int(u[i]), " ", term(int(u[i])), " ", u[i])

Este programa recorre los números del 0 al 99, determina cuáles de ellos corresponden a ordinales, los ordena según el orden \( \preceq \) y luego los muestra como sucesiones de números naturales y en forma normal. Si ponemos LaTeX(u[i]) los escribe en LaTeX.

Otro ejemplo:

Código: [Seleccionar]

a = w**3 * 4 + w**2 * 5 + w + 7
b = w**2 + w + 3

print("({}) \u00b7 ({}) = {}".format(a, b, a*b))
produce el resultado

\( (\omega^{3} \cdot 4 + \omega^{2} \cdot 5 + \omega + 7) \cdot (\omega^{2} + \omega + 3) = \omega^{5} + \omega^{4} + \omega^{3} \cdot 12 + \omega^{2} \cdot 5 + \omega + 7 \),

mientras que con el código de los mensajes precedentes Python se me congela porque el producto es un número natural astronómico.

[Carlos Ivorra]

Llegados a este punto, ya podemos empezar a "filosofar". El problema principal que plantea la construcción que he dado de los ordinales es el siguiente:

¿Existe una sucesión infinita decreciente de ordinales?

Así:

\( \alpha_0\succ \alpha_1\succ \alpha_2\succ \alpha_3\succ \cdots \)

O equivalentemente:

Si vamos construyendo una sucesión decreciente de ordinales como la anterior, ¿llegaremos necesariamente a 0 tras un número finito de pasos?

Porque, mientras no lleguemos a 0, la sucesión se puede prolongar. Si tratamos esta pregunta como los matemáticos tratan habitualmente cualquier pregunta de naturaleza matemática, la respuesta es muy simple: NO. Y la razón es que en ZF se puede demostrar que no.

Ordinales en ZF

Aunque no vamos a entrar en ello aquí, lo que sucede es que en ZF los ordinales (los que hemos definido aquí y muchos más) se pueden definir de un modo completamente distinto que hace relativamente fácil probar que están bien ordenados, es decir, que todo conjunto no vacío de ordinales tiene un mínimo elemento, y esto equivale a que no existen sucesiones decrecientes infinitas de ordinales.

Además, los ordinales que hemos definido aquí se corresponden biunívocamente con los ordinales conjuntistas menores que uno de ellos: \( \epsilon_0 \), de modo que la biyección conserva el orden, por lo que si existiera una sucesión decreciente de (nuestros) ordinales también la habría de ordinales conjuntistas, y en ZF se prueba que esto es imposible.

[cerrar]

Normalmente, el hecho de que algo pueda probarse en ZF (o en ZFC) hace que un matemático dé por zanjado el problema, pero esta afirmación que nos ocupa es un caso peculiar en el que "el protocolo habitual" no es razonable.

La razón es la que expliqué en el primer mensaje: Gentzen demostró que si la aritmética de Peano AP es contradictoria, entonces existe una sucesión estrictamente decreciente de ordinales. Más aún, que se puede programar a un ordenador para que vaya generando una sucesión decreciente de ordinales con la garantía de que nunca terminará.

Más precisamente, Gentzen mostró cómo asociar un ordinal (es decir, un número natural que, de hecho, es un ordinal) a cualquier demostración en AP, y probó que a partir de una demostración de una contradicción es posible construir siempre otra demostración de una contradicción con ordinal menor. La construcción es completamente finitista, de modo que es posible programar a un ordenador para que si le damos una demostración de una contradicción en AP él vaya construyendo sucesivamente nuevas demostraciones, cada una con un ordinal asociado menor que la anterior.

Por lo tanto, si podemos asegurar que no existen tales sucesiones decrecientes, podemos asegurar que AP es consistente. Otra cosa es que muchos pensemos que AP es obviamente consistente, pero ese "obviamente" no satisfará a un formalista radical que no acepte que hablemos informalmente de números naturales o, por lo menos, que "abusemos" de ello.

Pero muy, muy radical tendría que ser un formalista para cuestionar que un programa de ordenador hace lo que un análisis detallado de su programa muestra que puede hacer, y por ello aquí no voy a cuestionar la corrección del resultado de Gentzen (no creo que nadie se haya planteado nunca hacerlo). Es un hecho innegable que podemos programar un ordenador con un criterio para construir una sucesión decreciente de ordinales, con la única "pega" de que dicho criterio necesita partir de una demostración formal de una contradicción en AP.

El interés de todo esto es obtener una prueba "absoluta" de la consistencia de AP que no dependa de la consistencia de ZF, porque es trivial que si ZF es consistente también lo es AP. Y es por esto que —justo en este caso— no podemos aceptar el criterio usual de los matemáticos por el que si algo es demostrable en ZF, pues ya está demostrado y punto.

Un matemático "se fía" de ZF, porque sabe (o debería saber) que no es posible demostrar que ZF es consistente, pero, precisamente por eso, porque es imposible demostrarlo, no debe extrañarnos que no tengamos ninguna prueba de ello, sin que eso sea motivo para sospechar que ZF es contradictorio. Pero si confiar en ZF es razonable habitualmente, no es razonable fiarse de ZF justamente cuando lo que queremos es ver si podemos probar para AP lo que no podemos probar para ZF: su consistencia.

Por eso no vale la actitud del formalista que dice: tú déjame claro cuáles son tus axiomas y con eso yo ya doy tus afirmaciones por buenas (supuesto que sean lógicamente correctas). Si dejamos claro que "los axiomas" son los de ZF, la prueba de que no hay sucesiones decrecientes de ordinales no aporta nada. La pregunta realmente interesante es:

¿Podemos asegurar que es imposible que un ordenador genere una sucesión decreciente de ordinales?

No se trata de si se puede demostrar en ZF, sino de si es verdad. También se puede probar en ZF que \( 2+2=4 \), pero si ZF resultara ser contradictorio, eso no sería motivo para sospechar que, a lo mejor, resulta que dos y dos no son cuatro. Tenemos argumentos sobrados para estar convencidos de que \( 2+2=4 \) tanto si ZF es consistente como si no. Por eso probar que \( 2+2=4 \) en ZF no nos aporta nada que no sepamos ya. Nos podemos fiar más de la conclusión que de sus premisas. Eso vale para \( 2+2=4 \) y para muchas afirmaciones más, pero la cuestión es si también vale para la que nos ocupa:

¿Podemos asegurar que es imposible que un ordenador genere una sucesión decreciente de ordinales de modo que, aunque ZF resultara ser contradictorio, no tendríamos motivos para poner esto en duda, como no dudaríamos de que dos y dos seguirían siendo cuatro?

Para no llegar a una prueba ridículamente trivial de la consistencia de AP (una prueba que se limite al hecho obvio de que si ZF es consistente también lo es AP), no nos vale que "a partir de tales o cuales axiomas" se pueda demostrar lo que queremos, sino que necesitamos un argumento que nos convenza de que eso es verdad pase lo que pase con los axiomas de ZF y su consistencia.

Insisto en que no es que no sea paranoico plantearse que ZF podría ser contradictorio, sino que no podemos dar por hecho que es consistente cuando se trata de probar la consistencia de una teoría más modesta como AP sin caer con ello en el ridículo.

Muchos formalistas radicales tienden a recelar de cosas intuitivamente obvias (las que dan trabajo en ZF) y, en cambio, aceptan alegre e irreflexivamente otras cosas nada obvias (las que en ZF no dan ningún problema), como es el uso indiscriminado de palabras como "para todo" o "existe" (que la lógica de ZF permite usar sin preocupación alguna). Así, yo diría que "existe una sucesión" es un concepto muy difuso, porque yo no sé lo que significa "la totalidad de las sucesiones" como para poder darle un significado preciso a una afirmación sobre la totalidad de las sucesiones (o sobre si existe una entre ellas que cumpla algo), por lo que no podría decir tranquilamente que una afirmación con tal generalidad tiene que ser objetivamente verdadera u objetivamente falsa. En ZF se prueba que la totalidad de las sucesiones de números naturales es un conjunto no numerable, y —yo al menos— no sé lo que significan las afirmaciones que involucran una cantidad no numerable de cosas.

Afortunadamente, en nuestro caso no tenemos que preocuparnos por este problema, porque la cuestión no es si existe una sucesión decreciente de ordinales, sino de si existe una que pueda calcular un ordenador, y la familia de todas las sucesiones calculables por un ordenador (los conjuntos recursivamente numerables) es algo perfectamente definido y sobre lo que se puede hablar objetivamente. No estamos hablando de si existe una entelequia, sino de si existe un programa de ordenador que tendría que hacer algo muy concreto. Gentzen probó que ese programa existe si AP es contradictoria. Si no, el programa "está cojo", tenemos un algoritmo, pero le falta un input para que pueda funcionar.

Uno podría plantearse si no sucederá como con \( 2+2=4 \), que el argumento que lo prueba en ZF es válido intuitivamente, con lo que se puede "extirpar" de la axiomática para dar lugar a un argumento convincente que no dependa de los axiomas en concreto de ZF, sino de hechos intuitivamente justificables.

No parece un buen camino. La prueba en ZF se basa en las propiedades de los ordinales conjuntistas, y los ordinales conjuntistas son precisamente la fuente de una de las paradojas a las que tuvieron que enfrentarse los matemáticos de principios del siglo XX que creían que podían hablar de cosas tan abstractas sin el marco y las limitaciones que impone una teoría axiomática formal. En cualquier caso, no voy a discutir esa vía porque nos llevaría a los tecnicismos de la construcción de los ordinales en ZF y de su relación con los axiomas. Una muestra de que no es algo trivial es que en la teoría Z de Zermelo (que sólo tiene un axioma menos, el axioma del reemplazo, y que basta para fundamentar casi toda la matemática clásica) no se puede construir siquiera el ordinal \( \omega\cdot 2 \). Así que, construir los ordinales en una teoría de conjuntos, incluso \( \epsilon_0 \), es "droga dura".

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.

Copio aquí la justificación de esta equivalencia, que había puesto en el hilo de comentarios respondiendo a Eparoh:

Spoiler

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 \).

[cerrar]

El resultado de Gentzen se puede formular equivalentemente en términos de inducción hasta \( \epsilon_0 \). Para ello consideramos, 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.

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\in E(\beta\prec \alpha{\color{red}\rightarrow} \phi(\beta))\rightarrow \phi(\alpha))\rightarrow \forall \alpha\in E\,\phi(\alpha). \)

Ahí afirmamos lo que habíamos planteado antes en azul: si bajo el supuesto de que todo \( \beta\prec \alpha \) cumple \( \phi(\beta) \) podemos probar \( P(\alpha) \), esto garantiza que todo ordinal cumple \( P(\alpha) \).

Este principio puede enunciarse, pero no demostrarse en AP, y la razón es que todo el argumento de Gentzen es formalizable en AP. En AP se puede demostrar que la sentencia \( \phi-\text{IND}(\epsilon_0) \) (para una fórmula concreta \( \phi(\alpha) \), la que afirma que \( \alpha \) no es el ordinal asociado a una prueba de una contradicción en AP) implica que AP es consistente, y los teoremas de Gödel implican que no es posible demostrar la consistencia de AP en AP.

Por lo tanto, tenemos dos enunciados equivalentes:

(BO)     No existen sucesiones estrictamente decrecientes de ordinales.

y

IND(\( \epsilon_0 \))    La inducción hasta \( \epsilon_0 \) es válida, es decir, que si, bajo la hipótesis de que todo ordinal menor que \( \alpha \) cumple una propiedad, podemos probar que \( \alpha \) también la cumple, podemos estar seguros de que todos los ordinales la cumplen.

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).

La finalidad principal de los mensajes anteriores es que estas propiedades no son abstracciones matemáticas como si la hipótesis del continuo es verdadera o falsa, o incluso si es verdad que existen conjuntos no medibles Lebesgue. Estos ordinales que hemos definido son algo muy concreto que "cabe" en un ordenador, y cabe preguntarse si un ordenador podría o no generar una sucesión decreciente de ordinales. O existe tal sucesión o no existe, pero ¿podemos razonar que no existe sin que nuestro razonamiento se apoye en el postulado de que los axiomas de ZF son consistentes?

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

Empezaremos a abordar este problema en el mensaje siguiente, pero, por si alguien quiere ir meditando sobre ello, planteo los casos más simples:

Si empezamos a construir una sucesión decreciente de ordinales y el primero \( \alpha_0 \) es un número natural, seguro que la sucesión llegará a 0 en un número finito de pasos. Si empiezo en \( \alpha_0 = 4 \), lo más que puedo retrasar lo inevitable es haciendo \( 4\succ 3\succ 2\succ 1\succ 0 \). Puedo llegar a 0 en menos de cuatro pasos, pero no en más.

Supongamos ahora que empezamos en un ordinal infinito \( \alpha_0\prec \omega\cdot 2 \). Hemos visto que \( \alpha_0 \) es necesariamente de la forma \( \alpha_0 = \omega + n \), donde \( n \) es un ordinal finito. Si, por ejemplo, \( \alpha_0 = \omega+4 \), aunque descendamos a paso de pulga, lo más lento que podemos hacer es

\( \omega+4\succ \omega+3\succ \omega+2\succ \omega+1\succ \omega \)

y en cuanto (inevitablemente) hemos llegado a \( \omega \), yendo a pasitos pequeños, el paso siguiente es necesariamente un paso de gigante, y hemos de pasar a un ordinal finito. Podemos elegir el \( 4 \), o el \( 4\,000 \) o \( 10^{1000} \), pero en cuanto hayamos dado ese paso, estaremos a un número finito de pasos del 0, y llegaremos a 0 en un número finito de pasos.

Por lo tanto, si empezamos en \( \omega+4 \) (o en cualquier \( \omega+n \)), es seguro que en un número finito de pasos llegaremos a \( \omega \) y, en cuanto demos el paso siguiente, "tendremos los pasos contados" para llegar a 0.

Hemos probado que no puede haber sucesiones decrecientes de ordinales que empiecen en un ordinal \( \alpha_0\prec \omega\cdot 2 \), y eso no depende de ningún axioma de ZF. Cualquiera que entienda lo que son los ordinales (que hemos definido aquí) entiende que es absolutamente imposible —caiga la consistencia de la teoría que caiga— construir una sucesión decreciente de ordinales que empiece en \( \alpha_0\prec \omega\cdot 2 \) y que no llegue a 0 en un número finito de pasos. Dicho número no puede ser acotado a priori, porque todo dependerá de dónde aterricemos cuando pasemos \( \omega \), pero será necesariamente finito.

Seguro que el lector se convence de que lo mismo vale si partimos de \( \alpha_0\prec \omega\cdot 3 \). La cuestión es: ¿hasta que altura podemos razonar que si empezamos desde ahí llegaremos a 0? ¿podemos ir ascendiendo hasta asegurar que no importa lo alto que empecemos, que siempre caeremos hasta 0 o llega un punto en el que ya no está claro que pasa? Lo analizaremos en el mensaje siguiente.

[Carlos Ivorra]

Entramos ya en el problema de convencernos (si es posible) de que no existen sucesiones decrecientes de ordinales.

Aun a riesgo de resultar repetitivo, quiero insistir en que se trata de un problema bien planteado, en el mismo sentido que lo está un problema de ajedrez del tipo: juegan blancas y ganan. O bien es cierto y las blancas tienen una estrategia que les permite ganar hagan lo que hagan las negras, o no es así, pero no vale decir "si suponemos estos axiomas ganan las blancas, y si no, no lo sé". Una vez fijadas las reglas del ajedrez, o las blancas tienen una estrategia ganadora o no la tienen, pero no hay medias tintas.

Igualmente, una vez hemos definido lo que son los ordinales y su relación de orden, o es posible programar un ordenador para que genere una sucesión decreciente de ordinales (que no acabe nunca) o es imposible. No vale decir "suponiendo estos axiomas sí, y si no, no sé". Si uno se plantea si existen conjuntos no medibles Lebesgue, la respuesta sí que depende de si adoptamos unos axiomas u otros, pero aquí estamos hablando de si un ordenador puede o no puede hacer algo, y ahí no caben respuestas relativas a axiomas.

Conviene introducir la definición siguiente:

Un ordinal \( \alpha \) es accesible si no existen sucesiones decrecientes de ordinales menores que \( \alpha \).

En estos términos, queremos probar que todo ordinal es accesible, pero esta definición nos permite ascender poco a poco, tratando de probar que ordinales cada vez mayores son accesibles.

Observemos que, trivialmente, si un ordinal es accesible, lo son todos los menores que él.

Recordemos ahora que hemos probado que la sucesión

\( \omega^{(1)} = \omega \prec \omega^{(2)}=\omega^\omega\prec \omega^{(3)}=\omega^{\omega^\omega}\prec \cdots \)

no está acotada, sino que todo ordinal es menor que uno de éstos, luego basta probar que todos los ordinales \( \omega^{(n)} \) son accesibles.

Obviamente, \( \omega \) es accesible. Si un ordenador empieza a enumerar ordinales hacia abajo empezando en un ordinal finito \( \alpha_0\prec \omega \), es seguro que llegará a \( 0 \) en un número finito de pasos. Concretamente, si empieza con \( \alpha_0 = 10 \), llegará a \( 0 \) a lo sumo en \( 10 \) pasos, y si empieza en \( 10^{1000} \), a lo sumo en \( 10^{1000} \) pasos, pero es inconcebible que un ordenador imprima un número natural y siga hacia abajo y no llegue nunca a \( 0 \).

Más aún, en el mensaje anterior probamos que \( \omega\cdot 2 \) es accesible, porque si empezamos en un ordinal de la forma \( \omega + k \), tras un número finito de pasos tendremos que llegar (o rebasar) \( \omega \) y luego, tras otro número finito de pasos, llegaremos a \( 0 \).

Más en general, podemos probar lo siguiente:

• Si \( \alpha \) y \( \beta \) son ordinales accesibles, también lo es \( \alpha+\beta \).

En efecto, supongamos que existiera una sucesión decreciente:

\( \alpha+\beta \succ \alpha_0\succ\alpha_1\succ\alpha_2\succ\alpha_3\succ \cdots \)

No podría ser \( \alpha_0\prec \alpha \), porque eso contradiría que \( \alpha \) es accesible. Así pues, tendría que ser \( \alpha\preceq \alpha_0\prec \alpha+\beta \).

¿Podría ocurrir que todos los términos de la sucesión cumplieran \( \alpha\preceq \alpha_n\prec \alpha+\beta \)?

Vamos a ver que esto es imposible. Para ello usamos que, según hemos probado, cada \( \alpha_n \) podría expresarse entonces como \( \alpha_n = \alpha+\beta_n\prec \alpha+\beta \). Tenemos, pues, que

\( \alpha+\beta\succ\alpha + \beta_0\succ \alpha+\beta_1\succ \alpha+\beta_2\succ \cdots \)

y hemos visto que esto implica que

\( \beta\succ \beta_0\succ \beta_1\succ \cdots \),

lo que contradice la accesibilidad de \( \beta \).

Por consiguiente, tiene que haber un \( n \) tal que \( \alpha_n\prec \alpha \), y entonces la sucesión

\( \alpha\succ \alpha_n\succ \alpha_{n+1}\succ \alpha_{n+2}\succ \cdots \)

contradice la accesibilidad de \( \alpha \).

En resumen: una sucesión decreciente que empiece en un ordinal menor que \( \alpha+\beta \) tiene que rebasar \( \alpha \) tras un número finito de pasos (por la accesibilidad de \( \beta \)) y luego tiene que llegar a \( 0 \) en otro número finito de pasos (por la accesibilidad de \( \alpha \)).

Por consiguiente, el hecho de que \( \omega \) sea accesible implica inmediatamente la accesibilidad de

\( \omega+\omega = \omega\cdot 2\prec \omega\cdot 2 + \omega = \omega \cdot 3\prec \omega\cdot 3\cdot \omega+\omega = \omega \cdot 4\prec \cdots \)

Más precisamente, lo que hemos visto es que una sucesión decreciente que empiece en un ordinal, digamos, menor que \( \omega\cdot 5 \), tiene que rebasar \( \omega\cdot 4 \) en un número finito de pasos, y luego rebasará \( \omega\cdot 3 \) en un número finito de pasos, y así hasta rebasar \( \omega \) y finalmente llegar a \( 0 \).

Ahora conviene probar otro principio general:

• 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}\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 \).

Por ejemplo, hemos visto que \( \omega^2 \) es el supremo de la sucesión

\( \omega\prec \omega\cdot 2\prec \omega\cdot 3\prec \omega\cdot 4\prec \cdots \prec \omega^2 \),

y como hemos razonado que todos los ordinales \( \omega\cdot n \) son accesibles, podemos concluir que \( \omega^2 \) también lo es. Explítitamente, una sucesión decreciente que empezara en un ordinal \( \alpha_0\prec \omega^2 \), cumpliría de hecho que \( \alpha_0\prec \omega\cdots n \), para cierto \( n \), y ya hemos razonado que eso es imposible.

Más en general, ahora podemos probar:

• Si \( \alpha \) es accesible, también lo es \( \alpha\cdot \omega \).

En efecto, según hemos razonado, serán accesibles los ordinales:

\( \alpha\prec \alpha+\alpha=\alpha\cdot 2\prec \alpha\cdot 2+\alpha = \alpha\cdot 3\prec \cdots \prec\alpha\cdot \omega \),

los primeros por la accesibilidad de la suma de ordinales y el último por ser supremo de ordinales accesibles.

Por lo tanto, podemos asegurar la accesibilidad de la sucesión

\( \omega\prec \omega^2\prec \omega^3\prec \omega^4\prec \cdots \prec \omega^\omega \)

y la de su supremo, \( \omega^\omega = \omega^{(2)} \).

Si vamos multiplicando \( \omega^\omega \) por \( \omega \) muchas veces, obtenemos la sucesión de ordinales accesibles

\( \omega^\omega\prec \omega^{\omega+1}\prec \omega^{\omega+2}\prec \omega^{\omega+3}\prec \cdots \)

y el supremo de esta sucesión es \( \omega^{\omega\cdot 2} \). Si ahora vamos multiplicando este ordinal por \( \omega \) vamos obteniendo la accesibilidad de

\( \omega^{\omega\cdot 2}\prec \omega^{\omega\cdot 2+1}\prec \omega^{\omega\cdot 2+2}\prec\omega^{\omega\cdot 2+3}\prec \cdots \prec \omega^{\omega\cdot 3} \)

y es claro entonces que, de este modo, podemos ir probando la accesibilidad de todos los ordinales

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

Si no desfallecemos y seguimos multiplicando por \( \omega \), obtenemos la accesibilidad de

\( \omega^{\omega^2}\prec \omega^{\omega^2+1}\prec \omega^{\omega^2+2}\prec \omega^{\omega^2+3}\prec \cdots \prec \omega^{\omega^2+\omega} \).

Todo esto es prometedor, pues cada vez estamos más arriba, pero así no vamos a acabar nunca, a menos que encontremos un patrón general en los argumentos que estamos dando.

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{red}\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} \).

Pero el mismo bloque de pasos que nos ha permitido pasar de la accesibilidad de \( \omega \) a la de \( \omega^{\omega^3} \), aplicado ahora a \( \omega^{\omega^3} \), nos permite pasar a la de \( \omega^{\omega^3\cdot 2} \), y aplicando sistemáticamente dicho bloque de pasos llegamos a la accesibilidad de

\( \omega^{\omega^3}\prec \omega^{\omega^3\cdot 2}\prec \omega^{\omega^3\cdot 3}\prec \omega^{\omega^3\cdot4}\prec \cdots \prec \omega^{\omega^4} \),

y si admitimos que sabemos razonar la accesibilidad de todos los ordinales de la forma

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

Y en este punto uno se plantea si sería legítimo concluir con un "y así sucesivamente". Gentzen consideraba que sí:

Podemos, por ejemplo, visualizar los casos iniciales con características 1, 2, 3 con detalle. A medida que la característica crece, no se añade nada básicamente nuevo, el método de progresión es siempre el mismo. Desde luego, hay que admitir que la complejidad de los infinitos múltiplemente anidados que hay que recorrer crece considerablemente; este recorrido debe considerarse siempre como potencial [...] La dificultad reside en que, aunque el sentido finitista preciso de "recorrer'' los ordinales es razonablemente claro  en los casos iniciales, se vuelve de tal complejidad en el caso general que apenas es remotamente visualizable.

Pero Gödel no estuvo de acuerdo:

La situación, a grandes rasgos, puede ser descrita como sigue: La inducción transfinita hasta \( \epsilon_0 \) podría probarse finitistamente si y sólo si la consistencia de la teoría de números pudiera probarse finitistamente. Por otra parte, la validez de esta inducción no puede hacerse inmediatamente evidente, como sucede, por ejemplo, en el caso de \( \omega^2 \). Es decir, uno no puede captar de un vistazo las diversas posibilidades estructurales que existen para las sucesiones decrecientes y no existe, por lo tanto, un conocimiento concreto inmediato de la terminación de cada una de dichas sucesiones. Pero, más aún, tal conocimiento concreto (en el sentido de Hilbert) no puede alcanzarse a través de una transición gradual de ordinales menores a otros mayores, porque los pasos concretamente evidentes, como \( \alpha\mapsto \alpha^2 \) son tan pequeños que tendrían que repetirse \( \epsilon_0 \) veces para llegar hasta \( \epsilon_0 \).

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.

[Carlos Ivorra]

En este mensaje "demostraré" que la aritmética de Peano es contradictoria. Obviamente, la prueba tiene trampa. Me basaré en un argumento de Gentzen.

Vamos a probar que todo ordinal es accesible demostrando el principio de inducción hasta \( \epsilon_0 \):

Si, suponiendo que todo ordinal \( \beta\prec \alpha \) cumple una propiedad \( P(\beta) \) podemos razonar que también se cumple \( P(\alpha) \), entonces podemos concluir que todo ordinal cumple \( P(\alpha) \).

Si admitimos esto, tomando \( P(\alpha) \equiv  \) \( \alpha \) es accesible, podemos concluir que todo ordinal es accesible, pues es inmediato que si todos ordinales menores que \( \alpha \) son accesibles, entonces \( \alpha \) también lo es.

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^*(\alpha)\equiv \forall \beta\in E(\beta\preceq \alpha\rightarrow P(\beta)) \).

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\in E(P^*(\alpha)\rightarrow P^*(\alpha+\omega^\eta)) \).

En primer lugar vamos a demostrar:

(1)              \( \forall\alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha))\rightarrow \forall \eta\in E(\forall \delta\in E(\delta\prec \eta\rightarrow P'(\delta))\rightarrow P'(\eta)) \).

Informalmente: vamos a ver que si, bajo el supuesto de que todos los ordinales menores que \( \alpha \) cumplen \( P \), podemos probar que también \( \alpha \) cumple \( P \), entonces también podemos asegurar que si todos los ordinales menores que \( \alpha \) cumplen \( P' \), necesariamente \( \alpha \) cumple \( P' \).

Suponemos, pues, que se cumple:

(A) \( \forall\alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha)) \).

y vamos a probar en primer lugar que esto implica

(B) \( \forall\alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P^*(\beta))\rightarrow P^*(\alpha)). \)

Para ello fijamos \( \alpha\in E \) y suponemos que \( \forall \beta\in E(\beta\prec \alpha\rightarrow P^*(\beta)) \).

De la propia definición de \( P^* \) se sigue que \( P^*(\beta)\rightarrow P(\beta) \), luego tenemos

(C) \( \forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta)) \).

Ahora, aplicando (A) concluimos \( P(\alpha) \), y uniendo esto a (C) llegamos a que \( \forall \beta\in E(\beta\preceq \alpha\rightarrow P(\beta)) \), que es \( P^*(\alpha) \), por definición. Con esto tenemos probado (B).

Nuestro objetivo es probar:

(D) \( \forall \eta\in E(\forall \delta\in E(\delta\prec \eta\rightarrow P'(\delta))\rightarrow P'(\eta)) \),

así que fijamos \( \eta\in E \) tal que

(E) \( \forall \delta\in E(\delta\prec \eta\rightarrow P'(\delta)) \),

y tenemos que probar \( P'(\eta) \). Para ello fijamos un ordinal \( \alpha \), suponemos \( P^*(\alpha) \) y tenemos que probar \( P^*(\alpha+\omega^\eta) \).

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 (A), que nos da \( P^*(\alpha+1) \), como queríamos.

Supongamos ahora que \( \eta = \delta+1 \), y entonces tenemos que probar \( P^*(\alpha+\omega^{\delta+1}) \) y, por (B), basta probar a su vez:

(F) \( \forall \beta\in E(\beta\prec \alpha+\omega^\delta\cdot \omega\rightarrow P^*(\beta)) \).

Ahora bien, en el mensaje sobre aritmética ordinal hemos visto que si \( \beta\prec \alpha+\omega^\delta\cdot\omega \), existe un \( \gamma <\omega^\delta\cdot \omega \) tal que \( \beta\prec \alpha+\gamma \), y a su vez existe un \( k\prec \omega \) tal que \( \gamma \prec \omega^\delta\cdot k \), luego en total \( \beta \prec \alpha+\omega^\delta \cdot k \).

Esto hace que baste con demostrar:

(G) \( \forall k\in E(k\prec \omega\rightarrow P^*(\alpha+\omega^\delta\cdot k)) \).

En efecto, admitiendo (G), para probar (F) basta observar que si \( \beta\prec \alpha+\omega^\delta\cdot \omega \) existe un \( k \) tal que \( \beta\prec \alpha+\omega^\delta\cdot k \), luego por (G) se cumple \( P^*(\alpha+\omega^\delta\cdot k) \), luego también \( P^*(\beta) \), por la definición de \( P^* \), y así tenemos (F).

Demostramos (G) por inducción sobre \( k \). Para \( k=0 \) hay que probar \( P^*(\alpha) \), que se cumple por hipótesis.

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^*(\alpha+\omega^\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).

Falta el caso en que \( \eta \) es un ordinal límite. Para probar \( P^*(\alpha+\omega^\eta) \) tomamos \( \beta\prec \alpha+\omega^\eta \), con lo que existe un \( \gamma\prec \omega^\eta \) tal que \( \beta\prec \alpha+\gamma \) y a su vez existe un \( \delta \prec \eta \) tal que \( \beta\prec \alpha+\omega^\delta \).

Por (E) tenemos \( P'(\delta) \), y por definición de \( P' \) tenemos que \( P^*(\alpha)\rightarrow P^*(\alpha+\omega^\delta) \), pero estamos suponiendo \( P^*(\alpha) \), luego tenemos \( P^*(\alpha+\omega^\delta) \) y, por definición de \( P^* \), también \( P^*(\beta) \). Esto prueba que

\( \forall \beta\in E(\beta\prec \alpha+\omega^\eta\rightarrow P^*(\beta)) \),

y por (B) concluimos \( P^*(\alpha+\omega^\eta) \). Esto termina la prueba de (1).

Recordemos que

\( \omega^{(0)}= 1, \omega^{(1)}= \omega, \omega^{(2)}= \omega^{\omega}, \omega^{(3)}= \omega^{\omega^\omega},\ldots \)

Con esto es fácil probar que, si se cumple \( P(0) \), entonces se cumple:

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

Informalmente: si todos los ordinales menores o iguales que \( \omega^{(n)} \) cumplen \( P' \), entonces los ordinales hasta \( \omega^{(n+1)} \) cumplen \( P \).

En efecto, suponemos que \( \forall \alpha\in E(\alpha\preceq \omega^{(n)}\rightarrow P'(\alpha)) \), con lo que en particular tenemos \( P'(\omega^{(n)}) \), es decir:

\( \forall \alpha\in E(P^*(\alpha)\rightarrow P^*(\alpha+\omega^{(n+1)})) \),

luego tomando \( \alpha=0 \) (puesto que \( P^*(0) \) es lo mismo que \( P(0) \)) llegamos a \( P^*(\omega^{(n+1)}) \), que es, precisamente, \( \forall \alpha\in E(\alpha\preceq \omega^{(n+1)}\rightarrow P(\alpha)) \).

Con esto ya podemos probar fácilmente el principio de inducción. Para ello observemos que hemos razonado con una propiedad arbitraria \( P \), pero todo lo que hemos hecho con \( P \) vale en particular para la propiedad \( P' \), es decir, que tiene sentido considerar la propiedad \( P'' \), e igualmente podemos considerar \( P''', P'''' \), etc.

Supongamos:

\( \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha)) \)

y tenemos que probar que todo ordinal cumple \( P(\alpha) \). Para ello, dado un ordinal \( \alpha \), sabemos que existe un \( n \) tal que \( \alpha\prec \omega^{(n)} \), luego basta probar que todo ordinal menor que \( \omega^{(n)} \) cumple \( P(\alpha) \). Por ejemplo, si \( \alpha\prec \omega^{(4)} \), podemos razonar así:

Aplicando repetidamente (1), tenemos:

\( \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha)) \)

\( \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P'(\beta))\rightarrow P'(\alpha)) \)

\( \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P''(\beta))\rightarrow P''(\alpha)) \)

\( \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P'''(\beta))\rightarrow P'''(\alpha)) \)

En particular, tenemos \( P(0), P'(0), P''(0), P'''(0) \) (pues los antecedentes de las implicaciones anteriores para \( \alpha = 0 \) se cumplen trivialmente). Más aún, la última implicación nos permite probar por inducción que \( \forall \beta\in E(\beta\prec \omega\rightarrow P'''(\beta)) \), de donde, a su vez, esa misma implicación nos lleva a \( P'''(\omega) \), luego en total tenemos que:

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

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)) \)

y así hemos probado que todo ordinal \( \alpha\preceq \omega^{(4)} \) cumple \( P(\alpha) \). Hemos supuesto \( n= 4 \), pero es claro que el argumento vale igualmente para cualquier \( n \), sin más que aplicar las veces que haga falta (1) y luego (2). Por lo tanto, hemos probado que \( \forall\alpha\in E\,P(\alpha) \).

Esto demuestra el principio de inducción hasta \( \epsilon_0 \) con un argumento que cualquier finitista radical denunciará que "en realidad" es pura lógica formal, es decir, que no hemos hecho ni más ni menos que lo que hace cualquier matemático cuando razona en ZF.

De hecho, podemos decir más: supongamos que partimos de una propiedad aritmética \( P \), es decir, una propiedad de los números naturales definible a partir de la aritmética elemental y, por lo tanto, definible en la aritmética de Peano. Las propiedades \( P', P'', P''' \), etc., son entonces propiedades aritméticas (porque se definen a partir de \( P \) y de la aritmética ordinal, pero toda la aritmética ordinal se define a partir de la aritmética elemental de los números naturales, según hemos visto en los mensajes anteriores), y en todo el argumento no hemos usado ninguna propiedad "extraña" de los números naturales que no sea demostrable en AP. Entonces: ¿hemos demostrado el principio de inducción \( P-\mbox{IND}(\epsilon_0) \) en AP (para propiedades aritméticas)?

Si es así, tenemos un problema, porque Gentzen demostró que, para cierta propiedad aritmética P (la que expresa que \( \alpha \) no es el ordinal asociado a la prueba de una contradicción en AP), el principio \( P-\mbox{IND}(\epsilon_0) \) implica la consistencia de AP, luego si hemos demostrado \( P-\mbox{IND}(\epsilon_0) \) en AP resulta que la consistencia de AP es demostrable en AP, y el segundo teorema de incompletitud de Gödel implica entonces que la aritmética de Peano es contradictoria.

Que en AP se puede demostrar que  \( P-\mbox{IND}(\epsilon_0) \) implica la consistencia de AP es un hecho muy técnico que aquí no podemos discutir pero que aceptan unánimemente cuantos entienden el asunto. Doy mi palabra de honor de que ahí no hay trampa (conocida por la comunidad matemática). Y lo mismo vale para el teorema de incompletitud de Gödel.

La cuestión es si la demostración que acabamos de ver del principio de inducción es formalizable en AP o no, es decir, si hemos usado en algún momento algo que no pueda demostrarse a partir de los axiomas de Peano. Y la respuesta no es nada técnico, no hay que ir a los mensajes anteriores a ver si hay algo que hayamos probado usando algo sospechoso, sino que el fallo está aquí mismo, bien a la vista, y no es sino un ejemplo más del eterno problema de la matemática formal.

Ahí lo dejo.