Teorema de los árboles de Kruskal

En matemáticas, el teorema de los árboles de Kruskal indica que el conjunto de árboles finitos más de un conjunto bien cuasi-ordenada de las etiquetas es en sí misma bien cuasi-ordenado (bajo incrustación homeomorfo). El teorema fue conjeturado por Andrew Vázsonyi y demostró por Joseph Kruskal (1960); una breve prueba fue dada por Nash-Williams (1963).

Lema de Higman es un caso especial de este teorema, de las cuales hay muchas generalizaciones que implican árboles con una incrustación plana, árboles infinitos, y así sucesivamente. Una generalización de los árboles a los gráficos arbitrarias está dado por el teorema de Robertson-Seymour.

Forma finita de Friedman

Friedman (2002) observó que el árbol teorema de Kruskal tiene casos especiales que se pueden exponer, pero no resultaron en primer orden la aritmética (a pesar de que fácilmente pueden ser probadas en segundo orden aritmética). Otra declaración similar es el teorema de París-Harrington.

Supongamos que P(n) es la declaración

Hay algo de m tal que si T₁,...,T_m es una secuencia finita de árboles donde T_k tiene k+n vértices, a continuación, T_i ≤ T_j para algunos i < j.

Esto es esencialmente un caso especial del teorema de Kruskal, donde se especifica el tamaño del primer árbol, y los árboles están obligado a crecer en tamaño en la tasa de crecimiento no trivial más simple. Para cada n, la aritmética de Peano puede demostrar que P(n) es cierto, pero la aritmética de Peano no puede probar la afirmación "P(n) es verdadera para todo n". Además, la prueba más corta de P(n) en la aritmética de Peano crece extraordinariamente rápido como una función de n; mucho más rápido que cualquier función recursiva primitiva o la función de Ackermann, por ejemplo.

Friedman también probó la siguiente forma finita del teorema de Kruskal para los árboles etiquetados sin fin entre los hermanos, parametrización del tamaño del conjunto de etiquetas en lugar de en el tamaño del primer árbol en la secuencia (y la incorporación homeomorfo, ≤, siendo ahora INF-y la etiqueta de preservación):

Para cada n, hay una tan grande que m si T₁,...,T_m es una secuencia finita de árboles con vértices etiquetados a partir de un conjunto de n etiquetas, donde cada T_i tiene en la mayoría de los vértices i, a continuación, T_i ≤ T_j para algunos i < j.

Este último teorema asegura la existencia de una función de rápido crecimiento que Friedman llama ÁRBOL, de tal manera que ÁRBOL(n) es la longitud de una secuencia más larga de n marcado con árboles T₁,...,T_m en el que cada T_i tiene en la mayoría de i vértices , y ningún árbol es integrable en un árbol después.

La secuencia ÁRBOL comienza ÁRBOL(1) = 1, ÁRBOL(2) = 3, entonces de repente ÁRBOL(3) explota a un valor tan enormemente grande que muchos otros "grandes" constantes combinatorios, como de Friedman n(4), son extremadamente pequeño en comparación. Una cota inferior para n(4), y por lo tanto una muy débil cota inferior para el ÁRBOL(3), es A(A(...A(1)...)), donde el número de As es A(187196), y A() es una versión de la función de Ackermann: A(x) = 2 [x + 1] x en hiperoperación. Número de Graham, por ejemplo, es de aproximadamente A⁶⁴(4), que es mucho menor que el límite inferior A^A(187196)(1). Se puede demostrar que la tasa de crecimiento del ÁRBOL de funciones sea superior al de la f_Γ0 función en la jerarquía de rápido crecimiento, donde Γ₀ es el ordinal Feferman-Schütte.

El ordinal que mide la fuerza del teorema de Kruskal es el pequeño ordinal Veblen (a veces confundido con el ordinal Ackermann más pequeño).

• Datos: Q3527100