# Short

The goal here is to get a rough idea of why $$| P(\mathscr{S})| > |\mathscr{S}|$$ for any set $$\mathscr{S}$$.

Let $$\mathscr{S}$$ be any set. By definition, $$P(\mathscr{S})$$, called the power set of $$\mathscr{S}$$, is the set of subsets of $$\mathscr{S}$$. This is a tricky thing to think about. It's a new set, whose elements are the subsets of $$\mathscr{S}$$.

An example is helpful. Suppose for a moment that $$\mathscr{S} = \{a, b, c\}$$. Here are some subsets of $$\mathscr{S}$$:

$\{a\}\\ \{b\}\\ \{c\}\\ \{a, b\}\\ \{a, c\}\\ \{b, c\}$

Because mathematicians like to be pedantic, we also consider $$\{a, b, c\}$$ to be a subset of $$\{a, b, c\}$$. In other words, every set is a subset of itself. There's not much deep to this statement; it's just how we define the term subset. It's also handy to allow for the empty subset, the set that has nothing in it. We'll write this $$\{ \}$$. This is also an acceptable subset of $$\mathscr{S}$$.

Adding the full and empty subsets, this means that $$\{a, b, c\}$$ has a total of 8 subsets.

Thus the power set $$P(\{a, b, c\})$$ in this example is this set:

$\{ \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{a,b\}, \{ \}, \{a,b,c\} \}.$

Yes, all the brackets are confusing. The elements of the power set are sets. So the elements of the power set have elements! (Except for $$\{ \}$$, which has no elements.) This takes some getting used to. For example, $$a$$ is not an element of $$P(\mathscr{S})$$, but $$\{a\}$$ is.

In this finite example, the power set is certainly bigger than the original set. The set $$\{a,b,c\}$$ has size three. But its power set has size eight. In fact, for any finite set of size $$n$$, the power set will have size $$2^n$$.

But we want to talk about infinite sets. Suppose now that $$\mathscr{S}$$ is some infinite set. We can build $$P(\mathscr{S})$$, its power set, whose elements are all the subsets of $$\mathscr{S}$$. I'm claiming that $$| P(\mathscr{S})| > | \mathscr{S}|$$.

Everything in $$\mathscr{S}$$ appears in $$P(\mathscr{S})$$, as a singleton set. In our finite example, $$a$$ and $$b$$ and $$c$$ in $$\mathscr{S}$$ appeared as $$\{a\}$$ and $$\{b\}$$ and $$\{c\}$$ in $$P(\mathscr{S})$$. So it seems intuitively clear that $$| P(\mathscr{S})|$$ should be at least as big as $$|\mathscr{S}|$$. But $$P(\mathscr{S})$$ has a lot of other subsets, besides the singleton sets.

So we want to show now that $$|\mathscr{S}|$$ and $$| P(\mathscr{S})|$$ are not the same size. In other words, we want to show that there is no one-to-one correspondence between $$\mathscr{S}$$ and $$P(\mathscr{S})$$.

It's possible to do this, but the details are quite tricky. If you're curious you can read about them in the In-Depth explanation.

Basically, we show that any assignment of elements of $$\mathscr{S}$$ to elements of $$P(\mathscr{S})$$ -- that is, any rule that assigns an element of $$\mathscr{S}$$ to a subset of $$\mathscr{S}$$ -- will always fail to hit everything in $$P(\mathscr{S})$$. More specifically, given any such assignment, we can explicitly find a subset of $$\mathscr{S}$$ -- i.e. an element of $$P(\mathscr{S})$$ -- that doesn't get anything assigned to it.

There are just too many elements in $$P(\mathscr{S})$$. Thus it's not possible to construct a one-to-one correspondence, and we conclude that $$| P(\mathscr{S})|$$ is bigger than $$|\mathscr{S}|$$.

Top