In the previous section we learned about these two infinite sets of numbers:

Rational numbers: Q = {0, … 1/2, … 3/4, … 1, …}

Real numbers: R = {0, … 1/2, … 3/4, … 1, … √2, …}

In that section, we focused on Q, and we proved that the size of Q is still the same size as N. That means that so far, every infinite set we have considered is still the same size, ℵ_{0}.

In this section, we focus on R, the real numbers.

R = the real numbers. The rational numbers plus the irrational numbers.

Set R includes all the rational numbers from Q, * and* all the irrational numbers too. (Like for Q, in R we just include positive numbers and 0.)

* Irrational numbers* are those that cannot be expressed with fractions, like π (pi) and √2 (the square root of 2).

If you write out the decimal value of an irrational number, the decimal will keep going forever without repeating or terminating.

Let’s see if you’ve got it.

What we want to know is what is the cardinality of R? Is it the same as all of the other infinite sets we’ve considered?

If you think it is impossible for there to be different sizes of infinity, you are not alone!

Many people have that reaction when they first hear about the different sizes of N and R.

We will prove that the size of R is a larger infinity than N.

We can use the logic you’ve learned in this course, though, to prove that the size of R is a larger infinity than N.

**What we will prove, actually, is that |R| ≠ |N|.**

We prove |R| ≠ |N| by reductio.

If their sizes are not the same, then it is quite easy to show that R is larger, because everything in N is in R, but not vice versa.

Our proof of |R| ≠ |N| will be a reductio.

For our reductio, we assume that R and N are the same size.

For our reductio, we assume that R and N are the same size, and we prove that a contradiction results.

Next, we use our reductio assumption to start working toward that contradiction.

If R and N are the same size, then there must exist a 1-to-1 correspondence between them.

So now we know an existential claim: there exists a 1-to-1 correspondence between R and N. We need to use the proof strategy of existential instantiation (the informal version of EElim), in order to prove that a contradiction follows.

As you know, to use an existential claim with existential instantiation (EElim), we need to use arbitrary names to talk about the 1-to-1 correspondence.

Since we will need a lot of arbitrary names, we will use n_{0}, n_{1}, n_{2}, etc., for them.

If there exists a 1-to-1 correspondence between N and R, then we know there is a pairing like this:

N—R

0—n_{0}

1—n_{1}

2—n_{2}

3—n_{3}

Etc.

Where n_{0} is the real number paired with 0; n_{1} is the real number paired with 1; etc.

To take an example: we don’t know which real number n_{14} is. All we know, if there is a 1-to-1 correspondence, is that * some* real number is paired with the natural number 14. We are using n

We know that every real number is on this list.

Since this is a 1-to-1 correspondence, we know that every real number is on this list.

In order to show that a contradiction follows, we will prove that it also follows that there is a real number * not* on the list.

If we can show that there is a real number * not* on the list, then our work is done. That contradiction finishes the reductio, and that means that R and N are not the same size.

So our new goal is to show that there is a real number * not* on the 1-to-1 correspondence given above.

In order to do that, we need to look more closely at the arbitrary real numbers n_{0}, n_{1}, n_{2}, etc.

Each real number can be expressed by an infinitely long decimal expansion.

Each one of them can be expressed by an infinitely long decimal expansion, such as 0.1342970178…

If the number is * irrational*, then this decimal expansion will never terminate or repeat.

If the number is * rational*, then it will either terminate or repeat. For example, 1/4 terminates: 0.25. And 1/3 repeats: 0.33333…

But if a number terminates, we can still represent it by an infinitely long decimal, because just zeros come after it. So we will represent 1/4 as 0.250000…

Let’s see if you’ve got it.

Now that we know how each real number can be represented by an infinitely long decimal expansion, * we will focus on just one decimal place* of each real number in our 1-to-1 correspondence.

N—R

0—n_{0}

1—n_{1}

2—n_{2}

3—n_{3}

Etc.

The * first* real number on the list is n

The * second* real number on the list is n

And so forth for the rest of the real numbers.

Here’s an example, which will make this clearer. Let’s say:

n_{0} = 0.35879…

n_{1} = 0.19154…

n_{2} = 4.00000…

n_{3} = 0.33333…

