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

更新日時 2021/03/07
カントールの定理

任意の集合 AA に対して,A<2A|A| < |2^A|

目次
  • カントールの定理の意味

  • AA が有限集合の場合

  • AA が無限集合の場合

  • 対角線論法

  • 実数が多いことの証明

カントールの定理の意味

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

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

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

AA が有限集合の場合

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

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

AA が無限集合の場合

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

証明

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

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

このとき,a∉f(a)a\not\in f(a) となる AA の要素 aa を全て集めた集合を BB とする。ここで,ff は全射なので,行き先が BB となるものが存在する。つまり,ある bAb\in A が存在して,f(b)=Bf(b)=B となる。

  • bBb\in B のとき,BB の定義より b∉f(b)b\not\in f(b) である。f(b)=Bf(b)=B と合わせて b∉Bb\not\in B となり矛盾。

  • b∉Bb\not \in B のとき,BB の定義より bf(b)b\in f(b) である。f(b)=Bf(b)=B と合わせて bBb\in B となり矛盾。

対角線論法

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

ポイントは「対角成分を並べてひっくり返すとどれとも一致しない」です。

証明(言い換え)

対角線論法のイメージ

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

各行,各列がそれぞれ AA の要素に対応した(無限のサイズの)行列を考える。行が aa,列が aa' に対応する部分には af(a)a'\in f(a) なら 11 を格納し,そうでないなら 00 を格納する。

対角成分の 0011 とを反転させたものを並べたベクトル Bundefined\overrightarrow{B} に対応する集合を BB とする。すると,Bundefined\overrightarrow{B} は行列のどの行とも一致しないので,いかなる aAa\in A に対しても f(a)Bf(a)\neq B である。

一方,背理法の仮定より,ffAA から 2A2^A への全単射なので f(b)=Bf(b)=B となる bAb\in A が存在しなくてはならない。

これは矛盾である。よって,背理法により全単射が存在しないことが証明された。

実数が多いことの証明

対角線論法の例をもう1つ紹介します。さきほどと同じく,ポイントは「対角成分を並べてズラすとどれとも一致しない」です。

定理

Q<R|\mathbb{Q}|<|\mathbb{R}|

つまり,実数全体の集合の濃度は有理数全体の集合の濃度より真に大きい。

Q=N|\mathbb{Q}|=|\mathbb{N}|R=(0,1]|\mathbb{R}|=|(0,1]| より,N<(0,1]\mathbb{N}<|(0,1]| を示せば十分です。

証明の概要

N<(0,1]\mathbb{N}<|(0,1]| を示す。つまり「正の整数全体」から「00 より大きく 11 以下の実数全体」への全単射 ff が存在すると仮定して矛盾を示す。

「各 nn について f(n)f(n) の小数第 nn 位が偶数なら 11,奇数なら 22 としてできる実数」を xx とする。例えば,

  • f(1)=0.123f(1)=0.123\cdots
  • f(2)=0.345f(2)=0.345\cdots
  • f(3)=0.789f(3)=0.789\cdots
  • \vdots

のように,f(1)f(1) から順番に無限小数の形で並べて(→補足),対角成分 1,4,91,4,9 の偶奇を見て x=0.212x=0.212\cdots とする。これはすべての f(n)f(n) と異なるので ff は全射にならない!

補足:例えば,f(1)=1f(1)=1 なら f(1)=0.9999999f(1)=0.9999999\dots のように無限小数の形で書きます。無限小数の形で書く方法はただ1つであることが知られており,本証明ではそれを前提としています(無限小数展開の一意性。有限桁以降すべて 00 が並ぶものは「有限小数」と考えて「無限小数」とは考えない立場です)。

また,Q<R|\mathbb{Q}|<|\mathbb{R}| を示す方法は他にもあります。例えば,2N|2^{\mathbb{N}}|R|\mathbb{R}| の間の全単射を構成することができます。

このあたりの話題は闇が深そうですが,ちゃんと読むと実は簡単ということもよくあります。