克魯斯卡爾樹定理

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 Joseph Kruskal . 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 w contains no other vertex.Take "T"2 such thatKruskal's tree theorem then states: If "Ti" ≤ "Tj".)Weak tree function.Define "X" = {1}) such that:It is known that tree(1) = 2, tree(2) = 5, and tree(3) ≥ 844424930131960, but TREE(3) (where the argument specifies the number of "labels"; see ) is larger than formula_1Friedman's work.For a countable label set formula_2, 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 formula_2 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 "T"1...,"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" &lt; "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 "T"1...,"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" &lt; "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""n"(5)(5). A lower bound for "n"(4), and hence an "extremely" weak lower bound for "TREE"(3), is "A""A"(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") = 2"n", "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 formula_4 in the . "A""A"(187196)(1) is approximately formula_5, where "g""x" 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 x"i"...,x2"i" is a subsequence of any later block x"j"...,x2"j". formula_6.