Cantor's Diagonalization Proof of the uncountability of the real numbers

[Leucippus]

I have a problem with Cantor's Diagonalization proof of the uncountability of the real numbers. His proof appears to be grossly flawed to me. I don't understand how it proves anything.

Please take a moment to see what I'm talking about.

Here is a totally abstract pictorial that attempts to show how Cantor's proof works. However, this pictorial is grossly flawed in two ways. First off, it's perfectly square, and secondly, it abstractly uses letters in place of numerals totally missing the point of what this proof is based upon.

In the above picture we're supposed to assume that we've gone down a nice neat square list of numbers and came up with a brand new number that clearly cannot be on the list.

But is that truly the case? I claim that it can't be the case. It's impossible. Why?

Well to realize what the problem is we must first recognize that this list is entirely based upon numerals and numbering systems. It is not based on abstract letters as show in the previous graphic. So let's get a more suitable graphic like the one below so we can illustrate why this can't work.

Ok now we'll be able to see why this can't work. What he's doing here is listing numerals (please understand that he is listing numerals not numbers). Numerals are a system that we use to write out numbers. He is using a graphic system of writing out numerals and then crossing them off diagonally to obtain a brand new number that is supposedly not already on the list.

And if numerical lists were perfectly square he would indeed have a valid proof. But lists of numerals are not square. They are extremely rectangular in the vertical direction. We have no such thing as a square numerical system in terms of being able to write it out graphically as a square. The decimal notational system is extremely rectangular.

What do I mean by this?

Well, take all possible 2-digit decimal numbers (assume non-negative numbers) and list them out. What do you get? You get a very tall narrow rectangular list of numbers like so:

http://users.csonline.net/designer/me/dec_digit.gif

This list is not even remotely close to being square. Add another digit to make it a list a mere 3 digits wide, and it will become almost 1000 rows deep. With every additional digit you add, the list innately becomes longer by powers of 10.

Lists of numbers using the decimal numerical system are far from being square lists.

What does this have to do with Cantor's diagonalization proof, you may ask. Well it has everything to do with it. Cantor is claiming to take a process out to infinity. But I claim that his process can't even be made to work in the simplest finite case.

I would like to use the binary number system to try to illustrate this point. It's far more manageable than trying to do this in base 10. Even the Binary numeralic system isn't square, but it's far more manageable so please bear with me for a few quick examples.

Let me start with a simple 2-digit binary list. This will be four rows long:


Please keep in mind that these are binary numbers now.
http://users.csonline.net/designer/me/2_digit.gif

So what do we do? Well, we go down the list diagonally replacing every digit we cross out with some other arbitrary digit that is not the same digit. In binary this is extremely simple because we are forced to swap 1's for 0's and vice versa.

So we go down this list and changing the first 0 to a 1 and the second 1 to a zero and come up with our new number 10. Then we ask. Is that number already on our list. And yes of course it is. In fact it's the very next number on the list. We just weren't able to reach it because a diagonal line doesn't go down the list fast enough to cover all the rows.

So the new number that we created was already on our 2-digit wide list.

Let's try it now on a binary list 3-digits wide:

http://users.csonline.net/designer/me/3_digit.gif

Well this time it's easy. When we draw our digaonal line we hit three 0's and create the new binary number 111 which happens to be the last number on the list. But it's on the list!

It fact, any number we create this way must always be on the list. It's the very nature of the numerical system. And this is precisely due to the fact that these lists are far taller than they are wide.

Let's to it one last time for a 4-digit binary list. If the list if 4-digits wide it's going to also be 16 rows tall.

http://users.csonline.net/designer/me/4_digit.gif

Yep, sure enough, when we create our new number using Cantor's diagonalization method we come up with another number that is already on our list. This must necessarily always be the case simply due to the very nature of these numerical systems of notation.

Now, you might be tempted to say, "But wait a minute, Cantor is taking this process out to infinity!"

So?

If a diagonal line is already this far behind in a mere finite situation taking it out to infinity is only going to make matters that much worse. Look the binary examples I gave above. When the list was 2-digits wide the diagonal line went half way down the list. When the list was 3-digits wide the diagonal line went only about a third of the way down the list. When the list was 4-digits wide the diagonal line only when down the list about a quarter of the way. The wider the lists become the worse the situation gets.

Using decimal notation (which is what Cantor actually used) the situation is far worse.

If he can't even make it to the bottom of a finite list how could he ever hope to cross off every possible number on a list infinity many digits wide?

He's claiming to have created a brand new number that cannot be on the list.

I say baloney. He could never get to the bottom of the list. How can he claim that the new number that he has constructed "cannot be on the list" when he can't possibly be making enough downward progress in the vertical direction to have ever gotten to the bottom of his list?

As far as I'm concern this so-called "proof" doesn't prove anything other than Cantor must have been mistakenly assuming that it makes sense to assume that lists of numerals could be made square (that is a false assumption).

~~~~~

Please note that this does not mean that the results of Cantor's proof are false. It simply means that his proof does not prove the assertion that he's claiming.

~~~~~

Now if I'm in error please advise. But I honestly don't see how Cantor's diagonalization proof proves anything when it's based on a numerical representation of numbers that simply cannot be made to be square which his "proof" apparently requires.

At no point can he legitimately claim to have reached the "bottom" of his list. And claiming to take this out to infinity doesn't help. Because with every digit wider the list just gets that much taller by an increasing magnitude. He could never hope to reach the bottom of his infinite list to make the proclamation that he has created a new number that's not on the list. His diagonal line simply can't have a steep enough slope to accomplish this task.

I seriously don't see how that could be made to work.

See in these pictures in math books (like the one shown below) they make it look like he can easily reach the bottom of the list. He's going down at what appear to be a nice 45 degree angle on a seemingly square list. But that is a mistaken illusion in these graphic examples. Real numerical lists don't behave this way.

So can anyone explain to me how Cantor's Diagonalization Method can be accomplished if taken out to infinity when it clearly can't even work in simple finite examples?

Seriously, I'd appreciate an explanation.

If you can explain to me why his proof makes sense and why my objections are flawed, I would truly be very grateful because I honestly cannot see how his proof makes any sense at all.

Thank you for taking the time to read my concerns.

 

[pwsnafu]

