Insanely Large Numbers

britney-spears-3.16420Let’s talk about large numbers, why don’t we?

Have you ever thought of what the largest number is? 7?  19?  21 perhaps?  The computer scientists might smugly insist on 1 and a couple nerds out there will try to say 42 while laughing at themselves and thinking to themselves how clever they are for out-nerding the nerd writer writing about large numbers.

Some might claim, there is no largest number, but on the other hand do any numbers larger than the largest number you can say in your lifetime matter?  Or any person could in principle have said in the lifetime of the universe?  Saying out large numbers is a bit cumbersome.  We can count hundreds, thousands, millions even.  But then it gets iffy – what comes after a million?  A billion?  Only if you are of lower intelligence; us Europeans will claim we first have milliard, then a billion, billiard, trillion and so on.  At some point we reach a googol and then a googolplex, and now our counting has turned into baby language, and are sure to reach fantasillion and britnillion along the way.

The Largest Number You Can Write Down

How about, then, the largest number anybody could ever have written down?  The universe is estimated to be roughly 14 billion years old; that’s roughly 14.000.000.000 years or 442.000.000.000.000.000 seconds.  How large a number could we write down in that time?  Well, it depends on how we write down numbers.

The simplest way to write numbers is just jotting down a line for each number. 1 = I, 2 = II, 3 = III and so on.  Using this scheme, and assuming we can write down 1.000 lines a second (using our new patented number-writing machine devised solely to write down the largest number in the world), we would be able to write down the number 442.000.000.000.000.000.000.  That’s pretty big, but doesn’t go a long way to describe how great I am or how many Zimbabwe dollars you need to pay to get a stamp.

We can instead decide to group our lines, and once we reach, say, ten lines, we instead start counting groups.  Then the number III IIIII would represent “3 groups of ten and 5” or 35.  This gets tedious after a while, so after we reach ten groups of ten, we start counting groups of groups of ten. IIII II III is “4 groups of ten groups of ten, 2 groups of ten and 3” or 423.  We can continue this trick, and we get to our normal numbering system.  Now I can write down the number 442.000.000.000.000.000.000 in less time than the time it takes two virgins to have sex for the first time.  As opposed to two virgins having sex for the second time.  By being more smarter in my number writing techniques, I can write down the number 4.420.000.000.000.000.000.000 and outdo our mighty biggest-number-in-the-world-writing-machine by a factor of 10.  You’re right; I am pretty great.

But this technique also becomes tedious after a while.  It’s great for most everyday things, where we don’t really see large numbers of anything.  Heck, using this technique, I can write down the total number of atoms in the universe.  It’s roughly 1.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.  Sure that’s longer than the average nerd penis, but still perfectly write-down-able.  But I cannot write down the largest number, I can write down in the lifetime of the universe using this technique, using this technique.  That previous sentence makes sense – read it again.  At least I can’t do that if I expect to push Publish in the course of tonight.

Instead, we try the same trick again.  Instead of counting groups of groups of groups… of ten, I count how many times I need to do that. 1000 is 4 – 4 groups in total.  1.000.000 is 7.  You get the idea.  I only care about the length of the number.  Since we’re dealing with super large numbers, the accuracy doesn’t really matter that much.  I can easily make a number composed solely of ones that is larger than any number composed of, say, nines.  Just write down one more one than the number of nines.  For example, 1.111 > 999. 1.111.111.111 > 999.999.999.  Only the number of digits count.  Mathematicians and other sad existences often write this at 10number of digits.  1234 is 104.  That number of atoms in the universe is 1082.  Assuming I can write down 1.000 digits a second (by building number writer 2000 version 2.0), the largest number I can write down using my previous technique is 10442.000.000.000.000.000.  Mathematically, 10n is really 10 * 10 * 10 … * 10 (n times), so 104 is really 10 * 10 * 10 * 10 = 10.000, and we might be off by a factor of 10.  But that’s literally the smallest number in the world, so nobody cares.

That’s all great, but what is then the largest number I can write down using that technique?  Well, that’s obviously 10^{10^{442.000.000.000.000.000}}. Which is again pretty great, but then how many times…? I can continue the game, and each time, we continue how many times we count the number of digits. We then get a series of 10 (the number ten), 1010 (a number with ten digits), 10^{10^{10}} (a number which has a number of digits with 10 digits), 10^{10^{10^{10}}} (a number which has a number of digits which has a number of digits which is 10). A googol is 10100 and a googolplex is 10googol = 10^{10^{100}}.

