If you enjoy this article, subscribe (via RSS or e-mail) and follow me on twitter.
I have a computer science degree, but I like hacking low level systems code and very rarely ever actually do any real computer science. That said, I was reminded about this cool proof by my old college buddy Dan. I decided to share it and possibly motivate myself to dust off some old computer science knowledge that is going to waste as I crawl through the Linux garbage dump. If you’ve never seen it before, maybe this will be interesting.
I’m going to assume you don’t know anything about math, so let’s start with….
Let’s define the set of natural numbers to be all whole numbers starting from 1. So, the set of natural numbers is: 1, 2, 3, 4, 5, …. off into infinity.
A bijection is a mathematical function that maps input values to output values such that all input values map to a unique output value and there are no leftovers.
this is a bijection:
This is not a bijection:
Anything that has a bijection with the natural numbers can be called countably infinite. That’s it. Not too bad.
Cantor’s diagonal argument
So, on to the cool part, thanks to my dogg Cantor.
Imagine you have an infinite sequence called . We can number the elements of with the natural numbers, starting at 1:
Now, imagine that each element of S is an infinitely long binary string. So, for example, maybe your is the infinite string of 0s, like this:
And maybe your is the infinite binary string of alternating 1′s and 0′s, like this:
And so on, until we’ve mapped every natural number to an infinitely long binary string.
Imagine a new string, call it , that we construct by “walking” diagonally down our sequence of infinite binary strings, starting with the first element of and picking the opposite bit, such that the ‘th element of is the reverse of the ‘th element of .
Imagine our set looks like this:
Then our would look like this:
, by construction, can not exist in our infinite sequence . If did exist as (let’s just say) the 3rd element of , then the 3rd bit of and the 3rd bit of would be the same, which is not possible with the construction outlined above.
Thus, is an infinite binary string we have created that exists outside of our infinite sequence . However, we’ve already mapped all the natural numbers to elements in and yet there is at least one more binary string (our ) that doesn’t have a natural number paired with it.
So it follows that the infinite set of all infinite binary strings (which would include, at least, and our ) is larger than the countably infinite set of natural numbers and so we say it is uncountably infinite.
I’ll try to show that the real numbers are uncountable and probably regret using a binary string representation to show that it is possible to construct a set that is not countable.