Diferencia entre revisiones de «Teorema de los árboles de Kruskal»
Contenido eliminado Contenido añadido
Sin resumen de edición |
mSin resumen de edición |
||
Línea 9:
:Hay algo de ''m'' tal que si ''T''<sub>1</sub>,...,''T''<sub>''m''</sub> es una secuencia finita de árboles donde ''T''<sub>''k''</sub> tiene ''k''+''n'' vértices, a continuación, ''T''<sub>''i''</sub> ≤ ''T''<sub>''j''</sub> para algunos ''i'' < ''j''.
Esto es esencialmente un caso especial del teorema de Kruskal, donde se especifica el tamaño de la primera á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):
| |||