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}|\).

You can read a short explanation of why \(|P(\mathscr{S})| > |\mathscr{S}|\), or an in-depth explanation (a rigorous proof), or you can take our word for it, and go read the story or the meta-discussion.

Short Version Meta Discussion In-Depth Version True Story

Short

NEXT