Solution

Prove that the cardinality of the power set of a given set is never equal to the cardinality of the set itself.



(For a metaphorical context for the below argument, consult the notes on the cardinality of the power set.)

We argue indirectly.

Suppose we assume that the cardinality of a set $S$ and its power set $P(S)$ are equal.

As such, there must exist some function $f: S \rightarrow P(S)$ which is a bijection.

Let us define the following subsets of $S$:

$$C = \{x \in S \;|\; x \in f(x) \}$$ $$H = \{x \in S \;|\; x \not\in f(x) \}$$

Note, $H$ is a subset of $S$, so it must be an element of the power set $P(S)$.

Since $f$ is a bijection, there must exist some $a \in S$ such that $f(a) = H$

Clearly, any element of $S$ must be in either $H$ or $C$, but never both. With this in mind, consider the implications for the aforementioned element $a$...

If $a \in H$, then $a \not\in f(a)$. As $f(a)=H$, this implies $a \not\in H$. Contradiction.

If $a \in C$, then $a \in f(a)$. As $f(a) = H$, this implies $a \in H$, which requires $a \not\in C$. Contradiction.

So $a$ is not an element of $H$ or $C$.

However, we argued just moments before that every element of $S$ (which includes $a$) must be in one of these two sets.

This gives us the contradiction needed to reject our original assumption that the cardinality of a set $S$ and its power set $P(S)$ are equal.

It must then be the case that the cardinality of a set $S$ and its power set $P(S)$ are not equal.

QED.