Why do we need TREE(n)?

127 Views Asked by At

According to this website, the following is said about the Tree-sequence:

The smallest nontrivial member of the sequence is the famously large TREE(3), notable because it is a number that appears in serious mathematics that is larger than Graham's number.

Why do we need functions where the two first terms are trivial, and the third is impossible to calculate? I find a bunch of questions regarding the TREE-function, so I'm assuming it's used (by some), I just can't see any application where it can be useful.

1

There are 1 best solutions below

0
On BEST ANSWER

The TREE function itself is not very important, I think - by which I mean that I don't know of any particularly interesting applications of it. (That's not a great indicator: there's a lot I don't know.)

However, it's created by invoking Friedman's finite form of Kruskal's tree theorem, which is a much more interesting theorem: the set of finite trees over a well-quasi-order is well-quasi-ordered under the obvious embedding. (This is a theorem of the form "something that we might hope would be true is in fact true", so it's always useful to have.)

That theorem is interesting in its own right because it can't be proved within $\mathrm{ATR} _0$ (a certain theory of arithmetic) and so there's a certain sense in which the theorem is not constructive. This is interesting for people who study the relative strength of proof-theoretic systems.