Teorema del árbol de Kruskal

Cuasiordenación correcta de árboles finitos

En matemáticas , el teorema del árbol de Kruskal establece que el conjunto de árboles finitos sobre un conjunto de etiquetas bien cuasi ordenado es en sí mismo bien cuasi ordenado bajo incrustación homeomórfica .

Historia

El teorema fue conjeturado por Andrew Vázsonyi y demostrado por Joseph Kruskal (1960); Crispin Nash-Williams (1963)  dio una prueba breve  . Desde entonces se ha convertido en un ejemplo destacado en matemáticas inversas como una afirmación que no se puede demostrar en ATR ₀ (una teoría aritmética de segundo orden con una forma de recursión transfinita aritmética ).

En 2004, el resultado se generalizó de los árboles a los grafos como el teorema de Robertson-Seymour , un resultado que también ha demostrado ser importante en matemáticas inversas y conduce a la función SSCG de crecimiento aún más rápido , que eclipsa a . Una aplicación finita del teorema da la existencia de la función TREE de crecimiento rápido . ${\displaystyle {\text{TREE}}(3)}$

Declaración

La versión que se da aquí es la que demostró Nash-Williams; la formulación de Kruskal es algo más sólida. Todos los árboles que consideramos son finitos.

Dado un árbol T con una raíz y dados los vértices v , w , llame a w un sucesor de v si el camino único desde la raíz hasta w contiene a v , y llame a w un sucesor inmediato de v si, además, el camino desde v hasta w no contiene ningún otro vértice.

Consideremos que X es un conjunto parcialmente ordenado . Si T ₁ , T ₂ son árboles con raíz cuyos vértices están etiquetados en X , decimos que T ₁ es inf-incrustable en T ₂ y escribimos si existe una función inyectiva F desde los vértices de T ₁ a los vértices de T ₂ tal que: ${\displaystyle T_{1}\leq T_{2}}$

• Para todos los vértices v de T ₁ , la etiqueta de v precede a la etiqueta de ; ${\displaystyle F(v)}$
• Si w es cualquier sucesor de v en T ₁ , entonces es un sucesor de ; y ${\displaystyle F(w)}$ ${\displaystyle F(v)}$
• Si w ₁ , w ₂ son dos sucesores inmediatos distintos de v , entonces el camino de a en T ₂ contiene . ${\displaystyle F(w_{1})}$ ${\displaystyle F(w_{2})}$ ${\displaystyle F(v)}$

El teorema del árbol de Kruskal establece entonces:

Si X está bien cuasi ordenado , entonces el conjunto de árboles enraizados con etiquetas en X está bien cuasi ordenado bajo el orden inf-incrustable definido anteriormente. (Es decir, dada cualquier secuencia infinita T ₁ , T ₂ , … de árboles enraizados etiquetados en X , hay alguno tal que .) ${\displaystyle i<j}$ ${\displaystyle T_{i}\leq T_{j}}$

La obra de Friedman

Para un conjunto de etiquetas contables X , el teorema del árbol de Kruskal se puede expresar y demostrar utilizando aritmética de segundo orden . Sin embargo, al igual que el teorema de Goodstein o el teorema de París-Harrington , algunos casos especiales y variantes del teorema se pueden expresar en subsistemas de aritmética de segundo orden mucho más débiles que los subsistemas donde se pueden demostrar. Esto fue observado por primera vez por Harvey Friedman a principios de la década de 1980, un éxito temprano del campo entonces naciente de las matemáticas inversas. En el caso en el que los árboles anteriores se toman como no etiquetados (es decir, en el caso en el que X tiene tamaño uno), Friedman encontró que el resultado era indemostrable en ATR ₀ , ^[1] dando así el primer ejemplo de un resultado predicativo con una prueba impredicativa demostrable. ^[2] Este caso del teorema todavía se puede demostrar mediante Π¹
₁-CA ₀ , pero al añadir una "condición de brecha" ^[3] a la definición del orden en los árboles anterior, encontró una variación natural del teorema indemostrable en este sistema. ^{[4] [5]} Mucho más tarde, el teorema de Robertson-Seymour daría otro teorema indemostrable por Π¹
₁-CA ₀ .

El análisis ordinal confirma la fuerza del teorema de Kruskal, con el ordinal de prueba teórica del teorema igual al pequeño ordinal de Veblen (a veces confundido con el ordinal más pequeño de Ackermann ). ^[6]

