1. 高校数学の美しい物語
  2. ベルンシュタインの定理とその証明

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

更新日時 2021/03/07
ベルンシュタインの定理

集合 A,BA,B について,AA から BB への単射があり,BB から AA への単射があれば AA から BB への全単射(一対一対応)がある。

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

  • 応用例

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

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

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

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

また,BB から AA への単射があるとき,AB|A|\geq |B| が成立します。よって,A=B|A|=|B| となります。

AABB が無限集合の場合が非自明で面白いです。ベルンシュタインの定理を集合の濃度の言葉で表現すると,(無限集合に対しても)

AB|A|\leq |B| かつ BA|B|\leq |A| なら A=B|A|=|B| が成立する」

となります。

応用例

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

例題

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

解答

開区間から閉区間への単射は,f(x)=xf(x)=x とすればよい。

閉区間から開区間への単射は,例えば g(x)=x2+0.1g(x)=\dfrac{x}{2}+0.1 とすればよい。

よって,ベルンシュタインの定理により題意は示された。

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

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

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

証明

記述の都合上,AABB が共通の要素をもたない場合について証明する(このようにしても一般性を失わない)。

AA から BB への単射を ffBB から AA への単射を gg とする。

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

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

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

  • パスの片方の端点が AA に属するグループ(図の一番上のようなグループ)ff を使えばよい。

  • パスの片方の端点が BB に属するグループ(図の上から2番目のようなグループ)g1g^{-1} を使えばよい。

  • パスが両側に無限に続くグループ ff または g1g^{-1} を使えばよい。

  • サイクルに対応するグループ(図の一番下のようなグループ)ff または g1g^{-1} を使えばよい。

最初見たときはあまりピンとこない定理でしたが,じっくり考えてみるとなかなか味わい深いです。

人気記事
  1. 高校数学の美しい物語
  2. ベルンシュタインの定理とその証明