TREE函数

TREE函数是由数理逻辑学家Harvey Friedman提出的图论函数。

定义

给定两棵树 $A$ 和 $B$ ，我们称 $A$ 能嵌入到 $B$ 中，如果 $B$ 能通过有限次以下操作得到 $A$ ：

例如，图中右边的两棵树均能嵌入到左边的树中，但它们不能互相嵌入。

TREE函数研究的是一类特殊的树，其每个顶点被赋予一个值，称为该点的“颜色”。

给定正整数n， $T R E E (n)$ 被定义为满足以下条件的“树列” ${T_{n}}$ 的最大长度：

$t r e e (n)$ (注意大小写)被称为弱tree函数，它研究的不是染色树，而是普通树。

给定正整数n， $t r e e (n)$ 被定义为满足以下条件的“树列” ${T_{n}}$ 的最大长度：

$T R E E (n)$ 和 $t r e e (n)$ 的序列总是有限的，这可由Kruskal树定理保证。

我们首先要引入良拟序(Well-quasi-ordering)的概念，它可以看成良序在一般偏序集上的推广。

设 $(X, \leq)$ 为一偏序集，若对于 $X$ 中任意无穷序列 $x_{0}, x_{1}, x_{2}, \dots$ ，总存在 $i < j$ 使得 $x_{i} \leq x_{j}$ ，则称 $\leq$ 为集合 $X$ 上的一个良拟序。

换句话说，若偏序集中不存在“无穷降链”，也不存在“无穷不可比较链”，则称该偏序为一个良拟序。

Kruskal树定理说明，树的嵌入关系是一个良拟序。

也就是说，任意无限棵树构成的序列中，必存在两棵树，前面的树能嵌入到后面的树中。这就证明了 $t r e e (n)$ 的有限性。

对于 $T R E E (n)$ ，有：

$T R E E (1) = 1$

$T R E E (2) = 3$

对于 $t r e e (n)$ ，有：

$t r e e (1) = 2$

$t r e e (2) = 5$

$t r e e (3) > 844, 424, 930, 131, 960$

和 $T R E E (1)$ 、 $T R E E (2)$ 仅有一位数的取值相比， $T R E E (3)$ 的值出现了“暴涨”，其远远超过了葛立恒数和Hydra(5)，这使它成为大数领域中最著名的数字之一。

右图是 $T R E E (3)$ 序列可能的前几项。

HypCos在这篇回答^[1]中给出了 $T R E E (3)$ 的一个下界：

${\rm TREE(3)}>H_{\varphi(1@\omega,3)\cdot\varphi(1@\omega)}({\rm tree(tree(3)+1)})$(其中H为哈代层级，下同)

2025年5月24日，HypCos在这篇回答^[2]中给出了 $t r e e (4)$ 的一个下界： $t r e e (4) > H_{ε_{ω^{2} 2 + 1} + α} (2 ↑ ↑ ↑ 6)$