Cantor ( カントール ) の定理

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

定義（べき集合）

Xを集合とする。

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

べき集合の例：

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

Xの部分集合は、

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

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

Cantor(カントール)の定理

Aを集合とする。

cardA＜card2^A

カントールの定理の証明

方針：

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

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

証明：

cardA≧card2^Aと仮定する。

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

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

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

すなわち、X∈2^A.

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

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

(i)

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

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

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

(ii)

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

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

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

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

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

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

よって、cardA＜card2^A.

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