Cantor diagonalization is a method of proof developed by the mathematician

Georg Cantor in the late 1800's. It's a simple, elegant, and powerful form of

proof by contradiction (a.k.a.

reductio ad absurdum), and it has been used in one form or

another in many of

the most important mathematical results of the last century. (It's

also known as diagonal proof,

diagonal argument, or just plain old diagonalization. It's not to be confused with

this, which is something totally different.) In their abstract form, diagonal proofs can be rather confusing, so we'll start with a simple and relatively concrete example: Cantor's proof that there are more

real numbers than there are

whole numbers.

"But wait," I hear you say, "aren't there an infinity of both whole numbers and real numbers? How can there possibly be more of one than the other?"

Well, it's true that there's an infinity of both. It's also true that there's an infinity of integers, an infinity of odd numbers, an infinity of perfect squares -- and it's even true that there are as many of each of those as there are of whole numbers. (If you're wondering how or why that's so, then I strongly recommend reading this node before proceeding.) Nontheless, there are MORE real numbers than there are of any of these, and we're going to prove it, using Cantor diagonalization. Before we begin, however, it's important that we review exactly what whole numbers and real numbers *are*:

The whole numbers, also known as the the positive integers, are simply the numbers we use to count:

{1, 2, 3, 4, 5, 6,...}

The real numbers are simply all of the rational numbers and all of the irrational numbers. You can find a good definition over at the real number node (and you can go here or here [or even here] for a more technical sort of definition), but the important thing to note is that all real numbers can be represented as non-terminating decimals.^{1} So, for example, all of the following are real numbers:

3 = 3.0000000000000.. .

42 = 42.000000000…

1/9 = 0.11111111111…

22/7 = 3.142857142857142857…

π = 3.141592653589793238…

√2 = 1.41421356...

*e* = 2.718281828...

√3 = 1.7320508...

φ = 1.6180339887...

The first few digits of other, less famous ones can be seen by typing a decimal point and then mashing your hand into the keypad for several minutes.

Now we can begin our proof. Since it's a proof by contradiction, we'll start by stating the opposite of what we want to prove, and then we will, in essence, go for the jugular: we will show that such an assumption leads directly to a contradiction.

*Assumption*: There are as many real numbers as there are whole numbers.

If this is the case, then it must be possible to make a numbered list of ALL the real numbers, thus setting up a one-to-one correspondence between the two sets of numbers. So, let's say we've got this list. Here it is:^{2}

`
`**1)** .14159265...

**2)** .41421356...

**3)** .34354357...

**4)** .25302211...

**5)** .34978923...

**6)** .11453934...

**7)** .12333222...

**8)** .34568285...

.

.

.

Now, have a look at the primary diagonal of the list; the first digit of the first number, the second digit of the second number, and so on:

`
`**1)** .**1**4159265...

**2)** .4**1**421356...

**3)** .34**3**54357...

**4)** .253**0**2211...

**5)** .3497**8**923...

**6)** .11453**9**34...

**7)** .123332**2**2...

**8)** .3456828**5**...

.

.

.

Now, this diagonal is itself a real number, which we'll call **b**:

**b = .11308925...**

