[Carlos Ivorra]

Bien, Eparoh ha resuelto el enigma en el hilo de comentarios:

Todo el argumento anterior es formalizable en la aritmética de Peano excepto la última parte. Más precisamente, del mismo modo que los matemáticos demuestran teoremas "en ZFC" sin mencionar ZFC, e incluso en muchas ocasiones sin saber siquiera qué es ZFC, todo lo anterior puede verse como una demostración en AP de las afirmaciones (supuesto que \( P \) sea una propiedad aritmética):

\( P-\mbox{IND}(\omega^{(1)})\equiv \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha))\rightarrow \forall \alpha\in E(\alpha\prec \omega^{(1)}\rightarrow P(\alpha)), \)

\( P-\mbox{IND}(\omega^{(2)})\equiv \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha))\rightarrow \forall \alpha\in E(\alpha\prec \omega^{(2)}\rightarrow P(\alpha)), \)

\( P-\mbox{IND}(\omega^{(3)})\equiv \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha))\rightarrow \forall \alpha\in E(\alpha\prec \omega^{(3)}\rightarrow P(\alpha)), \)

\( P-\mbox{IND}(\omega^{(4)})\equiv \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha))\rightarrow \forall \alpha\in E(\alpha\prec \omega^{(4)}\rightarrow P(\alpha)), \)

\( \vdots \)

En otras palabras, hemos demostrado (y en AP podemos demostrar) que la inducción hasta \( \omega^{(1)} \) es válida, que la inducción hasta \( \omega^{(2)} \) es válida, que la inducción hasta \( \omega^{(3)} \) es válida, etc., pero NO es posible demostrar en AP (admitiendo que es consistente) que la inducción hasta \( \epsilon_0 \) es válida.

Si pudiéramos demostrar en AP que la inducción hasta \( \epsilon_0 \) es válida, podríamos probar en AP que AP es consistente, y Gödel nos daría automáticamente la demostración de una contradicción en AP.

