The chance that a positive integer in base-10 doesn’t have a “9” in it falls below 50% at a mere seven digits.

Agreed. I went out to 100 digits to get the percentage down to less than a hundredth of a percent, for my own nefarious reasons.

For a similar brain-melting fact: It’s widely known that some numbers, such as pi, can’t be expressed exactly in a finite amount of space, using our standard base-10 notation. But that’s OK, because we can extend our notation in various ways so that we can express it, like π or 4*Sum((-1)^(k+1)/(2k-1),k=1…inf).

But there are numbers that can’t be expressed finitely in *any* system of notation. And in fact, *almost all real numbers* can’t be expressed finitely in any system of notation.

Another fun fact: while, as every schoolchild learns, the real numbers are uncountable (in fact 2[sup]א[sub]0[/sub][/sup]), it follows from the Löwenheim–Skolem theorem that there exists a countable model of set theory.

That’s correct. The trick is that that model cannot contain the function that counts the subsets of the integers. It is there from the outside but not in the model.

You want a rapidly-growing function? Take an integer, e.g. 9. Write using numbers no bigger than 2: 2^{2+1} + 1. Now replace every instance of 2 by 3 and then subtract 1. This gets you 3^{3+1} = 81. Now replace every instance of 3 by 4 and subtract 1: 4^{4+1} - 1 = 1023 = 3*4^4 + 3*4^3 + 3*4^2 + 3*4 +3. Next replace every 4 by a 5 and subtract 1 to get 3*5^5 + 3*5^3 + 3*5^2 + 3*5 + 2, which I won’t calculate, but could. Continue, replacing every 5 by a 6, then subtract 1. Although it seems unlikely, the sequence eventually becomes 0, but the number of steps required is unimaginably large. You can start with any number. Curiously, there is no proof in finite arithmetic that it does eventually become 0 no matter where you start. Of course, given any actual number, you could, in principle, see it go to 0, but no general proof is possible. But it is nearly trivial using what is called epsilon_0 arithmetic. Though larger than aleph_0, epsilon_0 is still countable.

Regarding TREE(3)…

That’s why I love Graham’s Number so much - any description of it and/or how it’s determined sort of more-slowly “ramps” you up to its value. For example here’s a quick description and here’s a more detailed and relatable presentation.

Graham’s Number is so large and ungraspable that I appreciate how these summaries take you step by step to how one could theoretically reach the number. TREE(3), because it jumps so quickly like you mentioned, gets abstract way to fast to get a similar mental handle on it. For example, the sites mentioned help you understand that saying Graham’s Number wouldn’t fit in the universe GREATLY understates it’s size. Wikipedia sums this up nicely (see what I did there?).

As an aside, Graham’s Number is more of an offshoot from the original work by Ronald Graham and Bruce Rothschild to prove that the following specific problem in Ramsey theory…

… actually had a solution, which was the point of the award-winning paper. Graham’s Number was more of an “oh by the way” from the proof of a solution’s existence. When you see listed the computed last 100 or so digits of Graham’s number,

it kinda feels like you’re tickling the dragon’s tail - mathematically (not nuclear-ly) speaking of course.

To be clear, that should say “2[sup]n[/sup] vertices”, or “2^n”, not “2n”. The superscript got lost in copying and pasting.

Speaking of large numbers, does anyone have more information/examples on the practical uses of really bigly big numbers like Rayo’s number (“the smallest number bigger than any finite number named by an expression in the language of set theory with at most 10[sup]100[/sup] symbols”) and its ilk? Not of much obvious use in combinatorics or number theory. Perhaps proof theory, computational complexity theory, model theory?

Rayo’s number isn’t actually well-defined. Constructions like that are only used for creating paradoxes, which in turn are used to illustrate impossibility theorems.

I believe this is incorrect. Rayo’s number is defined, in the language of * 2nd-order* set theory, with the phrasing " any number that can be named by an expression in the language of

*set-theory." — No paradox. I’ll defer to the Board’s mathematicians to explain this more completely.*

**first order**OK, I don’t know precisely what is meant by orders of set theory, but that looks like the sort of construction that at least might be valid, sort of like how a larger finite computer can solve a smaller finite computer’s halting problem. I was just basing it on **DPRK**’s statement, which didn’t make the distinction.

I apologize; the short rough description of Rayo’s number that I quoted was not meant to be a formal mathematical definition. Quoting from Rayo’s home page, the number he had in mind is defined as follows:

Oh yeah? I can beat that:

The smallest number bigger than every finite number m with the following property: there is a formula φ(x1) in the language of first-order set-theory (as presented in the definition of `Sat’) with less than a googol symbols and x1 as its only free variable such that: (a) there is a variable assignment s assigning m to x1 such that Sat([φ(x1)],s), and (b) for any variable assignment t, if Sat([φ(x1)],t), then t assigns m to x1… Plus 1

Now if only someone would explain, in simple words, Woodin Cardinals for us. Any Woodin Cardinal would have to be greater than ℵ[sub]G[/sub], where G is Graham’s number. IIRC their existence would confirm the axiom of choice. Or something like that.

This blurb by Steel explains that the existence of infinitely many Woodin cardinals implies the axiom of projective determinacy, which would indeed count as a “practical use”; is that what you mean? That is not the axiom of choice, though.

NB a Woodin cardinal is a large *cardinal* number, not a large *natural* number. Are you saying there is a connection or parallel between these notions, because that sounds fascinating?

ETA you can’t get a large cardinal as any kind of finite ℵ number, unless I’m missing something - so there is no direct connection to Graham’s number or any other finite number there?

Is there a way to find the last few digits of TREE3 like there is to get the last hundred digits of Graham’s number?

Also, how do they prove numbers like TREE3 and Rayo’s and Loader’s number are finite?

Layman stepping in then tiptoeing out here…

I’ve actually had to use this in a proof recently. Or rather, the more general concepts “if you can prove something occurs within N steps, where N is an unknown but finite number, there are infinitely more numbers beyond that.” This was more specifically a proof that if something converges within a certain tolerance in a finite amount of steps (guaranteed true in this case), you can prove a decomposition of it also converges to a correct value by running the convergence beyond that.

That’s probably a bit fuzzy but I’d have to give too much background to give a full version. The takeaway is that for any arbitrary number, most numbers are bigger than it.

I’d suspect the other thing you said is true too – for any function that grows at rate Ω(f(n)), there’s an infinite number of functions that grow more quickly, but functions are a bit more messy and sometimes seemingly obvious things like this turn out to be untrue.

No connection. Except that just as Graham’s Number is a ridiculously large *finite* number, so the Woodin cardinals are ridiculously large *infinities*. My “Any Woodin Cardinal would have to be greater than ℵ[sub]G[/sub]” was just a (very poor) way to allude to that.