カントールの定理

背理法で示す。
すなわち、$g:X\to 2^X$ が全射であると仮定する。

ここで、$B\in 2^X$ を
$$\begin{array}{rl}B& =\{x\in X|x\notin g(x)\}\end{array}$$
と定義する。

いま、$g$ は全射であるので、$\mathrm{\exists }x\in X,g(x)=B$ となる。

もしも、$x\notin B$ とすると、$B$ の定義より　$x\in g(x)$ であり、$g(x)=B$ であることより、$x\in B$ となり矛盾する。

さらに、$x\in B$ とすると、同様に $B$ の定義より $x\notin g(x)=B$ となり、矛盾する。

どちらの場合も矛盾が生じる。

従って、$X$ から $2^X$ への全射は存在しない。