2016/01/18

ベルンシュタインの定理とその証明

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

ベルンシュタインの定理:
集合 $A,B$ について,$A$ から $B$ への単射があり,$B$ から $A$ への単射があれば $A$ から $B$ への全単射(一対一対応)がある。

ベルンシュタインの定理について

関数 $f(x)$ が単射とは,$x\neq y$ なら $f(x)\neq f(y)$ であることを意味します。→全射と単射

$A,B$ が有限集合の場合はベルンシュタインの定理は当たり前です。実際,$A$ から $B$ への単射があるとき,要素数の間に $|A|\leq |B|$ が成立します。また,$B$ から $A$ への単射があるとき,$|A|\geq |B|$ が成立します。よって,$|A|=|B|$ となります。

$A$,$B$ が無限集合の場合が非自明で面白いです。ベルンシュタインの定理を集合の濃度の言葉で表現すると,(無限集合に対しても)
「$|A|\leq |B|$ かつ $|B|\leq |A|$ なら $|A|=|B|$ が成立する」
となります。

応用例

実際に全単射を構成しなくても,全単射の存在を証明できます!

例題

開区間 $(0,1)$ と閉区間 $[0,1]$ の間に全単射が存在することを証明せよ。

解答

開区間から閉区間への単射は,$f(x)=x$ とすればよい。
閉区間から開区間への単射は,例えば $g(x)=\dfrac{x}{2}+0.1$ とすればよい。
よって,ベルンシュタインの定理により題意は示された。

なお,この例題の結果は,カントール集合の濃度が実数の濃度と同じことの証明に使います。カントール集合とその性質

ベルンシュタインの定理の証明

英語版Wikipedia:Schröder–Bernstein theorem の証明を参考にしました。少し表現を緩くしています。

証明

記述の都合上,$A$ と $B$ が共通の要素をもたない場合について証明する(このようにしても一般性を失わない)。
$A$ から $B$ への単射を $f$,$B$ から $A$ への単射を $g$ とする。

$A\cup B$ を「$f$ または $g$ を何回かかましてうつるものは仲間」という基準でグループ分けする(図参照)。

ベルンシュタインの定理の図

$f,g$ はともに単射なので,図において,各頂点から辺は高々2本しか出ていない。よって,1つのグループには1つのパス(長さは無限)またはサイクルが対応する。以下では、$A$ から $B$ への全単射を,各グループごとに構成する。

  • パスの片方の端点が $A$ に属するグループ(図の一番上のようなグループ)
    $f$ を使えばよい。
  • パスの片方の端点が $B$ に属するグループ(図の上から2番目のようなグループ)
    $g^{-1}$ を使えばよい。
  • パスが両側に無限に続くグループ
    $f$ または $g^{-1}$ を使えばよい。
  • サイクルに対応するグループ(図の一番下のようなグループ)
    $f$ または $g^{-1}$ を使えばよい。
最初見たときはあまりピンとこない定理でしたが,じっくり考えてみるとなかなか味わい深いです。
分野: 集合,命題,論証  レベル: 大学数学