克鲁斯卡尔树定理

TREE函数、Kruskal树定理（英语：Kruskal's tree theorem）是逆数学的突出示例。由安德鲁·瓦兹尼（英语：Andrew Vázsonyi）推测并由约瑟夫·克鲁斯卡尔证明。

已隐藏部分未翻译内容，欢迎参与翻译。

In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered（英语：well-quasi-ordering） set of labels is itself well-quasi-ordered under homeomorphic（英语：homeomorphism (graph theory)） embedding. 在数学中，克鲁斯卡树定理指出，在准有序（英文：well-quasi-ordering）标签集上的有限树集合本身在同胚下也是良准有序的（英文：同胚（图论））嵌入。

历史该定理由安德鲁·瓦兹索尼（Andrew Vázsonyi）猜想并由约瑟夫·克鲁斯卡尔（Joseph Kruskal，1960）证明； Crispin Nash-Williams（1963）给了一个简短的证明。它从此成为逆向数学（英语：reverse math）中的一个突出例子，作为在 ATR0 内无法证明的陈述（算术超限递归（英语：arithmetic transfinite recursion）的一种形式）和有限（英语：finitary）应用该定理给出了快速增长的TREE 函数的存在性。

2004年，这个结果被从树推广到图，成为罗伯逊-西摩定理（英语：Robertson-Seymour theorem），这一结果在逆向数学中也被证明很重要，并导致了增长更快的SSCG 函数（英语： Friedman 的 SSCG 函数）。

陈述这里给出的版本是由 Nash-Williams 证明的；克鲁斯卡尔的表述要强一些。我们认为的所有树木都是有限的。

给定一棵有根的树T，并给定顶点v、w，如果从根到w 的唯一路径包含v，则称w 为v 的后继；如果从v 到w 的路径另外不包含v，则称w 为v 的直接后继其他顶点。

取X为偏序集（中文：partiallyorderedset）。如果 T1、T2 是顶点标记为 X 的有根树，我们说 T1 可 inf-embeddable 在 T2 中，并且如果存在从 T1 的顶点到 T2 的顶点的单射映射 F，则写 T1 ≤ T2，使得

弗里德曼的工作对于可数标签集 X X.克鲁斯卡树定理可以用二阶算术来表达和证明（中文：二阶算术）。然而，就像古德斯坦定理或巴黎-哈灵顿定理（英语：Paris-Harrington theorem）一样，该定理的一些特殊情况和变体可以用比可以证明它们的子系统弱得多的二阶算术子系统来表达。这是哈维·弗里德曼（Harvey Friedman）在 20 世纪 80 年代初首次观察到的，这是当时新兴的逆向数学领域的早期成功。在上面的树被认为是未标记的情况下（即，在 X X 有顺序一），Friedman 发现结果在 ATR0（英语：算术超限递归）,[2] 从而给出了第一个谓词（英语：impredicativity）结果的例子，并带有可证明的谓词证明.[3]此定理的这种情况仍可由 Π1 证明 1-CA0，但透过在上述树的顺序定义中添加“间隙条件”[4]，他发现该定理的自然变体在该系统中无法证明。[5][6]很久以后，罗伯森-西摩定理给了另一个无法由 Π1 证明的定理 1-CA0。

序数分析（中文：序数分析）证实了克鲁斯卡尔定理的强度，该定理的证明论序数等于小维勃伦序数（英文：小维勃伦序数）（有时与较小的阿克曼序数（英文：阿克曼序数）相混淆） ).[来源请求]

树(3) 假设 P(n) 是这样的语句：

存在一些 m，如果 T1,...,Tm 是未标记有根树的有限序列，其中 Tk 有 n+k 个顶点，则对于某些 i < j，Ti ≤ Tj。根据克鲁斯卡定理和柯尼格引理，所有陈述 P(n) 都是正确的。对于每个n，皮亚诺算术（英语：Peano axioms）可以证明P(n)为真，但皮亚诺算术不能证明“P(n)对于所有n都为真”这一命题。[7]此外，皮亚诺算术中 P(n) 的最短证明的长度作为 n 的函数增长得非常快，远远快于任何原始递归函数（英语：primitive recursive function）或阿克曼函数。 P(n) 所适用的最小 m 同样随 n 增长得非常快。