So can anyone explain to me how Cantor's Diagonalization Method can be accomplished if taken out to infinity when it clearly can't even work in simple finite examples?

This here is your problem. Just because a mathematical statement is true (or false) for the finite case does not mean it is true (or false) for the infinite case. For example
1/2 < 1
1/2 + 1/4 < 1
1/2 + 1/4 + 1/8 < 1
and so on
1/2 +1/4 + 1/8 + ... 1/(2ⁿ) < 1.
For any finite sum, that sum will be strictly less than 1. But when you take the infinite sum it equals 1.

You can't say, it fails for finite length expressions therefore it will fail for infinite length expressions.

More to the point "taken out to infinity" is wrong. The proof starts with an infinite list of infinite length expressions. Not starting with a finite list and expanding it.

 

[Leucippus]

Thank you for your reply pw, but the problem you referred to doesn't have anything at all to do with the problem I posted.

The problem I posted isn't based solely on the idea that just because something doesn't work in a finite case that means it can't work in an infinite case.

The problem I posted shows clearly that the problem gets increasingly worse as it approaches the infinite case.

The problem you posted actually gets increasingly better as it approaches infinity.

There's no comparison at all.

 

[pwsnafu]

The problem I posted shows clearly that the problem gets increasingly worse as it approaches the infinite case.

The problem you posted actually gets increasingly better as it approaches infinity.

There's no comparison at all.

"Better" and "Worse" are useless arguments when it comes to proofs. It's true or false. That's it. Seriously, I have no idea what you mean by "[t]he problem posted actually gets increasingly better". What do you mean by "better"? The inequality fails with the infinite sum.

 

[Parlyne]

All you're demonstrating here is that the diagonalization proof fails to show that the integers are uncountable. But, that's no surprise because the integers are, in fact, countable.

What changes in the case of the reals on [0,1) is that any number in this range may be represented by an infinitely long string of digits, even if all the digits trailing beyond a certain point have the value of 0. The proof works because it can act on these 0s just as easily as on any other digit. This means that it can't run out of digits to change before it runs out of numbers in the list.

 

[Deveno]

there's a couple of things worth pointing out here:

"twice" a countably infinite set is the same size as the original set.

the standard argument here is that there is a bijection between the natural numbers, and the even natural numbers:

n↔2n

cantor's proof, is a proof-by-contradiction.

if the reals between 0 and 1 WERE countable, then the list WOULD be "square", there would be a 1-1 correspondence between "digit places" and "elements of (0,1)". so the diagonal method WOULD apply. we would exhaust the reals and the number of digits at the same rate (bijectively). so it's not the case that the list is "longer" than it is "wide".

this fact is hard for people to swallow, because it is contrary to our finite experiences.

another way to express this idea is that "countable infinity is elastic", an infinite "part" is equinumerous to the "whole".

only infinite sets have this quality, which some people take as the DEFINITION of infinite (the technical term is Dedekind-infinite, and there are some set-theoretical niceties involving the validity of certain "optional" axioms that keep this from just being plain "infinite", for all people).

in other words, if you take a finite set "two at a time" you'll out-race me just taking "one at a time", but if both of our sets are countably infinite, we'll both finish at the same time, namely, never.

the bijection between the natural numbers and "half the natural numbers" isn't just restricted to a factor of 2, we could use any other infinite subset we liked, as well:

1↔2
2↔3
3↔5
4↔7
5↔11
6↔13
...
k↔k-th prime

since there's an infinitude of primes, even though we're going through the natural numbers "faster", we'll still never run out of primes, they'll always "keep up" (the well is inexhaustible).

comparing this to a convergent series isn't very apt. a better comparison, is to a divergent series like:

$$\sum_{k=1}^\infty \frac{1}{k}$$

you'd think that as k runs to infinity, since the "height" of our sum is just crawling along and becomes almost imperceptible, that eventually (since we're adding "virtually nothing") the sum would stop growing. but it NEVER DOES. even though it takes many, many terms, the series will eventually pass any limit you set for it. that is the power of infinity, it can do things finite stuff just can't.

the conclusion of the diagonal argument, by the way, is that indeed the list is "too long" to list.

one consequence of this is that the vast majority of real numbers, are numbers we will NEVER know. in reaction to this, some mathematicians (called constructivists), believe that the existence of something should not be taken as "given" unless you can actually produce it somehow. in other word, they feel that the power sets of some sets are "too big" to be called sets.

in fact, there is a theorem that says that every consistent set theory, has a countable model. but normal ZF set theory says that the reals are uncountable. so who's right? in some ways, it's a moot point. in actual practice, mathematicians rarely invoke "global features" of the theory (a notable exception being the use of the axiom of choice), but use "a local piece of the theory" relevant to what they're working on. that is, if you reject "the uncountable set" of real numbers, there's still plenty of "computable real numbers" to use for analysis (the murkiness of the waters does get a bit muddled when talking about measure theory, though, where you often need large collections of sets).

 

[lavinia]

The diagonalization proof does not go down any list. It merely asserts the existence of a number whose n'th digit is different from the n'th digit of the n'th number in the list. Such a number must clearly exist since the sequence of partial decimal expansions forms a Cauchy sequence.

There is one technicality. that is that decimal expansions are not unique. so it is possible to get an alternative expansion for one of the numbers already in the list. So how would you get around this?

 

[Deveno]

The diagonalization proof does not go down any list. It merely asserts the existence of a number whose n'th digit is different from the n'th digit of the n'th number in the list. Such a number must clearly exist since the sequence of partial decimal expansions forms a Cauchy sequence.

There is one technicality. that is that decimal expansions are not unique. so it is possible to get an alternative expansion for one of the numbers already in the list. So how would you get around this?

i'd disallow all the sequences that are "eventually" all 9's.

 

[Leucippus]

"Better" and "Worse" are useless arguments when it comes to proofs. It's true or false. That's it. Seriously, I have no idea what you mean by "[t]he problem posted actually gets increasingly better". What do you mean by "better"? The inequality fails with the infinite sum.

You're problem got "better" with respect to what you were trying to prove.

You were trying to prove that just because a finite problem doesn't work doesn't that doesn't prove that the same situation taken out to an infinite case can't work.

However, your problem got increasingly "better" with every finite step. (with respect to what you were attempting to prove).

