Mathematics, philosophy, code, travel and everything in between. More about me…

I write about

English | Czech
Choose your language. I write in English, but I translate many of my articles to Czech as well. Zvolte si jazyk. Píšu anglicky, ale řadu svých článků překládám i do češtiny.

Infinity of Infinities

Our long journey through the infinite lands is coming to an end. What end is there to infinity, you ask? I’d have to put on a theologian’s hat to answer that. But as a mathematician, I can answer a question much more daring: what end is there to infinities?

Welcome to another part of the “Maths For Normal People” series. You will find all the previous parts in this article.

Mapping Mappings

In order to make this article more readable, we need to clarify the notation of “correspondences” between sets, which we’ve been using somehow loosely. In mathematics, these “correspondences” are called mappings.

Let’s have two sets, <$A$> and <$B$>, and a mapping between them which we can call <$f.$> This <$f$> is a “rule” that tells us how to assign elements from <$B$> to elements of <$A.$> For any element <$x$> from <$A$>, <$f(x)$> denotes its image, that is, the element from <$B$> which is assigned to <$x$> by the “rule” <$f.$> In the notation we’ve already used, <$x \mapsto f(x).$>

For instance, let <$A = \{1,2,3\},$> <$B = \{1,4,9\},$> and let <$f$> be a mapping that assigns to every number from <$A$> its square from <$B.$> (<$f$> maps numbers to their squares.)

1, 2, and 3 assigned to 1, 4, and 9, respectively.

<$1$> is the image of <$1,$> <$4$> is the image of <$2,$> and <$9$> is the image of <$3.$> Or, <$f(1) = 1, f(2) = 4, f(3) = 9.$>

Power(set)-ful Mappings

We’ll also need to establish mappings between sets and their power sets. Thinking about this can be a little tricky. As the elements of a power set are also sets, all images in these mappings will be sets.

For instance, suppose our mapping <$f$> between <$\{1,2\}$> and <$\mathcal{P}(\{1,2\})$> defined the rule “<$2\mapsto\{1,2\}.$>” <$\mathcal{P}(\{1,2\})$> is the set <$\{\emptyset, \{1\}, \{2\}, \{1,2\}\},$> so we can freely choose to assign its element <$\{1,2\}$> to <$2.$> This means that the image of <$2$> is a set: <$f(2) = \{1,2\}.$>

With such complicated mappings, we can start asking odd questions like this one:

Is <$2$> contained in its own image?

In our example, yes. <$2$> maps to the set <$\{1,2\}$> which contains a <$2.$> But this is not a universal rule. Our mapping could easily say that <$1\mapsto\{2\}$>, and in that case <$1$> would not be contained in its own image.

Pondering such abstract questions may seem pointless. But it’s not. For analyzing the cardinality of power sets, this question is essential.

Is <$x$> contained in <$f(x)$>?

Pause here for a while and think about mapping elements of a set to subsets of that set. It’s important!

The Power Set of Infinity

Now we’re ready to prove the following shocking statement:

The power set of any set <$X$> has a cardinality strictly greater than <$X$> has. <$(|\mathcal{P}(X)| > |X|.)$>

Does that sound shocking to you? No? Then realize this: the statement holds true for any set, even if it’s infinite. Given any set <$X$>, we can create a bigger set by the power set operation!

This means that the power set of the set of real numbers (<$\mathbb{R}$>) is bigger than <$\mathbb{R},$> which is already bigger than the set of natural numbers (<$\mathbb{N}$>), which is infinite. So we have a third infinity, bigger than the previous two!

<$$ |\mathbb{N}| < |\mathbb{R}| < |\mathcal{P}(\mathbb{R})| $$>

We shall discuss all the consequences later on, but first, let us prove this bold claim.

Contradiction Reveals The Truth

First, let’s deal with the possibility that <$\mathcal{P}(X)$> is actually smaller than <$X.$> This cannot be true, since for every element <$x$> contained in <$X,$> <$\mathcal{P}(X)$> contains at the very least a one-element set <$\{x\}.$> (The element <$x$> and the set <$\{x\}$> are two different things!) For instance, the power set of <$\{1,2,3\}$> contains, among other, the sets <$\{1\},\{2\},\{3\}.$> Therefore, <$(|\mathcal{P}(X)| \geq |X|.)$> It remains to be proved that the two values aren’t equal.

