[argentinator]

Por inducción en \( k \)
me sale que \( \langle k\rangle_\infty<\langle k+1\rangle_\infty \).

Luego, por inducción en \( n \),
valdría que \( \omega^{(n)}<\omega^{(n+1)} \).

Lo segundo es un caso particular del hecho de que \( x_i<\left<x_1,\ldots, x_n\right>_\infty \) (la prueba está esbozada hacia el final de la respuesta #2), pues \( \omega^{(n+1)}= \omega^{\omega^{(n)}}= \left<\omega^{(n)}\right>_\infty \).

Claro, eso es lo que usé.

[Carlos Ivorra]

Claro, eso es lo que usé.

No entiendo. Si ya tienes que \( x_i<\left<x_1,\ldots, x_n\right>_\infty \), no necesitas ninguna inducción en \( n \). El caso \( n = 1 \) de esta desigualdad es \( x< \left<x\right>_\infty \), y particularizando a \( x = \omega^{(n)} \) tienes la desigualdad \( \omega^{(n)}<\omega^{(n+1)} \).

[argentinator]

Claro, eso es lo que usé.

No entiendo. Si ya tienes que \( x_i<\left<x_1,\ldots, x_n\right>_\infty \), no necesitas ninguna inducción en \( n \). El caso \( n = 1 \) de esta desigualdad es \( x< \left<x\right>_\infty \), y particularizando a \( x = \omega^{(n)} \) tienes la desigualdad \( \omega^{(n)}<\omega^{(n+1)} \).

Claro. Había pensado que de
\(\langle k\rangle _\infty< \langle k+1\rangle _\infty\)
deduzco que \(\langle k\rangle_\infty < \langle \ell\rangle_\infty\),
siempre que \(k<\ell\),
y que en particular
\(\omega^{(n)}<\omega^{(n+1)}\)
implica que
\( \omega^{(n+1)}=\langle\omega^{(n)}\rangle_\infty <\langle\omega^{(n+1)}\rangle_\infty=\omega^{(n+2)}\),
y de ahí la inducción en \(n\) para probar que la sucesión \(\omega^{(n)}\)
es estrictamente creciente (mirada en \(\mathbb N\)).

De hecho, tampoco necesito inducción para probar
\(\langle k\rangle_ \infty < \langle \ell\rangle_\infty\), cuando \(k<\ell\),
pues uso la monotonía del producto y la suma en \(\mathbb N\).

\(\langle k\rangle_\infty = \langle 0,\langle k\rangle_1\rangle_2 + 1=\langle 0,k\rangle_2 + 1=(0+k)(0+k+1)/2 + 0=k(k+1)/2\), que es creciente en  \(k\).

[Carlos Ivorra]

Claro, eso es lo que usé.

No entiendo. Si ya tienes que \( x_i<\left<x_1,\ldots, x_n\right>_\infty \), no necesitas ninguna inducción en \( n \). El caso \( n = 1 \) de esta desigualdad es \( x< \left<x\right>_\infty \), y particularizando a \( x = \omega^{(n)} \) tienes la desigualdad \( \omega^{(n)}<\omega^{(n+1)} \).

Claro. Había pensado que de
\(\langle k\rangle _\infty< \langle k+1\rangle _\infty\)
deduzco que \(\langle k\rangle_\infty < \langle \ell\rangle_\infty\),
siempre que \(k<\ell\),
y que en particular
\(\omega^{(n)}<\omega^{(n+1)}\)
implica que
\( \omega^{(n+1)}=\langle\omega^{(n)}\rangle_\infty <\langle\omega^{(n+1)}\rangle_\infty=\omega^{(n+2)}\),
y de ahí la inducción en \(n\) para probar que la sucesión \(\omega^{(n)}\)
es estrictamente creciente (mirada en \(\mathbb N\)).

De hecho, tampoco necesito inducción para probar
\(\langle k\rangle_ \infty < \langle \ell\rangle_\infty\), cuando \(k<\ell\),
pues uso la monotonía del producto y la suma en \(\mathbb N\).

\(\langle k\rangle_\infty = \langle 0,\langle k\rangle_1\rangle_2 + 1=(0+k)(0+k+1)/2 + 0=k(k+1)/2\), que es creciente en  \(k\).

Vale, es un camino alternativo. Tú te apoyas en la desigualdad \(\langle k\rangle_\infty < \langle \ell\rangle_\infty\) (con ángulos en los dos miembros), mientras que yo usaba la desigualdad \( k<\left<\ell\right>_\infty \), con ángulos sólo a la derecha.

[argentinator]

Pues a pesar de lo fea que es la biyección \(\langle x , y\rangle_2\),
parece que se pueden probar varias cosas respecto el orden usual de \(\mathbb N\).

Está muy linda esta cosa de Gentzen.
Igual parece que hay espacio para mejoras.

¿Podrías citar el artículo donde Gentzen publicó esto, así como las fuentes citadas que pusiste de Gödel y Gentzen sobre estos dichos?:

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

¿Y dónde es que Hilbert definió o explicó esto:?

Pero, más aún, tal conocimiento concreto (en el sentido de Hilbert)

¿Qué es "finitísticamente"?

[Carlos Ivorra]

Pues a pesar de lo fea que es la biyección \(\langle x , y\rangle_2\),
parece que se pueden probar varias cosas respecto el orden usual de \(\mathbb N\).

Justamente a esa biyección no la llamaría yo "fea". Se trata de la biyección natural entre \( \mathbb N \) y \( \mathbb N\times \mathbb N \) que se obtiene recorriendo el producto cartesiano en diagonal.

¿Podrías citar el artículo donde Gentzen publicó esto,

Los artículos originales de Gentzen están en alemán (mira el apartado de publicaciones aquí):

https://en.wikipedia.org/wiki/Gerhard_Gentzen

Yo, obviamente, no los he leído, y probablemente diferirán mucho del tratamiento que les estoy dando, que debe de ser algo más moderno. Lo que estoy contando lo estoy sacando de mi libro de Cálculo secuencial, que a su vez se basa en varios libros, principalmente (en lo que aquí nos ocupa) el de Takeuti, pero la forma concreta de presentar los ordinales se basa en técnicas usuales de codificar sucesiones de números naturales en la aritmética de Peano que son más o menos "de dominio público" en los libros de lógica y de teoría descriptiva de conjuntos.

así como las fuentes citadas que pusiste de Gödel y Gentzen sobre estos dichos?:

Pues ahora mismo no lo sé. Las he sacado de mi libro de Cálculo secuencial, pero ahora no recuerdo de dónde las saqué. Es posible que buscara en internet información sobre la polémica en torno a la prueba de Gentzen. El caso es que no me suena que las citas sean traducciones mías del inglés, y si eso es así reduciría bastante las fuentes posibles. Si las localizo te lo diré.

¿Y dónde es que Hilbert definió o explicó esto:?

Pero, más aún, tal conocimiento concreto (en el sentido de Hilbert)

Pues no lo sé. Habría que preguntárselo a Gödel. Hilbert tiene trabajos con reflexiones sobre la fundamentación de la matemática, y probablemente Gödel se referirá a ellos.

¿Qué es "finitísticamente"?

En principio, "finitismo" es admitir únicamente razonamientos con conjuntos finitos, aunque alguien puede declararse finitista y admitir hasta cierto punto "infinitos potenciales". Hay distintas formas de pensamiento finitismo que pueden oscilar entre el ultrafinitismo, que niega incluso que los números demasiado grandes tengan significado alguno, y un finitismo más laxo que admita tratar con conjuntos numerables en la medida en que lo que se diga sobre ellos pueda expresarse en términos de cálculos finitos. Entre medio tienes el finitismo estricto, que admite conjuntos finitos de cualquier tamaño (aunque sean mayores que el número de cosas del Universo), pero no conjuntos infinitos de ninguna clase, y otras versiones menos restrictivas.

Una forma más objetiva de clasificar finitismos es a través de las teorías axiomáticas que permiten formalizar los argumentos admitidos como finitistas. Por ejemplo, el finitismo más conservador se puede identificar con los argumentos formalizables en la Aritmética Recursiva Primitiva, mientras que un finitista que necesite toda la Aritmética de Peano para formalizar sus argumentos es más "liberal". Hay muchas teorías aritméticas más o menos restrictivas que pueden identificarse con finitismos más o menos rigurosos.

[argentinator]

Acá va mi demostración.

No sé bajo qué sistema axiomática lo probé, ni si es finitista, ni intuicionista, ni vaya-a-saber-uno-qué-diablosista.

Pero lo que más me preocupa es que esté mal, que es lo más probable... 

Acabo de publicarlo y ya vi mi error.

Asumo como estrictamente decrecientes unos ordinales que pueden ser iguales en realidad...
_____________________

Dado \(\alpha\), sea \([\alpha]\) el número \(n\) tal que
\[\omega^{(n)}\preceq \alpha\prec \omega^{(n+1)}.\]

Sea \(\{\alpha_j\}_{j=1}^\infty\) una sucesión de números naturales tales que \(\alpha_j \succ \alpha_{j+1}\).

El conjunto \(F=\{[\alpha_j]:j\in\mathbb N\}\) está acotado por \([\alpha_1]\).

Tenemos que \(\alpha\succeq \beta\) implica \([\alpha]\geq [\beta]\).

Sea \(N_1=\min(F)\).

Si \(j_1\) es el mínimo índice tal que \([ \alpha_{j_1}]=N_1\),
entonces \([ \alpha_j]=N_1\) para \(j\geq j_1\), pues \(\alpha_j\) es \(\prec\)-decreciente.

Sin pérdida de generalidad, supongamos que \(j_1=1\),
o sea, que todo \([\alpha_j]=N_1\).

Asumamos que \(N_1>0\).

Denotamos \(\alpha_j=\langle\alpha_{j,1},\alpha_{j,2},\ldots,\alpha_{j,m_j}\rangle\).

Como ningún \(\alpha_j\) es 0, tenemos \(m_j\geq 1\) para todo \(j\).

Debemos tener \([\alpha_{j,1}]<[\alpha_j]\), para todo \(j\).

Así que para la sucesión \(\{\alpha_{j,1}\}_{j\in\mathbb N}\),
podemos de nuevo obtener un mínimo \(N_2\) tal que
\([\alpha_{j,1}]=N_2\) a partir de cierto valor de \(j=j_2\) en adelante.
[En realidad no funciona porque no puedo asegurar que \(\alpha_{j,1}\) sea \(\prec\)-decreciente.]


Tiene que ocurrir que \(N_2<N_1\),
porque \([\alpha_{j,1}]<[\alpha_j]\), todo \(j\).

Asumamos que \(N_2>0\).

Repetimos lo anterior,
y nos quedamos sólo con los índices mayores de \(j_2\),
a partir del cual \([\alpha_{j,1}]\) es constante e igual a \(N_2\).

Si algún \(\alpha_{j,1}=0\),
significaría que \(N_2=0\), en contra de lo supuesto.

Así que podemos escribir
\(\alpha_{j,1}=\langle \alpha_{j,1,1},\ldots,\alpha_{m_{j,1}}\rangle\), todo \(j\).

De nuevo, \(\alpha_{j,1,1}\) está definido para todo \(j\),
porque ningún \(\alpha_{j,1}\) es 0.

Hallamos ahora un mínimo \(N_3\) tal que \([\alpha_{j,1,1}]=N_3\).

De nuevo, tiene que ocurrir que \(N_3<N_2\).

Asumimos que \(N_3>0\),
y repetimos el procedimiento.

_______

Vamos obteniendo una sucesión de naturales \(N_1>N_2>N_3>\cdots\),
lo cual es absurdo.

El error proviene de asumir que \(N_1>0,N_2>0\), etc.

Así que, algún \(N_q=0\).

Sin pérdida de generalidad, pensemos que \(N_1=0\).

Esto significa que \(\alpha_j < \omega\), para todo \(j\).

Por lo tanto, \(\alpha_j\) se corresponde con un ordinal finito.

Como son todos distintos, llegamos de nuevo a una contradicción.

[Carlos Ivorra]

[En realidad no funciona porque no puedo asegurar que \(\alpha_{j,1}\) sea \(\prec\)-decreciente.]

En efecto.    La sucesión es dececiente, pero no estrictamente, de modo que puede estabilizarse sin que se estabilice la sucesión de partida.

[argentinator]

De un elemento \(\alpha_j\) al siguiente \(\alpha_{j+1}\) de la sucesión,
la relación \(\succ\) significa uno de dos casos:

(A)
\(\alpha_{j+1}\) es una lista ordenada más "corta" que \(\alpha_j\).
Esto puede ocurrir a lo sumo en \(m_j\) pasos consecutivos
(acorde a la notación del post anterior).

(B)
Hay un mínimo índice \(h_j\) tal que \(\alpha_{j+1,h_j}\prec \alpha_{j,h_j}\).

Partiendo desde \(j=1\),
podemos construir una subcesión \(\alpha_{j_k}\)
tal que sólo cumpla el caso (B).

Así que, de aquí en más, voy a suponer que \(\{\alpha_j\}\) sólo cumple el caso (B)
para todo \(j\).

_______________________

Siguiendo la ideal del post anterior.

La sucesión \(\{\alpha_{j,1}\}\) está ordenada por \( \succeq\).

Puede ocurrir que tenga una subsucesión estrictamente decreciente, o no.

En el primer caso, me quedo con dicha subsucesión,
y la vuelvo a renombrar de modo que \(\{\alpha_{j,1}\}\)
sea estrictamente decreciente respecto \(j\),
y procede tal como hice allí en el post.

En caso contrario, a partir de un índice \(j\), todos los valores \(\alpha_j\)
son iguales, y no pierdo mucho en suponer que el primer índice donde ocurre es \(j=1\).
Me fijo, pues, en la sucesión \(\alpha_{j,2}\).
Debido a que \(\alpha_{j,1}\) es constante,
el número \(\alpha_{j,2}\) tiene que estar definido para todo \(j\),
de lo contrario tendríamos algún \(\alpha_j\) con longitud 1,
y su \(\alpha_{j+1,1}\prec \alpha_{j,1}\), contradicción (tienen que ser iguales).

De nuevo, o bien hay una subsucesión  \(\{\alpha_{j_k,2}\}_k\) estrictamente decreciente,
o bien es constante a partir de cierto índice \(k\) en adelante.
En el primer caso, nos quedamos con dicha subsucesión,
y en el segundo caso, analizamos \(\{\alpha_{j_k,3}\}\).
Seguimos así hasta llegar a \(\{\alpha_{j,m_1}\}\) si es necesario
(sí, el \(m_1\) de \(\alpha_1\)).

En algún momento llegaremos a un índice \(h\) tal que \(\alpha_{1,h}\succ\alpha_{j,h}\),
para todo \(j\), mientras que \(\alpha_{1,r}=\alpha_{j,r}\), todo \(r<h\), todo \(j\).

Para visualizarlo, he hecho como un barrido "vertical",
en el que las columnas \(r<h\) de las componentes de \(\alpha_j\)
tienen columnas con un elemento "constante",
y la única manera de hallar componentes \(\alpha_{j,h}\)
decrecientes es mirando en la columna \(h\) o a la derecha.

Ahora defino \(\tilde\alpha_j=\langle\alpha_{j,h},\ldots,\alpha_{j,m_j}\rangle\),
todo \(j\).
Me quedo con \(\gamma_1=\alpha_{1,h}\), \(\gamma_2=\alpha_{j_2,h}\),
donde \(j_2\) es el primer índice en el que \(\alpha_{1,h}\succ \alpha_{j_2,h}\).

A partir de acá realizo el mismo procedimiento,
aplicado a la sucesión \(\tilde\alpha_{j}\), para \(j\geq j_2\),
a fin de hallar un \(j_3\) que cumpla propiedades análogas a las que pinté de azul
en el párrafo anterior.

Así sigo, obteniendo una sucesión creciente de índices \(j_k\).

Lo que afirmo es que, con este procedimiento,
puedo obtener una sucesión de ordinales \(\alpha_{j,k_j}\), digamos,
tales que están estrictamente ordenados por \(\succ\).

En ese caso, todos ellos satisfarían la propiedad de que \([\alpha_{j,k_j}]<[\alpha_j]\),
claro está,
pero también, por ser estrictamente decreciente,
podemos volver a repetir el procedimiento otra vez,
yéndonos a una sucesión \(\{\alpha_{j,k_j,l_{k_j}}\}\)
estrictamente ordenada por \(\succ\), y con función \([...]\) estrictamente menor.

Con esta corrección, espero poder arreglar el error del post anterior,
y obtener esa sucesión de hiperexponentes \(N_1>N_2>N_3>...\) en forma decreciente,
que sería absurdo.

[Carlos Ivorra]

Esto es una versión (simplificada, a mi juicio) del argumento que acaba de dar argentinator.

Todo lo que sigue está mal, como bien ha señalado Eparoh más abajo.

Supongamos que no existen sucesiones de ordinales estrictamente decrecientes

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

que empiecen en \( \alpha_1\prec \omega^{(n)} \), y vamos a ver que tampoco las hay que empiecen en \( \alpha_1\prec \omega^{(n+1)} \).

Si \( \alpha_1 = \left<\alpha_{1,1},\ldots, \alpha_{1,m_1}\right>\prec \left<\omega^{(n)}\right> = \omega^{(n+1)} \), entonces \( \alpha_{1,m_1}\preceq \cdots \preceq \alpha_{1,1}\preceq \omega^{(n)}. \)

Además, tiene que ser \( \omega^n\succeq \alpha_{1,1}\succeq \alpha_{2, 1}\succeq \alpha_{3,1}\succeq \cdots \)

Si esta sucesión no se estabiliza tras un número finito de pasos, de ella podríamos extraer una subsucesión estrictamente decreciente, luego todos sus términos salvo a lo sumo el primero estarían por debajo de \( \omega^{(n)} \), en contra de lo supuesto, luego, eliminando un número finito de términos de la sucesión de partida, podemos suponer que todos los \( \alpha_{1, i} \) son iguales.

Pero entonces, que la sucesión sea decreciente implica que

\( \omega^{(n)}\succeq \alpha_{1,2}\succeq \alpha_{2, 2}\succeq \alpha_{3, 2}\succeq \cdots \)

(notemos que no puede ser que \( \alpha_i = \left<\alpha_{i,1}\right> \), pues entonces sería \( \alpha_i = \alpha_{i+1} \)) y, por el mismo argumento, eliminando un número finito de términos de la sucesión de partida podemos suponer que todos los \( \alpha_{i, 2} \) son iguales.

Repitiendo este argumento, llegamos a que, eliminando un número finito de términos de la sucesión de partida, todos los \( \alpha_{i,j} \), para \( j = 1, \ldots, m_1 \), son iguales, pero eso es imposible, porque entonces \( \alpha_1\preceq \alpha_2 \).

¡Yo la veo bien!, así que, en principio, 

Pero me sorprende que sea tan sencilla. Es posible que la única "objeción" contra ella es que sea "poco finitista", aunque, si es por eso, a mí me parece completamente aceptable. Tengo que pensar sobre esto, pero justo estos días va a ser cuando menos tiempo voy a tener.