You simply wouldn't have been able to prove what you did with a problem that gets increasingly worse with ever finite step. If you think you can, please give an example that illustrates this.

That's what I mean by "better" or "worse".

 

[Preno]

cantor's proof, is a proof-by-contradiction.

if the reals between 0 and 1 WERE countable, then the list WOULD be "square"

This seems to be the key point that you're missing, Leucippus. We are proving that the list cannot be square even in the infinite case. It's just that we're doing so by contradiction - we suppose that it is square and derive a contradiction. Your objection "but the list isn't square" is therefore absurd, seeing as how that's precisely what Cantor is trying to establish.

Edit: you said it yourself:

As far as I'm concern this so-called "proof" doesn't prove anything other than Cantor must have been mistakenly assuming that it makes sense to assume that lists of numerals could be made square (that is a false assumption).

That's Cantor's whole point, that such an assumption is false (leads to a contradiction).

 

[Leucippus]

All you're demonstrating here is that the diagonalization proof fails to show that the integers are uncountable. But, that's no surprise because the integers are, in fact, countable.

What changes in the case of the reals on [0,1) is that any number in this range may be represented by an infinitely long string of digits, even if all the digits trailing beyond a certain point have the value of 0. The proof works because it can act on these 0s just as easily as on any other digit. This means that it can't run out of digits to change before it runs out of numbers in the list.

I can see what you're attempting to get at here and I confess that this is the most interesting explanation I've heard thus far.

However, the problem here is that this proposed solution not only doesn't square up the list, but it makes the lists even that much longer. Thus making the slope of the diagonal line even more shallow.

You're claiming that because of these extra zeros permitted in a decimal expansion numerical representation of number we can clearly make up even more numbers than if those zeros weren't available. However, I have problem with that.

I mean, using a number system based on 10 you still only have the numerals 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9, available to you as replacements for those extra zeros.

You're claim is that since we have arbitrarily endless strings of zeros to work with this automatically means that we should be able to create arbitrarily endless new numbers.

But I'm not convinced that this is true. On the contrary, it appears to me that the limitation of the numerical system of digits simply won't permit that. In other words, we'd still restricted to only replacing any given zero with a numeral of 1 thru 9. So we'd still be restricted in what new numbers we can create. The fact that we seem to have more zeros to work with wouldn't change that fundamental limitation.

In other words you say, "The proof works because it can act on these 0s just as easily as on any other digit. This means that it can't run out of digits to change before it runs out of numbers in the list."

But is that really true? What do you mean that it can't run out of digits? It would still be stuck with only being able to replace those zeros with a very limited choice of numerals from 1 thru 9.

So I don't see where your proposal solves anything. I don't see where adding extra arbitrary rows of zeros helps.

In fact, as far as I can see I can actually apply your proposed solution to a finite list and demonstrate why it doesn't help a thing.

Let's try it,...

Please remember this example is in binary for brevity sake.
http://users.csonline.net/designer/me/40_digit.gif

Well, when we draw our diagonal line through our new additional arbitrary rows of zeros we still come up with a number that's already on the list. There's no way we could do otherwise because of the very nature of numerical lists and the limitations of their numerical digits.

We can demonstrate just as easily that this is also true of a numerical list that is based on ten. We would have more digits to chose from for replacements of zeros, (i.e. 1 thru 9), but we would still always come up with a number that is already on the list. Plus our lists would even be taller yet since we've added arbitrary rows of zeros.

So how is that helping?

I don't see where it helps at all. We'd have very same situation made 'worse'. By worse I simply mean that now the lists are even taller yet thus decreasing the downward slope of the diagonal line resulting in an even slower rate of decent through the list. We could never hope to claim to have created a new number that isn't already on the list.

And that is paramount, because that is precisely what Cantor is claiming to have done. He's claiming to have created a new number that isn't already on the list.

He's assuming that he can take this out to infinity in both the horizontal and vertical directions with equal "speed". In other words, he's assuming that he can do this clear to the bottom of this list of numbers as he moves to the right.

But he can't. The slope of his diagonal line simply isn't steep enough to accomplish this task. The very property of a numerical representation of a list of numbers simply won't permit what he is claiming to be able to do. They can't be used like that because they aren't square lists.

He must have been assuming that since he can take this out to infinity in the horizontal direction that he could also take the same process out to infinity in the vertical direction simultaneously too. But that's a folly. Henri Poincare warned him about this. It's a folly to start thinking of infinity as though it can be completed. But that's precisely what Cantor's proof would require. Cantor's "proof" is not a proof at all, if his diagonal line can't reach the bottom of the list at the same time that it reaches the right side of the list. And clearly that can never be accomplished on lists of numerals because lists of numeral are simply not square lists by their very nature.

So he could never complete his diagonal process to the bottom of his list. The slope of his diagonal line simply isn't steep enough, and it also dynamically takes on a shallower and shallower slope with every digit as he moves to the right. The situation gets increasingly "worse".

He could never hope to prove that he is creating a new number that isn't already on this list.

It's a flawed proof based on the erroneous assumption that lists of number are innately square when in fact they are actually highly rectangular and become increasingly rectangular with ever added digit.

 

[Leucippus]

if the reals between 0 and 1 WERE countable, then the list WOULD be "square", there would be a 1-1 correspondence between "digit places" and "elements of (0,1)". so the diagonal method WOULD apply. we would exhaust the reals and the number of digits at the same rate (bijectively). so it's not the case that the list is "longer" than it is "wide"..

I'm sorry but you've lost me right there.

I've just demonstrated that even a list of natural numbers cannot even be made to be square. So I don't understand how you can claim that any list of numbers could be square.

It's innately a property of our numerical representational systems that they cannot be made to be square. And this would even apply to a list of natural numbers.

So your claim, "if the reals between 0 and 1 WERE countable, then the list WOULD be square" makes no sense to me. How could any complete list of numbers be square?

Our numerical system of representing numbers simply won't permit that to happen. It's built-in to the very representation of our numbers that these lists cannot be both complete and square at the same time. If they are forced to be square they must necessarily be incomplete, and if they are said to be complete lists they must necessarily rectangular.

This is even true of the natural numbers.

It's an innate property of the very system of numerical notation. Yet it is this system of numerical notation that Cantor is attempting to use in his proof.

 

