# technical ramblings from a wanna-be unix dinosaur

## Different sizes of infinity ## 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.

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