Lesson 4

The next theorem will help us establish that, roughly speaking, there are infinitely many different infinite cardinalities.

Theorem (Cantor, 1891). No set is in bijection with the set of its subsets.

Proof. Suppose the contrary: \(\phi \colon X \to 2^{X}\) is such a bijection. Let \(Z = \{x \in X \colon x \notin \phi(x)\}\) and suppose \(Z = \phi(z)\) for some \(z \in X\). Then \[z \in Z \Leftrightarrow z \notin \phi(z) \Leftrightarrow z \notin Z \ .\]◼