# Can someone explain the reasoning behind Cantor's diagonal argument? [duplicate]

I'm taking a class that's covering cardinalities, and I was introduced to Cantor's diagonal argument today, and I'm having trouble following the logic. The theorem states, "If s[1], s[2], … , s[n], … is any enumeration of elements from T, then there is always an element s of T which corresponds to no s[n] in the enumeration." This sounds more like a logical paradox than a theorem to me.

Specifically, it states that "By construction, s differs from each s[n], since their nth digits differ. Hence, s cannot occur in the enumeration." (from Wikipedia)

However, if s[..] is "any enumeration of elements" in T, then it follows that any s created by choosing elements of T, by whatever method, must occur as some s[n], because s[..] represents every combination of digits possible, right?

This is where I can no longer follow the logic of the proof. Where does the assumption come from, that this diagonal sequence of digits is somehow special and doesn't occur anywhere else in s[..]? Wouldn't that invalidate the first statement of the theorem?

Sorry if this question seems obvious or stupid, but I can't find an explanation that doesn't seem (to me) to invalidate itself.

## migrated from mathoverflow.netSep 13 '15 at 2:21

This question came from our site for professional mathematicians.

• How about asking your professor or at math.stackexchange? This is not really research-level mathematics... – Per Alexandersson Sep 13 '15 at 2:11
• The key is that it is "an enumeration of elements from $T$"; as the argument shows, it cannot be an enumeration of all of the elements of $T$. The set of all elements of $T$ is therefore not enumerable. (Here, I assume we are talking about $T = [0,1)$, or some other uncountable set amenable to the diagonal argument.) – Eric Tressler Sep 13 '15 at 2:26
• It's an online class, there is no professor. I didn't know mathoverflow was different from math.stackexchange, but I think the moderators moved it to the right place. – HypnoToad Sep 13 '15 at 2:26
• Are you familiar with proofs by contradiction? Your objection applies to any proof by contradiction, including much simpler proofs. – littleO Sep 13 '15 at 3:18

That's the whole contradiction: You assume that there is a list of all the elements. Then you go on constructing an element that is not in the list (because it differs by some $n$-th digit). This contradicts the assumption that your list contains ALL elements. Hence there is no list which contains ALL elements. The concludion is that there are so many elements that it is not impossible to enumerate them (at least not by natural numbers). Is this helpful?
• It does not need to take the form of a contradiction: you can instead just show that an arbitrary enumeration of elements from the uncountable set $T$ misses elements of $T$. – Eric Tressler Sep 13 '15 at 2:29