克魯斯卡爾樹定理

TREE函數、Kruskal樹定理（）是逆數學的突出示例。由推測並由約瑟夫·克魯斯卡爾證明。

In , Kruskal's tree theorem states that the set of finite s over a  set of labels is itself well-quasi-ordered under  embedding.

History
The theorem was conjectured by  and proved by ; a short proof was given by  . It has since become a prominent example in  as a statement that cannot be proved within ATR0 (a form of ),  and a  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 , a result that has also proved important in reverse mathematics and leads to the even-faster-growing .

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  with a root, and given vertices , , call  a successor of  if the unique path from the root to  contains , and call  an immediate successor of  if additionally the path from  to  contains no other vertex.

Take  to be a . If ,  are rooted trees with vertices labeled in , we say that  is inf-embeddable in  and write  if there is an injective map  from the vertices of  to the vertices of  such that

For all vertices  of , the label of  precedes the label of ,
If  is any successor of  in , then  is a successor of , and
If ,  are any two distinct immediate successors of , then the path from  to  in  contains .

Kruskal's tree theorem then states: If  is , then the set of rooted trees with labels in  is well-quasi-ordered under the inf-embeddable order defined above. (That is to say, given any infinite sequence  of rooted trees labeled in , there is some  so that .)

Weak tree function
Define , the weak tree function, as the length of the longest sequence of 1-labelled trees (i.e. ) such that:

 The tree at position  in the sequence has no more than  vertices, for all .
 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, but  (where the argument specifies the number of labels; see ) is larger than

Friedman's work
For a countable label set , Kruskal's tree theorem can be expressed and proven using . However, like 古德斯坦定理 or the , 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  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  has order one), Friedman found that the result was unprovable in , thus giving the first example of a  result with a provably impredicative proof. This case of the theorem is still provable by Π-CA0, but by adding a "gap condition" to the definition of the order on trees above, he found a natural variation of the theorem unprovable in this system. Much later, the Robertson–Seymour theorem would give another theorem unprovable by Π-CA0.

 confirms the strength of Kruskal's theorem, with the proof-theoretic ordinal of the theorem equaling the  (sometimes confused with the smaller ).

TREE(3)
Suppose that P(n) is the statement:

There is some m such that if T1,...,Tm is a finite sequence of unlabeled rooted trees where Tk has n+k vertices, then Ti ≤ Tj for some i < j.

All the statements P(n) are true as a consequence of Kruskal's theorem and 柯尼格引理. For each n,  can prove that P(n) is true, but Peano arithmetic cannot prove the statement "P(n) is true for all n".  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  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. For a positive integer n, take TREE(n) to be the largest m so that we have the following:

There is a sequence T1,...,Tm of rooted trees labelled from a set of n labels, where each Ti has at most i vertices, such that Ti  ≤  Tj 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 nn(5)(5). A lower bound for n(4), and hence an extremely weak lower bound for TREE(3), is AA(187196)(1), where A(x) taking one argument, is defined as A(x, x), where A(k, n), taking two arguments, is a particular version of  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 AA(187196)(1). It can be shown that the growth-rate of the function TREE is at least  in the . AA(187196)(1) is approximately , where gx is .

参见

注释
 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 xi,...,x2i is a subsequence of any later block xj,...,x2j. .

數理邏輯
离散数学定理
序理论
良基性

參考 
Citations

Bibliography