TREE函数

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

定义

树的嵌入

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

• 删除一个叶子节点。
• 若某点只有两条边和它连接，删除这个点，用一条边连接与它相邻的两个顶点(即将两条相邻的边合并成一条)。

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

TREE(n)

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

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

1. 所有树的顶点至多有 $n$ 种不同的颜色；
2. $T_k$ 至多有 $k$ 个顶点；
3. 对于正整数 $k<l$，$T_k$ 不能嵌入到 $T_l$ 中。

tree(n)

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

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

1. $T_k$至多有$n+k$个顶点；
2. 对于正整数$k<l$，$T_k$不能嵌入到$T_l$中。

有限性证明

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

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

设 $(X,\le )$ 为一偏序集，若对于 $X$ 中任意无穷序列 $x_0,x_1,x_2,\cdots$，总存在 $i<j$ 使得 $x_i\le x_j$，则称 $\le$ 为集合 $X$ 上的一个良拟序。

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

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

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

取值

n 较小时

对于 $\mathrm{T}\mathrm{R}\mathrm{E}\mathrm{E}\mathrm{(}\mathrm{n}\mathrm{)}$，有：

• $\mathrm{T}\mathrm{R}\mathrm{E}\mathrm{E}\mathrm{(}\mathrm{1}\mathrm{)}\mathrm{=}\mathrm{1}$
• $\mathrm{T}\mathrm{R}\mathrm{E}\mathrm{E}\mathrm{(}\mathrm{2}\mathrm{)}\mathrm{=}\mathrm{3}$

对于$\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{(}\mathrm{n}\mathrm{)}$，有：

1. $\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{(}\mathrm{1}\mathrm{)}\mathrm{=}\mathrm{2}$
2. $\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{(}\mathrm{2}\mathrm{)}\mathrm{=}\mathrm{5}$
3. $\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{(}\mathrm{3}\mathrm{)}\mathrm{\ge }\mathrm{8}\mathrm{4}\mathrm{4},\mathrm{4}\mathrm{2}\mathrm{4},\mathrm{9}\mathrm{3}\mathrm{0},\mathrm{1}\mathrm{3}\mathrm{1},\mathrm{9}\mathrm{6}\mathrm{0}$

TREE(3)

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

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

HypCos 在这篇回答中给出了 $\mathrm{T}\mathrm{R}\mathrm{E}\mathrm{E}\mathrm{(}\mathrm{3}\mathrm{)}$ 的一个下界：

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

tree(4)

2025 年 5 月 24 日，HypCos 在这篇回答中给出了 $\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{(}\mathrm{4}\mathrm{)}$ 的一个下界：$\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{(}\mathrm{4}\mathrm{)}>H_{{\epsilon }_{{\omega }^{2}2+1}+\alpha }(2\uparrow \uparrow \uparrow 6)$

增长率

通过对树的嵌入关系进行编序(此处等待进一步说明)，我们可以得到 $\mathrm{T}\mathrm{R}\mathrm{E}\mathrm{E}\mathrm{(}\mathrm{n}\mathrm{)}$ 和 $\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{(}\mathrm{n}\mathrm{)}$ 的增长率分别为

\({\rm TREE(n)}\sim\varphi(\omega@\omega)\)

\({\rm tree(n)}\sim\varphi(1@\omega)\)