Cantor’s Diagonal “Proof”

In the effort to demonstrate how infinity comes in different sizes, many teachers bring out Cantor’s Diagonal Proof to show how this is true. It simply isn’t necessary, especially since figuring out why the diagonal proof doesn’t work may lead someone to believe that infinity doesn’t come in different sizes. It does, even though this “proof” doesn’t prove that it does. Allow me to give you some background…

Mathematicians posit that there are more real numbers between 0 and 1 than there are positive integers. If you clicked the links showing the definitions, you’ll quickly see why — “real” numbers include rational and irrational numbers while integers are made up only of rational numbers. This limitation is enough to make all of the positive integers (which are indeed infinite) a smaller set than the real numbers.

The way that we find out which is the “bigger” set is by finding the ratio of one set to another by matching numbers. This is incredibly easy to do when comparing these two sets because if you flip any integer around the decimal point (so that it reads backwards with a decimal point in front of it) you’ll find the real number between 0 and 1 that it matches. For example, 1 matches .1, 10060 matches .06001, 575757577 matches .775757575, etc. This can be done with any real number to match an integer except for the irrational numbers (such as pi and the square root of 2) which have no integer match when flipped backwards around the decimal point — therefore, the set of real numbers has “more” numbers than the set of positive integers.

But mathematicians don’t use a proof such as the one I’ve given here, eschewing it for Cantor’s Diagonal Proof. They posit that, after listing all of the real numbers in a column, you can draw a 45 degree diagonal line through all of the real numbers… through the 1st digit of the 1st number, through the 2nd digit of the 2nd number, 3rd of the 3rd, etc…. and then change each of those digits so that it matches none of the numbers that it travels through in order to come up with a “new” real number that you can then add to the bottom of the column to repeat the process and come up with yet other new numbers.

This thinking is flawed on 2 levels. For one thing, it’s logically impossible to create a “new” real number. Here it is as a logical deduction:

Premise 1: Cantor’s diagonal argument produces a new number, N.

Premise 2: N is a number not found within the set of all real numbers.

Conclusion: Therefore, N cannot be a real number.

Even further, the diagonal argument doesn’t produce a new number because it doesn’t cross through every single number. It can’t. Below is a long and detailed explanation, but I think it’s the best way to explain this complicated concept.

Consider two rockets headed into space. One is traveling at 5 kph and the other is going twice as fast at 10 kph. My question is this: when does the slower rocket catch up to the faster rocket? The obvious answer is that it doesn’t. Even when you consider that the slower rocket has gone an infinitely long distance, it has still traveled only as far as half of the faster rocket’s infinitely long distance… because we’ve already assumed that you can have two infinities of different sizes, haven’t we?

This is what happens when you try to draw a line through the set of real numbers. I’m going to do this by listing the set of real numbers in order, which is something that mathematicians purposely avoid because it allows them to avoid observing that this happens. Here are the 1-digit real numbers between 0 and 1 in order:

.1

.2

.3

.4

.5

.6

.7

.8

.9

You’ll notice that I drew a line through the first digit (.1) and now Cantor’s argument would suggest that we change it to some other digit in order to make a “new” number. But you can’t. All of the possibilities for what it can change to are listed in that same column, so whatever number you change it to will be underneath it.

“But wait!” you cry. “That’s not the end of the line. You are supposed to keep going infinitely with the line, and that way it doesn’t match any of those numbers once you add more digits.” That’s true, but it will then match other numbers below it. Consider the list of real numbers between 0 and 1 with one or two digits:

.10

.20

.30

.98

.99

Now we’ve got a line going from .1 to .2 (adding in the hidden zeroes behind them to allow for a digit to change) and you’re faced with the same situation — there is no combination of two digits that you can change those digits to that aren’t listed below it. This is true when you add another digit, and another, and ad infinitum… you’ll never hit a point where there aren’t more (and in fact an ever-increasing by a factor of 10) digits below the line. You can’t draw a 45 degree line that passes through “every” real number because the column expands much further and faster than the rows do.

Let’s look at this problem with a simpler infinite set: Flipping a coin any number of times. The only possibilities allowed are H (heads) and T (tails) and 0 (null, a non-flip). Let’s draw a line through that set.

H

T0

HH0

HT

TH

TT

HHH

You’re left with only one possible thing to change each result to… the H becomes a T (which is below it) and all of those null results become either H’s or T’s, the results of which are all found below it on the column. You can’t make a new result that isn’t found below it, no matter how far you go.

Let’s look at this one last time with a set that actually does produce a square for that line to go through at a 45 degree angle. Here is a set of zeroes (and only zeroes) taken to any length.

0

00

000

0000

Finally, the line passes through each and every result! However, what can you change each of those zeroes into? Only one possibility is allowed, so there’s literally nothing to make those zeroes into that follows the rule for making the set. Thus, even this example doesn’t allow us to create a new number with Cantor’s diagonal.

So I hope by now you can readily see why Cantor’s diagonal argument is not a paradox — it doesn’t do what it proposes to do. I’ve had mathematicians argue that this isn’t what it proposes to do, arguing that this argument isn’t supposed to create a “new” real number, but there are issues with that. For one thing, those who bring forth this argument always suggest that the newly minted number can be “added to the column to make another number”… in which case, why use the diagonal instead of just adding an infinite number of your choosing? Either way, you’ll have a duplicate number in that column. For another thing, the supposed reason given by Wikipedia and others for this argument is that it demonstrates that the real numbers are “uncountable”… but isn’t an infinite set’s uncountability, immeasurability, and incalculability true of infinite sets by definition? And while it may be seen as begging the question to assume that the real numbers between 0 and 1 are infinite without the diagonal argument, there are other ways to figure out if a set is infinite… after all, did we need the diagonal argument to prove that the positive integers make up an infinite set? Of course not

Advertisements

About starcrashx

I love statistics. They drive my poker playing, my reasoning, and my research. As Penn Gillete said "Luck is probability taken personally". There's no such thing as luck... but I wish you positive chance.
This entry was posted in Uncategorized. Bookmark the permalink.

4 Responses to Cantor’s Diagonal “Proof”

  1. Jeremy says:

    Wikipedia says the algebraic numbers are countable. This would disprove your argument for why there are more real numbers than natural numbers.

    • starcrashx says:

      I’m not arguing here that there aren’t more real number than natural numbers. In fact, I said as much, right after offering my own way of proving it:

      “…the set of real numbers has “more” numbers than the set of positive integers”

      What I’m arguing is that Cantor’s Diagonal Proof is not only based on faulty reasoning, but it is completely unnecessary for proving what it sets out to prove.

      • Jeremy says:

        The algebraic numbers are the set of numbers that make polynomial functions with rational coefficients spit out 0. This would make 3 an algebraic number since if you plugged it into f(x)=x^3-9 the out put would be zero. Likewise the square root of two is an algebraic number because if plugged into f(x)=x^2-2 the function will have zero as the output. Wikipedia says there are the same number of algebraic numbers as natural numbers.

      • Jeremy says:

        3 is an algebraic number because if you plug it into the function x^2 – 9 it will spit out 0*

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s