カントールの定理証明
証明
もし$X=\emptyset$ならば、 $$ \operatorname{card}(X)=0 \\ \operatorname{card}(\mathscr{P} (X))=1 $$ 従って$\operatorname{card}(X)<\operatorname{card}(\mathscr{P} (X))$。一方で$X \ne \emptyset$であれば、$X$とその冪集合の間には関数が存在するだろう。集合$X$の要素$x$に対して$g(x):={x}$として定義された$g : X \to \mathscr{P} (X)$は単射である。そして、 $$ X \sim g(X)={{x} ,|, x\in X} \\ {{x} ,|, x\in X}\subset \mathscr{P} (X) $$ 従って$\operatorname{card}(X)\le \operatorname{card}(\mathscr{P} (X))$。ここで$\operatorname{card}(X) \ne \operatorname{card}(\mathscr{P} (X)) $を示せば、望む結果を得る。背理法を使うために、一対一の対応$f : X \sim \mathscr{P} (X)$が存在すると仮定してみよう。
集合$S={x\in X ,|, x\notin f(x)}$について考えると、$S$は$X$の部分集合$f(x)$が$x$を含まない場合の$x$をすべて集めた集合である。確かなのは$S\subset X$、つまり$S\in \mathscr{P} (X)$である。$f$の定義により$f : X \sim \mathscr{P} (X)$であり、$S$の定義により$S\in \mathscr{P} (X)$であるから、$f(e)=S$を満たす何らかの要素$e \in X$が存在しなければならない。この時、$e \in S, e\notin S$の2つのケースを検討する。
- ケース1. $e\in S$
- 集合$S$の定義により$e\notin f(e)$であるが、$f(e)=S$より$e\notin f(e)=S$、つまり$e\notin S$である。
- ケース2. $e\notin S$
- $S=f(e)$であるから、$e\notin S=f(e)$、つまり$e\notin f(e)$であるが、集合$S$の定義により$e\in S$は矛盾するので、一対一の対応$f$は存在しない。したがって、$\operatorname{card}(X) \neq \operatorname{card}(\mathscr{P} (X))$であり、結果として $$ \operatorname{card}(X)<\operatorname{card}(\mathscr{P} (X)) $$
■