RPRobin Pourtaud東京 · 水辺の近く
流れに戻る
数学1 分で読めます

カントールの定理の証明

この記事ではカントールの定理とその証明を紹介します。

ENFR日本語

定義

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

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

証明

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

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

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

XX は EE の部分集合（= 2E2^E の要素）であり、ff による自身の像に属さない EE の要素の集合として定義されます。

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

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

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

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

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

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

補足

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

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