Oxford University Press's
Academic Insights for the Thinking World

Really big numbers

What is the biggest whole number that you can write down or describe uniquely? Well, there isn’t one, if we allow ourselves to idealize a bit. Just write down “1”, then “2”, then… you’ll never find a last one.

Of course, in real life you’ll die before you get to any really big numbers that way. So here’s a more interesting way of asking the question: what is the biggest whole number that you can uniquely describe on a standard sheet of paper (single spaced, 12 point type, etc.) or, more fitting, perhaps, in a single blog post?

In 2007 two philosophy professors – Adam Elga (Princeton) and Agustin Rayo (MIT)  – asked essentially this question when they competed against each other in the Big Number Duel. The contest consisted of Elga and Rayo taking turns describing a whole number, where each number had to be larger than the number described previously. There were three additional rules:

  1. Any unusual notation had to be explained.
  2. No primitive semantic vocabulary was allowed (i.e. “the smallest number not mentioned up to now.”)
  3. Each new answer had to involve some new notion – it couldn’t be reachable in principle using methods that appeared in previous answers (hence after the second turn you can’t just add 1 to the previous answer)

Elga began with “1”, Rayo countered with a string of “1”s, Elga then erased bits of some of those “1”s to turn them into factorials, and they raced off into land of large whole numbers. Rayo eventually won with this description:

The least number that cannot be uniquely described by an expression of first-order set theory that contains no more than a googol (10100) symbols.

A more detailed description of the Duel, along with some technical details about Rayo’s description, can be found here.

Fans of paradox will recognize that Rayo’s winning move was inspired by the Berry paradox:

The least number that cannot be described in less than twenty syllables.

This expression leads to paradox since it seems to name the least number that cannot be described in less than twenty syllables, and to do so using less than twenty syllables! Rayo’s description, however, is not paradoxical, since although it uses far fewer than a googol symbols to describe the number in English, this doesn’t contradict the fact that, in the expressively much less efficient language of set theory, the number cannot be described in fewer than a googol symbols.

The number picked out by Rayo’s description has come to be called, appropriately enough, Rayo’s number. And it is big – really big. But can we come up with short descriptions of even bigger numbers?

Notice that Rayo’s construction implicitly provides us with a description of a function:

F(n) = The least number that cannot be uniquely described by an expression of first-order set theory that contains no more than n symbols.

Rayo’s number is then just F(10100). So one way to answer the question would be to construct a function G(n) such that G(n) grows more quickly than F(n). Here’s one way to do it.

First, we’ll define a two place function H(m, n) as follows. We’ll just let H(0, 0) be 0. Now:

H(0, n) = The least number that cannot be uniquely described by an expression of first-order set theory that contains no more than n symbols.

So H(0, n) is just the Rayo function, and H(0, 10100) is Rayo’s number. But now we let:

H(m, n) = The least number that cannot be uniquely described by an expression of  first-order set theory supplemented with constant symbols for:

H(m-1, n), H(m-2, n),… H(1, n), H(0, n)

that contains no more than n symbols.

In other words, H(1, 10100) is the least number that cannot be described in first-order set theory supplemented with a constant symbol that picks out Rayo’s number. Note that, in this new theory, Rayo’s number can now be described very briefly, in terms of this new constant! So H(1, 10100) will be much larger than Rayo’s number.

But then we can consider H(2, 10100), which is the least the least number that cannot be described in first-order set theory supplemented with a constant symbol that picks out Rayo’s number and a second constant symbol that picks out H(1, 10100). This number is much, much bigger than H(1, 10100)!

And then we have H(3, 10100), which is the least the least number that cannot be described in first-order set theory supplemented with a constant symbol that picks out H(0, 10100), a second constant symbol that picks out H(1, 10100) and a third constant symbol that picks out H(2, 10100). This number is much, much, much bigger than H(2, 10100)!

And so on…

We can now get our quickly growing unary function G(n) by just identifying m and n:

G(n) = H(n, n).

And finally, our big, huge, enormous, number is:

G(10100)

G(10100) is the least number that cannot be described in first-order set theory supplemented with googol-many constant symbols – one for each of H(0, 10100), H(1, 10100), … H(10100-1, 10100).