透过合并标签，弗里德曼定义了一个成长速度更快的函数。[8]对于正整数 n，取 TREE(n)[*] 为最大的 m，这样我们有：

有一个由 n 个标签集标记的有根树序列 T1,...,Tm，其中每个 Ti 最多有 i 个顶点，使得 Ti ≤ Tj 对于任何 i < j ≤ m 不成立。 TREE 序列开始为TREE(1) = 1, TREE(2) = 3，然后突然TREE(3) 爆炸到非常大的值，以至于许多其他“大”组合常数，例如Friedman 的n(4), [*相较之下，*] 非常小。事实上，它比 nn(5)(5) 大得多。 n(4) 的下界（因此 TREE(3) 的下界极弱）为 AA(187196)(1),[9]，其中 A(x) 采用一个参数，定义为 A(x, x)，其中A (k, n) 有两个参数，是阿克曼函数（英语：Ackermann's function）的一个特定版本，定义为： A(1, n) = 2n, A(k+1, 1) = A (k , 1), A(k+1, n+1) = A(k, A(k+1, n))。例如，葛立恒数远小于下限 AA(187196)(1)。可以证明函数TREE的成长率至少为 F θ （ Ω ω ω ） {\displaystyle f_{\theta (\Omega ^{\omega }\omega )}} 中的快速成长层次结构（中文：快速成长层次结构）。 AA(187196)(1) 大约为 G 3 ↑ 187196 3 {\displaystyle g_{3\uparrow ^{187196}3}}，其中 gx 是格雷厄姆函数（中文：格雷厄姆数）。

History

The theorem was conjectured by Andrew Vázsonyi（英语：Andrew Vázsonyi） and proved by Joseph Kruskal （1960）; a short proof was given by Crispin Nash-Williams （1963）. It has since become a prominent example in reverse mathematics（英语：reverse mathematics） as a statement that cannot be proved within ATR₀ (a form of arithmetical transfinite recursion（英语：arithmetical transfinite recursion）), and a finitary（英语：finitary） application of the theorem gives the existence of the fast-growing TREE function.

In 2004, the result was generalized from trees to graphs as the Robertson–Seymour theorem（英语：Robertson–Seymour theorem）, a result that has also proved important in reverse mathematics and leads to the even-faster-growing SSCG function（英语：Friedman's SSCG function）.

Statement

The version given here is that proven by Nash-Williams; Kruskal's formulation is somewhat stronger. All trees we consider are finite.

Given a tree $T$ with a root, and given vertices $v$ , $w$ , call $w$ a successor of $v$ if the unique path from the root to $w$ contains $v$ , and call $w$ an immediate successor of $v$ if additionally the path from $v$ to $w$ contains no other vertex.

Take $X$ to be a partially ordered set（英语：partially ordered set）. If $T 1$ , $T 2$ are rooted trees with vertices labeled in $X$ , we say that $T 1$ is inf-embeddable in $T 2$ and write $T 1 \leq T 2$ if there is an injective map $F$ from the vertices of $T 1$ to the vertices of $T 2$ such that

For all vertices $v$ of $T 1$ , the label of $v$ precedes the label of $F (v)$ ,
If $w$ is any successor of $v$ in $T 1$ , then $F (w)$ is a successor of $F (v)$ , and
If $w 1$ , $w 2$ are any two distinct immediate successors of $v$ , then the path from $F (w 1)$ to $F (w 2)$ in $T 2$ contains $F (v)$ .

Kruskal's tree theorem then states:

If $X$ is well-quasi-ordered（英语：well-quasi-ordering）, then the set of rooted trees with labels in $X$ is well-quasi-ordered under the inf-embeddable order defined above. (That is to say, given any infinite sequence $T 1, T 2, \dots$ of rooted trees labeled in $X$ , there is some $i < j$ so that $T i \leq T j$ .)

Weak tree function

Define $tree(n)$ , the weak tree function, as the length of the longest sequence of 1-labelled trees (i.e. $X = {1}$ ) such that:

The tree at position $k$ in the sequence has no more than $k + n$ vertices, for all $k$ .
No tree is homeomorphically embeddable into any tree following it in the sequence.

