time to bleed by Joe Damato

technical ramblings from a wanna-be unix dinosaur

Different sizes of infinity

View Comments


If you enjoy this article, subscribe (via RSS or e-mail) and follow me on twitter.

Computer science

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….

Natural numbers

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.

Bijection

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 S. We can number the elements of S with the natural numbers, starting at 1:

S =\ (s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, \cdots )

Now, imagine that each element of S is an infinitely long binary string. So, for example, maybe your s_{1} is the infinite string of 0s, like this:

s_{1} =\ (0, 0, 0, 0, 0, 0, \cdots )

And maybe your s_{2} is the infinite binary string of alternating 1′s and 0′s, like this:

s_{2} = ( 1, 0, 1, 0, 1, 0, 1, \cdots )

And so on, until we’ve mapped every natural number to an infinitely long binary string.

Imagine a new string, call it s_{0}, that we construct by “walking” diagonally down our sequence of infinite binary strings, starting with the first element of s_{1} and picking the opposite bit, such that the i‘th element of s_0 is the reverse of the i‘th element of s_{i}.

an example

Imagine our set S looks like this:

S = \begin{pmatrix}  s_{1} = ( \underline{0}, 0, 0, 0, 0, 0, \cdots ), \\ s_{2} = ( 1, \underline{1}, 1, 1, 1, 1, \cdots ), \\ s_{3} = ( 1, 0, \underline{1}, 0, 1, 0, \cdots ), \\ s_{4} = ( 0, 1, 0, \underline{1}, 0, 1, \cdots ), \\ s_{5} = ( 1, 1, 0, 0, \underline{1}, 1, \cdots ), \\ s_{6} = ( 0, 0, 1, 1, 0, \underline{0}, \cdots ), \\ \vdots \end{pmatrix}


Then our s_{0} would look like this:

s_{0} = ( \underline{1}, \underline{0}, \underline{0}, \underline{0}, \underline{0}, \underline{1}, \cdots )

s_0, by construction, can not exist in our infinite sequence S. If s_0 did exist as (let’s just say) the 3rd element of S, then the 3rd bit of s_{3} and the 3rd bit of s_{0} would be the same, which is not possible with the construction outlined above.

Thus, s_0 is an infinite binary string we have created that exists outside of our infinite sequence S. However, we’ve already mapped all the natural numbers to elements in S and yet there is at least one more binary string (our s_{0}) 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, S and our s_{0}) is larger than the countably infinite set of natural numbers and so we say it is uncountably infinite.

Next time…

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.

If you enjoyed this article, subscribe (via RSS or e-mail) and follow me on twitter.

Written by Joe Damato

July 9th, 2012 at 7:00 am

Posted in computer science