# Cantor Diagonal Argument with complete list of reals

I don't understand the way cantor's diagonal argument work. I suppose the origin of the problem is an assumption that I think must be made for the proof to be correct. Personally I really thinks that cardinality of R is greater than N. The problem is in the proof.

In every cantor diagonal proof we have the following: 1) A "complete" list of reals. 2) a real sk defined this way: sk[n] = 0 if a[n][n] = 1 or sk[k] = 1 if a[n][n] = 0.

if the list is complete, sk must be in the list. So by assumption there must be a n where sk[k] = 0 if a[k][k] = 1 and sk[k] = 1 if a[k][k] = 0; This number is not correctly defined since it is not equal to itself. So the definition of sk is not a real if we assume that the list is complete and we assume that any real is equal to itself.

does it make sense to take an incomplete list of reals? I personally think if it is not complete it is useless to demonstrate that you have a real that is not in the list since by definition the list is incomplete. for example 1) lets take the subset of natural numbers of the real set as "the list of reals" 2) lets define a real sk as a fraction for example "sk = 0.5".

you can demonstrate that sk is not in the set but the set of rational numbers is countable so the set of "natural numbers with 0.5" must also be countable.

UPDATE:

First thanks a lot for all your comments. I'm sorry if I have been so "informal" expressing my point of view.

My main concern with the proof is that for me it seems that the definition of the mathematical object sk (the real number that is not in the list) is self contradictory. And from a contradiction we can deduce everything in classical logic.

first we start from this assumptions:

1. Q="L is a complete list of the reals".
2. P1="sk is a member of the real set".

We want to demonstrate this sentence F="sk is a member of the list L". Without any other assumption (only P1 and Q) F follows from Q and P1.

Now we are going to add some structure (property P2) to the number sk. First I'm going to explain two suppositions to introduce my idea.

Supposition 1:
P2="sk equals 2".
P1 and P2 are true. The definition of sk is no contradictory with Q. In this case F is true.

Suposition2:
P2="sk equals i".
P1 and P2 are not true since sk can not be defined has a real and a complex. In this case The definition of sk is at least ambiguous. We trust in P1 so P2 is false. Q still true and F is true since the only property that holds for sk is our first assumption P1.

Suposition3: (cantor diagonal proof)
We should remember that we trust in P1 and in Q so sk is a real and it is in the position k in the list. lets express sk like s[k] to be able to express the other real numbers of the list like a[n] (double index a[n][n] represents the n digit of the n number). Now we want to add this property to sk:
P2="s[k][n] equals 0 if a[n][n]=1 and equals 1 if a[n][n]=0". For n != k there is no problem. But for the k index we could express P2 in this terms "s[k][k] is not equal to s[k][k]". This is in contradiction with P1 since all real numbers are equal to themselves. like in our previous example (with complex property) since we trust in P1 then P2 must be false. Q is still true and F is true since the only property that holds for sk is our first assumption P1.

Now lets take it the other way. We start from this assumptions:

1. Q="L is a complete list of the reals"
2. P2="sk is a mathematical object with this structure: sk[n] equals 0 if a[n][n]=1 and equals 1 if a[n][n]=0"

From this assumptions, F (sk is in the list of reals) is not obviously true since we have first to demonstrate that sk is a real in the realm where Q and P2 holds.

We want to add the property P1: "sk is a member of the real set". from P1 and Q it follows that sk is in the list so sk has a position k in the list. Again if P1 and P2 are true then s[k][k] is not equal to s[k][k]. So in a realm where Q and P2 hold sk can not have the property P1. Since sk can not be a real the list is complete without sk so Q is still true and F (sk is in the list) is simply false.

It is important to understand that P2 can only be expressed in a realm were Q is taken as an assumption since P2 needs the list of reals to be correctly defined. This is probably one of the confusion of this issue since it seems that P2 is simply expressing a binary infinite sequence (so a real number) but the construction is dependent of the existence of Q. So if an object exist with P2 it must be in a realm where Q holds and a complete list exist.

We can resume all this feelings like this:

