📂集合論

カントールの定理証明

証明

もし$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))$$

■