Talk:Kruskal's tree theorem

another tree function?

Is written there function exact to exploding tree function described here: http://eusebeia.dyndns.org/veblen/etf.html If not which of these two functions is faster growing? —Preceding unsigned comment added by 91.94.67.142 (talk) 20:32, 8 May 2011 (UTC)

• That function is supposed to represent the Feferman-Schutte ordinal ($\Gamma _{0}$) in the slow-growing hierarchy; so it would be much slower growing than the "weak" TREE function (for unlabelled trees), which, if I understand correctly, corresponds to $\Gamma _{0}$ in the fast-growing hierarchy. The "strong" TREE function (for labelled trees) would increase even faster, since it corresponds to the small Veblen ordinal. Ben Standeven (talk) 22:56, 31 January 2012 (UTC)

Exact value

Just out of curiosity, is the exact value of TREE(3) known, or only bounds? More generally, is the theorem proving the existence of the TREE function constructive or non-constructive? --Dlevenstein (talk) 22:20, 31 July 2008 (UTC)

No exact value of TREE(k) for k > 2 is known. In the article FOM 272, Friedman sketches a proof of the following theorem:

THEOREM #. The above Proposition [entailing that TREE(3) exists] can be proved in strictly finite mathematics.

However, any such proof in ACA_0 + Pi12-BI must use at least 2^[1000] symbols.

Here 2^[1000] denotes what is often written as 2^^1000 in Knuth arrows; i.e., an exponential tower of 2's of height 1000.

Concerning the TREE function, however, Friedman states in this FOM article that the theorem establishing its existence (Theorem 6 in that article) "is not provable in Pi12-TI_0". According to his discussion there, this implies that the theorem has no predicative proof. Friedman writes elsewhere that "Pi12-TI_0 is certainly far stronger than normal accounts of constructivity, and in particular anything that Bishop used in his book."
--r.e.s. (talk) 03:11, 1 August 2008 (UTC)

Thanks. One other question, which I neglected to mention originally, even though I had thought about it then. Are there any known upper bounds for TREE(3)?

Appreciated, Dlevenstein (talk) 17:57, 2 August 2008 (UTC)

Not to my knowledge. BTW, I'm taking the expression "knowing the exact value" as referring to a representation in some conventional system of notation (as in the case of the cited lower bound). Of course TREE(3) is a well-defined computable mathematical object — one can write a program for it — so I suppose it is exactly "known" (or "knowable") in some peculiar Platonic sense. On the other hand, both TREE(3) and the cited lower bound are incomprehensibly large numbers, which one hesitates to call fully knowable in a realistic sense.
--r.e.s. (talk) 21:41, 2 August 2008 (UTC)

In answer to your question, I thought it was pretty obvious that I was referring to an exact value, using, eg, Knuth's up-arrow notation or Conway's chained arrow notation.

Thanks. My curiosity thirst has been quenched. :) Perhaps someday I'll learn to look these things up myself. --Dlevenstein (talk) 23:53, 2 August 2008 (UTC)

This is interesting stuff. If anyone can add more to this article, I'd love to read it. Fulvius (talk) 08:36, 30 October 2008 (UTC)

Definition of <=

This article depends on T_i < T_j to get the theorem statement, but this symbol isn't ever defined. I think either a link to a definition should be included, or a definition itself. I would edit the page--but I don't know the definition!

Dean p foster (talk) 00:28, 6 October 2009 (UTC)

I don't know for certain, but based on what I know of the meanings of homeomorphism and embedding, as well as a bit of playing around and seeing what leads to the statement being both true and non-trivial, and $TREE$ having the values shown, I think I have a definition that works. Just looking at the final form (the one used to define $TREE$), since that is the form I understand best, I think the definition is (or is equivalent to): $T_{i}\leq T_{j}$ if and only if there is a label-preserving isomorphism from a subdivision of $T_{i}$ to a subgraph of $T_{j}$. smithers888 (talk) 03:00, 24 January 2010 (UTC)

I'm unsure whether your educated guess is correct (for graph-theoretical trees), but I think it's best to go to reliable sources for precise definitions. For example, [Friedman, Harvey (1988), "The Incompleteness Phenomena", Proceedings of the AMS Centennial Celebration, August 8-12, 1988, AMS Centennial Publications, Volume II, Mathematics into the Twenty-first Century, 1992, pp. 73-79] discusses Kruskal's Tree Theorem under three different definitions of the term "tree": trees as partially ordered sets, trees as graphs, and trees as topological spaces ("one-dimensional complexes"). He states that Kruskal's theorem holds for trees of all three kinds, with correspondingly different definitions of the term "embedding". (The concept of homeomorphism as a continuous 1-1 mapping appears only in the topological version, of course.) Here's a paraphrased summary of the definitions in that article, for trees of the first two kinds:

Trees as partially ordered sets (this is the kind used to define Friedman's TREE function): A tree is a nonempty set V of vertices with a partial order ≤ on V such that (a) there is a unique least element (called the root), and (b) the set of predecessors of every vertex (under ≤) is linearly ordered under ≤. An embedding from tree T1 into tree T2 is a 1-1 mapping h from the set of vertices of T1 into the set of vertices of T2, such that h(a inf b) = h(a) inf h(b) for all vertices a, b in T1. (The latter is the so-called "inf-preserving" property.)

Trees as graphs: A tree is a connected graph with no cycles (and in this version, no root). An embedding of tree T1 into tree T2 is a 1-1 mapping h from the set of vertices of T1 into the set of vertices of T2, such that if ab and ac are edges in T1, where a, b, and c are distinct vertices, then the unique simple path from h(a) to h(b) does not cross the unique simple path from h(a) to h(c) except at h(a). (The latter is the graph-theoretic analog of the "inf-preserving" property.)

In all versions, the notation "T1 ≤ T2" means that there exists an embedding from T1 into T2. If the trees are labelled, then the embedding is required to be label-preserving as well.

The introduction of the present article states Kruskal's theorem in graph-theoretical terms, but Friedman says the original version was for trees regarded as partially ordered sets (as are Friedman's finite forms).

— r.e.s. (talk) 19:01, 25 January 2010 (UTC)

Does the Robertson-Seymour theorem generalize the strong form of Kruskal's result?

This is a bit outside my area, but I wasn't aware that the Robertson-Seymour theorem dealt with graphs which are labeled in any way. Does anyone know if they do? If not, then it would seem that they only generalize the application of Kruskal's result to unlabled trees. I looked into this a few years ago for other reasons, but couldn't really understand the methods of Robertson and Seymour. Kinser (talk) 16:50, 14 September 2010 (UTC)

Correcting TREE(2)

Not a big deal, but Friedman states in multiple posts that TREE(2) = 2, which agrees with my understanding of the function.Deedlit11 (talk) 22:04, 30 September 2010 (UTC)

He does state that, but I believe it's a typographical error. Consider the following sequence of three trees (T1, T2, T3), with vertices labelled from {1, 2}:

    T1:   1 
    T2:   2----2
    T3:   2

— r.e.s. (talk) 02:11, 1 October 2010 (UTC)

Ah yes, you're right. I don't know how I missed that.

Incidentally, I noticed a couple of quotes from Friedman:

"Also, numbers derived from Goodstein sequences or Paris/Harrington Ramsey theory, although bigger than n(4), are also completely UNNOTICEABLE in comparison to TREE[3]."

This suggests that TREE[3] is larger than F_e_0 (n) for reasonable values of n.

In another post, he says

"TR[3] blows up well beyond predicativity as analyzed by Feferman/Schutte."

suggesting that TREE[3] exceeds f_Gamma_0 (n) for reasonable values of n.

Would this be to vague to incorporate into the article? Deedlit11 (talk) 05:49, 1 October 2010 (UTC)

Faster growing functions?

Are there any known functions such that for sufficiently large n this function grows faster than TREE function? I don't mean uncomputable functions or functions clearly related to TREE function (like TREE(TREE(n))). Also, is TREE function total computable? Also I have question about understanding this function. I understand it like that: Length of longest sequence T_1,T_2... of trees such that Tn has at most n verticles and T_n isn't subset of T_m if n>m 79.191.122.39 (talk) 15:27, 5 February 2012 (UTC) If there is longest sequence in this function, then there is finite number of sequences of given length. Can we consider function f(n) which gives number of all tree sequences labeled from 1 to n which obey rules like in TREE function? 79.191.125.68 (talk) 13:07, 13 February 2012 (UTC)

Another one of Friedman's theorems involves a number called SCG(13) that is far larger than TREE(3). [1] --Ixfd64 (talk) 19:38, 25 September 2012 (UTC)

Friedman's n(4)

Exactly what is "Friedman's n(4)"? (Is the "n" defined somewhere on Wikipedia?) - Mike Rosoft (talk) 09:40, 5 August 2012 (UTC)

Friedman's article Long Finite Sequences treats the function n(k) in great detail. It's also described in Section 8 of his article Enormous Integers in Real Life. — r.e.s. (talk) 01:21, 7 August 2012 (UTC)

I've added a brief definition of n(k) to the article. --Ixfd64 (talk) 18:47, 17 September 2012 (UTC)

In that definition, the two-argument function A(.,.) has not been defined here (and could easily be mistaken for, say, the Ackermann–Péter function. Rather than adding more clutter by inserting the definition of A(.,.), I've simply changed "A(7198, 158386)" to the equivalent "2↑↑...↑158386 with 7197 ↑s" in terms of the already-introduced Knuth up-arrows.
— r.e.s. (talk) 03:47, 18 September 2012 (UTC)

TREE(4), etc ?

Has anyone said anything about high levels of the TREE() function than 3? I presume the function is defined for higher arguments, and would be even larger. (I'm not sure why anyone would want to, given how enormous TREE(3) is, but..) Jimw338 (talk) 15:03, 8 September 2012 (UTC)

definition of A(1)

It might be helpful to add that A(1) is to be interpreted as 2x1. I have searched for various variants on Ackermann's function and find this is at most suggested as a "possible" interpretation. Without this guidance, A(1) could be interpreted a s powers of 1 which of course will never exceed 1. — Preceding unsigned comment added by 74.37.130.75 (talk) 14:59, 3 May 2013 (UTC)

This article seems to be a bad WP:COATRACK

There's almost nothing in it about *Kruskal's* tree theorem and a lot about Friedman's. 86.127.138.234 (talk) 16:29, 27 February 2015 (UTC)