It is known that tree(1) = 2, tree(2) = 5, and tree(3) ≥ 844424930131960,^[1]^{[需要较佳来源]} but $TREE(3)$ (where the argument specifies the number of labels; see below（英语：Kruskal's tree theorem#TREE(3)）) is larger than $\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{8}(7)}(7)}(7)}(7)}(7)$

Friedman's work

For a countable label set $X$ , Kruskal's tree theorem can be expressed and proven using second-order arithmetic（英语：second-order arithmetic）. However, like 古德斯坦定理 or the Paris–Harrington theorem（英语：Paris–Harrington theorem）, some special cases and variants of the theorem can be expressed in subsystems of second-order arithmetic much weaker than the subsystems where they can be proved. This was first observed by Harvey Friedman（英语：Harvey Friedman） in the early 1980s, an early success of the then-nascent field of reverse mathematics. In the case where the trees above are taken to be unlabeled (that is, in the case where $X$ has order one), Friedman found that the result was unprovable in <span class="ilh-all " data-orig-title="ATR₀" data-lang-code="en" data-lang-name="英语" data-foreign-title="arithmetical transfinite recursion">[[:ATR₀|ATR₀]]（英语：arithmetical transfinite recursion）,^[2] thus giving the first example of a predicative（英语：impredicativity） result with a provably impredicative proof.^[3] This case of the theorem is still provable by Π1
1-CA₀, but by adding a "gap condition"^[4] to the definition of the order on trees above, he found a natural variation of the theorem unprovable in this system.^[5]^[6] Much later, the Robertson–Seymour theorem would give another theorem unprovable by Π1
1-CA₀.

Ordinal analysis（英语：Ordinal analysis） confirms the strength of Kruskal's theorem, with the proof-theoretic ordinal of the theorem equaling the small Veblen ordinal（英语：small Veblen ordinal） (sometimes confused with the smaller Ackermann ordinal（英语：Ackermann ordinal）).^{[来源请求]}

TREE(3)

Suppose that P(n) is the statement:

There is some m such that if T₁,...,T_m is a finite sequence of unlabeled rooted trees where T_k has n+k vertices, then T_i ≤ T_j for some i < j.

All the statements P(n) are true as a consequence of Kruskal's theorem and 柯尼格引理. For each n, Peano arithmetic（英语：Peano axioms） can prove that P(n) is true, but Peano arithmetic cannot prove the statement "P(n) is true for all n".^[7] Moreover the length of the shortest proof of P(n) in Peano arithmetic grows phenomenally fast as a function of n, far faster than any primitive recursive function（英语：primitive recursive function） or the 阿克曼函数 for example. The least m for which P(n) holds similarly grows extremely quickly with n.

By incorporating labels, Friedman defined a far faster-growing function.^[8] For a positive integer n, take TREE(n)^[*] to be the largest m so that we have the following:

There is a sequence T₁,...,T_m of rooted trees labelled from a set of n labels, where each T_i has at most i vertices, such that T_i ≤ T_j does not hold for any i < j ≤ m.

The TREE sequence begins TREE(1) = 1, TREE(2) = 3, then suddenly TREE(3) explodes to a value so immensely large that many other "large" combinatorial constants, such as Friedman's n(4),^[**] are extremely small by comparison. In fact, it is much larger than nⁿ⁽⁵⁾(5). A lower bound for n(4), and hence an extremely weak lower bound for TREE(3), is A^A(187196)(1),^[9] where A(x) taking one argument, is defined as A(x, x), where A(k, n), taking two arguments, is a particular version of Ackermann's function（英语：Ackermann's function） defined as: A(1, n) = 2n, A(k+1, 1) = A(k, 1), A(k+1, n+1) = A(k, A(k+1, n)). 葛立恒数, for example, is much smaller than the lower bound A^A(187196)(1). It can be shown that the growth-rate of the function TREE is at least $f_{\theta (\Omega ^{\omega }\omega )}$ in the fast-growing hierarchy（英语：fast-growing hierarchy）. A^A(187196)(1) is approximately $g_{3\uparrow ^{187196}3}$ , where g_x is Graham's function（英语：Graham's number）.

参见

Paris–Harrington theorem（英语：Paris–Harrington theorem）
Kanamori–McAloon theorem（英语：Kanamori–McAloon theorem）
Robertson–Seymour theorem（英语：Robertson–Seymour theorem）

注释

^{^ *} Friedman originally denoted this function by TR[n].

^{^ **} n(k) is defined as the length of the longest possible sequence that can be constructed with a k-letter alphabet such that no block of letters x_i,...,x_2i is a subsequence of any later block x_j,...,x_2j.^[10]

n(1)=3,n(2)=11,\,{\textrm {and}}\,n(3)>2\uparrow ^{7197}158386

.

Category:Trees (graph theory)（英语：Category:Trees (graph theory)）

参考

Citations

^ TREE sequence. Googology Wiki | Fandom. [9 July 2020]. （原始内容存档于2020-01-09）.
^ Simpson 1985, Theorem 1.8
^ Friedman 2002, p. 60
^ Simpson 1985, Definition 4.1
^ Simpson 1985, Theorem 5.14
^ Marcone 2001, p. 8–9
^ Smith 1985, p. 120
^ Friedman, Harvey. 273:Sigma01/optimal/size. Ohio State University Department of Maths. 28 March 2006 [8 August 2017]. （原始内容存档于2022-12-07）.
^ Friedman, Harvey M. Enormous Integers In Real Life (PDF). Ohio State University. 1 June 2000 [8 August 2017]. （原始内容存档 (PDF)于2016-10-18）.
^ Friedman, Harvey M. Long Finite Sequences (PDF). Ohio State University Department of Mathematics: 5, 48 (Thm.6.8). 8 October 1998 [8 August 2017]. （原始内容存档 (PDF)于2017-08-09）.

Bibliography

Friedman, Harvey M., Internal finite tree embeddings. Reflections on the foundations of mathematics (Stanford, CA, 1998), Lect. Notes Log. 15, Urbana, IL: Assoc. Symbol. Logic: 60–91, 2002, MR 1943303
Gallier, Jean H., What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory (PDF), Ann. Pure Appl. Logic, 1991, 53 (3): 199–260 [2022-11-07], MR 1129778, doi:10.1016/0168-0072(91)90022-E  , （原始内容存档 (PDF)于2023-02-03）
Kruskal, J. B., Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture (PDF), Transactions of the American Mathematical Society (American Mathematical Society), May 1960, 95 (2): 210–225 [2022-11-07], JSTOR 1993287, MR 0111704, doi:10.2307/1993287, （原始内容存档 (PDF)于2021-10-21）
Marcone, Alberto. Wqo and bqo theory in subsystems of second order arithmetic (PDF). Reverse Mathematics. 2001, 21: 303–330 [2022-11-07]. （原始内容存档 (PDF)于2022-05-08）.
Nash-Williams, C. St.J. A., On well-quasi-ordering finite trees, Proc. Camb. Phil. Soc., 1963, 59 (4): 833–835, Bibcode:1963PCPS...59..833N, MR 0153601, S2CID 251095188, doi:10.1017/S0305004100003844
Rathjen, Michael; Weiermann, Andreas. Proof-theoretic investigations on Kruskal's theorem. Annals of Pure and Applied Logic. 1993, 60 (1): 49–88. doi:10.1016/0168-0072(93)90192-g  .
Simpson, Stephen G., Nonprovability of certain combinatorial properties of finite trees, Harrington, L. A.; 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: 87–117, 1985
Smith, Rick L., The consistency strengths of some finite forms of the Higman and Kruskal theorems, Harrington, L. A.; 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: 119–136, 1985

[1] TREE sequence. Googology Wiki | Fandom. [9 July 2020]. （原始内容存档于2020-01-09）.

[2] Simpson 1985, Theorem 1.8

[3] Friedman 2002, p. 60

[4] Simpson 1985, Definition 4.1

[5] Simpson 1985, Theorem 5.14

[6] Marcone 2001, p. 8–9

[SmiA-7] Smith 1985, p. 120

[8] Friedman, Harvey. 273:Sigma01/optimal/size. Ohio State University Department of Maths. 28 March 2006 [8 August 2017]. （原始内容存档于2022-12-07）.

[9] Friedman, Harvey M. Enormous Integers In Real Life (PDF). Ohio State University. 1 June 2000 [8 August 2017]. （原始内容存档 (PDF)于2016-10-18）.

[10] Friedman, Harvey M. Long Finite Sequences (PDF). Ohio State University Department of Mathematics: 5, 48 (Thm.6.8). 8 October 1998 [8 August 2017]. （原始内容存档 (PDF)于2017-08-09）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[*]

[**]

[9]

[10]