5
$\begingroup$

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

https://googology.wikia.org/wiki/Loader's_number

  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

$\endgroup$
6
  • $\begingroup$ Related: math.stackexchange.com/questions/1950116/… $\endgroup$ – Maximilian Janisch Nov 24 '19 at 17:00
  • 1
    $\begingroup$ Also related: How big is TREE(3)? $\endgroup$ – Maximilian Janisch Nov 24 '19 at 17:04
  • $\begingroup$ And Wikipedia $\endgroup$ – Maximilian Janisch Nov 24 '19 at 17:06
  • $\begingroup$ 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. $\endgroup$ – Peter Nov 24 '19 at 18:08
  • $\begingroup$ @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. $\endgroup$ – r.e.s. Nov 27 '19 at 20:06
1
$\begingroup$

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<j,$ $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<j$, $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<j$, $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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.