ÁRBOL(3)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 21 de octubre de 2022; la verificación requiere 1 edición .

ÁRBOL(3) [1] es un número grande , que es el límite superior de la solución en el teorema teórico de gráficos de Kruskal . ÁRBOL(3) es un número inimaginable de veces el número de Graham . El número ÁRBOL(3) es tan grande que las notaciones de flechas de Knuth y Conway no pueden escribirlo.

Teorema de Kruskal

En la teoría de grafos, un árbol es un gráfico en el que todos los vértices están conectados por aristas (posiblemente a través de otros vértices) y no hay ciclos (secuencias de aristas que conectan cualquier vértice consigo mismo). En este caso, los árboles están enraizados, es decir, tienen un cierto vértice: la raíz. Esta es una definición clara pero informal de un árbol . El teorema de Kruskal [2] establece la secuencia de árboles ÁRBOL( n ) descrita por las siguientes leyes:

1. Cada i -ésimo árbol tiene como máximo i vértices.
2. Los vértices tienen uno de n tipos; para TREE(3) conviene llamarlos "rojo", "verde" y "azul".
3. Ningún árbol debe ser un menor topológico de un árbol posterior.

TREE(1) da un solo árbol con un vértice: si intenta agregar otro con dos vértices, eliminar cualquiera de ellos dará como resultado el primero. ÁRBOL(2)=3, en esta secuencia un árbol con un vértice rojo, dos vértices azules y un vértice azul. Pero a partir de TREE(3), hay una verdadera explosión en la longitud de la secuencia. Sin embargo, el teorema de Kruskal establece que para cualquier n finito , la secuencia no será infinita .

Es interesante notar que el primer árbol tiene un vértice "rojo" e independientemente de n , ningún otro árbol tiene vértices "rojos". De lo contrario, al eliminar todos los vértices, excepto este "rojo", se obtendría el primer árbol.

Función de árbol débil

Definimos árbol( n ), una función de árbol débil [3] , como la longitud de la secuencia más larga de árboles con vértices del mismo color, descrita por las siguientes leyes:

1. Cada i -ésimo árbol tiene como máximo i + n vértices.
2. Ningún árbol debe ser un menor topológico de un árbol posterior.

Se sabe [3] que , , y ya es mayor que el número de Graham.

También se sabe [4] que TREE(3) es mucho más grande que (el superíndice en este caso denota una función iterada ).

ÁRBOL (3) escala de números

Un concepto erróneo común es la afirmación de Guinness World Records de que el número de Graham  es el número más grande jamás utilizado en una prueba matemática : esta información está desactualizada hace mucho tiempo, ya que el número ÁRBOL (3) también se usa en un contexto matemático, y es desproporcionadamente más grande que el número Graham. Para representar el número ÁRBOL(3), no sólo son inútiles las torres de grados , sino también las notaciones de Knuth y Conway . En la notación masiva de Bird, [5] TREE(3) se puede expresar aproximadamente como . La tasa de crecimiento global de la función TREE( n ) se estima en términos de una jerarquía de rápido crecimiento .

Al mismo tiempo, TREE(3) está lejos de ser el número más grande encontrado en trabajos matemáticos: en años posteriores, se describieron números más grandes, por ejemplo, como SSCG(3) , SCG(13) [6] , así como números especificados mediante funciones no computables, como el número de Rayo .

Notas

1. ↑ Jay Bennet. Envuelva su cabeza alrededor de la enormidad del número ÁRBOL (3) . Mecánica Popular (20 de octubre de 2017). Consultado el 27 de mayo de 2020. Archivado desde el original el 1 de julio de 2020. (indefinido)
2. ↑ TREE(3) y juegos imparciales | Proyectivo Complejo 4-Espacio . Consultado el 1 de febrero de 2020. Archivado desde el original el 1 de febrero de 2020. (indefinido)
3. ↑ 1 2 secuencia de ÁRBOL | Wiki de Google | fanatismo _ Consultado el 1 de febrero de 2020. Archivado desde el original el 9 de enero de 2020. (indefinido)
4. ↑ teoría de grafos - ¿Cómo crece TREE(3) para volverse tan grande? (Explicación de laicos) - Intercambio de pila de matemáticas . Consultado el 1 de febrero de 2020. Archivado desde el original el 1 de febrero de 2020. (indefinido)
5. ↑ Notación de matriz de Bird . Consultado el 20 de mayo de 2022. Archivado desde el original el 11 de noviembre de 2021. (indefinido)
6. ↑ Número de gráfico subcúbico . Consultado el 1 de febrero de 2020. Archivado desde el original el 1 de febrero de 2020. (indefinido)

Literatura

• Friedman, Harvey M. (2002), Incrustaciones internas de árboles finitos. Reflexiones sobre los fundamentos de las matemáticas (Stanford, CA, 1998) , vol. 15, Lect. Notas Log., Urbana, IL: Assoc. símbolo. Lógica, pág. 60–91 
• Gallier, Jean H. (1991), ¿Qué tienen de especial el teorema de Kruskal y el ordinal Γ 0 ? Una encuesta de algunos resultados en la teoría de la prueba , Ann. Manzana pura. Lógica T. 53(3): 199–260, doi : 10.1016 / 0168-0072 (91)90022-E , 
• Kruskal, JB (mayo de 1960), Cuasiordenamiento de pozos, el teorema del árbol y la conjetura de Vazsonyi , Transactions of the American Mathematical Society (Sociedad Matemática Estadounidense) . — T. 95 (2): 210–225, doi 1993287/10.2307: > 
• Marcone, Alberto. Teoría wqo y bqo en subsistemas de aritmética de segundo orden  //  Matemáticas inversas: revista. - 2001. - vol. 21 . - P. 303-330 .
• Nash-Williams, C. St. JA (1963), Sobre árboles finitos bien cuasi-ordenados , Proc. Camb. Fil. soc. V. 59 (4): 833–835 , DOI 10.1017/S0305004100003844 
• Rathjen, Michael; Weiermann, Andreas. Investigaciones teóricas de prueba sobre el teorema de Kruskal  (inglés)  // Annals of Pure and Applied Logic: revista. - 1993. - vol. 60 , núm. 1 . - P. 49-88 . -doi : 10.1016 / 0168-0072(93)90192-g .
• Simpson, Stephen G. (1985), Imposibilidad de demostrar ciertas propiedades combinatorias de árboles finitos, en Harrington, LA; Morley, M. & Scedrov, A. et al., Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, p. 87–117 
• Smith, Rick L. (1985), Las fortalezas de consistencia de algunas formas finitas de los teoremas de Higman y Kruskal, en Harrington, LA; Morley, M. & Scedrov, A. et al., Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, p. 119–136 

Grandes números
Números	gogol Número de Shannon googolplex número de sesgos número de Moser número de graham ÁRBOL(3) Número de Rayo
Funciones	Función de Ackermann Función Veblen Funciones psi de Buchholz tetración pentación hiperoperador Jerarquía de rápido crecimiento Jerarquía de crecimiento lento Jerarquía resistente
Notaciones	Notación de Steinhaus-Moser Notación de flecha Knuth Notación de flecha de Conway Notación masiva de Bowers