> [!NOTE] **Theorem** (Cantor) > Suppose $X$ is a set and that $\mathcal{P}(X)$ is its [[Zermelo Frankel set theory (ZFC)|power set]]. If $f:X \to \mathcal{P}(X)$ is a [[Function|function]] then it is not [[Surjection|surjective]]. *Proof.* BWOC, suppose $f$ is a surjection that is, for all $A\in P(x),$ there is some $a\in X$ such that $f(a)=A.$ Consider the subset of $X$ consisting of those elements $x$ which do not lie in the subset $f(x)$ (which exists by [[Zermelo Frankel set theory (ZFC)|specification axiom]]): $C = \{ x\in X \mid x \not\in f(x) \}$Since $f$ is surjective, there exists $c\in X$ such that $f(c)=C.$ Either $c\in C$ or not: Suppose $c\in C.$ Thus, by the defining property of $C,$ we have $c \not \in f(c),$ a contradiction. Suppose $c\not \in C.$ Then $c\not \in f(c)$ since $C=f(c).$ So $c\in C$ by the defining property of $C,$ a contradiction. As both possibilities lead to contradiction, we deduce that our original assumption was incorrect. A