[Preno]

I'm sorry but you've lost me right there.

I've just demonstrated that even a list of natural numbers cannot even be made to be square. So I don't understand how you can claim that any list of numbers could be square.

It's a proof by contradiction. Do you understand how a proof by contradiction works? It works by assuming the thing you're trying to disprove (in this case, that there is a square list of reals).

Our numerical system of representing numbers simply won't permit that to happen. It's built-in to the very representation of our numbers that these lists cannot be both complete and square at the same time. If they are forced to be square they must necessarily be incomplete, and if they are said to be complete lists they must necessarily rectangular.

Yes, that is what Cantor proves. How do you not understand this?

 

[Leucippus]

The diagonalization proof does not go down any list. It merely asserts the existence of a number whose n'th digit is different from the n'th digit of the n'th number in the list. Such a number must clearly exist since the sequence of partial decimal expansions forms a Cauchy sequence.

There is one technicality. that is that decimal expansions are not unique. so it is possible to get an alternative expansion for one of the numbers already in the list. So how would you get around this?

That doesn't impress me at all, for the following reason:

Stop Cantor's process at any finite point. Chose whatever point you like.

Take this supposedly "new number" that you've created at that point 'truncated' precisely where you had stopped Cantors process and ask yourself, "What do I have?"

You will have a perfectly legitimate rational number. You haven't created anything "new" at all at that point.

And the mere fact that you can do this an ANY POINT in the process, pretty much proves that at no point have you created a "new number" that wouldn't already be on a list of rational numbers.

At NO POINT in this process does Cantor ever create a new number that wouldn't already be a rational number if truncated at that point of the process.

So how does claiming to take this process out to infinity change that?

He's clearly not making any "progress" along the way.

What supposedly 'magically' happens at infinity that changes this?

Cantor's claim seems to be, "Well I will have exhausted every possible number on the list and I obviously have created a new number, so I must have a number that wasn't on the original list"

But as I've shown, he has no reason to make such a claim because he could never make it to the "bottom" on any such list in the first place. His diagonal process simply doesn't have a steep enough slope to make that claim.

He can't claim to ever be able to complete his process (even in theory). Because his diagonal method simply doesn't go down the list fast enough to make such a claim.

There is never a point in this process where he creates a 'new number' that wouldn't already be a rational number if truncated at the point in question.

So how does it follow that this situation would ever change?

 

[Leucippus]

This seems to be the key point that you're missing, Leucippus. We are proving that the list cannot be square even in the infinite case. It's just that we're doing so by contradiction - we suppose that it is square and derive a contradiction. Your objection "but the list isn't square" is therefore absurd, seeing as how that's precisely what Cantor is trying to establish.

Edit: you said it yourself:
That's Cantor's whole point, that such an assumption is false (leads to a contradiction).

What are you talking about?

I've already demonstrated that any "complete" list of numbers cannot be square even a complete list of natural numbers.

So that cannot be what Cantor was attempting to show. All complete numerical lists that contain all the numbers allowed by that numerical system of representation must all necessarily be rectangular, including the natural numbers.

 

[Preno]

What are you talking about?

I've already demonstrated that any "complete" list of numbers cannot be square even a complete list of natural numbers.

So that cannot be what Cantor was attempting to show.

Well, you haven't demonstrated it, you just provided some sort of intuitive graphical argument, but other than that - that's precisely what Cantor was attempting to show. Cantor's theorem, phrased in your terms, states: there is no square list of real numbers. This is what both you and Cantor are saying.

 

[Deveno]

That doesn't impress me at all, for the following reason:

Stop Cantor's process at any finite point. Chose whatever point you like.

Take this supposedly "new number" that you've created at that point 'truncated' precisely where you had stopped Cantors process and ask yourself, "What do I have?"

You will have a perfectly legitimate rational number. You haven't created anything "new" at all at that point.

And the mere fact that you can do this an ANY POINT in the process, pretty much proves that at no point have you created a "new number" that wouldn't already be on a list of rational numbers.

At NO POINT in this process does Cantor ever create a new number that wouldn't already be a rational number if truncated at that point of the process.

So how does claiming to take this process out to infinity change that?

He's clearly not making any "progress" along the way.

What supposedly 'magically' happens at infinity that changes this?

Cantor's claim seems to be, "Well I will have exhausted every possible number on the list and I obviously have created a new number, so I must have a number that wasn't on the original list"

But as I've shown, he has no reason to make such a claim because he could never make it to the "bottom" on any such list in the first place. His diagonal process simply doesn't have a steep enough slope to make that claim.

He can't claim to ever be able to complete his process (even in theory). Because his diagonal method simply doesn't go down the list fast enough to make such a claim.

There is never a point in this process where he creates a 'new number' that wouldn't already be a rational number if truncated at the point in question.

So how does it follow that this situation would ever change?

you don't seem to grasp a key point. the numbers listed are not just rational numbers. the vast majority of them (as it turns out) are aperiodic non-terminating decimals.

if we stop the process after 3 steps, all we have is a decimal representation that differs from the first 3 numbers. if we continue, then after n steps, we just have a decimal that is different from the first n numbers listed.

now, if the real numbers between 0 and 1 COULD be put in a 1-1 correspondence with the natural numbers, at some finite time, we would reach any given real number. that is what it means to be "countable" (eventually you can "count up" to any given element of the set).

but the ever-increasing number we are creating at the bottom, doesn't match any number reached after a finite number of steps. so no matter how long we "count" (how far down the list we go), let's say we go down 3 million places, the number at the bottom is different from the first 3 million numbers.

you could write a computer program, that checked the number at the bottom against the first k numbers at step k, and if it found a match within the first k, instruct it to halt. it will never halt.

if the real numbers between 0 and 1 WERE countable, eventually, at some point, we would find a match, because at some point, we'd get to any real number we cared to name. but the way we are constructing the number (it grows by one digit, as we eliminate the possible matches from the "top down"), it's guaranteed not to match as many numbers as it has digits.

no match = not countable. and we're rigging it so there won't BE a match. which number on the list can it possibly match? the 1st? no. the 2nd? no. the 3rd? no. the 4th? no. the 3,567,281st? no.

