Cantor ( カントール ) の定理

べき集合の定義と例、カントールの定理と証明を紹介する。

定義(べき集合)

定義
Xを集合とする。

Xのすべての部分集合の集合を2Xで表す。

べき集合の例:

X={a,b,c}のとき,

Xの部分集合は、

∅, {a},{b},{c},{a,b},{b,c},{c,a},{a,b,c}の8個ですべてである。

よって、2X= {∅,{a},{b},{c},{a,b},{b,c},{c,a},{a,b,c}}である。

Cantor(カントール)の定理

Cantor(カントール)の定理
Aを集合とする。

cardA<card2A

カントールの定理の証明

方針

カントールの定理を証明するために、背理法を用いる。

cardA≧card2Aと仮定し、矛盾を導けばよい。

証明

cardA≧card2Aと仮定する。

すなわち、単射f:2A→Aが存在する。

X={f(C)∈A|C∈2A,f(C)∉C}と定義すると,

XはAの部分集合である。(i.e.X⊂A)

すなわち、X∈2A.

fは2AからAへの写像で、X⊂Aであるから,

f(X)∈Xまたは,f(X)∈Xcでなければならない。(※)

(i)

f(X)∈Xcとすると、f(X)∉Xで、X∈2Aである。

これは、Xの定義を満たしているということなので、

f(X)∈X.これはf(X)∈Xcに矛盾する。

(ii)

f(X)∈Xとすると、Xの定義より、

C∈2A,f(C)∉ C,f(C)=f(X)となるC∈2Aが存在する。

fは単射だから、C=X.よって,f(X)∉X.

これはf(X)∈Xに矛盾する。

(i)と(ii)より、f(X)はf(X)∈Xcでもf(X)∈Xでもないということになる。

これは,(※)に矛盾する。

よって、cardA<card2A.

これが、カントールの定理の内容であった。