# Comparing big numbers.

Let

1. $$G_{64}$$ is a Graham Number:

https://googology.wikia.org/wiki/Graham%27s_number

1. $$TREE(3)$$ is a particular value of a special sequence $$TREE(k)$$

https://googology.wikia.org/wiki/TREE_sequence

1. $$D^{5}(99)$$ is a output of program loader.c
1. $$Rayo(googol)$$ is a Rayo number

https://googology.wikia.org/wiki/Rayo%27s_number

How to prove that $$1.<2.<3.<4.$$ ?

First of all i know that there were several related question but in fact nobody has given a proper proof of any of these inequalities. That's why i wrote this question.

Let's take a look at all cases.

$$1.<2.$$

It is said that sequence that generates Graham numbers grows slower than sequence $$TREE(k)$$ But here are my questions:

• Where are the proofs, sources of this assertion?
• Even if some function $$f$$ grows faster than $$g$$ it doesn't prove that $$f(n)>g(n)$$ for certain value $$n$$.

$$2.<3.$$

Here is my idea to prove this:

First make a code that describes (not calculate) $$TREE(3)$$ Start it and see how much time it takes before you see a message (for example "Hello World") on the screen. The same with the code that describes $$loader.c$$. Compare these numbers. The number that has greater time is greater. Here are another problems.

• The code from the site i gave you in the link doesn't work on codeblocks.
• Is my reasoning even correct? If not( wich is very likely) then how to do this?

$$3.<4.$$

There is only one thing to know: an amount of symbols expressing $$D^{5}(99)$$ in language of First-Order-Set-Theory . If that number is smaller than $$googol$$ then proof follows.

• How we can show that?

Regards

• – Maximilian Janisch Nov 24 '19 at 17:00
• Also related: How big is TREE(3)? – Maximilian Janisch Nov 24 '19 at 17:04
• And Wikipedia – Maximilian Janisch Nov 24 '19 at 17:06
• TREE(3) is so much larger than Graham's number that we do not nedd a formal proof. The level of Graham's number is just $f_{\omega+1}$, whereas TREE(3) FAR exceeds level $f_{\Gamma_0}$. Maybe this site sites.google.com/site/largenumbers is a good start. TREE(3) is so large that , as far as I know, no upper bound is known. – Peter Nov 24 '19 at 18:08
• @Peter - Although there may exist $N$ such that $\text{TREE}(n)\ge f_{\Gamma_0}(n)$ for all $n\ge N$, that says nothing about $\text{TREE}(3)$, and would not imply that $\text{TREE}(n)\ge f_{\Gamma_0}(n)$ for all $n\ge 3$. I think the OP would ask for a proof that $N=3$ suffices in this case. – r.e.s. Nov 27 '19 at 20:06

In the article https://cs.nyu.edu/pipermail/fom/2006-March/010260.html

Friedman showed that $$\text{TREE(3)} >\text{tree}(n(4)) + n(4)\tag{1}$$

where $$n()$$ is Friedman's block-subsequence function and $$\text{tree}(n)$$ is defined as the length of a longest sequence of unlabelled trees $$T_1,T_2,\ldots$$, such that, for all $$i$$, $$T_i$$ has at most $$n+i$$ vertices, and for all $$i,j$$ with $$i $$T_i$$ is not homeomorphically embeddable into $$T_j.$$

(A sketch of his proof is appended to the present answer.)

Furthermore, at https://mathoverflow.net/a/95588/20307 there is a proof that

$$\text{tree}(n)\geq H_{\vartheta (\Omega^{\omega}, 0)}( n) - n\tag{2}$$

where $$H_{\alpha}$$ is an accelerated version of the Hardy hierarchy; hence, as pointed out there,

$$\text{TREE(3)} > H_{\vartheta (\Omega^{\omega}, 0)}(n(4)).$$

We note that the RHS is clearly larger than $$G_{64},$$ because $$H_{\omega^{\omega+2}}(3)>f_{\omega+2}(3)>G_{64},$$ where $$f_\alpha$$ is the usual fast-growing hierarchy.

The following is an attempt to briefly elucidate the proof that $$\text{TREE}(3) > \text{tree}(q) + q,$$ where $$q>n(4)$$, based on the tree sequence and symbol-encodings used by Friedman in the article cited above. I'll use balanced parentheses of types $$(\,),[\,],\{\,\}$$ to denote vertices labelled with $$1,2,3$$ respectively.

T_1   {}
T_2   [[]]
T_3   [()()]
T_4   [((()))]
T_5   ([][][][])
T_6   ([][][](()))
T_7   ([][](()()()))
T_8   ([][](()(())))
T_9   ([][](((((()))))))
T_10  ([][]((((())))))
T_11  ([][](((()))))
T_12  ([][]((())))
T_13  ([][](()))
T_14  ([][]())
T_15  (A(B(((([]))))))
(A(B((([])))))
(A(B(([]))))
(A(B([])))
(A(B[]))
T_20  (C(D(E(((([])))))))
(C(D(E((([]))))))
(C(D(E(([])))))
(C(D(E([]))))
(C(D(E[])))
T_25  (F(G(H(I(((([]))))))))
...
T_30  (J(K(L(M(N(((([])))))))))
...
T_q   (X(Y(...(Z((((([])))))...))))  where q = 10 + 5p
T_q+1 (((...(())...)))  with q+1 ()s
...
T_q+tree(q)  ()


Here, each letter A,B,C,... denotes one of the following symbol-codes for a 4-symbol alphabet {1,2,3,4}:

(((())))   <- codes the symbol 1
((()()))   <- codes the symbol 2
(()()())   <- codes the symbol 3
((())())   <- codes the symbol 4


Now, by Friedman's results on the function $$n()$$, there exists a $$p$$-long sequence of words $$x_1,...,x_p$$ on alphabet $$\{1,2,3,4\}$$ such that $$|x_i| = i+1$$ and for all $$i, $$x_i$$ is not a subsequence of $$x_j$$, where $$p = {n(4)-1\over 2}$$.

So tree-embeddings are avoided by choosing the symbol-codes $$A,B,C,...$$ such that $$AB$$ encodes $$x_1$$, $$CDE$$ encodes $$x_2$$, $$FGHI$$ encodes $$x_3$$, etc.

Hence the sequence of trees $$T_1,...,T_q$$ (where $$q = 10+5p>n(4)$$) is such that $$|T_i| \le i$$ and for all $$i, $$T_i$$ is not homeomorphically embeddable in $$T_j.$$

Then the sequence continues $$T_{q+1},...,T_{q+\text{tree}(q)}$$ for another $$\text{tree}(q)$$ trees after $$T_q$$, these trees being constructed with $$(\,)$$-vertices only. QED