1. If we belief in Q we can express and belief in P2 but an object that have the property P2 has not the property P1. (an object with property P2 is not a real in Q's realm).
2. If we belief in Q and we belief in P1 an object that have the property P1 can not have property P2. (a real can not have P2 has a property in Q's realm).
3. If we don't belief in Q we are not able to express P2 since we need the complete list of reals to define P2.

The only way to refute Q (is what Cantor Diagonal proof do) is to assume that there exist an object with both properties in the realm where Q holds. When I informally said that in the cantor diagonal proof the number sk is defined has "I'm a real not equal to myself" I wanted to express the fact that in a realm where Q holds there is no mathematical object that have both properties P1 and P2.

Another way of seeing this is: Since in the realm where Q holds, P1 express that sk is a real but P2 express that sk is not a real, an object with both properties (P1 and P2) in this realm seems to be a contradiction (a paradox) and we can derive anything from a paradox.

Probably what is so confusing about this issue is that it seems to express the idea than an object that is build from a complete list of reals is itself not a real.

That is the reason why in my first attempt to express this issue I was concerned with the completeness of the list. if the list is not complete P1 and P2 can both be true but I think that in that case the diagonal argument does not prove what it wants to prove.

• See this post. – Mauro ALLEGRANZA Mar 8 '15 at 13:43
• "In every Cantor diagonal proof we assume to have a "complete" list of reals" ... – Mauro ALLEGRANZA Mar 8 '15 at 13:44
• The argument shows that no list can be complete. You need not assume that it is or is not complete. – WimC Mar 8 '15 at 13:45
• @MauroALLEGRANZA in fact the answer have the same issue: if you take "all binary sequences" sk must be in this list so sk is not correctly defined since is not equal to itself. – J.F. Mar 8 '15 at 13:47
• @B.E. It sounds like you're having issues with the idea of a proof by contradiction. The whole point is sk should be in that list, but by showing that it isn't, Cantor proved there can be no list of "all binary sequences", which is equivalent to saying that set is uncountable. – Ixrec Mar 8 '15 at 13:51

You're right, the presentation of this proof is often very confused. People often want to say "suppose we have a complete list…" and then show this leads to a contradiction. But that is unnecessarily convoluted.

One should not think of the list as being complete or incomplete ahead of time. It's just a list. So say we have a list of real numbers, maybe a finite list or an infinite list, it doesn't matter.

1. We then construct a real number that is not in the list.
2. This shows that our original list was incomplete.
3. Since this construction would work for any list, the argument shows that every list of real numbers is incomplete.

(I don't know why people always want to make the argument more complicated than it is.)

• It's easier to explain a mumbled argument, than it is to give a clear and simple -- yet counterintuitive (since up to this point intuition is always that "things we cannot do" are proved by way of contradiction). At least this is what I can gather from grading so many exams in set theory in the past five years. – Asaf Karagila Mar 8 '15 at 23:18
• I'm not sure that if the list is not complete the diagonal argument proves what it wants to prove. Could you read my update to see why I'm concerned with the complete list and the definition of the real number not in that list? Thanks a lot for your time. – J.F. Mar 8 '15 at 23:31
• No, your post is way too long and I am not going to read it. – MJD Mar 9 '15 at 0:00
• Are you really claiming that a proof by contradiction of $\lnot \exists x (P(x))$ is "very confused" in comparison to an equivalent direct proof of $\forall x (\lnot P(x))$? I can see suggesting the latter, and pointing out that it's equivalent, to someone confused by the basic logic of the former, but I would not call it "very confused" or "unnecessarily convoluted." They really are equivalent and it seems more a matter of taste (assuming standard logic is applicable). – aes Mar 9 '15 at 0:57
• @be Your problem is in "I select one thing of that bag (P1: this think is in the bag) and add to this element the property(P2)". That is not what we are doing. Here, we take the first thing from the bag, it is large, so we say "okay, imagine a small thing". Then we take the second thing; it is red, so we say "imagine a small green thing". Then we take the third thing; it is light, so we say "imagine a small green heavy thing". When we're done, we know the thing we are imagining is not like anything in the bag: it's not large, so it's not the first object; it's not red, so it's not the second… – MJD Mar 9 '15 at 12:59

Cantor's Diagonal Argument is a proof by contradiction. In very non-rigorous terms, it starts out by assuming there is a "complete list" of all the reals, and then proceeds to show there must be some real number sk which is not in that list, thereby proving "there is no complete list of reals", i.e. the reals are uncountable.

does it make sense to take an incomplete list of reals?

Why not? [1, 2, 3] is an incomplete list of reals.

I personally think if it is not complete it is useless to demonstrate that you have a real that is not in the list since by definition the list is incomplete.

Actually, by definition it was complete. That's how it was defined at the beginning of the proof. The demonstration that some real number is not actually in the list contradicts that definition. That's how proofs by contradiction work.

This number is not correctly defined since it is not equal to itself.

I don't understand this assertion. sk is a real number not equal to any of the real numbers in the list, but it's still equal to itself.

you can demonstrate that sk is not in the set but the set of rational numbers is countable so the set of "natural numbers with 0.5" must also be countable.

Well, 0.5 is not a natural number, so that doesn't really prove anything. The diagonal proof wouldn't work if sk wasn't a real number. I'm not quite sure what you're trying to say here.

Post-Update: It's difficult to figure out what's going on in your update since you've assigned many different values to P2 all for no apparent reason, but I think where you went wrong is this:

1. "sk is in the set of reals"
2. "L is a complete list of reals"
3. Therefore, "sk has position k in list L"
4. Therefore, the definition of sk implies "s[k][k] is not equal to s[k][k]"

This is not an argument you can ever make, because sk is defined in such a way that it cannot possibly have a position in list L. That's the whole point of the proof. All you're doing is stating another contradiction that falls out of this proof, and from it incorrectly concluding the proof's definition of sk is wrong, rather than correctly concluding that the proof's definition of L is wrong.

The other big mistake is: "We should remember that we trust in P1 and in Q" We don't trust them at all. Q is an arbitrary assumption, which is assumed for the sole purpose of proving false at the end. P1 is directly provable from the definition of sk and needs no "trust". You never trust a statement in math unless it's an axiom, or you've proven it already.

Remember: The definition of L is a completely baseless assumption made at the start of the proof solely to be contradicted. The definition of sk is spelled out rigorously, and the fact that sk must be real and must not be in L can be directly proven from its definition without any further assumptions (which is exactly what the Diagonal Argument does). That's why L has to be the one with the "bad definition", not sk.

"The only way to refute Q (is what Cantor Diagonal proof do) is to assume that there exist an object with both properties in the realm where Q holds." Nope. The only way is to prove that such an object exists. Merely assuming a number like sk exists does not prove anything.

"in a realm where Q holds there is no mathematical object that have both properties P1 and P2" This is correct, but only because Q is false. When you assume a false statement is true, everything else is both true and false, so this statement is vacuous. The correct thing to say is "The Diagonal Argument shows that Q, P1 and P2 cannot all be true at the same time, so one of them must be false". P1 and P2 have clear proofs, while Q is an assumption, so it must be Q that's false.

P.S. Perhaps this belongs in chat.

• "Actually by definition it was complete." Rather, by assumption it was complete. – Théophile Mar 8 '15 at 14:16
• I'm sorry for my incomplete presentation of the issue. I tried to express it in a better way could you please read my update? thanks a lot for your time. – J.F. Mar 8 '15 at 23:33
• @B.E. I've attempted to respond to the update. – Ixrec Mar 9 '15 at 8:03
• Thanks a lot for your comments. You said: "This is not an argument you can ever make". In fact what I tried to demonstrate is that the way sk is build in the Diagonal Proof is inconsistent dividing the definition of sk in 2 properties P1 and P2. You said: "The Diagonal Argument shows that Q, P1 and P2 cannot all be true at the same time, so one of them must be false". This is because P1 and P2 are a contradiction so "notQ" or "the moon made of cheese" is no demonstrated. – J.F. Mar 9 '15 at 9:20
• Lets state it in another simple way. I have a bag of thinks (no mater what). I select one thing of that bag (P1) and add to this element the property(P2): "you are not equal to any other thing of that bag". From my humble point of view this is a non-sense since this is equal to say: "you are no equal to yourself". In this case do you prefer to accept the bag of elements or the existence of this element that is define as being in the bag (P1) and not being in the bag (P2) at the same time? – J.F. Mar 9 '15 at 9:20

The line where you mentioned "does it makes sense to take a incomplete set of reals" is the one place I think where you are having problem, you can view the cantors diagonal argument this way, we assume that all real numbers can be mapped with natural numbers (its in the form p --> q ) , now what the diagonal argument does is it shows that there is a number say z which is real but is not in the list ( ~q ) and then we conclude that ~p . The real number z is made of all the diagonal digits,now since our assumption is all real numbers are already mapped then there must be some place in list where this number z is, however we can see that this number can't belong to the list, this leads us to a contradiction that all numbers are indeed mapped ( ~q ), thus we conclude ~p.

• This is hard to read. Please use you instead of u, I instead of i, etc., and avoid run-on sentences. – Théophile Mar 8 '15 at 14:11
• I'm sorry but I don't really understand your answer. My question was not really well expressed. Could you please read my update? thanks a lot for your time. – J.F. Mar 8 '15 at 23:35
• I didn't read all the whole post of what you edited but the part where you had written,"sk[k] = 0 if a[k][k] = 1 and sk[k] = 1 if a[k][k] = 0", I think this is slightly confusing, i give u a small example let our list be of length 3, consisting of 1 2 3, 2 3 4 , 3 4 5 , then taking the diagonal elements and adding 1 to it we get a number as 2 4 6 which is not in the list , for other lists similar thing can be done – Cloverr Mar 9 '15 at 7:27