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:

\begin{array}{ccc} 1 & \longrightarrow & (000000 \ldots)\\ 2 & \longrightarrow & (111111 \ldots)\\ 3 & \longrightarrow & (010101 \ldots)\\ 4 & \longrightarrow & (101010 \ldots)\\ \ldots &  & \end{array}

Let us make a new infinitely long binary number like this: Take the nth bit of the nth binary number, flip it, and write it down as the nth 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.

\begin{array}{ccc} N & \longrightarrow & (101110 \ldots)\\ \end{array}

Let us for a second, assume that this new binary number is  the kth number in the list of all binary numbers given above. But Hey! If that were the case, then the kth bit of that kth number in the list would be equal to the kth bit of the new number we have created. But that is not so. Because we flipped the kth bit of the kth 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…)


One thought on “Cantor’s Diagonalization Argument

  1. Pingback: (defun haltp (a i) … « Me in Words

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s