Chasing the infinite

Surprising mathematical results on infinity

Sunday, 10 May 2015

What is infinity? Perhaps, like me, you were told that it’s just a concept to remind us that there is no largest number. It’s true that if you treat it like a regular number, subject to the usual rules of arithmetic, you run into all kinds of confusing nonsense. But this needn’t prevent us from studying the properties of infinity – it just means we need to be careful. The infinite is far more interesting and surprising than I could have imagined.

Cardinality and bijections

In order to understand infinity, we need to make a detour to set theory. A set is a collection of objects, and the cardinality of a set is the number of unique objects it contains. For example, the set $S = {◯, □, △}$ has cardinality $| S | = 3 .$ Two sets have the same cardinality if and only if their objects can be paired off without leaving any out. This pairing-off is a called a bijection or a one-to-one correspondence, technically defined as a function that is both injective and surjective.¹ For example, given the set $B = {2, 3, 5},$ we can prove that $| S | = | B |$ by constructing a bijection $f : S \to B$ that maps $◯$ to 2, $□$ to 3, and $△$ to 5.

Of course it’s obvious that both sets contain three objects, but the power of this method is that it allows us to compare infinite sets. Given that infinity plus one is still infinity, can we conclude that all infinities are the same? Common sense says yes: how can anything possibly be bigger than infinity? However, as is often the case in mathematics, we really need to throw common sense out the window if we want to discover the truth.

Hilbert’s hotel

Suppose you’re trying to book a room in an infinite hotel. The innkeeper informs you that all rooms are taken. Disappointed, you turn away to leave.

“Wait!” shouts the innkeeper, “I can make room for you.” He knocks on the door of Room 1, and politely asks the guest to move to Room 2. That room also being occupied, he persuades the guest of Room 2 to move to Room 3. And so it continues, each guest moving to an adjacent room. The innkeeper then hands you the key to the first room.

Soon afterwards, an infinite number of people arrive and cram in the hotel reception. They, too, are unhappy to discover that all rooms are occupied.

“It’s okay,” the innkeeper assures the party. “Just make sure you take odd-numbered rooms.” He then rushes ahead and knocks on your door, telling you to move to the second room. The guest in Room 2 is told to move to Room 4, and the guest in Room 3, to Room 6. Each guests goes to the room whose number is double their own, and in this way an infinite amount of odd-numbered rooms become free for the new guests.

Countability

Hilbert’s hotel illustrates that adding one to a regular infinity, or even multiplying it by two, leaves you with the same infinity. This value is the cardinality of the natural numbers $ℕ = {0, 1, 2, \dots},$ and we denote it by $| ℕ | = ℵ_{0}$ (pronounced aleph nought). If a set’s cardinality is equal to $ℵ_{0},$ then we call it a countable infinity, because it’s possible to count off all its objects by association with natural numbers. Roughly speaking, if you can generate a list of all objects in a set by following some pattern, then the set is countably infinite. All other infinities are larger, and called uncountable.

Another way of interpreting the hotel example is this: there are just as many even numbers as natural numbers. In a way this seems wrong – surely there are twice as many natural numbers? But both sets are countably infinite, so their cardinalities must be the same: we prove this by constructing the bijection $f (n) = 2 n .$ You might argue that this is just a matter of definition, and that it is meaningless to say that two infinities are equal. Perhaps, but that is a philosophical question, not a mathematical one. Whether you subscribe to the formalist “useful but meaningless marks on paper” or the Platonist “objective, timeless truths about abstract entities” is completely up to you. Rest assured: there are good reasons for using the bijection-based definition, and there is still more we can learn from it.

For example, the integers are countably infinite as well: we can construct the bijection $f : ℕ \to ℤ$ that lists the integers by alternating signs:

0, + 1, - 1, + 2, - 2, + 3, - 3, \dots