all our number on the bottom has to do, to "not match" is be different in ONE digit-place from any given number. how do you think that will fail to happen?

 

[Leucippus]

Well, you haven't demonstrated it, you just provided some sort of intuitive graphical argument, but other than that - that's precisely what Cantor was attempting to show. Cantor's theorem, phrased in your terms, states: there is no square list of real numbers. This is what both you and Cantor are saying.

But I have demonstrated it. You claim that I just provided some sort of intuitive graphical argument. But that is precisely what Cantor's diagonal proof is. It's a graphical argument based on using a numerical representation of numbers.

I'm demonstrating (using precisely the same kind of numerical graphical representations of numbers) why Cantor's graphical diagonalization proof has no merit.

And my points should indeed be extremely easy to intuitively understand.

Let me try to make this as clear as possible using a numerical representation of the natural numbers based on 10.

Let's start with the simplest case and expand on this and see where it leads,...

Here's the simplest case of a 1-digit wide list of number based on ten digits. There are exactly ten of them so in order to list them all the list must be 1 column wide by 10 rows long.

http://users.csonline.net/designer/me/1_dec.gif

This is an extremely rectangular list of numbers, necessarily so, forced by the very nature of this numerical representation.

Now, let's move on to a 2-digit complete list of these numbers. And it's important that these list are indeed complete. Incomplete lists would be incomplete and therefore meaningless.

http://users.csonline.net/designer/me/2_dec.gif

Now the list has become even vastly more rectangular. Now it has only 2 columns, but it requires a length of almost a hundred rows. It is an extremely skinny tall rectangle, force by the very nature of the numerical representation of these numbers.

Let's do it one more time just to be sure that we have a convincing trend,...

http://users.csonline.net/designer/me/3_dec.gif

Yep the trend is pretty convincing. Now we have a list only 3 digits wide yet it's almost a thousand rows long. In fact, it doesn't take a genius to realize that these lists are going to continue getting longer by powers of ten every time we increase their width by a single digit.

So it should be pretty obvious that lists of natural numbers are innately far longer than they are wide.

Therefore to think that we should be able to draw a diagonal line down through a list of numbers represented by these numerical digits and proclaim to have created a new number "that isn't already on the list" is basically a false claim that could never hold true.

Yet this is precisely what Cantor's diagonal proof requires that we must be able to do. We must be able to go down through such a list of number diagonally and actually "reach" the bottom of the list creating a new number in the process, in order to concluded that we have created a new number that isn't already on this list.

That makes absolutely no sense. Cantor is assuming that these lists could somehow be square enabling him to successfully cross over every number on the list diagonally.

That simply isn't possible.

Cantor's diaganoalization proof based on this method is necessarily a flawed proof and doesn't prove what he claims it proves.

It's pretty obvious to me.

~~~~

This isn't to say that the result is necessarily untrue. Maybe the real numbers truly are uncountable. But Cantor's diagonalization "proof" most certainly doesn't prove that this is the case.

It is necessarily a flawed proof based on the erroneous assumption that his diagonal line could have a steep enough slope to actually make it to the bottom of such a list of numerals. That simply isn't possible.

I don't care if he claims to take this out to infinity. How would that change anything? The slope of his diagonal line is only going to get shallower and shallower with ever digit he crosses out. He could never hope to claim to have reached the bottom of the list and created a new number that isn't already on the list.

It's nonsense. What else can I say?

 

[Leucippus]

you don't seem to grasp a key point. the numbers listed are not just rational numbers. the vast majority of them (as it turns out) are aperiodic non-terminating decimals.

if we stop the process after 3 steps, all we have is a decimal representation that differs from the first 3 numbers. if we continue, then after n steps, we just have a decimal that is different from the first n numbers listed.

now, if the real numbers between 0 and 1 COULD be put in a 1-1 correspondence with the natural numbers, at some finite time, we would reach any given real number. that is what it means to be "countable" (eventually you can "count up" to any given element of the set).

but the ever-increasing number we are creating at the bottom, doesn't match any number reached after a finite number of steps. so no matter how long we "count" (how far down the list we go), let's say we go down 3 million places, the number at the bottom is different from the first 3 million numbers.

you could write a computer program, that checked the number at the bottom against the first k numbers at step k, and if it found a match within the first k, instruct it to halt. it will never halt.

if the real numbers between 0 and 1 WERE countable, eventually, at some point, we would find a match, because at some point, we'd get to any real number we cared to name. but the way we are constructing the number (it grows by one digit, as we eliminate the possible matches from the "top down"), it's guaranteed not to match as many numbers as it has digits.

no match = not countable. and we're rigging it so there won't BE a match. which number on the list can it possibly match? the 1st? no. the 2nd? no. the 3rd? no. the 4th? no. the 3,567,281st? no.

all our number on the bottom has to do, to "not match" is be different in ONE digit-place from any given number. how do you think that will fail to happen?

With all due respect Deveno, your argument here makes no sense to me at all.

Why would you expect to ever get a number that's already on the list that you are generating?

That would never happen in this process. That's obvious.

But that doesn't prove anything in light of my observations.

You're always going to be generating a number that is "further down" the list than where you are currently working. That's a given. Even my finite examples clearly show that this will always be the case. The very process that is being used to generate your "new number" demands that this be the case.

My point is that it doesn't matter.

Numerical representations of numbers like this simply aren't square to begin with. So just because the new number you've created isn't on the list above where you are currently working in this process doesn't mean a thing.

That's my whole POINT.

The numbers above where you are working cannot be a "complete list" with respect to where you are at in the columns, because the slope of the diagonal line simply isn't steep enough to make that guarantee.

And this is why this diagonal method can't prove what Cantor claims it proves.

This diagonal method of creating a "new number" simply isn't anywhere near "fast enough" (i.e. it doesn't have a steep enough slope) to even deal with finite lists of numbers. It will always be "behind" the list. And it just gets further and further behind with every digit that is crossed out.

We can clearly see this in the finite examples I've given.

Why should this change if we try to take this process out to infinity?

The situation is only going to get worse with ever digit we cross out.

 

[SteveL27]

That would never happen in this process. That's obvious.

Leu, one point of confusion here is that you are thinking of Cantor's proof as a process. You are adding one row at a time and looking at the antigiagonal and then talking about rectangles.

