# Countable and Uncountable Infinities

*

“The man who ate from the tree of knowledge of the infinite, the great Gauss, had warned mathematicians: ‘Don’t deal directly with infinity! Never look at it face to face!’ But Cantor disobeyed. And so he discovered the amazing fact that there are degrees of infinity.”*

*

***

*

“David Hilbert, in 1924, devised a famous thought experiment, called the ‘paradox of the grand hotel’, to show us just how hard it is to wrap our minds around the concept of infinity. Imagine a hotel with an infinite number of rooms and it’s completely full ― totally booked up with an infinite number of guests.

A man walks into the hotel and asks for a room. How can the manager make room for him? The answer is that he asks the guest in room number 1 to move to room number 2, 2 to 3, 3 to 4, and so on. Every guest moves from room number n to room number n.+.1. Since there are an infinite number of rooms, there’s a new room for each existing guest, and this leaves room 1 open for the new customer. The process can be repeated for any finite number of new guests.

But what about an infinite number of new guests? How can the manager accommodate them all? The answer is that he asks the guest in room 1 to move to room 2, 2 to 4, 3 to 6, and so on. Each current guest moves from room number n to room number 2n, filling up only the even-numbered rooms. By doing this, he’s now emptied all of the odd-numbered rooms, which makes enough room for the infinite number of new guests.

But what about an infinite number of buses, each filled with an infinite number of passengers? How can the manager possibly make enough room this time? Well, he uses the fact that there’s an infinite quantity of prime numbers. He assigns every current guest to the first prime number, 2, raised to the power of their current room number. Then he takes the people on the first of the infinite buses and assigns them to the next prime, 3, raised to the power of their seat number on the bus. This continues for all of the first bus. The passengers on the second bus are assigned powers of the next prime, 5. The following bus, powers of 7. And so on. In this way, the manager can accommodate every passenger on every bus. There will be many rooms that go unfilled, like room 6, since 6 isn’t a power of any prime number. Luckily, his bosses weren’t very good at math and don’t recognize the inefficiency, so his job is safe.” 

*

***

*

“A countably infinite set is one you can ‘count’, meaning you can put its members into one-to-one correspondence with the natural numbers (1, 2, 3, …). All countably infinite sets are considered to have the same ‘size’ or cardinality.

This idea seems to make sense, but it has some funny consequences. For example, the even natural numbers are countably infinite because you can pair the number 2 with the number 1, 4 with 2, 6 with 3, and so on. So there are just as many even numbers as natural numbers, even though intuitively you’d think there should only be half as many.

It was Galileo (1562–1647) who first noticed these funny results, and they put him off thinking about infinity.” 

*

***

*

“What about the cardinality of the rational numbers? These are the numbers formed by dividing one integer by another non-zero integer. Well, with the natural numbers and integers, there are obvious gaps between them. Between 1 and 2, there are no other natural numbers. But between any two rational numbers, there’s always another rational number ― they’re dense. So between 1 and 2, there are an infinite number of rationals. So surely the cardinality of the rational numbers is larger than that of the natural numbers, right?

Astonishingly, it turns out that there is a way to create/demonstrate a one-to-one correspondence between the rational numbers and the natural numbers.

So the rational numbers are also countably infinite.

And a similar (though slightly more complicated) method can be used with the algebraic numbers, demonstrating that they’re countably infinite as well.” 

*

***

*

“What about the real numbers? They’re also dense.

How could you list them all? Or even just those in the interval between 0 and 1? Surely there must be a similar trick.

It turns out that it can’t be done.

In 1891, using his famous ‘diagonal argument’, Cantor proved that for any infinite list of numbers in the interval [0,.1], there will always be numbers in that interval that aren’t on the list.” 

“Thus, he rigorously showed that the cardinality of the real numbers is larger than the cardinality of a countably infinite set.” 

“I’ve found a clear difference between a collection like the totality of real algebraic numbers and the so-called continuum.” [Cantor]

*

***

*

“A set is uncountably infinite if it contains so many elements that they can’t be put in one-to-one correspondence with the set of natural numbers.

Examples of uncountably infinite sets include the real, complex, irrational, and transcendental numbers.” 

*

***

*

“Later on, Cantor revised the idea, proposing a whole hierarchy of infinities, each one ‘bigger’ than the last.

The smallest is the countable infinity ― the cardinality of the natural numbers ― which he named ‘aleph null’. This is followed by the cardinality of the real numbers ― which he named ‘aleph one’. This is followed by ‘aleph two’, and so on.” 

I once said to my friend Nikolai, “It’s so cool that the uncountable infinity is the size of 2 to the power of the countable one!” and he responded, “You shouldn’t think about it that way. That’s just ‘notation overload’.”

“Cantor’s ideas were controversial at first but have since become an accepted part of pure mathematics.” 

*

***

*

“What’s the length of a point? It’s 0.

So on the number line, what’s the length of the line segment from 0 to 1 if we remove the point ½? It’s still 1. Even though the line segment is made up of a continuous set of points ― there are nothing but points between 0 and 1 ― if we remove the point ½, we haven’t changed its length.

The naïve conception of a point is wrong. We might imagine that if we remove a point from a ruler, we should be able to hold it up to the sun and see a little bit of light shine through. But if that were the case, we’d be removing a little bit of length.

What about when we remove an infinite number of points?

Once again, imagine the line segment from 0 to 1. Now imagine that we remove all the fractions. What’s crazy is that between any two fractions, there’s another fraction ― it’s dense. However, the set of all fractions is countable or listable. If we add up the length of everything on our list of fractions, we get 0.+.0.+.0.+.…, which equals 0.

So if we remove a countable number of points from a continuum, the length of the continuum remains unchanged.” 

*

***

*

“The continuum hypothesis, first proposed by Cantor in 1878, states that there’s no set whose cardinality is strictly between that of the integers and the real numbers.

Cantor believed the continuum hypothesis to be true, and he tried in vain to prove it for many years. In 1963 however, complementing earlier work by Gödel in 1940, Paul Cohen proved that whether or not the continuum hypothesis is true is independent of ZFC set theory.” 

“Zermelo-Fraenkel set theory is an axiomatic system that was proposed in the early 20th century in order to formulate a theory of sets free of paradoxes such as Russell’s paradox. Today, Zermelo-Fraenkel set theory, with the axiom of choice included (ZFC), is the standard form of axiomatic set theory, and as such is the most common foundation of mathematics.” 

*

***

*

This amazed me when I first learned about it, and it still amazes me to this day. It feels like something strange is going on here, something that breaks my intuition. Since there’s a rational/algebraic number between every rational/algebraic number, it seems like there’d be no gaps ― like that would enough to form the continuum. But it turns out they’re not truly continuous ― there are numbers like e and π that are left out.

But not only that ― it also turns out that the real numbers are an entirely different beast than any of their subsets discussed ― you could even say categorically different. It’s like the transition from the rational/algebraic numbers to the real numbers is when the jump from discrete to continuous truly occurs. And this jump itself is discrete.

*

*

*

*

Citations

1. (source lost)
2. Jeff Dekofsky
3. plus.maths.org
4. irregularwebcomic.net
5. mathworld.wolfram.com
6. Simon Pampena & Numberphile
7. Wikipedia’s Continuum Hypothesis article
8. Wikipedia’s Zermelo-Fraenkel Set Theory article