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.

The Set of Subsets of a Set

Can there be any fact more shocking than that there are two infinities, one bigger than the other? Well, take a guess… But to crack the mystery underlying the existence of two different infinities, we first need to learn a little more from set theory… Monkeys, sheep, and leopards return!

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

In the first article of this series, we talked about sets. I gave the following vague “definition”:

We can intuitively understand the term set as an arbitrary collection of objects.

Until now, we’ve been using numbers, dots, and even animals as these “objects”. It’s now time to expand our abstract thinking. A set can itself also be an “object”.

Sets In Sets In Sets In…

Sets can contain other sets as their elements. If you imagine a set as a box, putting one set inside another is just like putting one box inside another. For instance, suppose we have these two sets of animals:

Set M with four monkeys and set S with five sheep.

If we wanted to group our animal sets, we could just put them inside another set, say, <$A$>:

Sets M and S together in set A.

Note that the cardinality (size) of <$A$> is 2, because it contains only two objects, <$M$> and <$S$>. We could write <$A = \{M, S\}$>.

There’s no rule saying what can or cannot go into a set. The following set is perfectly fine, because (a) we can mix objects however we want, and (b) the leopard is isolated in a separate set and can’t eat the sheep. We can also put sets in sets in sets in…

A set containing numbers, animals, polygons, and other sets.

The Power of Power Sets

Now that we can imagine putting sets into other sets, we’ll be able to understand an important set operator: the power set.

We’re already familiar with the concept of subsets: when we take out an arbitrary part of a set, we’ve created its subset. The relation of a subset and its set is denoted by the <$\subseteq$> sign. For instance, <$\{2,4,5\} \subseteq \{1,2,3,4,5,6,7\}$> or <$\{7,8,9,\ldots\} \subseteq \mathbb{N}.$> The empty set <$\emptyset$> is a subset of every set (a “nothing” is a part of “everything”). Every set is also a subset of itself (the whole is always a part of the whole).

Let’s say we have a set <$X$>. A power set of <$X$> is a set of all subsets of <$X$>. You may want to read that sentence a few times over before it starts making sense. Some examples will make things clearer. I shall denote the power set of <$X$> as <$\mathcal{P}(X).$>

<$$ \displaylines{ \mathcal{P}(\{1,2\}) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}. \\ \mathcal{P}(\{1,2,3\}) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\}, \{1,3\}, \{1,2,3\} \}. \\ \mathcal{P}(\emptyset) = \{\emptyset\}. \\ \mathcal{P}(\{\bullet\}) = \{\emptyset, \{\bullet\}\}. } $$>

If you’re not used to reading mathematics, the notation may seem very confusing to you. In that case, practice reading mathematics :-)

A power set of <$X$> is simply a collection of all possible sets that can be created by combining elements from <$X.$>

What’s all this good for, you ask? The power set is a concept leading to perhaps the greatest revelation in the “theory of infinity”. Even infinite sets have their power sets, and as it turns out, they have pretty interesting properties. We have finally reached the key needed to unlock and understand them… So see you next week ;-)

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

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