More surprising is the fact that the rationals are countable: $| ℚ | = ℵ_{0} .$ How can this be, when there are infinitely many rationals between 0 and 1? There are many ways of proving this, but I’m more interested in giving you an intuitive understanding of countability. We can take care of signs using the alternating trick, but what then? We can’t go in increasing order, since the rationals get arbitrarily close to zero. But look at this:

Counting the rationals by zigzagging through a matrix

We can generate a list of all rationals just by following the red arrows, as long as we include zero somewhere and put $\pm$ in each cell. We have to skip some cells to make it a bijection, but that’s not a problem. In fact, if we don’t skip any cells, the function is surjective and not injective, which tells us that $ℚ$ is either countably infinite or finite – and it clearly isn’t finite.

Cantor’s diagonal argument

What about the real numbers: is $ℝ$ countably infinite? Suppose, for the sake of argument, that it is – suppose we can map each natural number to a unique real number without missing any real numbers. This would give us a list of values that might look like this:

\begin{matrix} x_{0} = 0.7812272323372748 \dots \\ x_{1} = 25.823506400277566 \dots \\ x_{2} = 7.4937386056237065 \dots \\ x_{3} = 3.1415926535897932 \dots \\ ⋮ \end{matrix}

These are decimal expansions of real numbers; the digits go on forever. We’re assuming this is a bijection, so each real number must be unique.² We can represent the digits in our hypothetical list with variables:

\begin{matrix} x_{0} = ? . d_{11} d_{12} d_{13} d_{14} \dots \\ x_{1} = ? . d_{21} d_{22} d_{23} d_{24} \dots \\ x_{2} = ? . d_{31} d_{32} d_{33} d_{34} \dots \\ x_{3} = ? . d_{41} d_{42} d_{43} d_{44} \dots \\ ⋮ \end{matrix}

I’ve put question marks before the decimal points because I only care about the fractional part. Now, this list is supposed to be complete – every real number needs to be on it somewhere. But consider the real number $y = 0. e_{1} e_{2} e_{3} e_{4} \dots,$ where $e_{1} \neq d_{11},$ $e_{2} \neq d_{22},$ $e_{3} \neq d_{33},$ and so on. This still leaves us with eight symbols to choose from for each digit of $y .$ Since the first digits differ, $y \neq x_{0} .$ Similarly, $y \neq x_{1},$ because the second digits differ. Generalizing this to all the $x$ values, we realize that $y$ is not on the list. But $y$ is a real number! This is a contradiction, therefore our initial assumption was wrong: it is impossible to construct this list. In reality, $| ℝ | \neq ℵ_{0},$ so the set of real numbers is uncountably infinite.

The continuum hypothesis states that $| ℝ | = ℵ_{1},$ which means that there is no intermediate infinity between the cardinalities of the naturals and the reals. This has never been proven or disproven. In fact, it’s impossible to do either in ZFC,³ the standard axiomatic set theory used today. You can assume that it’s true or that it’s false, and the theory remains consistent, assuming ZFC is consistent in the first place (also unprovable). There is no consensus on what all this actually means. Does the question become meaningless just because it can’t be decided by our current axiomatic framework? We are once again getting into philosophical territory.

Higher dimensions

Yet another counterintuitive fact about cardinalities is that $| ℝ | = | ℝ^{2} | .$ In other words, there are just as many points on the real number line as there are on the Cartesian plane. This is true even even though we can divide the plane into infinitely many lines. Consider a point $(x, y)$ on the plane, where

\begin{matrix} x = \dots a_{3} a_{2} a_{1} . d_{1} d_{2} d_{3} \dots \\ y = \dots b_{3} b_{2} b_{1} . e_{1} e_{2} e_{3} \dots \end{matrix}

We can construct a bijection⁴ $f : ℝ^{2} \to ℝ$ by interleaving the digits:

f (x, y) = \dots a_{3} b_{3} a_{2} b_{2} a_{1} b_{1} . d_{1} e_{1} d_{2} e_{2} d_{3} e_{3} \dots

