Infinity is weird, and always will be. I mean, you can’t do something infinitely many times or have infinity dollars, no matter what Scrooge McDuck thinks.

Even mathematicians are not immune to thinking vaguely about infinity.

Georg Cantor was one of the first mathematicians to really sit down and investigate infinity. Until his work in the late 1800s, the conception of infinity, even among mathematicians, was really no deeper than a school child’s; infinity was the thing bigger than all the numbers.

But infinity is larger and deeper than that.

In the last post, we talked about how to determine the size of a set: if we can make a one to one correspondence between two different sets of objects, then those sets are the same size. This is easy if we’re comparing, say, the set consisting of a triangle, a square and a pentagon to the set .

However, using this same idea, we showed (using ideas from our friend, Georg Cantor) the surprising fact that the set of all rational numbers^{1} are only the same size as the set of the counting numbers .

In other words, both sets have the same cardinality, which we defined to be . We also called this size *countably* infinite, since, if we order the rationals in a clever way, we can count them.

Since there are infinitely many rational numbers between 0 and 1, but somehow there are only as many as you can count, it begs the question:

Can we go bigger?

It turns out we can! Just as there are countably infinite sets, there are also * uncountably infinite* sets.

^{2}

Let’s look at all the numbers^{3} between 0 and 1. (This includes numbers like 1/3 and 1/4 and 12358/342893, but also * irrational* numbers

^{4}, like or .) There are a lot of numbers hanging out between 0 and 1, but it isn’t immediately clear that there are

*more*of them than there are in a countable set, is it?

It turns out that the set of numbers between 0 and 1 is *bigger* than the set of counting numbers, i.e., that they are uncountable. We’ll prove it.

Now, even though we want to prove the real numbers are *un*countable, we’re going to prove it by assuming the opposite: that they are *countable.* By the definition of countable, that means we can set up a one to one correspondence with the counting numbers. In other words, we can count all those numbers between 0 and 1.

Counting them is the same as saying that we can put *all* of them in a list, since they are countable, or, rather, because we assumed they are countable.

So, if we can find a number between 0 and 1 that is *not* on the list, then something is wrong with the assumption we made about our set being countable. And since it can’t be countable, therefore it is uncountable^{5}. Still with me?

In order to explain how to find this number, we need to talk a bit about decimal representations. Every number can be expressed as an infinite decimal. So, 1/3 = 0.33333333333…, and = 0.141592652589…, and 1/4 = 0.2500000…

These representations are unique… *unless* we have a repeated nine. For instance, 0.499999999… = .5, for the same reason that 0.999999… = 1. ^{6} In order to avoid this, let’s outlaw repeated nines.

In order to find a number not on the list, we just need to find a decimal representation that is different than all of those in the list (and make sure it doesn’t accidentally have repeated nines.)

While our assumption that the numbers between 0 and 1 are countable does not mean we know what the list actually *is*, let’s pretend we have such a list, like this one:

Don’t worry that there is no rhyme or reason to this list. The main argument below should work for *any* list that we could think up, whether it is reasonable or random.

How can we construct a number not on the list? Well, in order for our new, constructed number to be different than any given number on the list, it has to differ by at least one digit.

We will ensure that our new number is different than any number already on the list by making sure that the **first** digit of the new number is different than the **first** digit of the **first** number on the list, the **second** digit of the new number is different than the **second** digit of the **second** number, the **third** digit of the new number is different than the **third** digit of the **third** number, the **fourth** digit of the new number is different than the **fourth** digit of the **fourth** number, and so on and so forth.

So, we make the first digit different than 8. Let’s start by saying the first digit of our new number is 6, giving us 0.6.

We also need it different from the second number. We’ve already decided on the first digit, but we can make the second digit 6 as well, since 6 is different than 7. This gives us 0.66.

For the third digit, we can’t use 6, but 5 would work instead, so the third digit of our new number is 5. Our new number is 0.665.

For the fourth digit, we’ll again pick 6, since 6 is different than 3.

So far, our new number is 0.6656. It is clearly different than the first four numbers on the list, since they each differ by (at least) a single digit.

And this pattern is easy to continue. If the **n-th** digit of the **n-th** number on the list is anything but a 6, we make the **n-th** digit of our new number a 6. If it *is* a 6, we’ll make the **n-th** digit a 5. We do this infinitely many times to define the new number.^{7}

Since our new number is different than *every *number in our list, it can’t be in the list!^{8}

And thus, the numbers between 0 and 1 are *uncountable*.

So we now have countable infinity, and the bigger *uncountable* infinity. Can we go biggerer?

We can!

You might first be tempted to guess that the set of *all* numbers (from to ) would be even bigger than the set of numbers between 0 and 1, but it turns out these two sets have the same cardinality, i.e. are the same size.

What’s more surprising is that all the points in the plane *also* have the same cardinality. I won’t prove this here, but the idea is to make a “curve” that goes through every point in the plane. You can do this in any dimension.

So how *do* you come up with a bigger(er) infinity?

In the next post, we’ll discuss power sets.

- As a reminder, rational numbers are the numbers that can be written as a fraction of integers, like 2/3 or -7/18. ↩
- “Uncountable” is not just the negation of countable. It’s the technical term for any set of larger cardinality than . ↩
- I mean real numbers. In other words, we’re not talking about imaginary numbers, but any other number will do. ↩
- Irrational numbers are just any number that can’t be written as a rational number, i.e., as a fraction. ↩
- This method of proof is called “proof by contradiction,” and is a standard method in mathematics. In this method, you assume that something is true, and then use it to show that something that is “obviously” false is true. ↩
- If you take two different representations, the representations have to differ by at least one digit. So, if you subtract the two, you have some (non-zero) difference between them, so they aren’t the same number. The only exception to this working is for repeated 9’s, as mentioned. This is because it isn’t immediately obvious what should be. However, those two numbers happen to be the same. (In case you haven’t seen this, let . Then , and so . Dividing by , we get , and so .) ↩
- This argument is called “Cantor diagonalization.” It shows that infinity is not a monolithic concept or size. I’m planning on writing a short extra post about Cantor. He was an interesting person. ↩
- How’s that for a tautology? ↩

It is fun that basically the same proof is used to show that for formal grammars, it is impossible to formally represent all possible formal grammars.

LikeLike