I bet you can see where I am going. Now, instead of counting digits and digits in the number of digits and so on, we just count how many times we need to do this. Just like we went from counting groups of ten and groups of groups of ten to just counting the number of times we count these groups (or the number of digits). This is sometimes written as tower(n), referring to how be make a “tower” of tens and then count the number of those. So 10 = tower(1) and 10^{10^{10}} = tower(3). Again, it doesn’t really matter if we’re counting towers of tens or twos or sevens. There’s some error, a huge error even, but compared to the numbers we look at, the error doesn’t matter in comparison except to the most penny-pinching Scotsman. Don’t know why they’d pinch pennies. The tower operation is also referred to as tetration, and some write 43 for a tower of threes of height 4, but that’s frankly just silly.

Now, we could start chaining towers, as in tower(tower(tower(… tower(4) …))), and eventually be able to describe the Greek debt. It would be quite satisfying, and eventually we’d reach some rather large numbers. Then we could come up with a name for what happens if we chain, say, 4 towers, start chaining those and so on. We would again end up with the kind of baby-talk that lead us to the whole billion debacle. Instead, let’s take a step back and consider what we’ve done. Then consider it mathematically.

Throwing Math at the Problem

At first, we were writing numbers as lines. Those are pretty if the only computation we do is adding one. III + I = IIII. We don’t really create numbers that get completely unhandy using this operation. At least not unless we do the operation many times. If we start adding one many times, we reach normal addition. III + IIII = IIIIIII; we add one to III four times (or add one to IIII three times). The simple unary representation of numbers works well for adding one, also known as the succession operation, but becomes unhandy for addition, adding numbers together.

Then we starting counting groups of 10. This is the decimal notation and the one we use the most in our daily lives if we’re not dreadful scientists or worse. This notation serves us well in representing most numbers of things we encounter in our daily lives. We can even rather conveniently represent every single atom in the universe using this annotation. The decimal operation handles addition well. 47 + 75 = 122. The result has roughly the same size as the input. The decimal system starts having trouble when we start doing multiplication. 100 * 10.000 = 1.000.000.

The scientific notation can handle multiplication much better than decimal notation. The scientific notation is the one roughly counting the number of digits. 100 = 102 and 10.000 = 104, so 102 * 104 = 106. In this notation, the size of the result of multiplication is around the same size as the operands. For shits and giggles, try doing multiplication using the unary notation – the numbers quickly get so large they are hard to wrap your head around.

We can think of multiplication as repeated addition, just like addition is repeated succession. 4 + 3 is add one to 4 three times. 4 * 3 is add 4 together 3 times. We can continue this train of thought and try and do repeated multiplication. We call this exponentiation, and 103 is multiply 10 by itself 3 times, or 10 * 10 * 10. The scientific notation starts having problems when we start using exponentiation, whereas the tower notation handles it – tower(3)tower(4) < = tower(7).

Our next step is obvious. Repeated exponentiation. That’s what the tower function does. Repeated towering. That sounds sexual somehow. Repeat that, etc. Our next step is to count how many times we do a repeated operation, starting with succession, addition, multiplication, exponentiation, towering, etc. We notice that each time we take a step, the largest number we could conceivable write in the lifetime of the entire universe can be written compactly. The largest number we can write in unary was 442.000.000.000.000.000 which, while impressive, is far from hard to write and grasp. In scientific notation, this number is only 1018 and using the tower notation it’s less than tower(3) = 10^{10^{10}}. In a hypothetical next notation, it would be one – we only needed to use the tower function once to describe the number.

More Meta!  More!  More!  Meta!

Mathematically, we can capture this using the Ackermann function. Skirting over some details, the Ackermann function basically counts how many time we do repeated computation. Details are for folks that don’t hve fun with large numbers, which is the opposite of what we do right now. Roughly, Ackermann(1) = succession(1) = 1 + 1. Ackermann(2) = addition(2) = 2 + 2 = 4. Ackermann(3) = multiplication(3) = 3 * 3 = 9. Ackermann(4) = exponentiation(4) = 44 = 256. Ackermann(5) = tower(5) = 5^{5^{5^{5^5}}} = very, very large. 5^{5^5} alone has more than 2000 digits. The name tetration comes from towering being the fourth (= tetra) repeated operation (addition being the first).