This number really is big. Can you come up with a bigger one?

Featured image: “Infant Stars in Orion” Public domain via Wikimedia Commons

Recent Comments

  1. Steven Reilly

    Huh. So is this number bigger than the Busy Beaver numbers Scott Aaronson talks about in his paper on big numbers? Or is that unknown?http://www.scottaaronson.com/writings/bignumbers.html

    (BTW the link isn’t working. You need to add an “l” to the end of the URL.)

  2. Nate

    @ Steven Reilly

    Busy Beaver numbers are not computable (if you could compute them, you could solve the halting problem by creating a machine that first computes bb(n) where n is the number of states in the input TM M, then executes M on its input for bb(n) steps. It will accept if M halts, rejects if it hasn’t yet halted).

  3. Benjamin Tilly

    Your description of the big number has a serious mistake. The number they defined is the least one bigger than any number that can be so described. Your description is the least number that cannot be so described.

    But there are lots of gaps between numbers describable with only a fixed number of symbols in first order set theory. And the first number found in the first gap is very, very much smaller than the first number found after the last number in that set.

  4. John Tromp

    You misquoted Rayo’s huge entry

    “The smallest number bigger than any finite number named by an expression in the language of set theory with a googol symbols or less”

    into the relatively minute

    “The least number that cannot be uniquely described by an expression of first-order set theory that contains no more than a googol (10^100) symbols.”

    by leaving out the crucial “bigger than”. The latter is no more than #symbols ^ googol since any N descriptions cannot describe all of the first N+1 numbers…

    Similarly, the proposed function F(n) is merely exponential in n.

  5. Steve HNM

    hi

    Do not know enough mathematics to answer this but this approach seems to produce numbers than are way smaller than Graham’s Number.

  6. Ricky McSmith

    Rayo’s description of his solution in the link you provided is: “The smallest number bigger than any finite number named by an expression in the language of set theory with a googol symbols or less.”

    This describes an incomprehensibly huge number.

    You version of the statement is mathematically slightly different. In particular, the number it describes cannot be larger than n^(10^100) where n is the number of distinct symbols is first order set theory. This is comparatively quite “small.”

  7. Tomi

    @Steven
    Yes, this number is much bigger than the Busy Beavers, or at least, say, BB(10^100). The reason is that while BB is not a computable function, it is nevertheless definable in first order set theory (and presumably in far fewer than 10^100 symbols).

    It seems to me that the function G proposed here, despite appearances, does not really grow all that much faster than F (or, as the other commenters have noted, what you meant F and G to be). Of course, on one level, G(10^100) is clearly much larger than F(10^100). We get to H(1, 10^100) by considering the language of set theory supplemented with a constant for Rayo’s number, and so on. But we can already write down Rayo’s number without that constant; it merely takes about 10^100 symbols (I’ll ignore any issues of +/- several symbols due to brackets or other such things). In particular, the largest number we can write in the supplemented language within 10^100 symbols can also be written in the old language with every Rayo constant replaced by a string of up to 10^100 symbols. This yields a bound of (10^100)*(10^100) symbols for defining, in the language of set theory, the largest number definable in 10^100 symbols in the augmented language (imagine every symbol used in the description were Rayo’s constant). Similarly, considering H(2, 10^100), each Rayo constant_2 can be written in (10^200) symbols. And so on. If this is all right, it should be apparent that G(10^100) is less or equal to F((10^100)^(10^100)). And if that’s the case it obviously would have been easier to merely do F(F(10^100)). As a side note, this applies to any method of augmenting the language with new symbols for old strings.

    If I were to try and look for something growing more quickly than F, my first thought would be to define F’ as F'(a) = F…(F(a) times)..F(a)))…). This is much bigger than G for large a, but still doesn’t seem to me to be a sea change compared to F. I could go a little higher and say something like “Define F^n(a) by: F^0(a) = F(a), F^{n+1}(a) = F^n … (F^n(a) times)…F^n(a)))…)”, and repeat such methods for a while.

    Such functions look an awful lot bigger than F, but in a sense they aren’t. The thing is that any procedure I were to come up with here is going to be in principle formalisable in the language of set theory. And so it’s going to be covered by F, so to speak, already. It’s not that the functions I specified aren’t growing more quickly than F, but the methods used to create them, if used on already computable functions, would result in another computable function. All computable functions are eventually dominated by all non-computable functions, so this won’t do. In fact it’s not just that the procedure I set out is computable: *any* method formalisable in first order set theory is going to do a worse job than the method generating F, including methods to get non-computable functions.

    If we take seriously the idea that first order set theory sufices for almost all mathematics, aside from some quirky logic, we can see informally that F will grow faster than any function produced via any method – aside, perhaps, from quirky logical trickery. I can’t see any trick that does better than F. I think there’s a good reason it was declared the winner.

  8. Tomi

    Slight correction: I suggested that every non-computable function dominates every computable function. I’m not sure that’s true.

  9. Roy T Cook

    First off, Tromp and Tilly are both correct – I of course meant the smallest number larger than all numbers definable in first order set-theory (and similar corrections throughout) rather than what I actually wrote. Thanks for the correction!

    With this correction in place, the function does grow faster than the Busy Beaver function. The Big Number Duel was in fact inspired by Aaronson’s article, if I’m remembering the details correctly, and Rayo’s function grows more quickly than the BB function, hence mine does as well.

  10. Roy T Cook

    In more detail: replace each occurrence of:

    “The least number that cannot be uniquely described by an expression of…”

    with:

    “The least number greater than every number that can be uniquely described by an expression of…”

    and you get the construction I intended.

    This construction does grow faster than Rayo’s function (for obvious reasons) which itself grows faster than the Busy Beaver function.

    I’m going to leave the original post as-is since I think it’s a good lesson (both for myself and others) in how seemingly minor mistakes in wording can equate to massive mistakes in the mathematics. The function I literally describe in the original post does not, as a number of commentators note, grow very fast (in the relevant sense) at all!

  11. Roy T Cook

    Steve HNM:

    I suspect that the construction that I literally give in the original post is less massive than Graham’s number. But what I intended – that is, what you get once the suggested corrections are made – is massively larger.

  12. Roy T Cook

    Tomi,

    There are two separate issues here, which by necessity were somewhat merged in the original post.

    The first is identifying a number larger than Rayo’s number that meets the rules of the competition (informal as those are). I suspect that your F(F(10^100)) violates those rules since you’re just iterating a previous idea, while my construction (although it obviously involves iteration in a different sense) involves a new idea. Or so I would argue.

    The second is constructing a function that grows more quickly than the Rayo function. Now mine does that in a trivial sense, but as you note there is a more substantial idea underlying this. Loosely put, the Busy Beaver function not only grows more quickly than any computable function, but it seem to involve a new ‘kind’ of growth. And similarly the Rayo function seems to involve a new ‘kind’ of growth in comparison to the Busy Beaver function. Then your argument seems to be for the claim that although my function grows more quickly than Rayo’s, it’s still, in some sense, the same ‘kind’ of growth.

    Now, I’m not yet convinced your argument (if this is in fact a fair gloss on what you’re claiming), but that’s mainly because I don’t have any clear grasp of how to explicate this notion of ‘sameness’ or ‘difference’ in ‘kind’ of growth. Maybe people who know more about computability than I do (and I teach graduate courses on the stuff!) can help here?

  13. Tomi

    Dear Roy –

    You’ve got my claims pretty much right. I also don’t know how to cash out exactly the informal notions involved in the competition. But if my reasoning above is correct, your number G(10^100) is bounded above not merely by F(F(10^100)), but also by the much smaller F((10^100)^(10^100)). In general, for large n, I claim that G(n) =< F(n^n). I take the rules of the competition to at the least exclude any method of generating a larger number which is bounded above by a feasible iteration of previous methods. In particular, since G is bounded above in this way, it should not qualify. Of course, if my bound is wrong, none of this goes through.

    The function G does clearly grow faster than F, and it does so by using a new idea. However, I claim that it does not grow faster than various feasible ways of applying previous methods together with F to get a new function. To be clear, I'm not claiming that something like F(F(10^100)) should qualify. I'm arguing that since it does not qualify, no numbers smaller than it should qualify either.

Leave a Comment

Your email address will not be published. Required fields are marked *