2015/11/15

カントールの定理の証明と対角線論法

分野: 集合,命題,論証  レベル: 大学数学

カントールの定理:
任意の集合 $A$ に対して,$|A| < |2^A|$

カントールの定理の意味

$|A|$ は集合 $A$ の濃度(→集合の濃度と可算無限・非可算無限)です。 $A$ が有限集合のとき $|A|$ は $A$ の要素数を表します。

$2^A$ は $A$ のべき集合(部分集合全体の集合)です。例えば $A=\{1,2\}$ のとき,$2^A=\{\phi,\{1\},\{2\},\{1,2\}\}$ です。

カントールの定理は,べき集合はもとの集合よりも(濃度の意味で)真に大きいと主張しています。直感的には当たり前に思えますが,きちんと証明すべき定理です。証明はけっこう面白いです。

$A$ が有限集合の場合

$A$ が有限集合の場合は簡単です。 $|A|=n$ とすると,$|2^A|=2^n$ となります(それぞれの要素を入れるか入れないかで $2^n$ 通りの部分集合が考えられる)。

任意の非負整数 $n$ に対して $n< 2^n$ なのでカントールの定理が成立します。

$A$ が無限集合の場合

$A$ が無限集合の場合,濃度の大小関係を示すには全単射(1対1対応)が存在しないことを言わなければいけません。

証明

まず,$A$ の要素 $a$ が与えられたときに,集合 $\{a\}$ を対応させる写像を考えると,これは単射である,よって $|A|\leq |2^A|$

あとは,$|A|\neq |2^A|$ であること,つまり $A$ と $2^A$ の間に全単射が存在しないことを言えばよい。これを背理法で証明する。全単射 $f$ が存在すると仮定する。

このとき,$a\not\in f(a)$ となる $A$ の要素 $a$ を全て集めた集合を $B$ とする。ここで,$f$ は全単射なので,ある $b\in A$ が存在して,$f(b)=B$ となる。

  • $b\in B$ のとき,$B$ の定義より $b\not\in f(b)$ だが,$f(b)=B$ なので $b\not\in B$ となり矛盾。
  • $b\not \in B$ のとき,$B$ の定義より $b\in f(b)$ だが,$f(b)=B$ なので $b\in B$ となり矛盾。

対角線論法

$B=\{a\mid a\not\in f(a)\}$ という集合を用いた上記のような証明手法を対角線論法と言います。上の証明を以下のように言い換えると「対角線論法」と呼ばれることが納得できるでしょう。

証明(言い換え)

対角線論法のイメージ

全単射 $f$ が存在すると仮定する。

各行、各列がそれぞれ $A$ の要素に対応した(無限のサイズの)行列を考える。行が $a$,列が $a’$に対応する部分には $a’\in f(a)$ なら $1$ を格納し,そうでないなら $0$ を格納する。

対角成分の $0$ と $1$ とを反転させたものを並べたベクトルに対応する集合を $B$ とする。すると,$B$ は行列のどの行とも一致しないので $f$ が全単射であることに矛盾。

このあたりの話題は闇が深そうですが,ちゃんと読むと実は簡単ということもよくあります。
分野: 集合,命題,論証  レベル: 大学数学