Teorema del árbol de Kruskal
Kruskal's tree theorem
- Fecha
- 1960 · fiabilidad baja
- Lugar
- Estados Unidos
- Autoría
- Joseph Kruskal
- Ámbito
- Saber y símbolos
Qué se descubrió
Teorema que establece que el conjunto de árboles finitos etiquetados con un conjunto bien cuasiordenado está a su vez bien cuasiordenado bajo inclusión homeomorfa; da lugar a la función de crecimiento TREE, de valores extraordinariamente grandes.
A qué dio paso
- Resultados sobre los límites de los sistemas axiomáticos (teoría de la prueba)
- La función TREE(3) como ejemplo de número de crecimiento extremadamente rápido
- Aplicaciones en teoría de la computabilidad
- Estudios de órdenes bien fundados en combinatoria