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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

It is not true, that there is "no known upper bound" for TREE(3). Unilluminating examples of larger numbers are TREE(3)+1 and TREE(4).

A more interesting upper bound is Σ(2000), where Σ(n) is the busy beaver function. Here, it has been shown, that Σ(2000) > Loader's number ≫ TREE(3). So, I am pretty sure, that the bound of 2000 can be reduced, probably to less than 1000, but to be safe, I have used a generous overestimate.

Have you ever thought about using the first-order set theory for TREE(3) in symbols? The first-order set theory would reduce the "required number of symbols for TREE(3)" from 2^^1000 to less than 7901. Emk has shown, that Rayo(7901) > S(2⁶⁵⁵³⁶−1), where S(n) is the maximum shifts function. And, there are only 7901 symbols (which can be easily written down). Here, it has been shown, that S(n) ≥ Σ(n) for all n. And of course, 2⁶⁵⁵³⁶−1 ≫ 2000. So, Rayo(7901) is an extremely huge upper bound for TREE(3) and I suspect, that even Rayo(3000) is larger than TREE(3). — Preceding unsigned comment added by 84.154.64.199 (talk) 07:30, 13 October 2020 (UTC)[reply]

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)[reply]

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)[reply]

Maybe, you should use the first order set theory for TREE(3) in symbols. The first order set theory is Rayo(n), where n is the number of symbols.

Rayo(0) = 0

Rayo(10) ≥ 1

Rayo(30) ≥ 2

Rayo(56) ≥ 3

Rayo(861) > 4

Rayo(926) > 16

Rayo(984) > 65536

Rayo(1026) > 2⁶⁵⁵³⁶

Emk has shown that Rayo(7901) > S(2⁶⁵⁵³⁶−1), where S(n) is the maximum shifts function.

In its own turn, S(n) ≥ Σ(n) for all n.

In its own turn, Σ(2000) > Loader's number ≫ TREE(3).

So, if you use the first order set theory, then you only need a few thousand symbols for TREE(3). range for n: 1026 < n < 7901 — Preceding unsigned comment added by 84.154.72.51 (talk) 10:17, 12 August 2020 (UTC)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

Kruskal's tree theorem implies that TREE(k) exists for any k. The functions is believed to grow as fast as f_θ((Ω^ω)*ω)(k) in the fast-growing hiearchy. For more information see here: http://googology.wikia.com/wiki/TREE_sequence and eventually here: http://googology.wikia.com/wiki/Talk:TREE_sequence/Archive_1 78.192.45.127 (talk) 12:12, 31 July 2015 (UTC)[reply]

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)[reply]

I agree that the definition of A was unclear. I hope it is better now after my clarification originating from the Friedman reference source. Jens Ahlström (talk) 01:42, 11 January 2022 (UTC)[reply]

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)[reply]

I agree, but lack the knowledge to correct it. The article as written is mostly about the TREE() function, and describes barely more of Kruskal's tree theorem than is needed to explain the TREE() function's terminology. Even the subsection describing the weak tree() function fails to explain who defined it or for what purpose; is it any more relevant to Kruskal's trees than the rest of this? G. Steemson (talk) 19:31, 3 May 2020 (UTC)[reply]

Is TREE (3) prime?

I thought that if TREE (1) = 1 and TREE (2) = 3, is there any possibility for TREE (3) be prime? It is far, far larger that we can prove. But... if we could prove that TREE (3) is prime, it will be great. — Preceding unsigned comment added by Pasha20d00 (talk • contribs) 09:00, 19 August 2018 (UTC)[reply]

TREE (3) vs tree₄(tree₃(tree₂(tree(219620)))) - Which is bigger?

googology wiki: A larger lower bound of TREE(3) is tree₃(tree₂(tree(8))).

tree(1) = 2

tree(2) = 5

tree(3) ≥ 844424930131960