All of that is erroneous thinking and has nothing to do with Cantor's proof.

Cantor asks us to consider any complete list of real numbers. Such a list is infinite, and we conceptualize it as a function that maps a number, such as 47, to the 47-th element on the list. There's a first element, a 2nd element, and DOT DOT DOT. We assume that ALL of these list entries exist, all at once.

Then we construct the antidiagonal. It's clear that the antidiagonal can't be on the list ... because it differs from the n-th item on the list in the n-th decimal place. (Or binary place if you do the proof in base-2).

Since we started by assuming we had a list of all reals; and we just showed that any such list must necessarily be missing a real; then it follows that there can be no such complete list in the first place.

I suggest that you make an attempt to fully understand this beautiful proof on its own terms. There is nothing here about processes and nothing here about rectangles. You are introducing those irrelevant concepts on your own and losing sight of the proof itself.

 

[Preno]

But I have demonstrated it. You claim that I just provided some sort of intuitive graphical argument. But that is precisely what Cantor's diagonal proof is. It's a graphical argument based on using a numerical representation of numbers.

Um, no, it's not a "graphical argument", it is (or can be made into) a precise formal argument.

I'm demonstrating (using precisely the same kind of numerical graphical representations of numbers) why Cantor's graphical diagonalization proof has no merit.

No, you are demonstrating why it's impossible for a list of numbers (finite or infinite) to be square. That's exactly what Cantor is saying. That is literally the content of his theorem: the width of the list (the cardinality of the naturals) is less than the height of the list (the cardinality of the reals). You are literally repeating Cantor's theorem while at the same time claiming you're denying it. Jesus Christ.

 

[Preno]

A: Let us prove that 2 is irrational. We use proof by contradiction. Thus, suppose that 2 is the ratio of two integers..."

B: But 2 is not a ratio of two integers! We can prove it's not."

A: Um, yeah, that's what I'm trying to prove, using the method of contradiction. Again, suppose that 2 is the ratio of two integers..."

B: But it's not! Your theorem is false."

A: *facepalm*

 

[Leucippus]

Leu, one point of confusion here is that you are thinking of Cantor's proof as a process. You are adding one row at a time and looking at the antigiagonal and then talking about rectangles.

All of that is erroneous thinking and has nothing to do with Cantor's proof.

Cantor asks us to consider any complete list of real numbers. Such a list is infinite, and we conceptualize it as a function that maps a number, such as 47, to the 47-th element on the list. There's a first element, a 2nd element, and DOT DOT DOT. We assume that ALL of these list entries exist, all at once.

Then we construct the antidiagonal. It's clear that the antidiagonal can't be on the list ... because it differs from the n-th item on the list in the n-th decimal place. (Or binary place if you do the proof in base-2).

Since we started by assuming we had a list of all reals; and we just showed that any such list must necessarily be missing a real; then it follows that there can be no such complete list in the first place.

I suggest that you make an attempt to fully understand this beautiful proof on its own terms. There is nothing here about processes and nothing here about rectangles. You are introducing those irrelevant concepts on your own and losing sight of the proof itself.

"There is nothing here about processes and nothing here about rectangles. You are introducing those irrelevant concepts on your own and losing sight of the proof itself."

I disagree. Cantor is using a numerical presentation of numbers and crossing them out using a diagonal line.

My observations of why this cannot be used in the way he is using it are valid observations, IMHO.

You can't just tell me to ignore the very things that Cantor's proof rely upon.

As far thinking of the thing as a "process", that too is irrelevant. It doesn't matter whether it's thought of as a process, or as some sort of miraculous completed object.

The slope of the diagonal line is too shallow to prove what Cantor claims to have proved in either case.

Trying to imagine a "Completed infinite process" isn't going to help. If you're imagining that you could have actually made it to the bottom of any list at all, then you are imagining something that simply won't work in this situation.

The innate rectangular nature of numerical systems of representation cannot be ignored either. In fact, if you are ignoring that, it's no wonder the proof appears to be so beautiful to you. You're just wrongfully assuming that such a list could be square and that a diagonal line could traverse the whole list from top to bottom.

You absolutely need to realize that it makes no sense to think of lists of numbers in that way before you can even begin to see why this proof cannot hold.

Recognizing the innate rectangular nature of numerical representations of numbers is paramount to understanding why this proof has no validity and cannot work.

Pretending that such lists could be square is the only thing that 'saves' the proof.

Why would I want to pretend that such lists could be square?

~~~~

So basically you're telling me that if I ignore that numerical lists are innately rectangular, and pretend that they are square, I too could see the "beauty" of Cantor's proof?

Well, I guess so.

But that's not reality, so why should I go there?

 

[micromass]

Cantor's argument has NOTHING to do with squares and rectangles. I know that there are often fancy pictures of squares in books, but those are ILLUSTRATIONS of the argument. The real formal argument is indisputable.

I'll number the steps so you can specifically say where you disagree.

Here is the formal argument:
1) Assume that ]0,1[ is countable, then we can write $]0,1[=\{x_1,x_2,x_3,x_4,...\}$.

2) Every number has a decimal expansion. So we can write $x_i=x_i^1\frac{1}{10}+x_i^2\frac{1}{10^2}+...+x_i^n\frac{1}{10^n}+...$.

3) Put $y_n=x_n^n$ for all n. Put $z_n=4$ if $y_n=5$ and put $z_n=5$ otherwise.

4) Put $z=z_1\frac{1}{10}+z_2\frac{1}{10^2}+...+z_n\frac{1}{10^n}+...$.

