Cantor’s Diagonalization Argument

I need to say something, but to understand that you need to know this.

Let us enumerate all possible infinitely long lists of binary numbers, and try to count them using natural numbers on the left:

Let us make a new infinitely long binary number like this: Take the th bit of the th binary number, flip it, and write it down as the th bit of our new binary number. In other words lets the take the complement of the binary number represented by the diagonal of the above list.

Let us for a second, assume that this new binary number is  the th number in the list of all binary numbers given above. But Hey! If that were the case, then the th bit of that th number in the list would be equal to the th bit of the new number we have created. But that is not so. Because we flipped the th bit of the th number to get the new number we created.

So we have no choice but to accept that this new number is not in the list of all infinitely long binary numbers we tried to count using natural numbers. But did we not define the list as the list of all possible infinitely long binary numbers? Yet the new number can’t be in the list because we made it that way.

This is the essence of proof that there are actually more infinite sequences of ones and zeros than there are natural numbers.

Neat, huh?

(To be continued…)