Exercise 1560Logic, sets and proofs › Countability and cardinalityL1Added 3 Nov 2026

Cantor's theorem

#Cantor theorem#power set#larger cardinality

Statement

Prove $|A|<|\mathcal{P}(A)|$ for any set $A$ .

Hint

Suppose $f:A\to\mathcal{P}(A)$ is a surjection, consider $S=\{x\in A:x\notin f(x)\}$ .

Show solutionHide solution

Solution

Injection. $a\mapsto\{a\}$ injects $A$ into $\mathcal{P}(A)$ .

No surjection. If $f$ surjective, let $S=\{x\in A:x\notin f(x)\}$ . Since $f$ surjective, $S=f(a)$ for some $a$ . Then $a\in S\iff a\notin f(a)=S$ , contradiction.

Conclusion. $|A|<|\mathcal{P}(A)|$ ; power sets strictly increase cardinality.

Cantor's theorem

Statement

Solution

More problems in Countability and cardinality