We can make a one-to-one correspondence between \(\mathscr{S}\) and the set of singleton subsets of \(\mathscr{S}\); each element \(s\) of \(\mathscr{S}\) gets assigned to the singleton \(\{s\}\). This is a valid one-to-one correspondence, between \(\mathscr{S}\) and a subset of \(P(\mathscr{S})\). So we know that \(\mathscr{S}\) has to be no larger than \(P(\mathscr{S})\).

**Next we will show that \(P(\mathscr{S})\) is not the same size as \(\mathscr{S}\), and this will be enough to conclude that \(| P(\mathscr{S})| > |\mathscr{S}|\).**

To show \(\mathscr{S}\) and \(P(\mathscr{S})\) are not the same size, we must show that there can be no one-to-one correspondence between them. Here it's helpful to think of assignments between sets as functions.

**What we will show is that any function \(f\) from \(\mathscr{S}\) to \(P(\mathscr{S})\) fails to hit everything.** In other words, given a function \(f\), we'll show that we can construct a special subset \(Y\) of \(\mathscr{S}\) in such a way that we are sure no element of \(\mathscr{S}\) gets assigned to \(Y\) by \(f\).

So now suppose we have a function \(f\) from \(\mathscr{S}\) to \(P(\mathscr{S})\). Consider the following subset of \(\mathscr{S}\), i.e. element of \(P(\mathscr{S})\).

\(Y= \{\) elements \(s\) in \(\mathscr{S}\), such that \(s\) is not an element of \(f(s) \}\)

This may seem like an odd way to define a subset, describing it in words. But it is perfectly acceptable (at least in this basic version of set theory we are using). The words clearly give a condition for deciding what elements of \(\mathscr{S}\) should be included in \(Y\). Mathematicians do this all the time. For example, we could describe the set of even natural numbers as

\(2\mathbb{N} = \{\) all natural numbers that are divisible by two\( \}\).

What did we just conclude? **For each element \(s\) in \(\mathscr{S}\), the sets \(f(s)\) and \(Y\) are not the same.** Now, thinking of \(f\) as a function from \(\mathscr{S}\) to \(P(\mathscr{S})\), this says that there is no element of \(\mathscr{S}\) getting assigned to \(Y\)! **The set \(Y\) is the special element of \(P(\mathscr{S})\) that is not -- cannot -- be hit by the function \(f\).**

This trick works for any function from \(\mathscr{S}\) to \(P(\mathscr{S})\). We can always construct a special element of \(P(\mathscr{S})\) that does not get hit by the function. **The conclusion is that any function from \(\mathscr{S}\) to \(P(\mathscr{S})\) will fail to be a one-to-one correspondence; there can be no one-to-one correspondence between \(\mathscr{S}\) and \(P(\mathscr{S})\); and so \(\mathscr{S}\) is strictly smaller than \(P(\mathscr{S})\).**