Definition of cardinalities

• $|S| \leq |T|$ if there exists an injective function $f:S\to T$
• $|S| < |T|$ if $|S| \leq |T|$ and $|S| \neq |T|$, i.e. there is an injective function but not a bijective function.

Lemma 1: If $S$ is a set, then there’s an injection $f:S \to \wp(S)$.

Sketch of proof: basically, use the function $f(x)= \{x \}$.

Lemma 2: If $f:S \to \wp(S)$ is a function, then $f$ is not bijective.

Sketch of proof: show it’s not surjective, using diagonalization to find the set $D$ such that $f(a) \neq D$ for all $a \in S.$ $D=\{x \in S~|~x \notin f(x)\}.$

Proof: Let $S$ be an arbitrary set. We will prove that $|S| \neq |\wp(S)|$ by showing there are no bijections from $S$ to $\wp(S).$ To do so, consider an arbitrary function $f:S \to \wp(S).$ We will prove that $f$ is not surjective.

Starting with $f$, we define the set $D=\{x \in S~|~ x \notin f(x)\}.$ We will show that there is no $y \in S$ such that $f(y)=D.$ To do so, we proceed by contradiction. Suppose that there is some $y \in S$ such that $f(y)=D.$ From the definition of $D$, we know that

$$ y \in D \text{ if and only if } y \not \in f(y). $$

Since we know that $f(y)=D$, the above statement means that

$$ y \in D \text{ if and only if } y \not \in D. $$

We’ve reached a contradiction, so our assumption must have been wrong. Therefore, there is no $y \in S$ such that $f(y) \in D$, so $f$ is not surjective. $\blacksquare$