Cantorの定理
定理1. Cantorの定理
任意の集合 \(S\) について
\[|S|\lt |2^S|\]証明
定理1の証明
背理法によって示す.
ある集合 \(S\) について全射 \(f:S\rightarrow 2^S\) が存在すると仮定する.
\[Y\triangleq\{x\in S\ |\ x\notin f(x)\}\in 2^S\]とすると, 全射 \(f\) の定義より
\[\exists x\in S\quad(Y=f(x))\] \[\exists x\in S\quad\forall a\in S\quad(a\in Y\leftrightarrow a\in f(x))\]これは \(Y\) の定義に矛盾し, 定理は示された.