next up previous contents
Next: Induction and Counting Up: Countability Previous: Countable sets   Contents

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

$\displaystyle \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$

next up previous contents
Next: Induction and Counting Up: Countability Previous: Countable sets   Contents
root 2002-06-10