カントールの定理の証明

定義

集合 $E$ について、$E$ と $2^E$ の間に全単射関数が存在しない。

これは、どの集合もその冪集合と等势ではないことを意味しています。しかし、それだけではありません。詳しくは、カントールの定理に関するWikipediaページ（セクション：「定理の帰結」）をご覧ください。

証明

この定理を証明するために、背理法によって論じましょう：

全単射関数である $f : E \rightarrow 2^E$ を考える。

$X := \{e \in E : e \notin f(e) \}$ と置く。

$X$ は $E$ の部分集合（= $2^E$ の要素）であり、$f$ による自身の像に属さない $E$ の要素の集合として定義されます。
なぜこの $X$ を取るのかを理解するために、例を考えてみましょう：$E = \{a,b,c\}$ で、$f(a) = \{a,b\}$ 、$f(b) = \{\}$、$f(c)=\{a\}$ の場合、$X =\{b,c\}$ となり、$X$ は $E$ の部分集合でありながら、$f$ による先行要素を持ちません。カントールの対角線論法を参照してください 2

$\exists y \in E$ なので、$f(y) = X$ です。

$E$ から $2^E$ への関数 $f$ が全射であるとは、$2^E$ の任意の要素 $y$ に対して、少なくとも1つの $E$ の要素 $e$ が存在し、$f(e) = y$ となる場合を言います。形式的には、$\forall y \in 2^E \ \exists e \in E ; f(e)=y$ となります。$2^E$ の要素である $X$ は、$f$ が全射であるため、$f$ による先行要素 $y$ を持たなければなりません。

2つのケースがあります：

もし $y \in X$ ならば、$X$ の定義により、$y \notin f(y)$ です。したがって、$y \notin X$ となり、これは矛盾しています。
もし $y \notin X$ ならば、$X$ の定義により、$y \in \bar{X}^E$ です。従って、$y \in f(y)$ なので、$y \in X$ となり、これもまた矛盾しています。

$X$ は $2^E$ の要素でありながら、$f$ による先行要素を持ちません。したがって、$f$ は全射でも単射でもありません。これによりカントールの定理が成立します。

補足

カントールの定理は、以下のようにも表現できます：任意の集合 $E$ に対して、$|E| < |2^E|$ です。これは、上述の全射の不存在（証明された）と単射関数 $f(x)=\{x\}$ の存在により自然に証明されます。

例えば、$E = \{a,b\}$ の場合、$2^E = \{\{\},\{a\},\{b\},\{a,b\}\}$ で、$a$ は $\{a\}$ に、$b$ は $\{b\}$ に対応しています。