Teorema del árbol de Kruskal

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

Historia

El teorema fue conjeturado por Andrew Vázsonyi y demostrado 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 demostrar en ATR₀ (una teoría aritmética de segundo orden con una forma de recursión aritmética transfinita).

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

Declaración

La versión dada aquí es la probada por Nash-Williams; La formulación de Kruskal es algo más contundente. 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 la ruta única desde la raíz hasta w contiene v< /span> y llame a w un sucesor inmediato de v si además la ruta de v a w no contiene ningún otro vértice.

Toma. X para ser un conjunto parcialmente ordenado. Si T₁, T₂ son árboles arraigados con vértices etiquetados X, decimos eso T₁ es inf-embeddable dentro T₂ y escribir ${\displaystyle T_{1}\leq T_{2}$ si hay un mapa inyectable F de los vértices T₁ a los vértices T₂ tal que:

• 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 dentro T₁Entonces ${\displaystyle F(w)}$ es un sucesor ${\displaystyle F(v)}$; y
• Si w₁, w₂ son dos sucesores inmediatos distintos de v, entonces el camino desde ${\displaystyle F(w_{1})}$ a ${\displaystyle F(w_{2}}$ dentro T₂ contiene ${\displaystyle F(v)}$.

El teorema del árbol de Kruskal establece:

Si X está bien ordenada, entonces el conjunto de árboles enraizados con etiquetas en X está bien ordenado bajo el orden inf-embeddable definido anteriormente. (Es decir, dada cualquier secuencia infinita T₁, T₂, ... de árboles arraigados etiquetados X, hay algunos ${\displaystyle i donej}$ así ${\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 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 en los que pueden demostrarse. Esto fue observado por primera vez por Harvey Friedman a principios de la década de 1980, uno de los primeros éxitos del entonces naciente campo de las matemáticas inversas. En el caso en que se considere que los árboles anteriores no están etiquetados (es decir, en el caso en que X tiene tamaño uno), Friedman encontró que el resultado no era demostrable en ATR0, dando así el primer ejemplo de un resultado predicativo con una prueba demostrablemente impredicativa. Este caso del teorema todavía se puede demostrar mediante Π¹
>< sub style="font-size:inherit;line-height:inherit;vertical-align:baseline">1-CA₀, pero agregando una "condición de brecha" Según la definición anterior del orden de los árboles, encontró una variación natural del teorema no demostrable en este sistema. Mucho más tarde, el teorema de Robertson-Seymour daría otro teorema que no se puede demostrar mediante Π¹
>₁-CA₀.

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

Función de árbol débil

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

Hay algunos m tal si T₁,... T_m es una secuencia finita de árboles arraigados sin etiquetar donde T_i tiene ${\displaystyle i+n}$ vertices, entonces ${\displaystyle T_{i}\leq T_{j}$ para algunos ${\displaystyle i donej}$.

Todas las declaraciones ${\displaystyle P(n)}$ son verdaderas como consecuencia del teorema de Kruskal y la lema de Kőnig. Por cada uno n, Peano aritmética puede probar que ${\displaystyle P(n)}$ es verdad, pero Peano aritmético no puede probar la declaración "${\displaystyle P(n)}$ es verdad para todos n". Además, la longitud de la prueba más corta de ${\displaystyle P(n)}$ en Peano aritmética crece fenomenalmente rápido como una función de n, mucho más rápido que cualquier función recursiva primitiva o la función Ackermann, por ejemplo. Lo menos m para la cual ${\displaystyle P(n)}$ sostiene de forma similar crece extremadamente rápido con n.

Define ${\displaystyle {\text{tree}(n) }$, la función del árbol débil, como la mayor m para que tengamos lo siguiente:

Hay una secuencia T₁,... T_m de árboles arraigados sin etiqueta, donde cada uno T_i tiene ${\displaystyle i+n}$ vertices, tal que ${\displaystyle T_{i}\leq T_{j}$ no se mantiene para ninguno ${\displaystyle i donej\leq m}$.

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

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

Función ÁRBOL

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

Hay una secuencia T₁,... T_m de árboles arraigados etiquetados de un conjunto de n etiquetas, donde cada T_i tiene i vertices, tal que ${\displaystyle T_{i}\leq T_{j}$ no se mantiene para ninguno ${\displaystyle i donej\leq m}$.

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