I’m sure that the first thing anybody thinks of now is “where can I get chocolate,” and the second thing is “why don’t we repeat the Ackermann function?” And of course that’s a thing. Donald Knuth, typically famous for making nerds interested in latex to a degree disproportional with their sex-life, devised the notation summarizing the Ackermann function. This is known as the Knuth arrow. It roughly captures the Ackermann function, so 4 ↑ 3 = 43, 4 ↑↑ 3 = 4^{4^{4}} and so on. Roughly, the Ackermann function is Ackerman(n) = n ↑↑ … (n times) … ↑↑ n or n ↑n n. Plus or minus one or two here and there, but who counts? People that don’t deal with large numbers, that’s who!

The generalization of Knuth’s arrow is Conway’s chained arrows. Using this notation, we basically have 3 → 4 = Ackermann(Ackermann(Ackermann(4))) and a chain of length more than 2 counts how many times we have to repeat the sequence once shorter. Conway’s arrows count the number of times we repeat doing Ackermann the same Ackermann count the number of times we repeat a simple operation. Where Ackermann(5) is so silly large, I cannot write it in the lifetime of the universe using normal decimal notation.

Just using Ackermann’s function, we can create silly large numbers. Conway’s notation allows us to repeat that. There’s nothing preventing us from repeating the Conway arrows systematically, and then repeating that. There’s also nothing preventing us from counting how many times we do this. Or counting how many times we repeat repeating this silly thing. Every time, the largest numbers we could hope to ever write using the previous generation of silly reptition will seem small and trivial. Using simple tricks, we can represent mindbogglingly large numbers very compactly, and there is no limit to how many times we can do this.

I think it is impossible to get a hold of just how large these numbers are without getting a feeling for how we repeatedly compress numbers into a more and more compact notation, and it’s cool how limited we are using the decimal number system we are used to.

If Infinitely Many Monkeys Can Reproduce Shakespeare, How Can I Come Up with this Shit?

The elephant in the room is of course infinity. How about infinity, smart guy? That’s larger than any of these supposedly large numbers, right? Well, infinite is not a number, and it’s not possible to appreciate the magnitude of infinity without first having a concept of very large but finite. And infinity is not just infinity.

In fact, what we most often think of as infinite is the number of natural numbers. Natural numbers are 1, 2, 3, 4, 5, and so on. If we think of the set of the numbers {1, 2, 3} as N3 and {1, 2, 3, 4, 5} as N5, the set of all natural numbers, {1, 2, 3, 4, 5, 6, …} is N. The number of elements in N3 is often denoted |N3| = 3. There’s 3 elements, 1, 2, and 3. |N5| = 5 and |N| is infinity. At times written |N| = ∞. Note how Na is fully contained in Nb if a < b. This means that |Na| < |Nb| if a < b. This can also be seen as |Na| = a < b = |Nb| if a < b.

This also means that if ∞ was a number (which is really isn’t!), we would have that Ackermann(5) = |NAckermann(5)| < |N| = ∞. All the numbers from 1 … Ackermann(5) are natural numbers, so there must be more natural numbers. We can in general see that ∞ is larger than any of the large numbers we found above, no matter how many time we do silly repetitions to generate larger and larger numbers. Viewed as a number, ∞ is insanely great.

But there are larger quantities. If you think there are many natural numbers, what happens if we add more numbers? It turns out, we have to very particular about how we do that. Let’s first look at fewer numbers. How many even numbers are there? To answer that, we first have to be able to compare the size of infinite sets. We do that by paring up elements of each set. It turns out, that |{2, 4, 6, 8, 10, …}| = |{1, 2, 3, 4, 5, …}| = |N| = ∞. How can that be? Well, we can pair the numbers up as (2, 1), (4, 2), (6, 3), (8, 4), (10, 5). We pair each number 2 * i up with its half, i. Each number of the set of even numbers has a partner from the number of natural numbers, so there must be equally many.