Con más detalle. El argumento anterior nos da una demostración de \( P-\mbox{IND}(\omega^{(2)}) \) en la que se usa la propiedad \( P \) y la propiedad \( P' \) definida a partir de ella, y en la que se usan una vez las afirmaciones que en el mensaje anterior hemos numerado como (1) y (2).

Por otra parte, el argumento del mensaje anterior nos da también una demostración de \( P-\mbox{IND}(\omega^{(3)}) \) que es más compleja, porque usa las propiedades \( P, P', P'' \) y más larga, porque requiere usar dos veces las propiedades (1) y (2).

Y el mismo argumento nos da una demostración de \( P-\mbox{IND}(\omega^{(4)}) \) más compleja (usa \( P, P', P'', P'' \)) y más larga (usa las propiedades (1) y (2) tres veces).

Y así sucesivamente. Desde un punto de vista formal, el argumento anterior no es el esbozo de una demostración (en el mismo sentido en que las demostraciones que vienen en todos los libros de matemáticas son esbozos de demostraciones formales en ZFC), sino que es un esquema que nos asegura que podemos construir una demostración de

\( P-\mbox{IND}(\omega^{(n)})\equiv \forall \alpha\in E(\forall \beta\in E(\beta\prec \alpha\rightarrow P(\beta))\rightarrow P(\alpha))\rightarrow \forall \alpha\in E(\alpha\prec \omega^{(n)}\rightarrow P(\alpha)), \)

para \( n = 0, 1, 2, 3\ldots \)

Si nos dan \( n = 1\,000 \) sabemos cómo demostrar que la inducción transfinita vale hasta \( \omega^{(1000)} \), pero globalmente no tenemos una única demostración, sino que sabemos construir una demostración para cada \( n \), una demostración que será más larga y compleja cuanto mayor sea \( n \), pero que sigue un sencillo patrón general.

Sin embargo, desde un punto de vista metamatemático (intuitivo), no falta nada por demostrar. Esas infinitas demostraciones prueban que la inducción transfinita es válida para todo ordinal. Sabemos probar que es válida hasta \( \omega^{(1)} \), y hasta \( \omega^{(2)} \), y hasta \( \omega^{(3)} \), etc. y, como todo ordinal es menor que uno de éstos, sabemos que la inducción transfinita es válida para todos los ordinales (menores que \( \epsilon_0 \)).

El formalista que crea que las demostraciones metamatemáticas son meras demostraciones formales "disfrazadas", aquí tiene un ejemplo sobre el que reflexionar: tenemos un argumento intutivamente convincente que no es formalizable porque usa el ingrediente intuitivo por excelencia: que los números naturales son sólo el 0, el 1, el 2, el 3, etc.

Intuitivamente, si estamos seguros de que algo se puede demostrar para \( \omega^{(1)} \), y para \( \omega^{(2)} \), y para \( \omega^{(3)} \), etc., podemos asegurar que eso se cumple para todos los \( \omega^{(n)} \) y, en este caso, eso significa que eso se cumple para todos los ordinales. Sin embargo, formalmente, NO tenemos una prueba para todos los ordinales, es decir, una prueba de

\( \forall n\ P-\mbox{IND}(\omega^{(n)}) \),

sino un esquema que nos garantiza cómo construir infinitas pruebas, una para cada número natural. Formalmente no es lo mismo, intuitivamente sí.

Decía en el primer mensaje que demostrar la inducción transfinita en ZF es hacer el ridículo (si lo que pretendemos es probar la consistencia de AP), porque la consistencia de AP es trivial como teorema de ZF, y lo que interesa es una prueba que no dependa de ZF. La prueba que hemos dado en el mensaje anterior es, ciertamente, independiente de ZF, en el sentido de que no dejaría de ser concluyente aunque ZF resultara ser contradictorio. Pero, de cara a probar la consistencia de AP, no deja de ser un tanto ridícula:

Aunque el final de la prueba trasciende a AP, lo cierto es que el argumento principal no es más que un razonamiento en AP.  Quiero decir que cualquiera que lo acepte como válido, tácitamente está aceptando que razonar en AP es fiable (y en particular, consistente), luego en esencia estamos demostrando la consistencia de AP fiándonos de AP.

Claro que es difícil precisar qué significaría demostrar la consistencia de AP sin fiarse de AP. Una de las razones por las que la teoría de Gentzen suscita perplejidad es porque es difícil conceder que demuestre realmente algo, ya que uno tiende a acabar convencido de que le están demostrando lo que ya sabe que es cierto, con lo que es difícil juzgar si el argumento es concluyente.

Esto no quita para que la relación entre la consistencia y los ordinales y la inducción sea muy interesante, pero, si realmente queremos un argumento para la consistencia de AP que sea "más concreto", "más finitista", "más a prueba de escépticos de la intuición", más qué sé yo... no parece que con este argumento hayamos descendido nada en evidencia o conclusividad que el mero argumento basado en que existen los números naturales y cumplen los axiomas de AP, por lo que éstos no pueden probar mentiras sobre números naturales.

Quizá un argumento en la línea del dado en la respuesta #8 sería más aceptable en esa línea, pero con el dado allí tal cual se plantea la duda de si realmente se está concluyendo algo o si es un mero "repugna a la naturaleza de una recta".

En el mensaje siguiente daré la demostración de Takeuti que había prometido.

[Carlos Ivorra]

Expongo ahora el argumento de Takeuti sobre la buena ordenación de los ordinales (menores que \( \epsilon_0 \)). Se basa en esta definición:

Diremos que un ordinal es 1-accesible si es accesible y, supuesto definido lo que es un ordinal n-accesible, diremos que un ordinal \( \alpha \) es n+1-accesible si cuando \( \beta \) es n-accesible, también lo es \( \beta\cdot \omega^\alpha \).

Ahora generalizamos dos hechos que hemos probado para ordinales accesibles:

• Si \( \delta_0\prec \delta_1\prec \cdots \) es una sucesión estrictamente creciente de ordinales n-accesibles que tiene a \( \lambda \) por supremo, entonces \( \lambda \) también es n-accesible.
• Si \( \alpha \) es n-accesible, también lo es \( \alpha\cdot \omega \).

Demostración: La primera propiedad la tenemos probada para n = 1 en la respuesta #8. Supongamos que es cierta para \( n \) y veamos que también vale para \( n+1 \).

Para ello partimos de una sucesión creciente de ordinales \( n+1 \)-accesibles y sea \( \beta \) otro ordinal \( n \)-accesible (que podemos suponer no nulo). Entonces, por definición de la \( n+1 \)-accesibilidad, cada ordinal \( \beta\cdot \omega^{\delta_i} \) es \( n \)-accesible. Ahora bien, es fácil ver (= ejercicio) que la sucesión

\( \beta\cdot\omega^{\delta_0}\prec \beta\cdot \omega^{\delta_1}\prec\cdots \)

tiene supremo \( \beta\cdot\omega^\lambda \), luego por hipótesis de inducción es \( n \)-accesible, y esto prueba la \( n+1 \)-accesibilidad de \( \lambda \).

Para la segunda propiedad también tenemos que el caso \( n=1 \) está probado en la respuesta #8. Supuesta cierta para \( n \), tomamos un ordinal \( n+1 \)-accesible \( \alpha \) y otro \( n \)-accesible \( \beta \). Tenemos que probar que \( \beta\cdot \omega^{\alpha\cdot \omega} \) es \( n \)-accesible. Pero este ordinal es el supremo de la sucesión

\( \beta\cdot\omega^\alpha\prec \beta\cdot\omega^{\alpha\cdot 2}\prec \beta\cdot\omega^{\alpha\cdot 3}\prec\cdots  \)

luego, por la primera propiedad, basta probar que cada \( \beta\cdot\omega^{\alpha\cdot k} \) es \( n \)-accesible, pero \( \beta\cdot\omega^{\alpha\cdot k} = \beta\cdot \omega^\alpha\cdots \omega^{\alpha} \), y basta usar \( k \) veces la accesibilidad de \( \alpha \).

Como consecuencia inmediata:

• El ordinal \( 1 \) es \( n \)-accesible para todo número natural \( n\geq 1 \).

En efecto, sabemos que (trivialmente) \( 1 \) es \( 1 \)-accesible y, si \( \beta \) es un ordinal \( n \)-accesible, entonces \( \beta\cdot \omega^1 \) es \( n \)-accesible por la segunda propiedad que hemos probado antes, y esto significa, por definición, que \( 1 \) es \( n+1 \)-accesible.

Con esto ya es fácil probar que todos los ordinales \( \omega^{(n)} \) son accesibles. Por ejemplo, para \( n=5 \) razonamos así:

• Según acabamos de probar, \( 1 \) es \( 6 \)-accesible.
• Como \( 1 \) también es \( 5 \)-accesible, por definición \( \omega = 1\cdot \omega^1 \) es \( 5 \)-accesible.
• Como \( 1 \) es \( 4 \)-accesible, por definición \( \omega^{(2)} = 1\cdot \omega^\omega \) e \( 4 \)-accesible.
• Como \( 1 \) es \( 3 \)-accesible, por definición \( \omega^{(3)} = 1\cdot \omega^{\omega^{(2)}} \) es \( \color{red}3 \)-accesible.
• Como \( 1 \) es \( 2 \)-accesible, por definición \( \omega^{(4)} = 1\cdot \omega^{\omega^{(3)}} \) es \( \color{red}2 \)-accesible.
• Como \( 1 \) es \( 1 \)-accesible, por definición \( \omega^{(5)} = 1\cdot \omega^{\omega^{(4)}} \) es \( \color{red}1 \)-accesible.

La pregunta filosófica es: ¿es esto una demostración finitista?  O mejor: ¿Sirve este argumento (junto con la prueba de Gentzen) para que alguien se convenza de que al aritmética de Peano es consistente?

[Carlos Ivorra]

No cabe duda de que el argumento de Gentzen tiene interés por varios motivos:

Por una parte, nos proporciona un ejemplo sencillo de afirnación sencilla sobre los números naturales (la buena ordenación de los ordinales o, equivalentemente, el principio de inducción hasta \( \epsilon_0 \)) que, aunque cualquiera debería aceptar que es cierto, no es demostrable a partir de los axiomas de Peano, lo que pone en evidencia que sabemos más cosas sobre los números naturales que lo que afirman estos axiomas.

Esto ya podría dar que pensar a algunos formalistas radicales, pero lo más importante —o, al menos, la razón por la que me propuse escribir este hilo— es que la prueba de la validez de la inducción hasta \( \epsilon_0 \), por mucho que se parezca a una demostración formal típica (expuesta con el nivel de informalidad propio de todos los textos matemáticos) y por mucho que —por supuesto— se pueda considerar como una demostración formal típica en ZF, el caso es que considerarla como tal la desvirtúa por completo, en cuanto a que, si aporta algo, es precisamente como argumento informal, independiente de cualquier teoría axiomática, pues es la hipótesis de una prueba de la consistencia de AP que sólo tiene valor en la medida en que no dependa de la consistencia de ZF, pues es trivial que la consistencia de ZF implica la de AP.

Por ello un formalista radical debería plantearse que el hecho de que todo argumento metamatemático "convincente" sea formalizable en ZF y que, por lo tanto, todo argumento metamatemático convincente pueda presentarse bajo el aspecto de una demostración formal típica no es razón para concluir que los razonamientos metamatemáticos son razonamientos formales disfrazados, o algo así.

Por otro lado, quienes consideran dudosa la evidencia de la buena ordenación de los números naturales, o del principio de inducción usual, pueden hacerse una idea del grado de sofisticación que puede necesitar un argumento metamatemático intuitivo, y cómo en un momento dado es inevitable tener que recurrir a que los números naturales son 0, 1, 2, 3 ... y ninguno más, por lo que todo intento de evitar enfrentarse a este hecho no es más que un intento de posponer lo inevitable.

Para terminar de destacar aspectos de interés de la teoría de Gentzen cabe señalar que la prueba de que la inducción hasta \( \epsilon_0 \) implica la consistencia de AP no sólo es formalizable en AP, sino en una teoría formal mucho más restrictiva, conocida como Aritmética Recursiva Primitiva, que puede decirse que formaliza el finitismo más estricto posible (sin entrar en el ultrafinitismo, que niega la existencia de los números muy grandes). La teoría ARP sólo permite demostrar teoremas que se prueben explícitamente sin hacer referencia más que a una cantidad finita de números naturales. Una evidencia de su limitación es que en ARP no se puede demostrar siquiera la inducción hasta \( \omega\cdot 2 \).

Así pues, Gentzen separó toda la parte estrictamente finitista de la prueba de la consistencia de AP de un único ingrediente no finitista: la inducción hasta \( \epsilon_0 \).

Como acabo de señalar (o más bien, recordar, pues ya lo he dicho muchas veces), demostrar la inducción hasta \( \epsilon_0 \) en ZF es pervertirla, convertirla en una trivialidad, pero el debate filosófico que suscitan las demostraciones informales es justo el contrario: si al demostrar informalmente la validez de la inducción hasta \( \epsilon_0 \) no estamos suponiendo ya la consistencia de AP que en principio podríamos demostrar a partir de ella.

Por ejemplo, uno puede demostrar que existen rectas perpendiculares a partir de unos axiomas razonables para la geometría euclídea, pero sin duda tal teorema será tan evidente o incluso más que algunos de los axiomas. Nadie necesitará una demostración a partir de unos axiomas evidentes para convencerse de que es verdad que existen rectas perpendiculares (otra cosa es que la axiomatización de la geometría sirva para lo que sirve, pero no para convencer a alguien de algo obvio a partir de otras obviedades o incluso de cosas menos obvias). Aquí pasa (o podría pasar) lo mismo: ¿existirá alguien que diga "yo no estaba convencido de que AP era consistente hasta que no vi la prueba de Gentzen"?

Es poco probable, pero no porque el argumento de Gentzen no sea convincente, sino porque es difícil encontrar a alguien que no esté convencido de antemano. Sobre eso se ha escrito mucho. A poco que busquéis en google encontraréis artículos al respecto.

Se trata de comparar el argumento de Gentzen con el obvio: AP tiene que ser consistente porque sus axiomas son afirmaciones verdaderas sobre números naturales, luego sus teoremas también, luego nunca se podrá demostrar a partir de ellos ninguna falsedad.

La cuestión es si este uso de los números naturales como garantes de que en AP siempre se dicen cosas verdaderas (no como en ZFC, que no podemos hacer referencia a ninguna realidad clara que "esté ahí" y que nos permita decir que los axiomas de ZFC dicen cosas verdaderas sobre esos objetos) es distinto del uso que estamos haciendo de los números naturales al hablar de ordinales y probar su buena ordenación.

Por ejemplo, un posible argumento en favor de Gentzen sería que el argumento "directo" por el que uno se convence de la consistencia de AP exige admitir que cualquier afirmación sobre números naturales, sea la que sea, tiene que ser verdadera o falsa en un cierto sentido intuitivo, aunque en muchos casos sea imposible saber cuál es el caso. En cambio, el argumento de Gentzen sólo requiere una parte estrictamente finitista que se formaliza con afirmaciones muy limitadas en su significado, y de la prueba de la validez de la inducción hasta \( \epsilon_0 \) que sólo requiere que reconoceer que unas afirmaciones muy concretas sobre números naturales (no cualquier afirmación en general) son verdaderas.

Aunque cabe señalar que digo "muy concretas" en el sentido de "unas afirmaciones determinadas", pero éstas son, en otro sentido de la palabra, bastante abstractas. Me refiero a lo que, en términos de la prueba de Takeuti, se expresa como que todos los ordinales son accesibles, 2-accesibles, 3-accesibles, etc.

En fin: no voy a extenderme con filosofías. En principio con esto termina lo que quería contar en este hilo, pero voy a prolongarlo un poco más relacionando lo que hemos visto con un problema famoso interesante.

[Carlos Ivorra]

Como sabe todo el mundo que tiene Wikipedia a mano, Hércules mató a su esposa y a sus hijos en un arrebato de locura que le provocó la diosa Hera (que no llevaba bien que su marido Zeus hubiera engendrado a Hércules con otra mujer). Angustiado por su crimen, Hércules consultó el oráculo de Delfos, que le dijo que para expiar su culpa tenía que ponerse al servicio del rey Euristeo de Micenas, que le encomendó doce trabajos. El segundo de ellos fue matar a la Hidra de Lerna, un monstruo con muchas cabezas (hasta 10.000, según las fuentes) que podía regenerar dos cabezas por cada una que le cortaban. Pese a ello, Hércules se las arregló para matar a la Hidra.

No obstante, aquí vamos a enfrentarlo a una Hidra mucho más peligrosa. No sabemos cómo es exactamente ni cuántas cabezas tiene, pero podría ser tal que así:

Para un matemático, que ve las cosas más esquemáticamente, una hidra es un árbol con una única raíz, que en la figura hemos numerado como 0, de la que puede salir un número finito de nodos (en la figura tres, numerados como 1, 2, 3), de los cuales a su vez pueden salir más nodos, etc., pero sólo puede haber un número finito de nodos en total. Los nodos de los que no salen más nodos son las cabezas de la hidra. La hidra de la figura tiene 5 cabezas.

No parece tan peligrosa como la Hidra de 10.000 cabezas a la que tuvo que enfrentarse Hércules, pero su peligro se debe a que su capacidad de regenerar cabezas es muy superior.

Supongamos que Hércules decide atacar a la Hidra cortándole la cabeza numerada como 5 (con su "cuello" correspondiente, es decir, que quitamos la rama que une el nodo 1 con el 5). Nos fijamos entonces en la rama de la que salía el cuello amputado, es decir, la que une la raíz 0 con el nodo 1. Dicha rama se duplica con todo lo que tiene sobre ella, con lo que la Hidra pasa a tener este aspecto:

La copia de la rama 0-1 es la rama 0-9. Ahora la Hidra tiene 6 cabezas.

Pongamos que, en un segundo asalto, Hércules decide cortar la cabeza número 7. Nos fijamos ahora en la rama 1-4 de la que salía dicha cabeza. Esta vez la Hidra no regenera una copia de dicha arista y todo lo que hay sobre ella, sino DOS copias, y el resultado es:

Las copias de la rama 1-4 son las ramas  1-13 y 1-15, con lo que ahora la Hidra tiene 7 cabezas. Si en el tercer asalto Hércules le amputa la cabeza 8, la Hidra genera TRES copias de la arista 1-4 y, si en el cuarto asalto Hércules corta la cabeza número 4, la Hidra regenera CUATRO copias de la arista 0-1, y el resultado es

Ahora la Hidra tiene 29 cabezas.

Es crucial señalar que si Hércules corta una cabeza que sale directamente de la raíz de la Hidra, entonces no se produce regeneración alguna. Por ejemplo, si en el quinto asalto Hércules corta la cabeza número 2, la Hidra no sufrirá más cambio que la amputación de dicha cabeza (pero el contador de asaltos sigue avanzando y en el sexto asalto, si se corta una cabeza que no salga de la raíz, la Hidra generará SEIS copias de la rama de la que salía).

El problema que se plantea es si Hércules podrá matar a la Hidra en un número finito de pasos, es decir, reducirla a su raíz, sin cabeza alguna. Naturalmente, esto puede depender de la hidra inicial concreta a la que se enfrente o de la estrategia que siga para elegir qué cabeza corta en cada momento.

Si yo fuera malévolo y despiadado, podría haber planteado este problema en la sección de "propuestos por todos" a ver quién se anima a ayudar a Hércules  derrotar a la Hidra (si es que se puede). Pero lo he planteado en este hilo.

Es un sano ejercicio jugar un poco con las hidras, para lo cual conviene programarlas. Es importante codificar las hidras de forma práctica que permita subir y bajar por ellas con facilidad. A continuación pongo cómo lo he hecho yo con Python, por si le sirve a alguien de guía para adaptarlo a su lenguaje favorito.

Salvo que alguien encuentre una forma más práctica, yo diría que lo mejor es codificar una hidra como una sucesión de nodos: el nodo i-ésimo contiene dos datos: el índice del nodo "padre" del cual sale y el conjunto de índices de los nodos "hijos" que salen de él. Así, si estamos en un nodo lo tenemos fácil para bajar o para subir a los nodos siguientes.

Me ha parecido que sería más eficiente computacionalmente llevar la cuenta redundante del conjunto de índices correspondientes a cabezas, para no tener que calcularlas cada vez que queremos elegir una para cortarla.

Por comodidad he definido una clase "nodo" que simplemente contiene la información del nodo padre y del conjunto de nodos hijos, y la Hidra la he definido como un diccionario que a cada índice le asigna un nodo:

Código: [Seleccionar]

class nodo:
    def __init__(self, pdr, hjs = None):
        if hjs == None:
            hjs = set()
        self.padre = pdr
        self.hijos = hjs
    def __str__(self):
        return("{}->{}".format(self.padre,self.hijos))
    def __repr__(self):
        return("nodo({},{})".format(self.padre,self.hijos))

Hidra = ({0:nodo(None)})
Cabezas = set()     #Conjunto de índices de las cabezas
Puntero = 0         #Último índice usado
Este código define la "Hidra muerta":

{0: nodo(None,set())}

Consta de un único nodo 0 sin padre y con un conjunto vacío de hijos.

Para dotarla de cabezas uso las funciones siguientes:

Código: [Seleccionar]

def indice():
    """Nuevo índice"""
    global Puntero
    Puntero += 1
    return Puntero

def añade(i,r = None):
    """Añade una cabeza que sale del nodo i con índice r"""
    global Hidra
    if r == None:
        r = indice()
    Hidra[r]=nodo(i)            #Añadimos una cabeza de índice r.
    Hidra[i].hijos.add(r)       #La incluimos entre los hijos de i.
    Cabezas.add(r)              #La incluimos en la lista de cabezas
    if i in Cabezas:            #Si i era una cabeza, deja de serlo.
        Cabezas.discard(i)
La función indice() simplemente va generando números no usados para tomarlos como índices de los nuevos nodos, mientras que la función añade() le añade a la Hidra una nueva cabeza que sale del nodo i con índice r.

Por ejemplo, si hacemos:

Código: [Seleccionar]

Hidra.clear()
Hidra = ({0:nodo(None)})
Puntero = 0
Asalto = 0
añade(0)
añade(0)
añade(0)
añade(1)
añade(1)
añade(3)
añade(4)
añade(4)
Generamos la Hidra de la primera imagen. Primero hemos añadido tres cabezas sobre el nodo 0 (que son los nodos 1, 2, 3), luego hemos añadido nodos 4 y 5 sobre el nodo 1, luego un nodo 6 sobre el nodo 3 y luego los nodos 7 y 8 sobre el nodo 4.

El resultado se ve así:

{0: nodo(None,{1, 2, 3}), 1: nodo(0,{4, 5}), 2: nodo(0,set()), 3: nodo(0,{6}), 4: nodo(1,{8, 7}), 5: nodo(1,set()), 6: nodo(3,set()), 7: nodo(4,set()), 8: nodo(4,set())}

Por ejemplo, el nodo 1 tiene por padre al nodo 0 y por hijos a los nodos 4 y 5.

Los gráficos los he hecho con Mathematica, porque tiene una instrucción a la que le das un árbol y ella se encarga de dibujarlo de la forma más clara posible, y queda muy bien. En Python he programado algo más rudimentario, simplemente para ver qué vamos teniendo entre manos:

Código: [Seleccionar]

def arb(i):
    u = []
    h = sorted(Hidra[i].hijos)
    n = len(h)
    if n == 0:
        u = [str(i)]
    else:
        l = 0
        for j in h:
            s = arb(j)
            ll = len(s)
            if l == 0:
                s[0] = ("{}___".format(i))+s[0]
            else:
                s[0] = "|___"+s[0]
            u.append(s[0])
            for k in range(1, ll):
                s[k] == "   "+s[k]
                if l+1 < n:
                    s[k] = "|   "+s[k]
                else:
                    s[k] = "    "+s[k]
                u.append(s[k])
            l += 1
            if l < n:
                u.append("|")
    return u
       
def arbol():
    """Representa la Hidra en forma de árbol."""
    s = arb(0)
    t =""
    for i in s:
        t = t + "\n" + i
    return(t)
El resultado es:

0___1___4___7
|      |      |
|      |      |___8
|      |
|      |___5
|
|___2
|
|___3___6

Para cortar cabezas a la Hidra se puede usar este código:

Código: [Seleccionar]

def traslada(i, j):
    """Traslada todo lo que hay sobre el nodo i al nodo j"""
    global Hidra
    for k in Hidra[i].hijos:
        r = indice()
        añade(j,r)          #Añadimos una cabeza (provisional) en r.
        traslada(k,r)       #Trasladamos sobre r todo lo que hay sobre k.

def corta(i,n):
    """Corta la cabeza i y regenera n veces"""
    global Hidra, Cabezas
    if not i in Cabezas:
        raise Exception("El nodo {} no es una cabeza.".format(i))
    cuello = Hidra[i].padre
    del(Hidra[i])            #Borramos la cabeza i
    Cabezas.discard(i)       #La borramos tambien de la lista de cabezas
    Hidra[cuello].hijos.remove(i)   #La borramos del conjunto de hijos.
    if cuello != 0:     
        pecho = Hidra[cuello].padre
        if Hidra[cuello].hijos == set():
            Cabezas.add(cuello)     #Si el cuello no tenía más hijos, ahora es cabeza.
        for s in range(0,n):        #Regeneramos n veces la Hidra.
            r = indice()
            añade(pecho, r)         #Creamos un nuevo nodo sobre el pecho.
            traslada(cuello, r)     #Y trasladamos todo lo que hay sobre el cuello.

def ataca(n):
    """Le corta a la Hidra la cabeza n-sima y calcula la regeneración correspondiente."""
    global Asalto
    Asalto += 1
    if n != None:
        corta(n, Asalto)
Por ejemplo, así se generan las Hidras de las imágenes de este mensaje:

Código: [Seleccionar]

print(arbol())
ataca(5)
print(arbol())
ataca(7)
print(arbol())
ataca(8)
print(arbol())
ataca(4)
print(arbol())
El código siguiente muestra la evolución del combate si Hércules juega con más fuerza que maña, cortando en cada asalto la primera cabeza que se le ocurre:

Código: [Seleccionar]

import random

while Asalto < 100:
    n = random.randrange(0,len(Cabezas))
    c = list(Cabezas)[n]
    ataca(c)
    print("Asalto {}: Cortamos la cabeza {} -> quedan {} cabezas"
          .format(Asalto, c, len(Cabezas)))
Si el lector juega con estos programas (o los que él se programe) podrá hacerse una idea sobre si Hércules necesitaría o no algo de asesoramiento sobre qué estrategia usar para derrotar a la Hidra. Se puede empezar con la que he puesto de ejemplo o con alguna otra más sencilla, para familiarizarse con el problema.

[Carlos Ivorra]

Es interesante programar un combate entre Hércules y la Hidra, por ejemplo en el que en cada asalto se corte una cabeza elegida al azar. Acabo de organizar uno partiendo de la Hidra del mensaje anterior, y el número de cabezas ha ido evolucionando así:el

\( \begin{array}{rr|rr}
\text{Asalto}&\text{Cabezas}&\text{Asalto}&\text{Cabezas}\\
\hline
0&5&30&5\,535\\
1&8&40&10\,319\\
2&13&50&19\,488\\
3&21&60&29\,675\\
4&24&70&39\,043\\
5&33&80&55\,710\\
6&38&90&79\,635\\
7&44&100&107\,377\\
8&52&200&449\,556\\
9&60&300&1\,325\,027\\
10&69&400&2\,972\,177\\
20&1\,956&500&5\,839\,070\\
\end{array} \)

Todo apunta a que Hércules perderá el combate y que, si tiene alguna opción de ganar, tendrá que ser con alguna ingeniosa estrategia, porque lo de cortar cabezas al azar no funciona.

Sin embargo, no es así. Sucede que Hércules siempre gana a la Hidra sea cual sea el criterio que use para elegir la cabeza que corta en cada asalto.

La prueba es muy sencilla teniendo en cuenta lo que hemos visto en este hilo.

Se basa en que a cada Hidra le podemos asignar un ordinal con el criterio siguiente (la figura muestra el caso del ejemplo del mensaje anterior):

Primero asignamos un ordinal a cada nodo de la Hidra:

• A cada cabeza le asignamos el ordinal 0
• Para calcular el ordinal de un nodo, consideramos los ordinales de sus "hijos", digamos que son \( \delta_1,\ldots, \delta_n \), los ordenamos de mayor a menor, y le asignamos al nodo el ordinal \( \omega^{\delta_1}+\cdots + \omega^{\delta_n} \)
• El ordinal de la Hidra es el de su raíz.

Así, en el ejemplo, las cinco cabezas tienen ordinal \( 0 \), el nodo 4 tiene ordinal \( \omega^0+\omega^0 = 2 \), el nodo 1 tiene ordinal \( \omega^2+\omega^0 = \omega^2+1 \), el nodo 3 tiene ordinal \( \omega^0 = 1 \) y el nodo 0 tiene ordinal \( \omega^{\omega^2+1}+\omega^1+\omega^0 = \omega^{\omega^2+1}+\omega+1 \).

Recíprocamente, a partir del ordinal podemos reconstruir la Hidra. Si nos dan el ordinal \( \omega^{\omega^2+1}+\omega+1 \), vemos que se trata de una Hidra de cuya raíz salen tres ramas, correspondientes a los tres sumandos. La correspondiente al sumando \( 1= \omega^0 \) termina en una cabeza, la correspondiente al sumando \( \omega^1 \) llega a un nodo de ordinal \( 1= \omega^0 \), luego de él sale una única cabeza, y la correspondiente al sumando \( \omega^{\omega^2+1} \) llega a un nodo de ordinal \( \omega^2+1 \), luego de él salen dos ramas, la correspondiente a \( 1 = \omega^0 \) llega a una cabeza y la correspondiente a \( \omega^2 \) llega a un nodo del que salen dos cabezas.

En particular, la única Hidra de ordinal 0 es la Hidra muerta.

Ahora sólo tenemos que observar que, cuando Hércules le corta una cabeza a la Hidra, tras la regeneración correspondiente, la Hidra resultante tiene ordinal menor que la anterior.

En efecto, supongamos que le cortamos a la Hidra una cabeza que no sale de la raíz, sino de un nodo que tiene por debajo otro nodo de ordinal \( \alpha \). Este \( \alpha \) será de la forma

\( \alpha = \omega^{\eta_0}\cdot k_0+\cdots + \omega^{\eta_n}\cdot k_n, \)

con  \( \eta_0\succ \eta_1\succ\cdots \succ \eta_n \). Pongamos que la cabeza cortada está en una de las ramas de ordinal \( \eta_i \). Entonces \( \eta_i=\eta'+1 \), donde el \( 1 \) corresponde a la cabeza cortada. Por lo tanto, tras la decapitación, tenemos que cambiar uno de los sumandos \( \omega^{\eta_i} \), con lo que nos queda \( \omega^{\eta_i}(k_i-1) \), y por otra parte tenemos que añadir \( m+1 \) sumandos \( \omega^{\eta'} \), donde \( m \) es el número de asalto en curso. En total, hemos de cambiar:

\( \omega^{\eta_i}\cdot k_i\mapsto \omega^{\eta_i}(k_i-1)+\omega^{\eta'}\cdot (m+1). \)

En suma, quitamos un término \( \omega^{\eta_i} \) y añadimos \( m+1 \) términos \( \omega^{\eta'}\prec \omega^{\eta_i} \). Claramente, esto hace que \( \alpha \) cambie a un ordinal \( \alpha'\prec \alpha \), y es claro que entonces el ordinal de la raíz también pasa de un ordinal \( \beta \) a otro \( \beta'\prec \beta \), pues para compararlos nos encontraremos todos los términos iguales hasta llegar al correspondiente a la rama donde estaba la cabeza, para comparar estos términos comparamos los exponentes, y serán todos iguales excepto los correspondientes a la rama donde estaba la cabeza, y así vamos subiendo hasta llegar a los exponentes \( \alpha'\prec \alpha \). Si la cabeza cortada sale de la raíz, el ordinal de la Hidra pasa de un cierto \( \alpha+1 \) hasta \( \alpha \), luego también disminuye estrictamente.

Por lo tanto, cada combate entre Hércules y la Hidra va generando una sucesión decreciente de ordinales, luego tiene que llegar a 0 en un número finito de pasos, y cuando eso suceda la Hidra habrá muerto. No importa el criterio que use Hércules para cortar las cabezas.

En el mensaje siguiente analizaré la evolución del combate para una estrategia concreta.

De momento, concluyo observando que las Hidras nos proporcionan una representación gráfica de los ordinales menores que \( \epsilon_0 \).

[Carlos Ivorra]

Hemos visto que Hércules siempre gana a la Hidra, sea cual sea el criterio que elija para cortar cabezas. No obstante, vamos a ver una estrategia posible que podemos probar que es ganadora sin necesidad de hablar de ordinales.

Para ello definimos la altura de un nodo de la Hidra como el número de nodos que tiene por debajo. Diremos que dos cabezas son hermanas si ambas salen del mismo nodo.

La estrategia que le proponemos a Hércules es la siguiente:

En cada asalto, Hércules corta una cabeza de altura máxima que tenga el mayor número posible de hermanas.

Por ejemplo, esta Hidra:

tiene \( 5 \) cabezas de altura \( 3 \), pero la estrategia exige cortar la \( 11 \) o la \( 12 \), que forman una familia de dos hermanas, mientras que las otras tres no tienen hermanas.

En general, a cada hidra le podemos asociar tres números \( (h, m, s) \), donde \( h \) es la máxima altura de sus cabezas, \( m \) es el máximo número de cabezas hermanas de altura \( h \) y \( s \) es el número de familias con \( m \) cabezas hermanas de altura \( h \).

En la hidra anterior es \( (h, m, s) = (3, 2, 1) \).

Si a una hidra con valores \( (h, m, s) \) le cortamos en el asalto \( n \)-simo una cabeza de altura \( h \) según la estrategia, su familia de \( m \) cabezas ha perdido una, y pasa a tener \( m-1 \) cabezas. Por otra parte, la hidra genera \( \color{red}n \) familias de \( m-1 \) cabezas hermanas. Esto no influye en que los números de la nueva hidra son \( (h, m, s-1) \).

Tras un número finito de asaltos, llegaremos a una hidra de tipo \( (h, m, 1) \), es decir, con una única familia de \( m \) cabezas hermanas. Al cortar una de estas cabezas ya no habrá familias de cabezas de altura \( h \) con \( m \) hermanas, y la nueva hidra será de tipo \( (h, m-1, s) \), para cierto valor de \( s \), que volverá a disminuir una unidad en cada asalto y, al llegar a \( 0 \), se descuenta un valor a \( m \). Por lo tanto, tras un número finito de asaltos, llegaremos a una hidra \( (h, 1, 1) \), que tiene una única cabeza de altura \( h \).

Al cortar esta última cabeza, pasamos a una hidra de tipo \( (h-1, m, s) \), para ciertos valores de \( m \) y \( s \).

En resumen, la terna \( (h, m, s) \) se comporta como un cronómetro en cuenta atrás: cuando los segundos llegan a \( 0 \), se reduce un minuto y \( s \) aumenta, no hasta \( 59 \), sino hasta un número arbitrario de segundos que continúan la cuenta atrás. Así, al cabo de \( m \) minutos (cada uno con un número distinto de segundos), llegamos a \( m=0 \), y entonces se reduce una hora, mientras que los minutos y los segundos aumentan a valores arbitrarios, pero lo cierto es que al cabo de \( h \) horas de distinta duración, la hidra llega a tener una única cabeza de altura \( h=0 \), lo que significa que está muerta.

En términos de ordinales, esta estrategia funciona así: consideremos la Hidra de 5 cabezas que habíamos puesto como ejemplo al plantear el juego de Hércules, la que tiene ordinal

\( \omega^{\omega^2+1}+\omega+1 \).

El exponente \( 2 \) corresponde a un único grupo de \( 2 \) cabezas hermanas de altura \( 3 \).

Por lo tanto su "esperanza de vida" (si Hércules sigue la estrategia que estamos considerando) es \( (h, m, s){\color{red}=}  (3, 2, 1) \). Al cortarle una de las dos cabezas posibles pasamos a la Hidra de 5 cabezas

\( \omega^{\omega\cdot 2+1}+\omega+1 \),

cuya esperanza de vida es \( (3, 1, 2) \) (tiene dos cabezas sin hermanas de altura 3). En el asalto siguiente pasamos a la hidra de 7 cabezas

\( \omega^{\omega+4}+\omega+1 \),

con \( (h, m, s) = (3, 1, 1) \) y ahora, al cortar la última cabeza de altura 3, obtenemos la hidra de 10 cabezas

\( \omega^8+\omega+1 \),

con \( (h, m, s) = (2, 8, 1) \).

A partir de aquí podemos razonar en general. Supongamos que, tras el \( n \)-simo asalto, la Hidra tiene ordinal

\( \omega^a\cdot b + \omega^{a-1}\cdot c+\cdots \)

En nuestro ejemplo, tras el asalto \( n=3 \), tenemos \( (a, b, c) = (8, 1, 0) \).

En general, la Hidra tiene \( b \) familias de \( a \) cabezas hermanas de altura 2 y \( c \) familias de \( a-1 \) cabezas hermanas de altura 2.

Tras el asalto \( n+1 \), una de las \( b \) familias pierde un miembro, con lo que sólo quedan \( b-1 \) familias de \( a \) cabezas hermanas, pero el número \( c \) de familias de \( a-1 \) cabezas hermanas aumenta en \( 1 \) (por el grupo de \( a \) cabezas que ha perdido un miembro) y en \( n+1 \) por la regeneración, luego el resultado es

\( \omega^a(b-1)+\omega^{a-1}(c+n+2)+\cdots \)

Tras \( b \) asaltos, es decir, tras el asalto \( n+b \), el ordinal será:

\( \omega^{a-1}(c+(n+2)+(n+3)+\cdots + (n+b+1)))+\cdots = \omega^{a-1}\left(c+\dfrac{(2n+b+3)b}2\right)+\cdots \)

En otras palabras, si partimos de

\( \omega^a\cdot b + \omega^{a-1}\cdot c+\cdots \)

tras el asalto \( n \), entonces, tras el asalto \( n+b \), el exponente \( a \) se ha convertido en \( a-1 \) y \( b \) se ha convertido en \( c+(2n+b+3)b/2 \).

Aplicando esta fórmula podemos construir la tabla siguiente para la hidra de nuestro ejemplo:

\( \begin{array}{r|l}
n&\text{ordinal}\\
\hline
3&\omega^8+\omega+1\\
4&\omega^7\cdot 5+\omega+1\\
9&\omega^6\cdot 40+\omega+1\\
49&\omega^5\cdot 1\,220+\omega+1\\
1\,269&\omega^4\cdot 805\,810+\omega+1\\
807\,079&\omega^3\cdot 325\,688\,659\,655+\omega+1\\
325\,689\,466\,734&\omega^2\cdot 53\,036\,814\,370\,901\,491\,046\,740+\omega+1
\end{array} \)

En este punto, el \( \omega \) que estaba suelto (la cabeza de altura 1) hace que por primera vez sea \( c=1 \), luego al aplicar la fórmula una vez más resulta que, tras el asalto

\( n = 53\,036\,814\,371\,227\,180\,513\,474 \)

el ordinal es

\( \omega\cdot 1\,406\,451\,839\,324\,004\,993\,542\,381\,326\,234\,890\,768\,738\,031\,071+1 \)

y una última aplicación de la fórmula (también con \( c=1 \)) nos da que, tras el asalto

\( n = 1\,406\,451\,839\,324\,004\,993\,542\,434\,363\,049\,261\,995\,918\,544\,545, \)

la Hidra tiene ordinal finito:

\( 989\,053\,388\,168\,938\,379\,565\,429\,552\,367\,644\,648\,402\,300\,580\,972\,977\,512\,412\,313\,364\,046\,356\,366\,229\,560\,313\,533\,900\,782, \)

lo que significa que tiene ese número de cabezas hermanas que salen de su raíz. Según las reglas del juego, cada vez que Hércules corta una de ellas, no se produce ninguna regeneración, por lo que la Hidra muere al cabo de ese número de asaltos, es decir, que muere tras el asalto

\( 989\,053\,388\,168\,938\,379\,565\,429\,552\,367\,644\,648\,402\,300\,582\,379\,429\,351\,736\,318\,357\,588\,790\,729\,278\,822\,309\,452\,445\,327. \)

Si Hércules pudiera cortar \( 100 \) cabezas por segundo, tardaría aproximadamente \( 3.12\cdot 10^{80} \) años en matar a la Hidra. La edad del Universo se estima en \( 1.37\cdot 10^{10} \) años.

[Carlos Ivorra]

Creo que con lo visto hasta aquí podemos dar este hilo por terminado, sin perjuicio de que cualquier lector presente o futuro considere oportuno añadir más cosas en el hilo de comentarios:

https://foro.rinconmatematico.com/index.php?topic=123547.0

En dicho hilo hay también bastantes observaciones de interés sobre lo que he expuesto aquí. En especial quiero destacar esta demostración no finitista de argentinator de la buena ordenación de \( \epsilon_0 \):

Spoiler

Dada una sucesión \(\{\alpha_j\}_j\), tal que:
\[\alpha_j= \langle \alpha_{j,1},\ldots,\alpha_{j,m_j}\rangle,\]
donde \(m_j\) es la "longitud" de \(\alpha_j\),
y que cumple \(\alpha_j\succ\alpha_{j+1}\), todo \(j\),
podemos asegurar algunas cosas:

(Hecho 1) No puede ser que \(\alpha_{j,1}=0\) para algún \(j\).

Si esto no fuese así, habría algún \(j_0\) tal que
todos los valores \(\alpha_{j_0,k}=0\), para \(k=1,\ldots,m_{j_0}\).
Rastreando en la sucesión \(\alpha_{j_0}\) hacia adelante,
tendríamos que tener que \(\alpha_{h}=0\), para algún \(h\leq j_0+m_{j_0}\),
con lo cual la sucesión ya no podría ser decreciente a partir de \(h\) en adelante.

En particular:

(Hecho 2) Para todo \(j\): \(m_j\geq 1\).

(Hecho 3) La expresión \([\alpha_j]\), que llamé hiperlogaritmo natural de \(\alpha_j\), es no-creciente con el orden usual de \(\mathbb N\), y en particular \([\alpha_j]\) es constante a partir de un índice \(j=j_0\) dado en adelante.

(Hecho 4) Podemos asumir que \(j_0=1\), y también que \([\alpha_j] = constante > 0\).

Esto último lo tomamos así, porque \([\alpha_j]=0\) significa que \(\alpha_j\prec\omega\),
con lo cual \(\alpha_{j,1}=0\), y caemos en el Hecho 1.

_______________________________

Si \(m_{j+1}<m_j\) y \(\alpha_{j+1,k}=\alpha_{j,k}\), para \(k=1,\ldots, m_{j+1}\),
estamos en lo que en posts anteriores llamé "Caso A".

A partir de \(\alpha_j\), sólo puede haber una cantidad finita de ítems
\(\alpha_{j+1},\alpha_{j+2}\), etc., tal que su siguiente se obtiene de esa forma,
vale decir, meramente recortando el ítem anterior en una o más componentes.

Por lo tanto, para cada \(j\), existe un mínimo \(\nu(j)>j\)
tal que \(\alpha_{\nu(j)}\) no se obtiene recortando la "cola" \(\alpha_j\).

Si denotamos
\[\nu^{(n)}(j)=\underbrace{\nu\circ\cdots\circ\nu}_n(j),\]
obtenemos una subsucesión:
\[\{\alpha_{\nu^{(n)}(1)}\}_{n\in\mathbb N},\]
donde por ejemplo establecemos \(\alpha_{\nu^{(0)}(1)}=\alpha_1\).

Esta subsucesión, que reetiquetamos como \(\{\tilde\alpha_n\}\),
dicha sucesión satisface los Hechos 1 a 4,
y además el elemento  \(\tilde\alpha_{n+1}\) no se obtiene de \(\tilde\alpha_n\)
meramente "recortando" la cola de \( \tilde\alpha_n\).

S.p.d.g., voy a suponer que la sucesión original \(\{\alpha_j\}_j\)
ya viene con esta propiedad.

Esto quiere decir que \(\alpha_{j+1,k}=\alpha_{j,k}\) para \(k=1,\ldots,h_j\),
para cierto índice \(h_j\), que puede ser 0,
y \(\alpha_{j+1,h_j+1}\prec \alpha_{j,h_j+1}\).
Además, en este caso tiene que ocurrir que \(m_j > h_j\).

Es en una sucesión con esa estructura que voy a realizar el análisis subsiguiente.

___________________________


El objetivo es hallar una sucesión de la forma \(\{\alpha_{j_n,k_{j_n}}\}_n\)
que sea \(\succ\)-monótona estrictamente.

Llamemos esto el objetivo \(\fbox{X}\).

En ese caso, satisfaría la condición de ser una sucesión con un hiperlogaritmo natural menor que la original \(\{\alpha_j\}\).

En tal caso, se repetiría todo el proceso con la sucesión obtenida.

_____________________________________

Primero elijo \((n_1,k_{n_1})=(1,1)\).

Lo primero que hago es observar la primer "columna" \(\{\alpha_{j,1}\}_j\).

Si existe una subsucesión con índices \(\{j_k\}_k\) crecientes, tal que
\(\alpha_{j_k,1}\succ \alpha_{j_{k+1},1}\),
entonces estamos hemos obtenido \(\fbox X\).

De lo contrario,
significa que a partir de un mínimo índice \(i\),
todos los ordinales \(\alpha_{j,1}\) son iguales, \(j\geq i\).
En ese caso, para todo \(j\geq i\) hay componentes \(\alpha_{j,2}\)
en la 2da columna, porque si no, significaría que \(\alpha_j\) es constante para \(j\geq i\).
Asimismo, \(\alpha_{j,2}\neq 0\) para \(j\geq i\),
porque de lo contrario, en un número finito de pasos, \(\alpha_{j,2}\) no existiría.

Ahora observamos lo que ocurre en la 2da columna.
De nuevo, puede haber una subsucesión \(\{\alpha_{j_k,2}\}_k\)
tal que esté estrictamente ordenada por \(\succ\).
En cuyo caso, hemos cumplido el objetivo \(\fbox X\).

Si esto no ocurre, hay un mínimo índice \(\iota\geq i\)
a partir del cual todos los ordinales \(\alpha_{j,2}\) son iguales.

Si \(\iota > i\), entonces elegimos \((n_2,k_{n_2}) = (i,2)\).

De lo contrario seguimos buscando la primer columna \(q\)
en la que haya algún elemento \(\alpha_{\iota,q}\prec \alpha_{i,1}\).
En dicha columna, buscamos el primer índice \(\iota\)
tal que \(\alpha_{i,1}\succ\alpha_{\iota,q} \).

Tenemos que \(\iota\geq i\geq 1\), \(q> k_{n_1}=1\).

Notemos que tal columna \(q\) tiene que existir, porque \(\alpha_{i}\succ \alpha_{i+1}\) implica que estos dos elementos difieren en alguna de sus componentes.

Denotamos \((n_2,k_{n_2})=(\iota,q)\).

____________________

Ahora repetimos el procedimiento, analizando lo que ocurre con los elementos
\(\alpha_{j,k_{n_2}}\), tal que \(j\geq n_2\).

De nuevo, si hay una subsucesión \(\{\alpha_{j_n,k_{j_n}}\}_n\) ordenada por \(\succ\),
hemos logrado el objetivo \(\fbox X\).

De lo contrario, otra vez tenemos que \(\{\alpha_{j,k_{n_2}}\}_j\) es constante
para \(j\) "grande", debajo de la columna \(k_{n_2}\).

Afirmo que se puede volver a repetir todo el procedimiento,
hasta hallar un par \((n_3,k_{n_3}\), de modo que \(n_3>n_2\), \(k_{n_3}>k_ {n_2}\),
de modo que \(\alpha_{n_3,k_{n_3}}\prec\alpha_{n_2,k_{n_2}}\).

________________________

Este procedimiento de búsqueda se continúa en sucesivos pasos,
obteniendo pares de índices
\((n_1,k_{n_1}),(n_2,k_{n_2}),\ldots,(n_r,k_{n_r})\),
tal que \(\alpha_{n_t,k_{n_t}}\succ\alpha_{n_{t+1},k_{n_{t+1}}}\),
\(n_t<n_{t+1},k_{n_t}<k_{n_{t+1}}\), \(t=1,\ldots, r-1\),
hasta conseguir el objetivo \(\fbox X\),
en cuyo caso hemos terminado;
o bien se continúa con el proceso,
formando una sucesión de pares de índices \(\{n_r,k_{n_r}\}_{r\in\mathbb N}\),
tal que \(\alpha_{n_t,k_{n_t}}\succ\alpha_{n_{t+1},k_{n_{t+1}}}\),
\(n_t<n_{t+1},k_{n_t}<k_{n_{t+1}}\), todo \(t\in\mathbb N\).

Esta última sucesión de ordinales \(\{\alpha_{n_t,k_{n_t}}\}_{t=1}^\infty\)
se pueden considerar como un proceso de diagonalización.

Con dicha sucesión, conseguimos asimismo el objetivo \(\fbox X\).

Esto prueba lo que queríamos.

[cerrar]

Y aquí está una versión alternativa que redacté yo tras ver la prueba de argentinator:

Spoiler

Suponemos que no existen sucesiones estrictamente decrecientes de ordinales \( \prec \omega^{(n)} \) y vamos a ver que tampoco las hay de ordinales \( \prec \omega^{(n+1)} \).

Para ello suponemos que existe una: \( \{\alpha_j\}_j \), donde \( \alpha_j = \left<\alpha_{j,1},\ldots, \alpha_{j,m_j}\right> \) (notemos que \( m_j\geq 1 \) o, de lo contrario, \( \alpha_j = 0 \)).

Llamo a \( \alpha_{1,1} \) el "primer exponente" de la sucesión. Necesariamente \( \alpha_{1,1}\prec \omega^{(n)} \), pues si fuera \( \omega^{(n)}\preceq \alpha_{1,1} \), entonces \( \omega^{(n+1)}= \left<\omega^{(n)}\right>\preceq \left<\alpha_{1,1}\right>\preceq\alpha_1 \).

De hecho, \( \alpha_{j, k}\preceq \alpha_{j,1}\preceq \alpha_{1,1}\prec \omega^{(n)} \).

Afirmo que si existe una sucesión decreciente de ordinales \( \prec \omega^{(n+1)} \) con primer exponente \( \beta_0\prec \omega^{(n)} \), existe otra con primer exponente \( \beta_1\prec \beta_0 \). Esto nos da ya una contradicción, pues así podemos construir una sucesión \( \omega^{(n)}\succ \beta_0\succ \beta_1\succ \beta_2\succ \cdots\ \), en contra de lo supuesto.

Para ello partimos de nuestra sucesión \( \{\alpha_j\}_j \) con \( \beta_0 = \alpha_{1,1} \).

Si existe un \( j \) tal que \( \beta_1 = \alpha_{j,1}\prec \alpha_{1,1}=\beta_0 \), entonces la sucesión \( \alpha_j\succ \alpha_{j+1} \succ \alpha_{j+2}\succ \cdots \) es una sucesión decreciente de ordinales con primer exponente \( \beta_1 \).

En caso contrario tenemos que todos los \( \alpha_{j,1} \) son iguales a \( \beta_0 \). Esto obliga a que existan todos los \( \alpha_{j,2} \), o si no, sería \( \alpha_{j}\preceq \alpha_{j+1} \).

Podría darse el caso de que todos los \( \alpha_{j,2} \) fueran iguales. En tal caso tendrían que existir todos los \( \alpha_{j,3} \), que podrían ser todos iguales, en cuyo caso tendrían que existir todos los \( \alpha_{j, 4} \), etc.

Por lo tanto, tiene que existir un mínimo \( k\leq m_1 \) tal que, para cada \( 1\leq l< k \), se cumple que todos los \( \alpha_{j,l} \) son iguales a un mismo \( \gamma_l \), luego existen todos los \( \alpha_{j,k} \), pero \( k \) es el mínimo índice para el que no son todos iguales. En particular tiene que haber un mínimo \( j_0 \) tal que \( \beta_1 = \alpha_{j_0,k}\prec \alpha_{1, k} \).

Esto significa que nuestra sucesión es de la forma

\( \alpha_1 = \left<\gamma_1, \ldots, \gamma_{k-1}, \alpha_{1, k},\ldots, \alpha_{1, m_1}\right> \)
\( \alpha_2 = \left<\gamma_1, \ldots, \gamma_{k-1}, \alpha_{1, k},\ldots, \alpha_{2, m_2}\right> \)
\( \vdots \)
\( \alpha_{j_0} = \left<\gamma_1, \ldots, \gamma_{k-1}, \beta_1,\ldots, \alpha_{j_0, m_{j_0}}\right> \)
\( \alpha_{j_0+1} = \left<\gamma_1, \ldots, \gamma_{k-1}, \alpha_{j_0+1,k},\ldots, \alpha_{j_0+1, m_{j_0+1}}\right> \)
\( \vdots \)

Pero entonces, la sucesión

\( \alpha^*_{j_0} = \left<\beta_1,\ldots, \alpha_{j_0, m_{j_0}}\right> \)
\( \alpha^*_{j_0+1} = \left<\alpha_{j_0+1,k},\ldots, \alpha_{j_0+1, m_{j_0+1}}\right> \)
\( \vdots \)

que resulta de eliminar los términos comunes, es una sucesión decreciente de ordinales con primer exponente \( \beta_1 \), lo que termina la prueba.

[cerrar]

Quiero terminar agradeciendo a Eparoh su atenta lectura, gracias a la cual he podido corregir las muchas erratas que me ha señalado (ojalá todas).