Infinity is weird: to infinity, and beyond!

The third and it-turns-out-not-final installment in a series of posts on the size of the infinite, as described in mathematical set theory. The first post can be read here, and the second here.

I think Buzz Lightyear captures the spirit of this post best:

Who knew that Buzz was such a mathematical philosopher? “To infinity, and beyond;” that is a concise summary of what we have seen in the first two posts in this series! So far, we have seen that we can characterize the “size” of different infinite sets, and that there are at least two different size infinities. The smallest infinity, the size of which is labeled $\aleph_0$ , is the size of the natural, or “countable,” numbers: 1,2,3,4,5, and so forth. Any set of objects that can be put into one-to-one correspondence with the natural numbers is of size $\aleph_0$ . What is bigger than this? It turns out that the set of all real numbers between 0 and 1 is a larger set than the natural numbers! We label the size of this set as $\mathcal{C}$ . This continuous set of numbers, appropriately known as the continuum, is an uncountable infinity: the set is so infinitely large that it is not possible to even put them in order to count.

That’s crazy enough, but we can even go further: it is possible to demonstrate that there are an infinite number of larger infinities: an infinity of infinities of increasing size!*

So how do we do this? We will tackle the problem in two different ways**. First, we will give a specific example of an infinite set that is a larger infinity than the continuum. With this example under our belt, we will give a general prescription to construct a larger infinity from any size infinity. This latter prescription implies that, no matter how “big” an infinity we find, we can always find one more: there are an infinite number of infinities!

To start our exploration of the mathematics of unending infinities, we need to introduce the concept of functions, which should be familiar to anyone who has taken an algebra class. For those who haven’t (or haven’t in a while): a function in the most general sense of the term is simply an operation that assigns to each member of a given set (the “input”) a single “output.” In equation form, we label the members of the input set as “x” and the function itself as “f” — then the output is called “f(x).” Schematically, this is illustrated below.

A schematic illustration of the concept of a function, and an example of one. Adapted from Wikipedia.

The example on the right illustrates how it works: we take a set of numbers — in this case 0,1,2,3 — and apply the function to it — in this case squaring the number. The output is therefore the set of the squares of each number, in order.

We can also employ functions on continuous sets of numbers — in fact, that is what we usually do. For instance, we can consider functions f(x) that act on the continuous set of numbers between 0 and 1: that is, we consider functions that act on the numbers x such that $0 < x < 1$ . Two examples of such functions are shown below.

In general, a function f(x) that acts on $0 < x < 1$ is an operation that associates a unique number to every value of x.

With this in mind, let us consider the set of all functions f(x) on the numbers $0 < x < 1$ . We consider two functions to be different if they disagree at even a single point on the range of x, as illustrated below.

It is hopefully clear that the set of all functions is at least as large as the continuum. Each function consists of continuum-size ordered set of numbers, namely the values f(x) of the function at each point $0 < x <1$ . It also seems like the set of functions must be larger than the continuum, because the continuum is contained in it! For instance, the set of constant functions, $f(x) = c$ , where $c$ is any real number, are the size of the continuum by themselves. However, our intuition can be flawed: we already saw in the first post that the set of even numbers $2,4,6,\ldots$ is the same size as the set of natural numbers $1,2,3,\ldots$ .

We can show, though, that the size of this set of all functions is in fact a larger infinity than the size $\mathcal{C}$ of the continuum. We do this by employing an argument similar to Cantor’s diagonal argument from the last post: we try and arrange the set of functions and the continuum in one-to-one correspondence, and then show that there are functions that are not included in this correspondence.

If the set of functions f(x) can be matched one-to-one to the continuum, then we should be able to label each function in the set with its appropriate place in the continuum: we will label the function associated with a number $0 < r <1$ as $f_r(x)$ .

We now construct a new function that we call $\phi(x)$ , which is built such that its value at location $r$ is equal to $f_r(r)$ , i.e.

$\phi(r) = f_r(r)$ .

This new function may or may not be included in our set $f_r(x)$ ; it is impossible to tell. However, let us now construct another new function $\psi(x)$ , defined as

$\psi(x) = \phi(x)+c$ ,

where $c$ is a real number. But here’s the thing: this new function $\psi(x)$ is not included in our continuum-sized set of functions, because

$\psi(r) \neq f_r(r)$

for any $0<r<1$ ! This means that our new function is different from every member of our continuum of functions at one point at least.

We have therefore constructed a function that is not included in our continuum of functions, and in fact have constructed an infinite number of them, because $c$ can be any real number! Our assumption that we can match the set of functions f(x) to the set of numbers between 0 and 1 does not hold — the set of functions is a larger size infinity than the continuum.

Over the course of these three posts, then, we have constructed three different infinities, of increasingly larger size. If we label the size of the function set as $\mathcal{F}$ , then we may write

$\aleph_0 < \mathcal{C} < \mathcal{F}$ .

Can we go further? Yes! In fact, we can introduce a method for constructing an unending set of increasingly larger infinities, as we now demonstrate.

The key to this new method is to introduce the idea of a subset. Loosely speaking, a subset of any given set is one that includes some, none, or all of the elements of the set. For instance, let us consider the finite set of numbers {1,2,3,4}. The subsets of this set are illustrated below.

There are 16 subsets of our original set, including the empty set $\emptyset$ which is the “set of nothing.”

It is clear that, for any finite-sized set, the number of subsets is larger than the size of the original set. In fact, we can derive a formula for the number of subsets by a simple argument.

Let us think of a subset of a set of N elements in a slightly different way than before. Each subset can be written as the realization of N possibilities, each “possibility” being the presence or absence of a particular element in the set. For example, several of the subsets of our {1,2,3,4} set are shown below.

As a final step, I’ve written each subset in a binary form: a “1” indicates that the element is present in the subset, while a “0” indicates that the element is not present.

