Set Wars: Episode III - Revenge of the Sizes

In the previous post we began exploring infinite sets - namely the integers and subsets thereof. However, we know that these are not the only infinite sets; there are the rationals (which contain the integers) and irrationals. We might be interested in determining properties of both of these sets. What is ahead of us is a weird exploration full of twists and turns and foundation-shaking results.

In the last post, we discovered that the even integers have the same number of elements as the integers. For convenience we will say that the integers are countably infinite (or just countable for short). Calling them countable is weird because it seems to imply you could actually count all of them, however that is not the reason for calling them countable. Instead it means you can list them in some meaningful way. In the case of the natural numbers (the numbers $1, 2, 3, \ldots$) we can just list them in order, starting at $1$: $1, 2, 3, 4, 5, 6, \ldots$ Or for the even integers: $0, 2, -2, 4, -4, 6, -6, \ldots$.

We will first observe the rationals. Recall that a number is rational if and only if it can be written in the form $\dfrac{p}{q}$ where $p$ and $q$ are integers. Since the rationals contain the integers, there are definitely an infinite amount of them; the question is: are they countable? In order to determine if they are countable, we will create a table as seen below. (Note that the table is actually infinite in size, but I have truncated it for convenience.)

\begin{array}{cccccc}
1/1 & 1/2 & 1/3 & 1/4 & 1/5 & \cdots \\
2/1 & 2/2 & 2/3 & 2/4 & 2/5 & \cdots  \\
3/1 & 3/2 & 3/3 & 3/4 & 3/5 & \cdots \\
4/1 & 4/2 & 4/3 & 4/4 & 4/5 & \cdots \\
5/1 & 5/2 & 5/3 & 5/4 & 5/5 & \cdots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{array}

The elements are created via the following construction: the numerator in each element is the row number and the denominator in each element is the column number. We will march through the table in the following manner. Start at $1/1$ and label this with the number $1$; migrate to $1/2$ and label this with the number $2$; move to $2/1$ and label this with $3$; move to $3/1$ and label this with $4$; move up to $1/3$ and label this with $5$, etc. The shape of the "graph" that resembles how we march through the elements in the table is a series of zig zags through the table. Note that $2/2$ since we had already accounted for it with $1/1$. This is a general procedure by which to enumerate the rationals. As we march through the graph, we label each rational in the table with a natural number. By this construction, we have created a bijective function (though we have not given it an explicit formula) that labels each rational with each natural number. Think: $f(1,1) = 1$, $f(1,2) = 2$, $f(2,1) = 3$, $f(3,1) = 4$, etc (this probably looks similar to an example from the last post). You may wonder why I elected to use a comma as opposed to a division symbol. It boils down to the fact that each rational will show up infinitely often so $f(1/1) = f(1) = f(2/2)$; instead I elected to use a multivariable function where the relation between the two elements is division and referring to that element in the table.

So since we have created a bijective function between the two, we have shown that the rational numbers are indeed countable. A property that we shall explore later is called the Archimedean property of the natural numbers, from this it follows that in any interval there exists a rational number. Another result is that in every interval there exists an irrational number. From this fact, we might figure that there are an equal amount of rationals and irrationals. It turns out that the rationals effectively take up no space on the real line as we can see with the following proof.

Since the rationals are countable, we can denote them in a list like so: $ q_1, q_2, q_3, \ldots $. Consider some $ q_i $. Let $ \varepsilon > 0 $ and select the interval $ \left (q_i - \dfrac{\varepsilon}{2^{i+1}}, q_i + \dfrac{\varepsilon}{2^{i+1}} \right ) = I_i.$

Since each rational is in one of the $ I_i $ (by definition), each rational is in $ \bigcup\limits_{i=1}^{\infty} I_i $. Therefore $ \mathbb{Q} \subseteq \bigcup\limits_{i=1}^{\infty} I_i$, where $ \mathbb{Q}$ represents the set of rationals.

A theorem we have not proved but makes logical sense is that if $A$ and $B$ are sets and $ A \subseteq B $, then $ |A| \leq |B| $ where $|A|$ represents the cardinality of $A$. So, $ |\mathbb{Q}| \leq \left |\bigcup\limits_{i=1}^{\infty} I_i  \right| .$

