Teorema del árbol de Kruskal

Mathematical theorem on well-quasi-ordering of finite trees

En las matemáticas , el árbol de Kruskal teorema afirma que el conjunto de finitos árboles sobre un bien cuasi-ordenado conjunto de etiquetas es en sí bien cuasi-ordenó bajo homeomorfa incrustación. El teorema fue conjeturado por Andrew Vázsonyi y probado por Joseph Kruskal  ( 1960 ); Crispin Nash-Williams  ( 1963 ) dio una breve prueba . Desde entonces se ha convertido en un ejemplo destacado en matemáticas inversas como una afirmación que no se puede probar dentro de ATR ₀ (una forma de recursividad aritmética transfinita), y una aplicación final del teorema da la existencia de la función TREE notoriamente de rápido crecimiento .

En 2004, el resultado se generalizó de árboles a gráficos 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 .

Declaración

Damos la versión probada por Nash-Williams; La formulación de Kruskal es algo más fuerte. Todos los árboles que consideramos son finitos.

Dado un árbol T con una raíz y vértices v , w dados , llame a w un sucesor de v si la ruta única de la raíz a w contiene v , y llame a w un sucesor inmediato de v si además la ruta de v a w contiene ningún otro vértice.

Tome X como un conjunto parcialmente ordenado . Si T ₁ , T ₂ son árboles con raíces con vértices etiquetados en X , decimos que T ₁ es incrustable en T ₂ y escribimos T ₁ ≤ T ₂ si hay un mapa inyectivo F desde los vértices de T ₁ a los vértices de T ₂ tal que

• Para todos los vértices v de T ₁ , la etiqueta de v precede a la etiqueta de F ( v ) ,
• Si w es un sucesor de v en T ₁ , entonces F ( w ) es un sucesor de F ( v ) , y
• Si w ₁ , w ₂ son dos sucesores inmediatos distintos de v , entonces la ruta de F ( w ₁ ) a F ( w ₂ ) en T ₂ contiene F ( v ) .

El teorema del árbol de Kruskal luego establece:

Si X está bien cuasi-ordenado , entonces el conjunto de árboles enraizados con etiquetas en X está bien cuasi-ordenado según el orden de incrustación definido anteriormente. (Es decir, dada cualquier secuencia infinita T ₁ , T ₂ ,… de árboles enraizados etiquetados en X , hay algo i < j de modo que T _i ≤ T _j .)

Función de árbol débil

Defina árbol ( n ) , la función de árbol débil, como la longitud de la secuencia más larga de árboles etiquetados con 1 (es decir, X = {1} ) de manera que:

• El árbol en la posición k en la secuencia no tiene más de k + n vértices, para todo k .
• Ningún árbol se puede incrustar homeomórficamente en ningún árbol que lo siga en la secuencia.

Se sabe que árbol (1) = 1, árbol (2) = 5 y árbol (3) ≥ 844424930131960, ^[1] pero TREE (3) (ver más abajo ) es más grande que${\displaystyle \mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{8}(7)}(7)}(7)}(7)}(7)}$

El trabajo de Friedman

Para un conjunto de etiquetas contables , el teorema del árbol de Kruskal se puede expresar y probar usando aritmética de segundo orden . Sin embargo, como el teorema de Goodstein o el teorema de Paris-Harrington , algunos casos especiales y variantes del teorema pueden expresarse en subsistemas de aritmética de segundo orden mucho más débiles que los subsistemas donde pueden demostrarse. Esto fue observado por primera vez por Harvey Friedman a principios de la década de 1980, un éxito temprano del entonces naciente campo de las matemáticas inversas. En el caso de que se considere que los árboles anteriores no están etiquetados (es decir, en el caso de que tenga el orden uno), Friedman descubrió que el resultado no se podía demostrar en ATR ₀ , ^[2]${\displaystyle X}$${\displaystyle X}$dando así el primer ejemplo de un resultado predicativo con una prueba demostrablemente impredicativa. ^[3] Este caso del teorema aún se puede demostrar en Π¹
₁-CA ₀ , pero al agregar una "condición de espacio" ^[4] a la definición del orden en los árboles de arriba, encontró una variación natural del teorema indemostrable en este sistema. ^{[5] [6]} Mucho más tarde, el teorema de Robertson-Seymour daría otro teorema indemostrable dentro de Π¹
₁-CA ₀ .

El análisis ordinal confirma la fuerza del teorema de Kruskal, con el ordinal de la teoría de la demostración del teorema igual al ordinal de Veblen pequeño (a veces confundido con el ordinal de Ackermann más pequeño ).

ÁRBOL (3)

Suponga que P ( n ) es el enunciado:

Hay algo m tal que si T ₁ , ..., T _m es una secuencia finita de árboles con raíces no etiquetadas donde T _k tiene n + k vértices, entonces T _i  ≤  T _j para algunos i < j .

