Humanity vs. Infinity
In this post I’m going to prove that there cannot exist a good notation system for talking about sizes of infinity.
It’s fun to think about big numbers. And by big numbers, I mean different sizes of infinity.
You can define different sizes of infinity in many ways – there are the cardinal numbers, the more specific ordinal numbers, and then the even more specific (and my personal favorite), surreal numbers. There are also the hyperreals, but those are not as cool as the surreals.
When you start talking about sizes of infinity, you have your first size of infinity – let’s call it omega – and you get numbers like omega + 1, 2 * omega, omega squared, and so forth. In the surreals, you can even talk about crazy-sounding things like x = the square root of omega, and this number really does exist (in the surreals), and has nice properties like x * x = omega (we would be offended otherwise!). The important thing is, I’m not just making up nonsense about some vague idea of sizes of infinity. These are well-defined mathematical constructs that very smart people have thought about, and nodded sagely in solemn agreement. For the sake of using something specific, when I say “size of infinity,” or “infinite number,” I’ll mean an infinite ordinal number.
So far so good. Now for the fun stuff.
A little while ago, I sat down with pencil and paper, and decided to invent a system of notation that would capture the notion of how big different sizes of infinity are. Having some basic math background I was already aware of Impossible Fact #1:
Impossible Fact #1: No system of notation can express every size of infinity.
Let me be more precise. By a “system of notation” I mean a way that we can turn a human-writeable string into a fixed ordinal number. The input string must be from a fixed-size alphabet, since otherwise humans couldn’t practically learn it. You could suggest analog parameters, such as “the length of this line I just drew,” but then you would be assuming we have infinite-precision measuring capacity, which we don’t. So a system of notation is any definable function from strings of a fixed alphabet into ordinal numbers. This is an extraordinarily general definition, and probably includes any practical system any human will ever come up with.
But the first thing to notice (as a mathematician), is that the set of possible outputs from this system of notation is necessarily countable. And there are an uncountable number of sizes of infinity. This was one of the first big surprises when set theory was being born – a fact that can be seen in Georg Cantor’s diagonal argument. So right away, there will be some specific size of infinity that is impossible to write down. And I don’t mean impossible like some number with a billion kazillion digits is “impossible;” I mean literally, logically impossible. As in, if you wrote down every number you could possibly write down, you would still be missing a number.
This will not suprise any mathematicians who are reading this, because it is a well-known idea in the math-world. However, the next fact is something I had to think about a little before understanding.
We know we have to give up on being able to write down every size of infinity – ok. So let’s compromise. How about we come up with a system of notation where, for any infinite number x, we can write down some number y with x < y. That’s a pretty big compromise. We’re giving up on being able to write down an infinite, arbitrarily-large portion of all numbers. But, no, infinity has no mercy.
Impossible Fact #2: Any one system of notation will have all its numbers < most numbers.
In other words, no matter what system of notation you invent, there will always be an infinite number y so that x < y for every single number x in the notation. In fact, it’s even worse than that. If you take the union of all numbers less than any number in the notation, the set you arrive at will still be smaller (as a set) than the numbers remaining. In other words, even in this compromised setting, we still are forced to miss so many numbers that our “captured” set looks infinitely small in comparison.
This last point is not completely obvious to see, although the proof from the ZFC axioms (the most commonly-used axioms of set theory) is easy to understand. Because ZFC works easily with ordinals, I’ll give the proof for ordinals as the sizes of infinity, but surreals are easy to understand as an order-preserving superset of ordinals, so the proof carries over to the surreals as well.
We think of the notation system as a definable function F(x) where x is a natural number (N = natural numbers), and F(x) is an ordinal.
1. By the axiom schema of replacement, there is a set A = {F(x) | x in N}.
Each ordinal number is itself a set, so every element a in A is a set. Every ordinal o can be defined as the set of all smaller ordinals o = {p : p < o}. So the union of A is the union of all elements smaller than any number F(x) that we can write in the notation. We’ll call this union B.
2. By the axiom of union, B = union(A), given by b in B iff b in a for some a in A, is also a set.
Let’s call the rest of the ordinals R. All ordinals O taken together form a proper class — essentially, they are too big to be considered a set. (We get paradoxes if we do – see Russell’s paradox.) As a class, we have R = O – B.
3. B is a set, O is not, so R cannot also be a set.
4. If there were a injective function f:R -> B, then we could use the axiom scheme of replacement (via f inverse) to show that R is a set. This would be a contradiction, so there is no such f, meaning that R can be thought of as having more elements than B.
We could informally write card(R) > card(B), but some might object since usually we only allow taking card(x) when x is a set. But we can safely say that R is infinitely larger than B.
QED
In fact, we’ve proven something even stronger than Impossible Fact #2, because even if we pretend that the input for our notation function F(x) is any ordinal, the same proof works to show that we still miss most infinite numbers R. So, for example, if we allow any real number as an input into our notation, it would still fail.
Alas, there is no system of notation that does what we want. But at least we know to stop looking.
Final score
Humanity: epsilon (for knowing to give up)
Infinity: omega