Therefore, each subset of a set of N elements can be written as an N digit binary number. What are the total number of possible elements that can be represented by this number? Well, there are 2 options for element 1, times 2 options for element 2, … times 2 options for element N. In short,

$\mbox{number of subsets} = 2^N$ .

A set of 2 elements therefore has 4 subsets, a set of 3 elements has 8 subsets, a set of 4 elements has 16 subsets, and so on. This argument would seem to also apply to a set of infinite size; the number of subsets of a countable infinity, then, can be written symbolically as

$\mbox{number of subsets of countably infinite set} = 2^{\aleph_0}$ ,

and superficially it would seem that this set must be larger than a countable infinity. But is it?

To answer this question, we need to employ a particularly devious construction, which happens again to be loosely related to Cantor’s diagonal construction. Let us illustrate the idea with a finite set X of six elements first; we want to show that there are more subsets of X than there are members of X itself. We start by trying to form a one-to-one correspondence again, lining up a collection of subsets of X, the set to be called $U_X$ , next to the elements of X itself, as shown below.

You’ll notice that I’ve somewhat randomly picked subsets to be placed into $U_X$ . When we extend this argument to infinite sets, especially uncountably infinite sets, we cannot in general assign some sort of definite order to the subsets, which means that we have to perform our proof without assuming that they can be arranged in any special way.

Now let’s take a closer look at the elements of X. We can divide them into two classes:

class I: those elements that appear in their corresponding subset
class II: those that do not appear in their corresponding subset

Now let us create another subset of X, which we will call L, by grouping together all of the elements of class II.

The important thing to note here is that our new subset L is not part of our set of subsets $U_X$ . We have therefore demonstrated that the set of subsets of X must be bigger than X itself. We proved this by trying to place the subsets in one-to-one correspondence and showing that there is at least one more subset that cannot fit in that correspondence.

How does this work? We can use a logical argument to show that the new subset cannot be a part of $U_X$ as follows.

First, we note again that L is the set of all elements in class II.
If we assume that L lies within our one-to-one correspondence set $U_X$ , then it has a corresponding member of X that we will call $x_l$ .
There are now two choices: either $x_l$ is part of L or it is not.
If $x_l$ is a part of L, then it is in class I; however, we have constructed L to only contain elements of class II! Therefore $x_l$ is not a part of L.
If $x_l$ is not a part of L, then it is in class II. But if it is in class II, then it must be a part of L! This contradiction tells us that one of the assumptions of our argument must be wrong.
The only assumption that we have made is that L, which is a subset of X, is included in a set with one-to-one correspondence with X. This assumption is flawed; the set L is not part of a correspondence with X. This tells us that the set of subsets of X is larger than the set X itself.

Did that completely lose you? It is a challenging logical argument, and in fact I myself had to go over it in my head multiple times before I was able to understand it and convince myself that it works! Don’t be bothered if you don’t get it at first: some of the best mathematical insights require time and effort to grasp.

Our argument above is even more impressive when you realize that there is no assumption that the sets must be of finite size, or even countably infinite! All we required is the ability to place elements of sets in correspondence with one another. We may therefore say the following:

For a given infinite set X, the set of all subsets of X is a larger infinity than X itself.

For any infinite set X, we can always construct an infinite set of larger size by constructing the set U(X) of all its subsets. We can then take that set U(X) and construct an infinite set of even larger size by constructing the set of all its subsets, and so on! We can therefore create an infinite number of infinities of increasingly larger size.

There is one more crazy thing to observe before we end this post. So far in this series of posts, we have illustrated three infinities: the countable infinity of cardinal number $\aleph_0$ , the continuum of cardinal number $\mathcal{C}$ , and the set of functions with cardinal number $\mathcal{F}$ . Thinking in terms of subsets, it is possible to show that

$2^{\aleph_0} = \mathcal{C}$ ,

$2^{\mathcal{C}}=\mathcal{F}$ .

In words: the set of all subsets of the natural numbers is the size of the continuum, and the set of all subsets of the continuum is the size of the set of functions! As I’ve gone on far enough at this point, I will not prove these results, but at least the first of these equations is surprisingly easy to demonstrate.

In the first post in this series, we introduced the size of the countable numbers; in the second post, we introduced a larger infinity, the continuum. In this post, we have shown that we can construct an infinite number of infinite sets of every-increasing size.

There is something seductive in the structure of these infinities, at least as we’ve presented them so far. We seem to have formed the basis of a countable set of infinities — that is, if we relabel $\aleph_0 = \infty_0$ , $\mathcal{C}=\infty_1$ , $\mathcal{F}=\infty_2$ , then it almost looks like we can introduce a countable infinity of infinities, of the form:

$\mbox{set of all infinities(?)} = \infty_0, \infty_1, \infty_2, \ldots$ .

Is this really true? There is a crucial question has has been ignored in making this argument: Are there any cardinal numbers (sizes of infinity) that lie between $\infty_0$ and $\infty_1$ ? This has been a long-standing problem in mathematical set theory, known as the continuum problem. When we look at this question in the (final?) post of this series, we will find that the answer, such as it is, is perhaps the strangest of all we have seen.

***

* It is really hard to write a post like this without italicizing everything: it is all just so cool!

** I am broadly following the arguments presented in the excellent book by J. Breuer “Introduction to the Theory of Sets” (Dover, 2006)

1 Response to Infinity is weird: to infinity, and beyond!

Adrian Morgan says:

December 8, 2013 at 8:38 pm

Nice to go a step beyond most discussions of the different infinities.

One minor improvement for clarity may be to replace “has a corresponding member of X” in step two with “corresponds to a member of X”. This may be trivial, but better reflects that the correspondence is not a property of L but a property of the mapping.