Todos los enunciados P ( n ) son verdaderos como consecuencia del teorema de Kruskal y el lema de Kőnig . Para cada n , la aritmética de Peano puede probar que P ( n ) es verdadero, pero la aritmética de Peano no puede probar el enunciado " P ( n ) es verdadero para todos los n ". ^[7] Además, la longitud de la prueba más corta de P ( n ) en la aritmética de Peano crece extraordinariamente 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. El mínimo m para el que se cumple P ( n ) de manera similar crece extremadamente rápido con n .

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

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 T _i  ≤  T _j no se cumple para ningún i < j  ≤  m .

La secuencia TREE comienza TREE (1) = 1, TREE (2) = 3, luego de repente TREE (3) explota a un valor tan inmensamente grande que muchas otras constantes combinatorias "grandes", como la n (4), ^{[* *]} son extremadamente pequeños en comparación. De hecho, es mucho más grande que n ^{n (5)} (5). Un límite inferior para n (4), y por lo tanto una muy débil límite inferior para ÁRBOL (3), es A ^{A (187196)} (1), ^[9] , donde A () es una versión de la función de Ackermann : .${\displaystyle A(x)=2\uparrow ^{x-1}x}$El número de Graham , por ejemplo, es aproximadamente A ⁶⁴ (4), que es mucho más pequeño que el límite inferior A ^{A (187196)} (1). Se puede demostrar que la tasa de crecimiento de la función TREE está al menos en la jerarquía de rápido crecimiento . A ^{A (187196)} (1) es aproximadamente , donde g _x es la función de Graham .${\displaystyle f_{\theta (\Omega ^{\omega }\omega )}}$${\displaystyle g_{3\uparrow ^{187196}3}}$

Ver también

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

Notas

^ * Friedman originalmente denotó esta función porTR[n].

^ ** n(k) se define como la longitud de la secuencia más larga posible que se puede construir con unalfabeto de letrasktal que ningún bloque de letras x_i, ..., x_2isea ​​una subsecuencia de cualquier bloque x posterior_j, ..., x_2j. ^[10] .${\displaystyle n(1)=3,n(2)=11,\,{\textrm {and}}\,n(3)>2\uparrow ^{7197}158386}$

Referencias

Citas

1. "Secuencia de ÁRBOL" . Wiki de Googología | Fandom . Consultado el 9 de julio de 2020 .^{[se necesita una mejor fuente ]}
2. Simpson 1985, Teorema 1.8
3. Friedman, 2002, p. 60
4. Simpson 1985, definición 4.1
5. Simpson 1985, Teorema 5.14
6. Marcone, 2001, p. 8–9
7. Smith, 1985, p. 120
8. Friedman, Harvey (28 de marzo de 2006). "273: Sigma01 / óptimo / tamaño" . 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). "Enteros enormes 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). "Secuencias finitas largas" (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), incrustaciones internas de árboles finitos. Reflexiones sobre los fundamentos de las matemáticas (Stanford, CA, 1998) , Lect. Notes Log., 15 , Urbana, IL: Assoc. Símbolo. Lógica, págs. 60–91, MR  1943303
• Gallier, Jean H. (1991), "¿Qué tiene de especial el teorema de Kruskal y el ordinal Γ 0 ? Una revisión de algunos resultados en la teoría de la prueba" (PDF) , Ann. Pure Appl. Lógica , 53 (3): 199–260, doi : 10.1016 / 0168-0072 (91) 90022-E , MR  1129778
• Kruskal, JB (mayo de 1960), "El cuasi-ordenamiento de pozos, el teorema del árbol y la conjetura de Vazsonyi" (PDF) , Transactions of the American Mathematical Society , American Mathematical Society, 95 (2): 210-225, doi : 10.2307 / 1993287 , JSTOR  1993287 , MR  0111704
• Marcone, Alberto (2001). "Teoría de wqo y bqo en subsistemas de aritmética de segundo orden" (PDF) . Matemáticas inversas . 21 : 303–330.
• Nash-Williams, C. St. JA (1963), "Sobre árboles finitos de cuasi ordenamiento bien", Proc. Camb. Phil. Soc. , 59 (4): 833–835, doi : 10.1017 / S0305004100003844 , MR  0153601
• Rathjen, Michael; Weiermann, Andreas (1993). "Investigaciones teóricas de prueba sobre el teorema de Kruskal". Anales de lógica pura y aplicada . 60 (1): 49–88. doi : 10.1016 / 0168-0072 (93) 90192-g .
• Simpson, Stephen G. (1985), "No demostrabilidad de ciertas propiedades combinatorias de árboles finitos", en Harrington, LA; Morley, M .; Scedrov, A .; et al. (eds.), Investigación de Harvey Friedman sobre los fundamentos de las matemáticas , Estudios de lógica y fundamentos de las matemáticas, Holanda Septentrional, págs. 87-117
• Smith, Rick L. (1985), "Las fortalezas de la consistencia de algunas formas finitas de los teoremas de Higman y Kruskal", en Harrington, LA; Morley, M .; Scedrov, A .; et al. (eds.), Investigación de Harvey Friedman sobre los fundamentos de las matemáticas , Estudios de lógica y fundamentos de las matemáticas, Holanda Septentrional, págs. 119-136