Wiki Googologie
Advertisement
Wiki Googologie

TREE(3) est un très grand nombre défini avec une fonction TREE à croissance rapide issue de la théorie des graphes, définie par le logicien mathématique Harvey Friedman.[1][2] Friedman a prouvé que la fonction domine éventuellement toutes les fonctions récursives prouvées totales dans le système .[1]

TREE(3) est remarquable parce que c'est un nombre qui apparaît dans les mathématiques sérieuses et qui est plus grand que le nombre de Graham.

Définition

TREE(n)

Supposons que nous ayons une séquence de arbre étiqueté comme k, T1, T2 ... avec les propriétés suivantes :

  1. Chaque arbre Ti a au plus i sommets.
  2. Aucun arbre qui préserve l'inf et l'étiquette ne peut être intégré dans un arbre qui le suit dans la séquence.

Le théorème des arbres de Kruskal affirme qu'une telle séquence ne peut être infinie.

Harvey Friedman a développé cette idée en posant la question suivante : étant donné un certain k, quelle est la longueur maximale d'une telle séquence ?

Cette longueur maximale est une fonction de k, et est appelée TREE(k). Les deux premières valeurs sont TREE(1) = 1 et TREE(2) = 3. La valeur suivante, TREE(3), est fameusement très grande. Elle dépasse largement le nombre de Graham et nn(5)(5).[3]

tree(n)

La fonction tree faible, tree(n), est définie comme la longueur de la plus longue séquence d'arbres étiquetés 1 telle que :

  1. Chaque arbre à la position k (pour tout k) n'a pas plus de k + n sommets.
  2. Aucun arbre n'est homéomorphiquement intégrable dans tout arbre qui le suit dans la séquence.

Analyse

On sait que tree(3) > 1010. L'évaluation de la borne inférieure de la fonction tree est difficile, et il y a tellement de déclarations douteuses à leur sujet sans montrer une preuve ou la source de la preuve. Bien qu'il existe peu de résultats connus, c'est-à-dire d'affirmations prouvées, concernant les limites inférieures de la fonction tree, un mathématicien spécialisé dans la théorie de la récursion Takayuki Kihara a vérifié que tree(4) est supérieur au nombre de Graham.[4] Il a introduit une hiérarchie treen de grandes fonctions indexées par les ordinaux n ≤ ω + 1 associée à une hiérarchie d'arbres binaires équipés d'un codage fixe d'une suite de nombres naturels, et a estimé précisément la hiérarchie en termes de hiérarchie de croissance rapide. La signification de ses travaux est qu'il a explicitement estimé la valeur des grandes fonctions combinatoires.

De plus, Kihara a développé la méthode pour estimer précisément la hiérarchie treen étendue aux ordinaux n < Γ0 associés à une hiérarchie d'arbres ternaires équipés d'un codage fixe de la hiérarchie de Veblen, et a vérifié que tree(4) > et tree(5) > par rapport au système canonique des séquences fondamentales, où G désigne le nombre de Graham.[5] Le résultat estime explicitement les limites inférieures des valeurs spécifiques de la fonction tree.

Comme conséquence de l'argument précis, Kihara a obtenu une inégalité stricte tree(1.0001n+2) > fSVO(n) pour n ≥ 3, où SVO désigne le petit ordinal de Veblen.

TREE(3) est beaucoup plus grand que tree(G).[5]

Dans l'article de wikipedia, Kruskal's tree theorem, il est écrit (consulté le 7 juillet 2021) que "It can be shown that the growth-rate of the function TREE is at least in the fast-growing hierarchy", mais cela n'a jamais été prouvé, et donc l'affirmation "It can be shown" est incorrecte, sauf si la preuve est démontrée. Voir article anglais pour plus de détails.

Vidéos

Source: Théorème de Kruskal et des arbres, LMSB#5

Références

  1. 1,0 et 1,1 H. Friedman, [FOM] 273:Sigma01/optimal/size
  2. H. Friedman, [FOM] n(3) < Graham's number < n(4) < TREE(3)
  3. How large is TREE(3), mathoverflow
  4. T. Kihara, Preuve que tree(4) > Nombre de Graham, conférence en japonais à YouTube, 05/2020.
  5. 5,0 et 5,1 T. Kihara, Lower bounds for tree(4) and tree(5), とりマセ Σ^0_2 (Le blog de Kihara), 05/2020.
Advertisement