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 0 (una forma de recursividad aritmética transfinita), y una aplicación final del teorema da la existencia de la función TREE 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 .
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 1 , T 2 son árboles enraizados con vértices etiquetados en X , decimos que T 1 es incrustable en T 2 y escribimos T 1 ≤ T 2 si hay un mapa inyectivo F desde los vértices de T 1 a los vértices de T 2 tal que
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 1 , T 2 ,… de árboles enraizados etiquetados en X , hay algo i < j de modo que T i ≤ T j .)
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:
Se sabe que árbol (1) = 1, árbol (2) = 5 y árbol (3) ≥ 844424930131960, [1] pero TREE (3) (donde el argumento especifica el número de etiquetas ; ver más abajo ) es mayor que
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 París-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 en los que 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 0 , [2]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 Π1
1-CA 0 , 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 no demostrable dentro de Π1
1-CA 0 .
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 ).
Suponga que P ( n ) es el enunciado:
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 entero positivo n , tome TREE ( n ) [*] como el m más grande de modo que tengamos lo siguiente:
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 : .El número de Graham , por ejemplo, es aproximadamente A 64 (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 .