# Are We There Yet? Still Searching For Infinity And Beyond

A few days ago we began an exploration of infinity (see How Much Farther Is It To Infinity And Beyond?) .  Specifically, the infinity of the integers.  During our journey we discovered that there are as many rationals as there are integers, even though there are an infinite number of rationals between each pair of integers.  That is, we determined that the rationals had a one-to-one relationship with the integers (one rational matched with one integer).  We termed this type of infinity as countable.

But at the end of the discussion I posed the following question:

Are there other types of infinity?

And given that we are talking about infinity again, you’d better believe that there are.  In this post, we are going to consider an uncountable infinity.  If you thought your mind was blown in the previous post, hold onto your grey matter; things are about to get crazy!

Before we get too crazy, however, recall that by stating that the rationals are countable we are actually stating that they can be lined up and matched with the integers; one rational per integer.  In essence, if given an infinite amount of time we could list the rationals and count each and every one of them.

But now we want to talk about an uncountable set of numbers.  That is, a set of numbers that can’t be counted.  In other words, we can’t line them up and assign one integer to each of the numbers in the set.

To motivate the conversation, let’s consider the real numbers.  The reals, which are denoted as $\mathbb{R}$ are a combination of the rationals (denoted $\mathbb{Q}$) and the irrationals (denoted $\overline{\mathbb{Q}}$).  We already know that the rationals are countable, so at minimum, the reals should be at least countable as well.  But is this the case?

Let’s assume that we can count the reals. That is, we can list all of the reals in order and match them with a unique integer. But all the reals might be a bit overwhelming.  Let’s just try to do this with all of the real numbers between 0 and 1.  The idea being, if we can’t list all the numbers between 0 and 1 and assign a unique integer to each one of them, then we won’t be able to do this for the entire set of real numbers.

So we begin by assuming that we’ve listed all of the reals between 0 and 1 in some order and have matched them up with the integers.  So, we could write this in a general form as

1. $0.p_{1,1}p_{1,2}p_{1,3}\ldots$,
2. $0.p_{2,1}p_{2,2}p_{2,3}\ldots$,
3. $0.p_{3,1}p_{3,2}p_{3,3}\ldots$,
4. etc.,

where $p_{i,j}$ represents the $j^{th}$ digit of the $i^{th}$ number.  Note that the $i$ identifies which integer has been matched up with the real number.

Now, if we’ve managed to match all of the real numbers between 0 and 1 with an integer, there should be no way that a real number would be missing from our list. Otherwise, we’d have a real number that couldn’t be matched with an integer. So the question is, can we construct a real number that is between 0 and 1 that isn’t on this list? Let’s try. We’ll write our new number as $0.q_{1}q_{2}q_{3}\ldots$.

We start with our first number: $0.p_{1,1}p_{1,2}p_{1,3}\ldots$.  To ensure our new number is different from this, we set our new number to have a different first digit. So, let’s set $q_{1}$ to anything other than $p_{1,1}$.  We also won’t set $q_{1}$ to 9, because that sets us up for the possibility of an infinite string of 9s1.

In a similar way we set our second digit $q_{2}$ to anything but $p_{2,2}$. This guarantees that our new number differs from both $0.p_{1,1}p_{1,2}p_{1,3}\ldots$ (in at least the first digit), and $0.p_{2,1}p_{2,2}p_{2,3}\ldots$ (in at least the second digit).

We continue building our number using this process for the entire list of all of the real numbers in our list. Our number is guaranteed to be different from every number in our list in at least the $i^{th}$ position of the $i^{th}$ number. This means that our real number hasn’t been matched up with an integer. But this contradicts our assumption that our list was complete and countable. The only conclusion is that the real numbers between 0 and 1 are uncountable.  Using the same argument, we can see that the entire set of reals must be uncountable.

So with that, dear friends, we have at least two types of infinity.  Those that are countable, and those that are uncountable.  And since we know that the real numbers (which are uncountable) contain the rationals (which are countable), it seems that the irrationals must be uncountable.  But we’ll talk more about that later.

CRAZY!

1 An infinite string of 9s would be bad because $0.999\ldots=1$ (and we want to avoid this type of duplication). Say what? Consider the following. Let $x=0.999\ldots$. Then $10x=9.999\ldots$. This means that $10x-x=9.999\ldots-0.999\ldots$, or in other words $9x=9$. Which means $x=1$. Crazy; even though we started by stating $x=0.999\ldots$, we come to the conclusion that $x=1$, which must mean that $0.999\ldots=1$.