What if in Graham’s Number every “3” was replaced by “tree(3)” instead? How big is this number? Greater than Rayo’s number? Greater than every current named number?
[Math] How Big would “Graham’s Tree” be
big numbers
Related Solutions
Just getting $3 \uparrow\uparrow\uparrow 3$, which is a power tower of $3 \uparrow 3 \uparrow 3=3^{27}\ \ =7625597484987\ \ 3$'s to be a handy number takes $7625597484985$ applications of the $\log$ to get to $3^3=27$. The logarithm is woefully inadequate for this purpose.
The concept of $\log^*$ is a step in the right direction, but still not enough. We have $\log^* 3 \uparrow\uparrow\uparrow 3=7625597484985$, which isn't handy, but $\log \log^* 3 \uparrow\uparrow\uparrow 3=27$ is. Unfortunately we have a lot more uparrows to go. We probably need to define $\log^{**}$ as the number of times you apply $\log^*$ to get handy, then $\log^{***}$, etc. I suspect we need another (several) layers-define $\log^\&$ as the number of stars you have to put on $\log$ to get a handy number in one go. I have no idea how to do the computation, or even what sort of data structure is appropriate.
The finiteness of $TREE(n)$ for each $n$ is a consequence of Kruskal's tree theorem. There are various proofs of Kruskal's theorem, including a particularly short one by Nash-Williams.
Ultimately, the proof - similarly to the proof of Goodstein's theorem - amounts to showing that an appropriate partial order is well-founded by assigning invariants to elements of the partial order; the proof then concludes by showing that these invariants are in fact ordinals, and so the theorem follows from an appropriate transfinite induction principle (e.g. Goodstein's theorem follows from, and is in fact equivalent to in an appropriate sense, the well-foundedness of $\epsilon_0$). There is also a connection between such arguments and consistency proofs, beginning with Gentzen's proof of the consistency of PA from an appropriate transfinite induction principle.
Incidentally, in the sense of reverse mathematics Kruskal's theorem is quite strong; it is not provable in the system ATR$_0$, or even in the stronger system $\Pi^1_1$-CA$_0$, making it quite rare amongst standard combinatorial facts. The proof of appropriate unprovability goes by showing that Kruskal's theorem implies that certain ordinals are well-founded; these ordinals are large enough that (a la Gentzen) induction along them implies the consistency of ATR$_0$ and of $\Pi^1_1$-CA$_0$, so by Godel's incompleteness theorem neither system can prove Kruskal's theorem.
Best Answer
The TREE function grows much much faster than any construction of knuth up arrows. Because of this, inserting the TREE function into Grahams number would yield a number still very close to TREE(3). It would be like trying to create a number larger than a googolplex by adding a 1 on the end. You would be better off inserting Grahams number into TREE instead of the other way around, creating a "TREE's Graham" instead of "Graham's TREE"