This idea generalizes: for any infinite set $X$ and finite natural number $n,$ we have $| X | = | X^{n} | .$ Before this was discovered, the number of coordinates required to represent a point in a space was assumed to be an invariant of that space. This is not true, since a single real number can be used to represent a point in a space of any dimension, and vice versa.

Cardinals and ordinals

So far, we’ve only talked about infinite values that are cardinalities of infinite sets. These values are the cardinal numbers:

0, 1, 2, \dots, n, \dots, ℵ_{0}, ℵ_{1}, ℵ_{2}, \dots, ℵ_{α}, \dots

Every natural number is finite. The first infinite cardinal is $ℵ_{0},$ and we call it countably infinite. Everything past $ℵ_{0}$ is uncountably infinite. The aleph numbers are strange because adding one to them, or even doubling them, results in the same cardinal. However, if we take the power set⁵ of $ℕ,$ we get a set with cardinality $2^{ℵ_{0}} = | ℝ | > ℵ_{0} .$ If the continuum hypothesis is true, then $ℵ_{1} = 2^{ℵ_{0}} .$ In any case, we can generate ever-larger uncountable infinities with this kind of exponentiation.

The ordinal numbers are another way of extending the natural numbers to infinity. The definition is a bit more complex: two well-ordered sets represent the same ordinal if and only if they are order isomorphic, meaning there exists an order-preserving bijection between them. As a result, ordinals can discriminate infinities more finely than cardinals:

0, 1, \dots, n, \dots, ω, ω + 1, \dots, ω \cdot 2, ω \cdot 3, \dots, ω^{2}, ω^{3}, \dots, ω^{ω}, ω^{ω^{ω}}, \dots, ϵ_{0}

As with cardinals, the finite ordinals are simply natural numbers. The least infinite ordinal is $ω,$ and it is equivalent to $ℵ_{0} .$ Unlike the cardinals, $ω + 1$ is distinct from $ω,$ though both are countable. Strange as it may seem, there are uncountably many countably infinite ordinal numbers. We can add to $ω,$ multiply it, square it, raise it to the power $ω,$ … each of these is a countable infinity greater than the last. The next step is to repeat the exponentiation using the recursive definition $ϵ_{0} = ω^{ϵ_{0}} .$

Spiral visualization of some countable ordinal numbers (Wikimedia Commons)

We can play this game as long as we want, but no matter what system we come up with, it will never capture all the infinities – there will always be a larger ordinal that lies outside the system. We can keep finding these larger ordinals, but they become more and more difficult to describe. And we’re still only talking about countable ordinals! The first uncountable ordinal is $ω_{1},$ and it is represented by the set of all countable ordinals.

Conclusion

We often use the symbol $\infty$ without thinking twice, but infinity is so much more strange and intricate than the simple idea of numbers never ending. Our human intuition is a poor guide here, as is demonstrated by nearly every result on the subject. Incidentally, it’s thanks to Georg Cantor, the inventor of set theory, that we know about (almost) everything I’ve written here. Cantor encountered fierce objection to his work precisely because it was so counterintuitive, but today we recognize it as a cornerstone of modern number theory. That being said, number theory is far from being a complete story! And there’s much more to be said about infinity than I’ve been able to fit in this finite article – I was tempted to make it infinitely long, but I’ve gone on for long enough now.

Injections and surjections are special classes of functions. An injective function (one-to-one function) preserves distinctness: no two inputs are mapped to the same output. A surjective function (onto function) is required to map to every output value in its codomain at least once. ↩︎
We have to watch out for values with infinite repeating nines. Although 0.999… and 1.0 look different, they in fact represent the same real number. We get around this by picking one representation and using it consistently in the list. ↩︎
ZFC is short for “Zermelo–Fraenkel set theory with the axiom of choice.” ↩︎
Once again, there are some complications with repeating decimals. There are other, more complicated ways of constructing the desired bijection. ↩︎
The power set of a set $S,$ denoted by $𝒫 (S),$ is the set of all subsets of $S,$ including the null set and $S$ itself. ↩︎