We’ll do that using a proof by contradiction again. So we’re going to assume the opposite is true and try to deduce some logical impossibility from it:

Let’s suppose there exists a bijection between a set and its power set.

Okay, let’s say there’s a bijection <$f$> that maps every element of <$X$> to some subset of <$X$>, i.e. to an element of <$\mathcal{P}(X).$> In that case, every possible subset of <$X$> we can imagine must be an image of some element of <$X.$>

Here comes the trick. We define a strange subset of <$X$> whose very existence leads to a logical impossibility – under the condition that <$f$> is really a bijection.

How do we define this horrific subset? Let’s give it an innocent name, <$A.$> Now, let <$A$> contain all elements of <$X$> which are not contained in their own image by <$f.$> That means all elements <$x$> which are not in the set <$f(x).$> Remember that <$f$> maps to sets, so every image is a set.

Example

Suppose we have <$X = \{1,2,3,4\}$> and our bijection <$f$> states the following rules:

<$$ \displaylines{ 1 \mapsto \{1,2,3\}, \\ 2 \mapsto \{3\}, \\ 3 \mapsto \{1,3\}, \\ 4 \mapsto \emptyset. } $$>

In this case, <$A$> would contain <$2$> and <$4,$> because these numbers map to subsets of <$X$> which don’t contain them.

Okay, we’ve got ourselves a strangely defined set which must be a subset of <$X$> because it contains elements from <$X.$> Therefore it must be in <$\mathcal{P}(X).$> Therefore, under our assumption that <$f$> is a bijection from <$X$> to <$\mathcal{P}(X),$> there must be an element (let’s call it <$a$>) in <$X$> that maps to <$A$> which is an element of <$\mathcal{P}(X).$>

<$$ f(a) = A. $$>

We are now the tiniest step away from the logical contradiction we’re after. We just have to ask cleverly…

The Crucial Question

Is <$a$> contained in <$A$>?

<$A$> is a set containing elements of <$X,$> so the question makes sense. But what is the answer?

  1. Suppose <$a$> is contained in <$A.$> That means that <$a$> is contained in its own image, since <$f(a) = A.$> But wait! We defined <$A$> as a set containing all elements of <$X$> which are not contained in their own image. Therefore, <$a$> can not be in <$A!$>
  2. No problem, you say. So <$a$> isn’t contained in <$A.$> That means that <$a$> isn’t contained in its own image. But wait! We defined <$A$> as a set containing all elements of <$X$> which are not contained in their own image. Therefore, <$a$> must be in <$A!$>

Now this is one hell of a logical mess. <$a$> can either be or not be in <$A,$> but neither of these options is possible! What’s the way out of this?

It’s actually quite straightforward. Such <$a$> simply cannot exist. You can’t accuse something of violating the rules of logic if it doesn’t exist!

If there’s no <$a$> whose image would be <$A,$> it follows that <$f$> can’t really be a bijection, so <$\mathcal{P}(X)$> must be strictly larger than <$X.$> And we’re home.

Infinity Factory

Nothing can stop us from creating power sets of infinite sets. For instance, the power set of <$\mathbb{N}$> might look like this:

<$$ \mathcal{P}(\mathbb{N}) = \{\emptyset, \{1\}, \{1,2\}, \{5,8,24\}, \{2,4,6,8,10,\ldots\}, \{1533, 1534, 1535,\ldots\}, \ldots\}. $$>

We have just proved that <$|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|.$> Another infinity to reckon with.

However, the power set operation can be applied to any set… even to power sets! And a power set of a power set will again be a bit bigger…

<$$ |\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < |\mathcal{P}(\mathcal{P}(\mathcal{P}(\mathbb{N})))| < \ldots $$>

Think about this sequence for a moment and see where it ends… (?)

There are infinitely many infinities!

Want to read more? You will find the outline of all parts of the series in this article.

October 15, MMXI — Mathematics, Maths For Normal People, Infinity.