I struggled to understand the Cantor's diagonal argument, but I have some problems comprehending the following:

By construction, $s$ differs from each $s_n$, since their $n^{th}$ digits differ (highlighted in the example). Hence, $s$ cannot occur in the enumeration.

Can someone explain why the built sequence $s$ cannot occur in the enumeration? I can imagine it somehow recursively that if we add it to $s_n$, we can pick another sequence with the same construction pattern and we can repeat these steps forever. However, I want to know if this is sufficient as a proof or there is some kind of other explanation.


closed as off-topic by Tsuyoshi Ito, Sasho Nikolov, Radu GRIGore, R B, Kaveh Jan 17 '15 at 10:14

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Tsuyoshi Ito, Sasho Nikolov, Radu GRIGore, R B, Kaveh
If this question can be reworded to fit the rules in the help center, please edit the question.


It's actually more trivial.

  1. Suppose that $s$ occurs in the enumeration.

  2. Then it occurs at some specific index. Let's call this index $n$. This means that $s = s_n$.

  3. But this is impossible, because $s$ and $s_n$ differ in the $n$th digit.


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