5) Notice that $z_n$ does not equal $x_n^n$ for all n. We can use this to prove that z does not equal any $x_n$. (I won't write this proof down. If the problem is here then you should say so and I will write the explicit proof down of this fact).

This argument is the pure formal argument. You should find a mistake in this proof, not in the illustration of the proof.

 

[Preno]

Cantor's argument has NOTHING to do with squares and rectangles. I know that there are often fancy pictures of squares in books, but those are ILLUSTRATIONS of the argument.

I disagree. Personally, I've never thought of Cantor's argument in terms of squares and rectangles previously but I do find it to be a rather nice way of thinking about it. Cantor's diagonal proof is precisely proof of the fact that the rectangles never become squares. That's just a very straightforward reformulation of Cantor's point - the rectangle is as wide as N and as high as R.

The only thing that's bizarre here is that Leucippus for some reason doesn't seem to understand that showing that an assumption cannot hold is precisely what you're supposed to do in a proof by contradiction.

 

[HallsofIvy]

I disagree. Personally, I've never thought of Cantor's argument in terms of squares and rectangles previously but I do find it to be a rather nice way of thinking about it. Cantor's diagonal proof is precisely proof of the fact that the rectangles never become squares. That's just a very straightforward reformulation of Cantor's point - the rectangle is as wide as N and as high as R.

No, it isn't. The whole point of Cantor's argument is that this list doesn't exist to begin with!

The only thing that's bizarre here is that Leucippus for some reason doesn't seem to understand that showing that an assumption cannot hold is precisely what you're supposed to do in a proof by contradiction.

 

[micromass]

I disagree. Personally, I've never thought of Cantor's argument in terms of squares and rectangles previously but I do find it to be a rather nice way of thinking about it. Cantor's diagonal proof is precisely proof of the fact that the rectangles never become squares. That's just a very straightforward reformulation of Cantor's point - the rectangle is as wide as N and as high as R.

The only thing that's bizarre here is that Leucippus for some reason doesn't seem to understand that showing that an assumption cannot hold is precisely what you're supposed to do in a proof by contradiction.

I agree that it's a rather nice way of thinking about it. But it's not rigorous.

You have to make a fundamental distinction in mathematics between a rigorous formal argument and "nice ways of thinking about it".

A pure formal argument uses axioms and inference rules, nothing else. It is often a very abstract argument, but it is always completely correct.

An illustration or a picture are NOT valid proofs. They're ok to form your intuition, but you have to realize that they are NOT proofs.

Realizing what a valid proof is, is very fundamental in mathematics.

 

[Leucippus]

Cantor's argument has NOTHING to do with squares and rectangles. I know that there are often fancy pictures of squares in books, but those are ILLUSTRATIONS of the argument. The real formal argument is indisputable.

I'll number the steps so you can specifically say where you disagree.

Here is the formal argument:
1) Assume that ]0,1[ is countable, then we can write $]0,1[=\{x_1,x_2,x_3,x_4,...\}$.

2) Every number has a decimal expansion. So we can write $x_i=x_i^1\frac{1}{10}+x_i^2\frac{1}{10^2}+...+x_i^n\frac{1}{10^n}+...$.

3) Put $y_n=x_n^n$ for all n. Put $z_n=4$ if $y_n=5$ and put $z_n=5$ otherwise.

4) Put $z=z_1\frac{1}{10}+z_2\frac{1}{10^2}+...+z_n\frac{1}{10^n}+...$.

5) Notice that $z_n$ does not equal $x_n^n$ for all n. We can use this to prove that z does not equal any $x_n$. (I won't write this proof down. If the problem is here then you should say so and I will write the explicit proof down of this fact).

This argument is the pure formal argument. You should find a mistake in this proof, not in the illustration of the proof.

Hello, Micromass.

I am not refuting the ultimate conclusion that reals are uncountable.

I am totally convinced that the real numbers cannot be placed into a one-to-one correspondence with the natural numbers. I'm not questioning that at all.

I'm addressing only what I set out to address: Cantor's Diagonalization Proof.

It is indeed a graphical proof, based on listing numerals and running a diagonal line through them. This is how Cantor originally proposed it, and it is the specific proof that I'm interested in addressing.

~~~~

I'll take a look at the formal abstract proof you offered too, and comment on that proof later. But that's really not what I'm addressing. I'm not concerned with proving or disproving the countability of the reals in general.

All I'm concerned with is whether Cantor's Diagonalization proof is valid. That's what I'm looking at, and that's what I'm addressing specifically.

I'm addressing the validity of this specific proof.

I'm not challenging the results of the proof in general, or whether the reals are uncountable.

I'm more interested in methods of proofs, than in what they are trying to prove. And this is what led me to finding the flaw in this particular proof.

So it is this specific method of proof that I'm addressing. And the flaws associated specifically with it.

~~~~

I've recently watched a course by the Teaching Company Course on Great theorems. I was able to follow all of the theorems and proofs without a hitch until it came to this proof by Cantor. As I tried to better understand it I actually realized why it doesn't prove anything.

The ultimate conclusions may very well be true coincidentally. But this diagonalization method (as it was presented in this course) is not a valid proof. It fails for the reasons I've already stated in previous posts. I don't understand why people think this is a valid proof?

It would require that numerical lists of numbers are square, but they aren't.

 

[micromass]

Hello, Micromass.

I am not refuting the ultimate conclusion that reals are uncountable.

I am totally convinced that the real numbers cannot be placed into a one-to-one correspondence with the natural numbers. I'm not questioning that at all.

I'm addressing only what I set out to address: Cantor's Diagonalization Proof.

It is indeed a graphical proof, based on listing numerals and running a diagonal line through them. This is how Cantor originally proposed it, and it is the specific proof that I'm interested in addressing.

~~~~

I'll take a look at the formal abstract proof you offered too, and comment on that proof later. But that's really not what I'm addressing. I'm not concerned with proving or disproving the countability of the reals in general.

All I'm concerned with is whether Cantor's Diagonalization proof is valid. That's what I'm looking at, and that's what I'm addressing specifically.

I'm addressing the validity of this specific proof.

I'm not challenging the results of the proof in general, or whether the reals are uncountable.

I'm more interested in methods of proofs, than in what they are trying to prove. And this is what led me to finding the flaw in this particular proof.

So it is this specific method of proof that I'm addressing. And the flaws associated specifically with it.

~~~~

I've recently watched a course by the Teaching Company Course on Great theorems. I was able to follow all of the theorems and proofs without a hitch until it came to this proof by Cantor. As I tried to better understand it I actually realized why it doesn't prove anything.

The ultimate conclusions may very well be true coincidentally. But this diagonalization method (as it was presented in this course) is not a valid proof. It fails for the reasons I've already stated in previous posts. I don't understand why people think this is a valid proof?

It would require that numerical lists of numbers are square, but they aren't.

IF you're talking about the graphical proof, then it is not a valid proof. Proofs should never be graphical.

Notice that how Cantor originally proposed the proof is irrelevant, mathematics has changed a lot in 100 years.

The abstract proof I just gave IS commonly known NOW as Cantor diagonalization. The "graphical proof" is not valid these days.

 

[willem2]

The ultimate conclusions may very well be true coincidentally. But this diagonalization method (as it was presented in this course) is not a valid proof. It fails for the reasons I've already stated in previous posts. I don't understand why people think this is a valid proof?

It would require that numerical lists of numbers are square, but they aren't.

I don't understand this at all. The proposed list will have an countably infinite number of reals, and each real will have an countably infinite number of digits (adding an infinite number of zero's if necessary).