Etc.

The * first* real number on this list is 0.35879…, so we focus on it’s

The * second* real number on this list is 0.19154…, so we focus on it’s

Here’s what it looks like, when bold those numbers:

n_{0} = 0.**3**5879…

n_{1} = 0.2**9**154…

n_{2} = 0.00**0**00…

n_{3} = 0.333**3**3…

Etc.

Notice how they make a diagonal line going downward to the right. (We ignore any number to the left of the decimal place.)

What we do next is we take all those digits and put them together to make a new real number: 0.3903…

We’ll call this number d, for the diagonal.

d = 0.3903…

The number d takes the first decimal place from the first number on the list, the second place from the second number, etc.

Let’s see if you’ve got it.

Notice that each different 1-to-1 correspondence will generate a different diagonal number. That doesn’t matter. We know there exists * some* correspondence between N and R.

So we know there exists *some* diagonal number for it.

So we know there exists * some* diagonal number for it.

For example, we were imagining that this is the 1-to-1 correspondence:

N

0

1

2

3

Etc.

—

—

—

—

—

R

0.**3**

0.2

0.0

0.3

5879…**9**154…

0**0**00…

33**3**3…

And for that correspondence, d = 0.3903… A different correspondence would have a different d. But it is helpful to work with an example, so let’s continue with this correspondence for now.

e = the counter-diagonal.

The next thing we do is define a new number, which we’ll label “e”. We will call e the * counter-diagonal*.

To make e, we just add 1 to every decimal place of d. If d has a 9, then it becomes 0. We leave the “0” in the ones place at the front alone. Just add 1 to every place right of the decimal point.

Let’s see if you’ve got it.

e is a real number.

Notice that e is a real number.

We don’t know if it is rational or irrational, but we know it is some real number or other, because it is just an infinitely long decimal. Since the number to the left of the decimal point is 0, we know e is some number between 0 and 1.

Now that you understand e, we can ask this key question.

e is a real number that is * not* on the 1-to-1 correspondence. But that is impossible, because every number must on the correspondence.

The nifty thing about how we defined e is we can show that it is * not* on the 1-to-1 correspondence between R and N.

That is, we can show that e ≠ n_{0}, and e ≠ n_{1}, and e ≠ n_{2}, etc.

For example, consider n_{0}, the first real number on the list; the real number paired with 0.

We know that e is different from n_{0} in its first decimal place (the 10ths place).

We know that e is different from n_{0} in its first decimal place (the 10ths place). That is because the 10ths place of n_{0} went into d, and e is different than d in every decimal place.

Similarly, e is different from n_{1} in its second decimal place. And so on for every real number on the list.

What that means is we have proven a contradiction: since the list is a 1-to-1 correspondence, every real number is on the list. Since e is a real number, e is on the list.

Contradiction: e is on the list, and e is not on the list.

But we can also show that e is not on the list. That is a contradiction.

The way we created e might now seem like a trick to you, but it isn’t just a trick. It really works!

Using just the proof ideas you’ve learned in this course, like reductio and reasoning with quantifiers, we can show that the cardinality of R is greater than the cardinality of N.

And thus there are different sizes of infinity.

A common reaction to this proof is to think that it can’t really work. For example, why can’t we just take e, and pair it with 0, and move all the other real numbers down?

That is how we operated when we were doing transfinite arithmetic in Chapter 34.

But that does not work here. This reductio proof does not depend on any specific 1-to-1 correspondence or any specific real number e.

No matter what 1-to-1 correspondence there is between N and R, there will always be some diagonal number d, and thus also some counter-diagonal e that is not on the list.

We discussed an example e only to make it easier to understand the proof. But really our proof method was completely general.

**No matter what 1-to-1 correspondence there is between N and R, there will always be some diagonal number d, and thus also some counter-diagonal e that is not on the list**.

And therefore it is not a 1-to-1 correspondence after all. **What this shows is that there can be no 1-to-1 correspondence between N and R**, and thus N and R are not the same size.

Hence there are different sizes of infinity.

That is as far as we will take our investigation in this textbook. If you wish to continue, there are many more amazing things we can prove in advanced logic!

Login

Accessing this textbook requires a login. Please enter your credentials below!