tree(4) > f_ε0(Graham's number)

tree(5) > f_Γ0(Graham's number)

tree(n) ≈ f_ϑ(Ω^ω)(n)

tree₂(n) = treeⁿ(n)

tree₃(n) = tree₂ⁿ(n)

tree₄(n) = tree₃ⁿ(n)

tree₄(tree₃(tree₂(tree(219620)))) = tree↑↑[tree↑↑[tree↑↑[...↑↑[tree(k)]...(k)](k)](k) with k layers, where k = tree₃(tree₂(tree(219620))).

In its own turn, tree₃(tree₂(tree(219620))) = tree^{tree^{tree^{...^tree(n)...}(n)}(n)}(n) with n layers, where n = tree^tree(219620)(tree(219620)). — Preceding unsigned comment added by 80.142.18.10 (talk) 07:54, 11 July 2020 (UTC)[reply]

A big exponent is much more significant than a big base.

The growth-rate of TREE(n) is at least $f_{\theta (\Omega ^{\omega }\omega )}$ in the fast-growing hierarchy.

What about $f_{\theta (\omega ^{\Omega }\omega )}$ as an upper bound of TREE(n)? — Preceding unsigned comment added by 80.142.18.10 (talk) 19:16, 11 July 2020 (UTC)[reply]

\Omega

is an epsilon number, so

\omega ^{\Omega }\omega =\Omega \omega

. C7XWiki (talk) 02:10, 6 April 2023 (UTC)[reply]

How large would be TREE(TREE(3))?

Is TREE(n) monotonic? — Preceding unsigned comment added by 83.4.136.110 (talk) 22:40, 18 August 2020 (UTC)[reply]

Yes. Any sequence of m-colored trees will also be a sequence of n-colored trees when n>m (with n-m unused colors). TREE is also strictly increasing because you can take any winning sequence for TREE(m) and append one node to the beginning with a new color. C7XWiki (talk) 02:10, 6 April 2023 (UTC)[reply]

TREE(3) vs g(n) - retry with the fast-growing hierarchy

What kind of $f_{\omega +1}(n)$ would be about as big as $f_{\theta (\Omega ^{\omega }\omega )}(3)$ ? — Preceding unsigned comment added by 84.154.65.66 (talk) 13:40, 19 October 2020 (UTC)[reply]

Incorrect definition of ≤ for TREE

In the section on Kruskal's tree theorem, the ≤ relation is defined including the requirement:

"For all vertices v of T1, the label of v precedes the label of F(v)"

I've seen this described as a "label dominating" embedding. Looking at Kruskal's original paper, this requirement seems to be present at one point (though I don't have the sophistication to tell whether it's carried through to the final result).

However, in the Wikipedia article the same definition for ≤ is apparently reused without further comment for the discussion on the TREE function, and as far as I can tell this is incorrect. Friedman explicitly mentions that the TREE function is based on a label preserving embedding, and I've seen comments pointing out that there's no need for labels with any ordering at all.

Should ≤ be redefined for the section on Friedman's work? There used to be a note to this effect but it was removed a few years ago. .froth. (talk) 18:08, 19 October 2020 (UTC)[reply]

I think you're right about label-preservingness, but we can choose an

X

to source labels from in a way that is compatible. Specifically set

X=(\{1,2,\ldots ,n\},=)

, comparison of labels is equality. According to (J. Van der Meeren, Connecting the Two Worlds: Well-partial-orders and Ordinal Notation Systems), Keuskal's theorem can be stated as follows: if

(X,\prec )

is a well-partial-ordering, then the set of trees with labels from

X

is well-partially-ordered under homeomorphic embeddability via label comparison

\prec

.

(\{1,2,\ldots ,n\},=)

has no infinite bad sequences because there are only finitely many elements. C7XWiki (talk) 02:10, 6 April 2023 (UTC)[reply]

Sentences

I don't know math, but English sentence structure, yes. The article says, "The least m for which P(n) holds similarly grows extremely quickly with n." There is no verb to this partial sentence. What about that least m? IAmNitpicking (talk)

Looking at it again, I see that it does have a verb, "grows", which I missed because "The least m for which P(n) holds similarly grows" is very peculiar, but valid. IAmNitpicking (talk) 02:15, 20 August 2021 (UTC)[reply]

Calibrating a related version

According to [2], ${\textrm {ACA}}_{0}$ proves ${\textrm {Kruskal}}\;{\textrm {for}}\;{\textrm {one-color-labeled}}\;{\textrm {trees}}\iff {\textrm {RFN}}_{\Pi _{1}^{1}}({\textrm {ACA}}_{0}+\Pi _{2}^{1}{\textrm {-BI}})$ . Should this be added? C7XWiki (talk) 15:54, 6 May 2023 (UTC)[reply]

About fω(n) symbols in strictly finite mathematics for TREE(n)?

Joseph's answer to What are Graham's number, TREE(3), SCG(13), SSCG(3), Rayo's number, and Fish Number 7? says, that it takes 2↑↑1000 symbols, to prove TREE(3) and 2↑↑↑↑↑5 symbols, to prove TREE(9). These 2 examples look like, it would take about f_ω(n) symbols to prove TREE(n).

So, since SSCG(3) >> TREE^TREE(3)(3), I think the number of symbols, to prove SSCG(3) is around SSCG(3). 94.31.88.138 (talk) 19:05, 15 November 2023 (UTC)[reply]