For the proof, it's only necessary that for each number N, there's an N'th row, and there's an N'th column. Since both the number of rows and the number of columns is infinite, this is obviously true, so it's always possible to find the N'th number of the diagonal and change it. Since this works for all N, we can find the complete diagonal.

 

[Leucippus]

IF you're talking about the graphical proof, then it is not a valid proof. Proofs should never be graphical.

That's certainly a controversial statement. I just finished taking a course on "The Shape of Nature" which is a cutting-edge course on Topology by Professor Satyan L. Devadoss of Williams College. He not only enthusiastically supports graphical proofs, but he even cites one that he personally introduced into mathematics and he suggests that it could not be stated any other way than graphically. But then again, he addresses topology which is clearly different from set theory concepts.

Here's a link to his course if you would like to watch it.

The Shape of Nature

By the way, you don't need to buy it. Usually you can get it through inter-library loan.

Notice that how Cantor originally proposed the proof is irrelevant, mathematics has changed a lot in 100 years.

The abstract proof I just gave IS commonly known NOW as Cantor diagonalization. The "graphical proof" is not valid these days.

His diagonalization proof is still being presented to people and taught to people in many math courses and books today. If it's a flawed proof then that flaw should be addressed and exposed.

So I would disagree with you that it's not a valid concern today.

Seems to me that all you're basically suggesting is that it's irrelevant if I might have found a flaw in Cantor's original proof. I personally don't think that's irrelevant at all.

Like I say. I'll look into the proof you provided and see if I can relate it back to Cantor's original idea.

 

[micromass]

That's certainly a controversial statement.

It's not a controversial statement at all. The idea of what a proof is and is not, is very well established. If you study mathematical logic, then you see that mathematicians have a very very very precise idea of what a proof really is.

That said, the formal logical proof is often to hard to comprehend. So that is why people make illustrations to proofs, and formulate proofs to make them easier. It is important to know that that is NOT what the proof is. It's like somebody pointing to the moon and the people are all looking at the finger. The logical proof is what mathematics is all about.

but he even cites one that he personally introduced into mathematics and he suggests that it could not be stated any other way than graphically.

THAT is the controversial statement. If a proof can only be stated graphically, then it's wrong. Period.

But then again, he addresses topology which is clearly different from set theory concepts.

Topology is not different from set theoretic concepts. Topology is well-established and formalized. All proofs in topology can be expressed in formal form.

His diagonalization proof is still being presented to people and taught to people in many math courses and books today. If it's a flawed proof then that flaw should be addressed and exposed.

His diagonalization is being presented to people today. But those people usually KNOW that the graphical proof is not the proof itself. When I first saw Cantor diagonalization, I realized very well that one should formalize the proof and write it in formal statements.

When they first showed me that $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$ using a picture, it was IMMEDIATELY made clear that this was not a valid proof. It simply SUGGESTS a valid proof.

So I would disagree with you that it's not a valid concern today.

Well, you got your answer: the proof is wrong. Is there anything else you would like to discuss?

 

[Leucippus]

I don't understand this at all. The proposed list will have an countably infinite number of reals, and each real will have an countably infinite number of digits (adding an infinite number of zero's if necessary).

For the proof, it's only necessary that for each number N, there's an N'th row, and there's an N'th column. Since both the number of rows and the number of columns is infinite, this is obviously true, so it's always possible to find the N'th number of the diagonal and change it. Since this works for all N, we can find the complete diagonal.

Yes, I understand what you are saying. But aren't you completely tossing out everything that I had previously pointed out?

You're basically assuming a "square" situation.

You're basically saying that since it's infinitely many rows and infinitely many columns that somehow makes it doable or even "square" in the sense that it's infinity by infinity in dimension.

But you're not taking into account the observations I've given. That lists of numbers represented by numerals cannot be made into 'square' lists. Pretending that "infinity by infinity" represents a square list that can be completed is the folly.

You'd also have to ignore the limitations on the slope of any line that needs to go down these lists crossing out a digit at time.

The slope of that line cannot be made steep enough to keep up with a list that would be required to represent even the natural numbers let alone the reals.

The very assumption that this problem can be viewed as a "square" infinity-by-infinity list is indeed the folly.

That's the false assumption right there that can't hold true.

 

[Leucippus]

Well, you got your answer: the proof is wrong. Is there anything else you would like to discuss?

No, I guess I'm done here then.

I wasn't aware the proof was considered to be wrong.

I only wish the people who teach these things would be more clear about that.

Then I wouldn't need to go around making myself look like an idiot proclaiming to have discovered things that everyone else already knows.

 

[willem2]

Yes, I understand what you are saying. But aren't you completely tossing out everything that I had previously pointed out?

You're basically assuming a "square" situation.

The term square or rectangle makes no sense at all for an array of numbers that's infinite in 2 dimensions. Both are countably infinite, and that's ALL you can say.

But you're not taking into account the observations I've given. That lists of numbers represented by numerals cannot be made into 'square' lists. Pretending that "infinity by infinity" represents a square list that can be completed is the folly.

I'll agree with you that the lists cannot be made into square lists, but that's just because an infinite square list is nonsense. But you don't need that. All you need is to be able to extend the diagonal arbitrarily far.

You'd also have to ignore the limitations on the slope of any line that needs to go down these lists crossing out a digit at time.

The slope of that line cannot be made steep enough to keep up with a list that would be required to represent even the natural numbers let alone the reals.

Note that an infinite list of numbers with an infinite number of digits only has a corner at (1,1) (the first digit of the first number). It does NOT have an opposite corner with the diagonal running between those corners. The diagonal does just fine with a slope of 1.