# In-Depth

Here we will carefully prove that $$|(0, 1)| > |\mathbb{N}|$$.

Recall that two sets are the same size if there is a one-to-one correspondence between them. We want to show this isn't the case; we want to show that it is impossible to make a one-to-one correspondence between $$\mathbb{N}$$ and $$(0, 1)$$.

In Basics of Set Theory, we saw that a correspondence between $$N$$ and another set $$\mathscr{S}$$ is the same as making a certain type of list of elements of that set.

$0 \leftrightarrow ?\\ 1 \leftrightarrow ?\\ 2 \leftrightarrow ?\\ 3 \leftrightarrow ?\\ 4 \leftrightarrow ?$

This list is a one-to-one correspondence if everything in the set $$\mathscr{S}$$ appears exactly once on the right side. In other words, if every element of $$\mathscr{S}$$ gets a natural number assigned to it (i.e. appears on the list), and it gets only one natural number assigned to it (i.e. it appears only once on the list).

We will show that any possible listing of the elements of $$(0, 1)$$ cannot represent a one-to-one correspondence with $$\mathbb{N}$$, because it will miss some element of $$(0, 1)$$. In fact, we'll imagine we have a listing of the elements of $$(0, 1)$$, and explicitly construct an element of $$(0, 1)$$ that is not on that list.

So suppose we have a list. Suppose we tried our best to systematically write down every element of $$(0, 1)$$ into a list. Remember $$(0, 1)$$ is the set of all decimals between $$0$$ and $$1$$. There's a lot of arbitrary choice in how the list goes, but that doesn't matter. The list is going to have to be infinite, but suppose we made this list (or used some clever algorithm to define it, like when we made a list between $$\mathbb{N}$$ and $$\mathbb{Z}$$ in Basics of Set Theory).

The list might start out like this.

$0 \leftrightarrow 0.0\\ 1 \leftrightarrow 0.0001\\ 2 \leftrightarrow 0.011001\\ 3 \leftrightarrow 0.0115\\ 4 \leftrightarrow 0.0111\\ 5 \leftrightarrow 0.1\\ 6 \leftrightarrow 0.2\\ 7 \leftrightarrow 0.25\\ 8 \leftrightarrow 0.5\\ 9 \leftrightarrow 0.55555...$

Notice how arbitrary it is. There's certainly no obvious systematic way to proceed, when making such a list. That's okay, though. Maybe someone else came up with a clever algorithm, and generated this list for us.

But now we'll construct a specific “magic” element of $$(0,1)$$ that is not on this specific list. This is how we do it. Our magic element is a decimal between zero and one, so it starts with zero and a decimal point.

Construction Step 1: Look at the first number on the list, the one that corresponds to $$0$$. Look at the tenths place digit of this number. Whatever that digit is, pick a number between $$0$$ and $$8$$ that is different than it, and put this as the tenths place digit of our magic number.

(A little bit later I'll explain why we don't want to choose the digit $$9$$.)

In our example, the first number on the list is $$0.0$$. The tenths place digit is $$0$$. So we choose a digit between $$0$$ and $$8$$ that isn't $$0$$ -- let's choose $$7$$. This becomes the tenths place digit of our magic number. So our magic number starts out "$$0.7…$$".

Construction Step 2: Look at the second number on the list. Look at its hundredths digit (the second one after the decimal point). Whatever that digit is, choose a digit between $$0$$ and $$8$$ that is different from it, and make that the hundredths digit of the magic number.

In our example, the second number is $$0.0001$$. It's hundredths digit is $$0$$. So let's choose $$3$$. Our magic number now starts "$$0.73…$$".

Construction Step 3: Look at the third number. Look at the thousandths digit (the third one after the decimal point). Whatever it is, choose a different digit (between $$0$$ and $$8$$), and make that the thousandths digit of the magic number.

In our example, the third number is $$0.011001$$. The thousandths digit is $$1$$. So we can choose $$3$$ for the thousandths digit of our magic number. We now have "$$0.733…$$".

And we repeat this process, or imagine repeating this process, forever:

At Construction Step $$N$$, we look at the $$N$$th number on the list. We look at the digit in the $$N$$th place to the right of the decimal point. Whatever it is, we choose a different digit (between $$0$$ and $$8$$), and set that as the digit in the $$N$$th spot to the right of the decimal point of our magic number.

Once we've done this for every $$N$$, our magic number is built. Let's call it $$X$$. It's a specific real number between zero and one.

To recap, we started with a (never-ending) list of elements of $$(0,1)$$. From it, we built a magic decimal $$X$$. I claim that this element $$X$$ is not on the list (and I'll prove this in a second). Therefore our list cannot be a one-to-one correspondence list -- it didn't actually list all the elements of $$(0,1)$$.

So how do we know that $$X$$ is not on the list? Since the list is infinite, couldn't $$X$$ show up somewhere, far enough down?

Here is the key insight: $$X$$ is not on the list, because it is different from everything on the list. It's not in the first spot, because it differs from that number, in the first digit to the right of the decimal point. It's not in the second spot, because it differs from that number, in the second digit out from the decimal point. And on and on.

The number $$X$$ doesn't show up in the 583rd spot, because it differs from whatever is there, when we look at their digits 583 spots out from the decimal point. We constructed $$X$$ in such a way that it is different from every number on the list.

Now, sure, we could add $$X$$ to the list, maybe put it at the top and bump everything else down. But then we have a new list. With this new list, we could construct a new magic element, call it $$Y$$. And by the same logic, $$Y$$ is not on the new list. Any list we make will still be missing an element of $$(0, 1)$$.

Therefore there can be no one-to-one correspondence between $$\mathbb{N}$$ and $$(0, 1)$$. And this shows that the infinite set is bigger than $$\mathbb{N}$$. Note, however, that we could make a one-to-one correspondence between $$\mathbb{N}$$ and a subset of $$(0,1)$$. So $$|(0, 1)| > |\mathbb{N}|$$.

Minor technical detail: Why didn't we want the digits in our magic element to include any nines? This is subtle. Many elements of $$(0, 1)$$ can actually be written in two ways, one of which uses repeated nines. You may have learned that

$1 = 0.99999999999…..$

This fact also means that, for example,

$0.1 = 0.0999999999….$

And so if we let the digits of the magic element include nines, in theory we could run into trouble. For example, suppose the list started out like this.

$0 \leftrightarrow 0.0\\ 1 \leftrightarrow 0.1$

In theory, if all the rest of the numbers on the list allowed it, we could end up constructing our magic element $$X$$ to be $$0.09999999…$$. Then in terms of digits, $$X$$ differs from everything on the list. However, since $$0.1 = 0.099999…$$, our magic element $$X$$ is right there on the list, in the second spot!

To avoid this hole in the argument, we just insist that the digits of $$X$$ are between zero and eight.

Top