Teorema de los árboles de Kruskal

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.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 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.