Each $ I_i $ has length $ \dfrac{\varepsilon}{2^i} $ and using the fact that $ \left |\sum_{i=0}^n a_n \right| \leq \sum\limits_{i=0}^n |a_n| $, so $ \left |\bigcup\limits_{i=1}^{\infty} I_i  \right| \leq \sum \limits_{i=0}^{\infty} \dfrac{\varepsilon}{2^i} = \varepsilon .$

Since we can set epsilon to as small a number we want, we conclude that the rationals have size $0$. We know that the real numbers are composed of the rationals and irrationals and that both sets are mutually disjoint. If the rationals take up basically no space on the real line, then we must conclude the irrationals take up most of the space on the real line. We are therefore led to the conclusion that the irrationals are much more numerous than the rationals. Before we motivate this, we will show that there are more reals than naturals.

For simplicity, we will consider the interval $(0,1)$. Assume (by way of contradiction) that the numbers in the interval $(0,1)$ are countable. We will consider the decimal expansions of numbers in this interval with one provision: we will omit numbers trailing in an infinite sequence of $9$s. Numbers like $.4\bar{9}$ we know to be equivalent to $.5$, so we will not be missing numbers like $.4\bar{9}$ since they will already be present.

To achieve our goal, we will construct another table (my! these seem handy!). ($n$ represents a natural number and $r$ represents a non-natural real number.)



\begin{array}{ccccc}
1 & .{r_1}_1{r_1}_2{r_1}_3{r_1}_4 \cdots \\
2 & .{r_2}_1{r_2}_2{r_2}_3{r_2}_4 \cdots \\
3 & .{r_3}_1{r_3}_2{r_3}_3{r_3}_4 \cdots \\
4 & .{r_4}_1{r_4}_2{r_4}_3{r_4}_4 \cdots \\
\vdots & \vdots
\end{array}

The individual terms are the numbers in the decimal expansion of each $r_i$.

Let's construct a number $r$ in $(0,1)$. $\Bbb R$ will differ from every number in the following way: $r$ will differ from $r_1$ in the first element, $r$ will differ from $r_2$ in the second element, $r$ will differ from $r_3$ in the third element, and so on. The way it shall differ is by adding $1$ to the $i$th element of $r_i$ unless the element is $9$, in which case the way it shall differ is by becoming $0$. It is evident that $r$ is definitely a number in $(0,1)$ with this construction, and that it differs from every number in our table. However, our table contains all numbers in $(0,1)$, so $r$ must be located somewhere in the second column of our table. So $r$ is in the table and it is not in the table, which gives a contradiction.

The only assumption we made at the get go was that we could find a one-to-one correspondence between the natural numbers and the numbers in $(0,1)$. Because we reached a logical contradiction we are forced to conclude that the numbers in $(0,1)$ are not countable. Since the real line includes $(0,1)$ we conclude that the real line is not countable. And since the reals are composed of the irrationals and rationals only and since the rationals are countable, we must conclude the irrationals are uncountable.

We have determined some deep properties of the rationals and irrationals and there are plenty more, but for the sake of brevity, I must stop here. There are some interesting things to note about the irrationals: there is an important countable subset of them called the (irrational) algebraic numbers. The algebraic numbers are roots of polynomials with rational coefficients. Those numbers that are irrational but not algebraic are transcendental and these numbers are those that are most (read: all others take up no space on the real line) abundant on the real line. Important examples are $\pi$ and $e$. There are many others listed and can be found on the Wikipedia article on them.

The preceding proof is due to Gregory Cantor and many at first found this concept utterly false. How can there possibly be a hierarchy of infinities? Surely infinity is the same regardless of context. As time progressed, set theory became very well accepted, however set theory has taken many interesting twists and turns since. There are many different axiomatic set theories and each has its strengths and weaknesses. The topic of advanced set theory is interesting, but beyond the scope of this blog as it carves a very fine description of mathematics. While important, it will not serve to enlighten the reader at this time. At the present time, coarseness is preferred.