3
$\begingroup$

I was reading about large numbers, and came across Rayo's Number which is defined to be the smallest integer that is not nameable by any expression in the language of set theory that contains less than $10^{100}$ symbols.

Now, my question is: Is this number really that large?

If we pick some "random" number $2091580284...384901284021$ with $10^{100}$ digits, wouldn't it be non-nameable with less than a googol symbols? Wouldn't this number be bigger or equal to Rayo's Number?

$\endgroup$
  • $\begingroup$ Lots of large numbers can be "named" quite efficiently. $10^{10^{101}}$ for example. The trick is to somehow characterize a large number without naming it. The problem is that "characterize" sounds kind of like a synonym for "name", hence the interest in examples. $\endgroup$ – lulu Aug 13 '16 at 11:44
  • $\begingroup$ Suppose you took your example number manipulated it as follows: $$2091580284\dots384901284021=2091580284\dots384901284020+1$$ $$=2(1045290142\dots192450642010)+1$$ $$=4(522645071\dots096225321005)+1$$ $$=20(1045290014\dots019245064201)+1$$ And so one, we factor. If we hit a prime, or a number we can't easily factor, subtract out a part like I did in the first step, then continue on. Eventually, you will hit a representation of the number using less than a googol of symbols. Or I could ask if that number is larger than $P(P(P(\dots P(A)\dots)))$ for some set $A$. $\endgroup$ – Simply Beautiful Art Aug 13 '16 at 11:47
  • $\begingroup$ You quoted the definition incorrectly. It is "The smallest number bigger than ..." so it is of course larger than 10^100 (which can be written with only a few symbols). $\endgroup$ – Samuel Aug 13 '16 at 11:47
  • $\begingroup$ @Samuel yes, thats why I'm picking some "random" number that has not a simple representation such as 10^100 $\endgroup$ – Andrei Kh Aug 13 '16 at 18:52
  • $\begingroup$ @Simple Art can this be done with every number? $\endgroup$ – Andrei Kh Aug 13 '16 at 18:55
4
$\begingroup$

As some of the comments already mentioned, you misquoted the definition. The correct definiton (quoting Googology Wiki) is:

the smallest positive integer bigger than any finite positive integer named by an expression in the language of first order set theory with a googol symbols or less

So while there are only approximately $(10^{100})^{(10^{100})}$ possible expressions, and only a very small fraction of them actually name a number, Rayo's number can be very large.

We don't exactly know how large, but there are good heuristic arguments that the busy beaver function $\Sigma$ can be implemented in a few million symbols. Given that $\Sigma$ grows much faster then $\mathrm{TREE}$ and all other computable functions, Rayo's number is much larger than $(10^{100})^{(10^{100})}$ .

$\endgroup$
  • $\begingroup$ :0 A million symbols for $\text{BB}$... that's interesting. $\endgroup$ – Simply Beautiful Art Mar 23 '17 at 0:00
4
$\begingroup$

It's not just about how many digits it has, it's about the SYMBOLS you can express in.... so basically you can throw in something like Tree(tree(tree(tree..9...) ) ) With a total of one googol symbols. Keep in mind that merely tree(3) is immeasurably large. You cannot fathom hard large tree(tree(3) is, don't even talk about ~nonillions of trees nested within one another.

$\endgroup$
  • 1
    $\begingroup$ Actually, there are two tree sequences, the one you refer to being $TREE$, but $tree$ is much smaller than $TREE$. $\endgroup$ – Simply Beautiful Art Mar 8 '17 at 12:45
2
$\begingroup$

Thanks to Googology, I found a nice explanation of this.

Explain Rayo please

I will be using the outline of the comments to avoid plagiarizing, though you can read them as you please.


Let's start with a simple language, which I will call simple_arithmetic.

In simple_arithmetic, you can say numbers, and you can link them together using addition $+$, multiplication $\times$, and exponentiation $\wedge$ (each counts as one symbol). Parenthesis are also usable (each one symbol). We follow PEMDAS and a^b^c=a^(b^c).

Likewise, the only number we have to start out with is $1$. From there we can build any other number.

From the above, you will also note the only numbers constructable are natural numbers larger than or equal to $1$ (it counts as one symbol). This is our entire set of numbers, and there can be no other numbers in simple_arithmetic.

There are no variables, no functions, etc. A pretty basic language.

Now we can make $\operatorname{SA}(n)$, which equals the smallest number larger than any number nameable in $n$ symbols of simple_arithmetic. So, let's start finding a few values:

$\operatorname{SA}(0)=1$, since I can't name any numbers yet, and $1$ is the smallest number in my language.

$\operatorname{SA}(1)=2$, since the only number you can make with one symbol is $1$, and $2$ is the smallest number larger than $1$.

$\operatorname{SA}(2)=2$ still, since we don't have enough operations to do anything, such as $1+1$.

$\operatorname{SA}(3)=3$, since we can now make $2=1+1$.

$\operatorname{SA}(4)=3$, not enough symbols to do much...

$\operatorname{SA}(5)=4$, since we can now make $3=1+1+1$.

$\operatorname{SA}(6)=4$


As you can probably tell, this is rather cumbersome, but there is eventually a small-ish jump. For $n<7$, we have:

$\operatorname{SA}(2n-1)=n$


But then this pattern breaks.

$\operatorname{SA}(13)=9$, since $8=(1+1)\wedge(1+1+1)$

Indeed, one may note that for sufficiently large $n$, we have

$\operatorname{SA}(6n-1)\ge\underbrace{2^{2^{2^{\dots}}}}_n+1$, as it takes $6$ symbols to write $(1+1)\wedge$ and no $\wedge$ needed for the last exponent.


Rayo's function is all the same, except the language it uses is way stronger. Rayo's function is given by the smallest number larger than any number nameable in $n$ symbols of first order set theory, a language strong enough to allow variables, functions, recursion, etc. Likely put, you can define stuff in this language you'd probably have a hard time explaining in English, and the results... are some very large, almost unexplainably large, numbers.

$\endgroup$
  • $\begingroup$ Even for this simple language, I think the situation is more complicated. For example, SA(13) = 10, because (1 + 1 + 1) ^ (1 + 1) is 9 and SA(15) is >= 28. $\endgroup$ – cbmanica Sep 10 '17 at 7:36
  • $\begingroup$ @cbmanica Meh, SA(15) couldn't be too big.... I hope. $\endgroup$ – Simply Beautiful Art Sep 10 '17 at 11:39

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.