We can do the same trick to show that |{1, 3, 5, 7, 9, …}| = |{1, 2, 3, 4, 5, …}| = |N| = ∞ by pairing 2 * i – 1 up with i. And then we see something weird. Intuitively if two sets A and B share no elements, |A| + |B| = |A + B|. The number of elements if we put all the elements together is the sum of elements in each of the sets. |{2, 4, 6}| + |{1, 3, 5, 7}| = 3 + 4 = 7 = |{2, 4, 6, 1, 3, 5, 7}| = |{2, 4, 6} + {1, 3, 5, 7}|. If we extend the same to the infinite sets, we get that |{2, 4, 6, 8, 10, …}| + |{1, 3, 5, 7, 9, …| = |{2, 4, 6, 8, 10, …, 1, 3, 5, 7, 9, …}| = |{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …}| = |N| = ∞. So ∞ + ∞ = ∞. That’s why ∞ is weird and not a number. Similarly, we can see that |{2, 3, 4, 5, 6, …}| = |{1, 2, 3, 4, 5, …}| = |N| = ∞ (pair i – 1 up with i), but then |{1}| + |{2, 3, 4, 5, 6, …}| = |{1, 3, 4, 5, 6, …}| = |N| so 1 + ∞ = ∞.

It seems that roughly no matter what we do to ∞, we are just stuck with ∞. Just don’t do ∞ – ∞ or ∞ / ∞ you silly person. This is comparable to how the size of the result of addition isn’t much larger than the size of the two operands. Adding to infinity doesn’t really do anything to the size. It turns out that multiplication doesn’t to much either in this case. I’ll not go into details, just notice that it is possible to make a Cartesian product of two sets A and B denoted A * B and that |A * B| = |A| * |B|. It is possible to show that ∞ * ∞ = |N| * |N| = |N * N| = |N| = ∞ (the proof is the same as showing there are as many fractions as there are natural numbers).

Larger than Infinitely Large (Your Mom)

It turns out, there is something we can do. A subset of a set A is a set where all elements come from A. {1, 2, 3} is a subset of {1, 2, 3, 4, 5}. So are {} (the empty set) and {1, 2, 3, 4, 5}. The set of all subsets of a set A is often denoted 2A. For example, 2N3 = { {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} } is the set of all subsets of N3 = {1, 2, 3}. Furthermore, the number of such subsets for a set A is |2A| = 2|A|, explaining the odd notation. You can see that |2N3| = 8 = 23 by counting for yourself (the empty set {} and N3 itself, {1, 2, 3}, also count).

It is possible to show that |2N| > ∞. This is done using a diagonal argument, which basically assumes that there is a pairing between all subsets Si of N and numbers i of N. It then constructs a new subset S of N which contains all numbers i such that i is not in Si. We can then see that our new set S is not in the list (as it differs from all Sis on at least the value i), which is in contradiction to the assumption that we could pair every subset of N with a number of N. The details are not important here, but the take-away is that there is a thing, 2 which is greater than ∞.

Not only that, but we can now construct 22N and using a similar argument prove that 22 > 2 > ∞. This looks eerily familiar. We now have a method of generating increasingly large infinities just like we did for regular numbers. And in fact we can. Using this same subset construction, we can generate larger and larger sets of larger and larger infinite size.

But wait, there’s more! How about “the set of all sets that doesn’t contain themselves”? If we denote this set F (for fuck you), does F then contain itself? If yes, then it should not contain itself and if no, it should. This seems like a logical paradox, but is really just the same as the diagonal argument we used to show that |2N| > |N|. It just means that F is not a set. It is instead what is denoted as a class. All sets are classes, but not all classes are sets (as F demonstrates). Typically mathematicians stop here, because the foundation gets shaky, but we are now constructing mindbogglingly large infinities.

And that concludes this – almost – infinitely long writeup. We have constructed extreme infinities as sizes of classes. Larger than any of the sizes of sets we have seen. Which were mindbogglingly large infinities, where even the smallest infinity was larger than any of the mindbogglingly large numbers we constructed. Where even one of the smaller values we saw, Ackermann(5), while one of the largest values that is possible to get a decent graps of with normal mathematics, is larger than I could write out before then end of the universe using our standard decimal number system.

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.