Bigger sets

The material from now on is starred. Recall that two sets $S$ and $T$ have the same cardinality ( $\lvert S\rvert = \lvert T\rvert$) if, and only if, there is a bijection between $S$ and $T$. One can show (the Schröder-Bernstein theorem) that if there is an injection from $S$ to $T$ and an injection from $T$ to $S$ then there is a bijection between $S$ and $T$. For any set $S$, there is an injection from $S$ to $\mathcal{P}(S)$, simply $x \mapsto \{ x \}$. However there is never a surjection $S \mapsto \mathcal{P}(S)$, so $\lvert S\rvert < \lvert\mathcal{P}(S)\rvert$, and so

$$\lvert\mathbb{N}\rvert < \lvert\mathcal{P}(\mathbb{N})\rvert < \lvert\mathcal{P}(\mathcal{P}(\mathbb{N}))\rvert < \dots$$

for some sensible meaning of $<$.

Theorem 7.4.1   There is no surjection $S \longrightarrow \mathcal{P}(S)$.

Proof. Let $f: \; S \longrightarrow \mathcal{P}(S)$ be a surjection and consider $X \in P(S)$ defined by $\{ x \in S : x \notin f(x) \}$. Now $\exists x' \in S$ such that $f(x') = X$. If $x' \in X$ then $x' \notin f(x')$ but $f(x') = X$ -- a contradiction. But if $x' \notin X$ then $x' \notin f(x')$ and $x' \in X$ -- giving a contradiction either way. $\qedsymbol$

If there is an

injection

surjection

$f: \; A \longrightarrow B$ then there exists a

surjection

injection

$g: \; B \longrightarrow A$. Moreover we can ensure that

$g \circ f = \iota_A$

$f \circ g = \iota_B$