I'm trying to grasp Cantor's diagonal argument to understand the proof that the power set of the natural numbers is uncountable. On Wikipedia, there is the following illustration:

enter image description here

The explanation of the proof says the following:

By construction, s differs from each sn, since their nth digits differ (highlighted in the example). Hence, s cannot occur in the enumeration.

I don't understand why the sequence s at the bottom cannot occur anywhere in the enumeration of sequences above. I have read the proof about five times, but I'm still not getting it. I think I'm having an error in reasoning. Could someone please explain me why s cannot be in the enumeration with an example?

  • $\begingroup$ however: math.stackexchange.com/questions/1526624/… $\endgroup$ – janmarqz Nov 22 '15 at 17:04
  • 5
    $\begingroup$ I had a strong reaction to your suggestion that you might be "too dumb to understand" the proof. Don't let learning anything make you feel that way! Understanding is the result of being confused, not the absence of it. $\endgroup$ – Eli Rose -- REINSTATE MONICA Nov 22 '15 at 23:32
  • $\begingroup$ See this post. $\endgroup$ – user 170039 Nov 23 '15 at 2:33
  • 1
    $\begingroup$ @EliRose Thanks for the advice, I edited my post :)) $\endgroup$ – Javiator Nov 23 '15 at 11:08

The key is that it's different by construction, which means that you're choosing the digits of $s$ specifically so that it will be different from every other item in the list.

Compare $s$ to $s_1$: you see right away that they are different because the first digit is different. Now compare $s$ to $s_2$: they are different at the second digit. The same holds for the remaining $s_i$. The reason this happens is precisely because we chose the digits of $s$ to have this property.

  • 2
    $\begingroup$ Oh gooood, it is so simple. Thank you very much. $\endgroup$ – Javiator Nov 22 '15 at 16:58

Basically, the diagonalizing method is to take every possible number one at a time and say "I can make a number that is different than this and different than any number so far". !!*!IF!!!* the resulting number did exist in the list then you would have come across it and you would have said "I can make a number different than this" and you would have, so the number can't be in the list.

That number can't be the first number because it has a different first term. It can't be the second number because it's got a different second term. It can't be the nth number because it's got a different nth term.

So let's suppose the number is on the list. Well, what number listing does it have? Let's say it's the coopledinkyfudgeth number on the list. Well when we do our diagonalization and we come the coopledinkyfudgeth number we change the coopledinkyfudgeth term and get a different number. So it ISN'T the coopledinkyfudgeth number after all!

It's not on the list! The list is impossible and there is no list.

  • 1
    $\begingroup$ Awesome explanation, I was laughing reading through it and it actually really helped me understand the proof! $\endgroup$ – jeremy radcliff Nov 22 '15 at 19:09

The reason that this works is because we are assuming that we can list every possible string in a sequence, but the point of the proof is to show that this cannot be done. If we $\textit{could}$ make a list, then $s$ has to be a term in the sequence, and thus would have to be equal to some $s_N$. But by our construction of $s$, we switch the $N$-th digit of $s_N$. Thus, $s$ is a new string of $0$ and $1$s - which is a contradiction to the assumption that we can make a list.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.