Is there any pratical use to really large number mathematics (e.g. Graham's Number or Tree(3))?

[Lumpy]

@Andy_L

This reminds me of this interesting fact. If you pick a positive integer less than a googol in magnitude at random, it is almost certain that that integer will have a “9” in its base-10 representation. But for integers in the range we see on a day to day basis (say, integers less than 2000 or so), having “9” in the base-10 representation is fairly rare.

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

[Andy_L]

@Lumpy

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.

[Chronos]

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.

[DPRK]

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.

[Hari_Seldon]

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 = 34^4 + 34^3 + 34^2 + 34 +3. Next replace every 4 by a 5 and subtract 1 to get 35^5 + 35^3 + 35^2 + 35 + 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.

[Reindeer_Flotilla]

Regarding TREE(3)…

@Whack-a-Mole

For me I think it is the amazing progression that blows my mind…1, 3, ludicrously huge.

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?).

…it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham’s number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space. But even the number of digits in this digital representation of Graham’s number would itself be a number so large that its digital representation cannot be represented in the observable universe. Nor even can the number of digits of that number—and so forth, for a number of times far exceeding the total number of Planck volumes in the observable universe.

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…

Connect each pair of geometric vertices of an n-dimensional hypercube to obtain a complete graph on 2n vertices. Colour each of the edges of this graph either red or blue. What is the smallest value of n for which every such colouring contains at least one single-coloured complete subgraph on four coplanar vertices?

… 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,

…25950695064738395657479136519351798334535362521430035401260267716226721604198106522631693551887803881448314065252616878509555264605107117200099709291249544378887496062882911725063001303622934916080254594614945788714278323508292421020918258967535604308699380168924988926809951016905591995119502788717830837018340236474548882222161573228010132974509273445945043433009010969280253527518332898844615089404248265018193851562535796399618993967905496638003222348723967018485186439059104575627262464195387

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

[Chronos]

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

[DPRK]

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?

[Itself]

Does this count as a practical application?

[Chronos]

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.

[septimus]

@Chronos

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 first order set-theory." — No paradox. I’ll defer to the Board’s mathematicians to explain this more completely.

[Chronos]

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.

[DPRK]

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:

For [φ] a (Gödel-coded) formula and s a variable assignment, let Sat([φ],s)' abbreviate the following second-order formula (where the second-order quantifier is understood plurally): ∀R { {for any (coded) formula [ψ] and any variable assignment t (R( [ψ],t) ↔ ( ([ψ] = x_i ∈ x_j’ ∧ t(x_1) ∈ t(x_j)) ∨
([ψ] = x_i = x_j' ∧ t(x_1) = t(x_j)) ∨ ([ψ] = (∼θ)’ ∧ ∼R([θ],t)) ∨
([ψ] = (θ∧ξ)' ∧ R([θ],t) ∧ R([ξ],t)) ∨ ([ψ] = ∃x_i (θ)’ and, for some an x[sub]i[/sub]-variant t’ of t, R([θ],t’))
)} →
R([φ],s)}
The winning entry is then this:
The smallest number bigger than every finite number m with the following property: there is a formula φ(x[sub]1[/sub]) in the language of first-order set-theory (as presented in the definition of `Sat’) with less than a googol symbols and x[sub]1[/sub] as its only free variable such that: (a) there is a variable assignment s assigning m to x[sub]1[/sub] such that Sat([φ(x[sub]1[/sub])],s), and (b) for any variable assignment t, if Sat([φ(x[sub]1[/sub])],t), then t assigns m to x[sub]1[/sub].

[k9bfriender]

@DPRK

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

[septimus]

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.

[DPRK]

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?

[DPRK]

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?

[Velocity]

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…

[Jragon]

@Sage_Rat

As Chronos noted, TREE(3) is just a tiny itsy-bitsy value in the greater scheme of things. Most numbers are bigger than the universe[…]

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.

[septimus]

@DPRK

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?

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.