For those of you who find this "using the diagonal of the picture to define a number" thing somewhat wishy-washy (which it most certainly is not, but I won't argue the point here), here's an alternate definition of **b**:

N^{th} digit of **b** = N^{th} digit of the real number at place N on the list.

In other words, the first digit of **b** is the first digit of the first number on the list, and the second digit of **b** is the second digit of the second number on the list, etc. Of course, this is exactly what the diagonal is, and thus we have here a totally equivalent definition of **b**.

Now, go back and look at what we've done. Specifically, we've defined an real number (namely, **b**) in terms of the list that we have above of *all* real numbers.^{3} Ergo, the number we've created MUST be on our list somewhere, since our list is a list of all real numbers, and **b** is as real as they come. Since **b** must be on our list, it's got to have a place number, just like every other number on the list. Let's call this number B. Now we ask the question: what about the B^{th} digit of **b**? Using our second definition of **b**, we see that:

B^{th} digit of **b** = B^{th} digit of *the real number at place B on the list.*

Note the phrase in italics. The real number at place B on the list is, by definition, **b**. So we now have:

B^{th} digit of **b** = B^{th} digit of **b**.

Terribly convenient, don't you think? So far, no problems. But if you have the sense that something is about to go horribly, horribly wrong, you're absolutely correct. Here it comes:

Let's define another number in terms of our list. Specifically, let's take **b** and add 1 to every digit -- unless the digit is 9, in which case we take it back to 0. Technically, this operation is called "adding 1 mod 10," but there's no need for you to worry about such things. It makes more sense when you see it:

**a = .22419036...**

Compare this to **b**, and you'll see what I mean. All we did was add one to each digit, except for 9, which cycles back to 0. Simple enough. Here's our totally equivalent definition of **a**:

N^{th} digit of **a** = (N^{th} digit of the real number at place N on the list) + 1.

Now, **a**, just like **b**, is a real number. Therefore, just like **b**, it must appear on our list somewhere, and must therefore have a place number. Let's call that number A. Now we ask the same question as before: What about the A^{th} digit of **a**? Just like before, using our second definition of **a**, we see that:

A^{th} digit of **a** = (A^{th} digit of *the real number at place A on the list*) + 1.

Once again, note the phrase in italics. The real number at place A on the list is, by definition, **a**. So we now have:

A^{th} digit of **a** = (A^{th} digit of **a**) + 1.

Well, shit. That can't be good. Look at that. Or better yet, look at what happens when you subtract the "A^{th} digit of **a**" from both sides of the equation:

0 = 1

...so black is white, and we go get ourselves killed at the next zebra crossing. Seriously, though, we've derived a contradiction from our initial assumption that the real numbers are no more numerous than the whole numbers, and therefore our initial assumption must be false: there are, in fact, MORE real numbers than there are whole numbers. You can try to list them all, but once you make such a list, you'll always be able to find a real number that is NOT on the list through the magic of diagonalization.^{4}

But don't change that dial, folks. There's more. This is just one example of a diagonal proof. It's the easiest to start with, but it's not the most elegant one around (just have a look at the footnotes to see what I mean). If you like, you can go home safe in your knowledge that the set of all reals is nonenumerable, and you'll have a pretty good idea of what Cantor diagonalization is. But if you want to see a *truly* elegant diagonal proof, stick around. We're just getting started.

Still here? Good. I knew you'd stay for the witty, non-interactive banter if for nothing else. Anyhow, for this bit, we need to define a bit of set-theory terminiology. Please don't run -- it's fairly simple. A subset of some set S is defined as a set with no members that are not in S. For example, let's look at a very simple set:

S = {Calvin, Hobbes}

S has four subsets:

- {Calvin, Hobbes}
- {Calvin}
- {Hobbes}
- {}, or Ø, the empty or null set.

We can also represent all possible subsets of S using a table:

**Calvin Hobbes**

**1)** Y Y

**2)** Y N

**3)** N Y

**4)** N N

So subset 1 has both Calvin and Hobbes in it, 2 has only Calvin, etc. It's the same as the list right above it, and both show that set S has 4 subsets.

Now we're ready. Let's go back to our old friend, the set of all whole numbers. We're going to prove, using Cantor diagonalization, that the number of subsets of the set of all whole numbers is bigger than the set of all whole numbers itself. In other words, we're going to prove that the set of all sets of whole numbers is nonenumerable. This result is known as Cantor's Theorem.

We start by assuming that there are not more subsets of the set of all whole numbers than there are whole numbers themselves. This means we can make a numbered list of all the subsets of the set of all whole numbers:

Is X in this set?

**1 2 3 4 5 6 7 8...**

**1)** Y N Y N Y N Y N...

S **2)** N N N N N Y N N...

E **3)** N Y N Y N Y N Y...

T **4)** Y Y Y Y Y Y Y Y...

**5)** N N N N N N N N...

# **6)** Y N N Y N N N N...

**7)** N Y Y N Y N Y N...

**8)** Y Y N Y N N N Y...

.

.

.

This list is a bit confusing, so let me take a moment to explain. It's just like the Calvin and Hobbes chart, just infinitely big and with numbers. The numbers running down the left are the list numbers of the subsets. Running off to the right of each one is a series of Ys and Ns. Each Y or N answers the question, "Is the number at the top of this column a member of the subset that has the list number at the far left of this row?" So, for example, subset number **1)** looks like this:

**1)** = {1, 3, 5, 7...}

Hopefully this makes the meaning of the chart clear to you. Now have a look at the diagonal of the chart:

Is X in this set?

**1 2 3 4 5 6 7 8...**

**1)** **Y** N Y N Y N Y N...

S **2)** N **N** N N N Y N N...

E **3)** N Y **N** Y N Y N Y...

