This article has been written by ロビン・ポルト ([email protected]) and published on December 1, 2023.
The content of this article is licensed under CC BY
NC 4.0 : You can freely share and adapt the content for non-commercial purposes as long as you give
appropriate credit and provide a link to the license. In my case, the link to the original article is enough.
Confidentiality if relevant: https://devmath.fr/page/confidentialite/
定義
集合 $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\}$ に対応しています。