For example, how to prove that TREE(n) for an extremely large n, like TREE(TREE(3)) is finite, in layman’s terms? Or is it impossible to understand the proof without being an expert in graph theory?
In: Mathematics
In general, anything that can be broken down into simple, solvable arithmetic operations is *always* finite. All TREE(n) is doing is a lot of exponent operations. If you put in a finite number, you always get a finite number out of them. That number can be ridiculously large, but it’s finite.
We get infinities in math when we start dealing with things like dividing by a number that gets closer and closer and closer to zero. Those are not simple arithmetic.
[deleted]
You’re correct in assuming that the existence of TREE(n) is not obvious. And just because we have an algorithm does not mean that the algorithm will complete – it could just get stuck in an infinite loop and we actually need a theorem which says that it will eventually end.
For TREE(n), the theorem is [Kruskal’s Tree Theorem](https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem). This is a result which puts constraints on lists of graphs and is maybe more easily seen with a different example. Consider Pythagorean Triples like (3,4,5) and (5,12,13), which are integer triples that fit in as the sides on a right triangle. If I have two triples, as above, then it is the case that either one is a multiple of the other or they are totally distinct from each other. So, for instance, (6,8,10) is a multiple of (3,4,5) and we can write (3,4,5) < (6,8,10), but we can’t write (3,4,5) < (5,12,13) or (5,12,13)<(3,4,5). A triple which is not a multiple of any other triple is called a Primitive Triple. So I might as the question: How comparable are Pythagorean Triples? For instance, if I have a list of 100 Triples can I guarantee that there will be at least *two* that are comparable? The answer to this is “No” because there are infinitely many primitive triples, so I can just use triples from the list of primitive triples and I’ll never run into a multiple.
If we have two trees, then we can sometimes compare them in a kinda similar way. If you have two trees T and S, then we can write T<S if we can view T as a smaller tree contained in S (in a technical way). So we can ask: If I have a list of trees T_1, T_2, T_3, etc then am I guaranteed to be able to find two trees so that T_i < T|_j when i<j. It’s a little different than the Pythagorean Triple example, but it’s the same kind of question that asks whether or not the size of a set can guarantee some kind of meaningful structure – which is common in math.
The answer to this is an affirmative. TREE(n) is the largest number that you *can’t* do this for when the trees have n-labels. But the theorem does guarantee that if you have too many such graphs, then you’ll always be able to compare at least two. As for why this theorem works, it’s actually not simple. I’m no graph theorist, but [people say](https://math.stackexchange.com/questions/2517207/proof-that-treen-where-n-3-is-finite) it is similar to Goodstein’s Theorem, which is another result dealing with huge numbers. In Goodstein’s Theorem, they find a fancy encoding for numbers which orders them in terms of the “complexity” of how they are written, and then show that the processes in Goodstein’s Theorem always make things less complex, which means that the sequences in Goodstein’s Theorem end. PBS Infinite Series had [an video](https://www.youtube.com/watch?v=oBOZ2WroiVY) on Goodstein’s theorem that explains it well.
Latest Answers