T **4)** Y Y Y **Y** Y Y Y Y...

**5)** N N N N **N** N N N...

# **6)** Y N N Y N **N** N N...

**7)** N Y Y N Y N **Y** N...

**8)** Y Y N Y N N N **Y**...

.

.

.

Let's define a set D based on the diagonal:

`D = {1, 4, 7, 8...}`

And here's a totally equivalent definition of D:

For any whole number x, x is a member of D if and only if x is a member of the x^{th} set on the list.

This should be looking mighty familiar. Now, let's consider the complement of D, the set that contains all the whole numbers that D does not and vice versa:

`C = {2, 3, 5, 6...}`

And a totally equivalent definition of C:

For any whole number x, x is a member of C iff x is NOT a member of the x^{th} set on the list.

This last definition is the key. Make sure you're clear on it before you read on. We're nearly done, don't worry. Now, C, being a set containing solely whole numbers, must be a subset of the set of all whole numbers. Thus, it must be on our list somewhere, and therefore it must have a place number on our list. Let's call this number c. Now, c must be a whole number, since it's one of our place numbers on our list. This brings us to the central question: is c a member of C? Let's use our definition of C to find out:

c is a member of C iff c is NOT a member of *the c*^{th} set on the list.

Note the clause in italics VERY carefully. The c^{th} set on the list is C, by definition. Therefore, we can substitute C in for the clause in italics, which leaves us with the following gem:

**c is a member of C iff c is NOT a member of C.**

This is, of course, a contradiction, and a particularly evil-looking one at that. Ergo, our initial assumption was false, and therefore we have proven exactly what we set out to prove; namely, Cantor's Theorem.

Diagonal proofs, despite the name, are generally done without pretty pictures and diagonal lines; they tend to be given in a wholly abstract form. While this makes them a bit harder to understand (as well as making the name rather strange-sounding until you see the pretty pictures), it does make it possible to give a diagonal proof in a (very short) paragraph. So, for your reading pleasure, I give you the above proof, minus the pictures.

*Cantor's Theorem*: The set of all sets of whole numbers (a.k.a. S) is nonenumerable.

*Proof:* Assume the opposite: that S is enumerable. If so, it is possible to uniquely assign each member of S a unique whole number as an index number. Now, consider the set D: for any whole number x, x is a member of D iff x is NOT a member of s_{x}, the member of S for which it (x) is the index number. All members of D are whole numbers; therefore, D must be a member of S, and must therefore have an index number itself. Let D's index number be d. By the definition given above, d is a member of D iff d is not a member of the set for which it is the index number. However, the set for which d is the index number is D itself, and so we have:

d is a member of D iff d is not a member of D;

which is a contradiction. Thus, our initial assumption must be false, and therefore S is nonenumerable. QED.

That's Cantor diagonalization, in a nutshell. Pretty, isn't it?

Note that the whole thing feels rather deliciously twisted, somewhat like a snake
eating its own tail. It's with good reason. The whole proof relies on indirect self-reference -- by using the list numbers, we've made it possible for a set to talk about itself. Have a look back at that paradoxical sentence in bold just above. This sentence, which is false, should remind you of it. Sorry. Sorry. What I meant to say is that the bold sentence above should be reminiscent of the sentence "This sentence is false". If c is a member of C, then c is not a member of C, in which case c is a member of C after all, &c. Both of these paradoxes stem from the fact that self-reference opens the door to all sorts of nasty business -- the same reason that there's a whole host of paradoxes and "limitative theorems" which are related to Cantor diagonalization.

Like I said, pretty.

Footnotes:

1: This isn’t to say that every real number has a UNIQUE representation as an infinite decimal. Certain rational numbers have two decimal expansions: one ending in an infinite string of zeroes, and one ending in an infinite string of nines. For example, 3 also equals 2.9999999..&c. This will be important later on, in footnote 4.

2: You've probably noticed that we're only using real numbers between zero and one. The reasons for our doing so will become clear once you've gone through the whole proof, but as it turns out, the number of real numbers between zero and one is the same as the number of real numbers everywhere. There's a nice proof of this here, though it will make more sense if you read this and this first.

3: Between zero and one, that is, but since **b** has to be on this interval too, we're safe.

4: Sharp-eyed readers may notice that this whole proof assumes that each real number has a UNIQUE decimal expansion, which we said was not the case in footnote 1. This is true. However, this doesn't kill diagonalization dead: to see why, have a look at Kalmakka's excellent and brief W/U immediately above this one.