¿Prueba de que TREE(n) donde n >= 3 es finito?

Question

Al leer en línea, generalmente parece aceptarse que TREE(n) donde n >= 3 es un número finíto, pero lo suficientemente grande como para ser incalculable y solo tiene límites inferiores extremadamente sueltos hoy en día. TREE(n) es la función definida por Harvey Friedman, basada en el teorema de árboles de Joseph Kruskal. Una definición simplificada:

"TREE(n) = la longitud máxima de un conjunto de árboles enraizados Tm con n etiquetas de vértices posibles, donde Tm tiene m o menos vértices, y los árboles subsiguientes no empotran homeomórficamente un árbol anterior."

Podemos mostrar trivialmente que TREE(1) = 1 y TREE(2) = 3.

Mi pregunta es, ¿cómo se puede saber que para valores de n mayores que 2, la serie de árboles posibles es finita? Si no podemos calcular la solución, ¿cómo sabemos que termina? Si hay un escrito en línea que describe la prueba de que estos números son finitos, por favor, envíame el enlace, estoy encontrando material de lectura limitado sobre la función TREE. Gracias.

Answer 1

La finitud de $TREE(n)$ para cada $n$ es una consecuencia del teorema del árbol de Kruskal. Hay varias demostraciones del teorema de Kruskal, incluyendo una particularmente corta por Nash-Williams.

En última instancia, la demostración - al igual que la demostración del teorema de Goodstein - consiste en mostrar que un orden parcial apropiado está bien fundamentado asignando invariantes a elementos del orden parcial; la demostración concluye entonces al mostrar que estos invariantes son de hecho ordinales, y por lo tanto el teorema se sigue de un principio de inducción transfinita apropiado (por ejemplo, el teorema de Goodstein se sigue de, y de hecho es equivalente en un sentido apropiado, a la bien-fundamentación de $\epsilon_0$). También hay una conexión entre tales argumentos y demostraciones de consistencia, comenzando con la demostración de Gentzen de la consistencia de PA a partir de un principio de inducción transfinita adecuado.

---

Por cierto, en el sentido de matemáticas reversas el teorema de Kruskal es bastante fuerte; no es demostrable en el sistema ATR$_0$, ni siquiera en el sistema más fuerte $\Pi^1_1$-CA$_0$, lo que lo convierte en algo bastante raro entre los hechos combinatorios estándar. La demostración de la improbabilidad apropiada se hace mostrando que el teorema de Kruskal implica que ciertos ordinales están bien fundamentados; estos ordinales son lo suficientemente grandes que (a la Gentzen) la inducción a lo largo de ellos implica la consistencia de ATR$_0$ y de $\Pi^1_1$-CA$_0$, por lo que según el teorema de incompletitud de Gödel ninguno de los sistemas puede demostrar el teorema de Kruskal.