Función de árbol débil

Supongamos que la afirmación es: ${\displaystyle P(n)}$

Hay algún m tal que si T ₁ , ..., T _m es una secuencia finita de árboles enraizados no etiquetados donde T _i tiene vértices, entonces para algún . ${\displaystyle i+n}$ ${\displaystyle T_{i}\leq T_{j}}$ ${\displaystyle i<j}$

Todas las afirmaciones son verdaderas como consecuencia del teorema de Kruskal y del lema de König . Para cada n , la aritmética de Peano puede demostrar que es verdadera, pero la aritmética de Peano no puede demostrar que la afirmación " es verdadera para todo n ". ^[7] Además, la longitud de la prueba más corta de en la aritmética de Peano crece fenomenalmente rápido en función de n , mucho más rápido que cualquier función recursiva primitiva o la función de Ackermann , por ejemplo. ^{[ cita requerida ] La} m mínima para la cual se cumple crece de manera similar extremadamente rápido con n . ${\displaystyle P(n)}$ ${\displaystyle P(n)}$ ${\displaystyle P(n)}$ ${\displaystyle P(n)}$ ${\displaystyle P(n)}$

Definamos , la función de árbol débil, como la m más grande de modo que tengamos lo siguiente: ${\displaystyle {\text{tree}}(n)}$

Hay una secuencia T ₁ , ..., T _m de árboles enraizados no etiquetados, donde cada T _i tiene como máximo vértices, de modo que no se cumple para ningún . ${\displaystyle i+n}$ ${\displaystyle T_{i}\leq T_{j}}$ ${\displaystyle i<j\leq m}$

Se sabe que , , (aproximadamente 844 billones), (donde es el número de Graham ), y (donde el argumento especifica el número de etiquetas ; ver más abajo) es mayor que ${\displaystyle {\text{tree}}(1)=2}$ ${\displaystyle {\text{tree}}(2)=5}$ ${\displaystyle {\text{tree}}(3)\geq 844,424,930,131,960}$ ${\displaystyle {\text{tree}}(4)\gg g_{64}}$ ${\displaystyle g_{64}}$ ${\displaystyle {\text{TREE}}(3)}$ ${\displaystyle \mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{8}(7)}(7)}(7)}(7)}(7).}$

Para diferenciar las dos funciones, "ÁRBOL" (con todas las letras en mayúsculas) es la función ÁRBOL grande, y "árbol" (con todas las letras en minúsculas) es la función árbol débil.

Función ÁRBOL

Una secuencia de árboles con raíz etiquetados a partir de un conjunto de 3 etiquetas (azul < rojo < verde). El árbol n -ésimo de la secuencia contiene como máximo n vértices y ningún árbol es inf-incrustable dentro de ningún árbol posterior de la secuencia. TREE(3) se define como la longitud más larga posible de dicha secuencia.

Al incorporar etiquetas, Friedman definió una función de crecimiento mucho más rápido. ^[8] Para un entero positivo n , tome ^[a] como el m más grande de modo que tengamos lo siguiente: ${\displaystyle {\text{TREE}}(n)}$

Hay una secuencia T ₁ , ..., T _m de árboles enraizados etiquetados a partir de un conjunto de n etiquetas, donde cada T _i tiene como máximo i vértices, de modo que no se cumple para ningún . ${\displaystyle T_{i}\leq T_{j}}$ ${\displaystyle i<j\leq m}$

La secuencia TREE comienza , , y de repente, explota a un valor que es tan grande que muchas otras constantes combinatorias "grandes", como , , y el número de Graham , ^[b] de Friedman son extremadamente pequeñas en comparación. Un límite inferior para , y, por lo tanto, un límite inferior extremadamente débil para , es . ^{[c] [9]} El número de Graham, por ejemplo, es mucho más pequeño que el límite inferior , que es aproximadamente , donde es la función de Graham . ${\displaystyle {\text{TREE}}(1)=1}$ ${\displaystyle {\text{TREE}}(2)=3}$ ${\displaystyle {\text{TREE}}(3)}$ ${\displaystyle n(4)}$ ${\displaystyle n^{n(5)}(5)}$ ${\displaystyle n(4)}$ ${\displaystyle {\text{TREE}}(3)}$ ${\displaystyle A^{A(187196)}(1)}$ ${\displaystyle A^{A(187196)}(1)}$ ${\displaystyle g_{3\uparrow ^{187196}3}}$ ${\displaystyle g_{x}}$

Véase también

• Teorema de París-Harrington
• Teorema de Kanamori-McAloon
• Teorema de Robertson-Seymour

Notas

^ Friedman originalmente denotó esta función como TR [ n ].

^ b n ( k ) se define como la longitud de la secuencia más larga posible que se puede construir con un alfabeto de k letras tal que ningún bloque de letras x _i ,...,x _{2 i} sea una subsecuencia de ningún bloque posterior x _j ,...,x _{2 j} . ^[10] . ${\displaystyle n(1)=3,n(2)=11,\,{\textrm {and}}\,n(3)>2\uparrow ^{7197}158386}$

^ c A ( x ) tomando un argumento, se define como A ( x , x ), donde A ( k , n ), tomando dos argumentos, es una versión particular de la función de Ackermann definida como: A (1, n ) = 2 n , A ( k +1, 1) = A ( k , 1), A ( k +1, n +1) = A ( k , A ( k +1, n )).

Referencias

Citas

1. Simpson 1985, Teorema 1.8
2. Friedman 2002, pág. 60
3. Simpson 1985, Definición 4.1
4. Simpson 1985, Teorema 5.14
5. Marcone 2001, págs. 8-9
6. Rathjen y Weiermann 1993.
7. Smith 1985, pág. 120
8. Friedman, Harvey (28 de marzo de 2006), "273:Sigma01/optimal/size", Departamento de Matemáticas de la Universidad Estatal de Ohio , consultado el 8 de agosto de 2017
9. Friedman, Harvey M. (1 de junio de 2000), "Enormes números enteros en la vida real" (PDF) , Universidad Estatal de Ohio , consultado el 8 de agosto de 2017
10. Friedman, Harvey M. (8 de octubre de 1998), "Long Finite Sequences" (PDF) , Departamento de Matemáticas de la Universidad Estatal de Ohio , págs. 5, 48 (Thm.6.8) , consultado el 8 de agosto de 2017

Bibliografía

• Friedman, Harvey M. (2002), Incrustación interna de árboles finitos. Reflexiones sobre los fundamentos de las matemáticas (Stanford, CA, 1998) , Lect. Notes Log., vol. 15, Urbana, IL: Assoc. Symbol. Logic, págs. 60–91, MR  1943303
• Gallier, Jean H. (1991), "¿Qué tiene de especial el teorema de Kruskal y el ordinal Γ0? Un estudio de algunos resultados en teoría de la demostración" (PDF) , Ann. Pure Appl. Logic , 53 (3): 199–260, doi : 10.1016/0168-0072(91)90022-E , MR  1129778
• Kruskal, JB (mayo de 1960), "El cuasiordenamiento, el teorema del árbol y la conjetura de Vazsonyi" (PDF) , Transactions of the American Mathematical Society , 95 (2), American Mathematical Society: 210–225, doi :10.2307/1993287, JSTOR  1993287, MR  0111704
• Marcone, Alberto (2001), "Teoría wqo y bqo en subsistemas de aritmética de segundo orden" (PDF) , Reverse Mathematics , 21 : 303–330
• Nash-Williams, C. St.JA (1963), "Sobre árboles finitos bien ordenados", Proc. Camb. Phil. Soc. , 59 (4): 833–835, Bibcode :1963PCPS...59..833N, doi :10.1017/S0305004100003844, MR  0153601, S2CID  251095188
• Rathjen, Michael; Weiermann, Andreas (1993), "Investigaciones teóricas de prueba sobre el teorema de Kruskal" (PDF) , Anales de lógica pura y aplicada , 60 (1): 49–88, doi :10.1016/0168-0072(93)90192-G, MR  1212407
• Simpson, Stephen G. (1985), "No demostrabilidad de ciertas propiedades combinatorias de árboles finitos", en Harrington, LA; Morley, M.; Scedrov, A.; et al. (eds.), Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, págs. 87-117
• Smith, Rick L. (1985), "La fuerza de la consistencia de algunas formas finitas de los teoremas de Higman y Kruskal", en Harrington, LA; Morley, M.; Scedrov, A.; et al. (eds.), Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, págs. 119-136