単射が両向きにあれば全単射が作れる - ベルンシュタインの定理

$[0,1]$ から $[0,1)$ への単射は $x\mapsto \frac{x}{2}$ で作れます。逆向きの単射は、そのまま入れるだけ。

両向きに単射があるとき、全単射も必ず作れます^[1]。カントール・シュレーダー・ベルンシュタインの定理です。作り方まで具体的に決まる。

主張

集合 $A$ から $B$ への単射と、$B$ から $A$ への単射が両方あるとします^[2]。このとき次が成り立ちます。

$$|A|\le |B|\wedge |B|\le |A|⟹|A|=|B|$$

濃度の言葉で書くと、$\le$ の反対称性そのものになります。有限集合なら鳩の巣原理で片づく話が、無限集合でも成り立つ。

証明は少しも自明ではありません。単射 $2$ 本から全単射 $1$ 本をどう組み立てるかが問題になる。

例：閉区間と半開区間

$A=[0,1]$、$B=[0,1)$ とします^[1]。$f(x)=\frac{x}{2}$ と、包含写像 $g(x)=x$ をとる。

答えの全単射は次の形になります。動くのは可算個の点だけ。

$$C=\left\{1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\dots \right\}$$

$C$ の点は半分の位置へずらし、それ以外は動かさない。これで $[0,1]$ が $[0,1)$ へちょうど移ります。

$1$ の行き先が $\frac{1}{2}$ になり、$\frac{1}{2}$ の行き先が $\frac{1}{4}$ になる。順に押し出して、$1$ の抜けたぶんを埋めます。

集合列による証明

一般の場合も同じ発想で進みます^[1,3]。単射 $f:A\to B$ と $g:B\to A$ から、$A$ の部分集合の列を作る。

$$C_0=A\setminus g(B),C_{n+1}=g(f(C_n))$$

$C_0$ は「$g$ で $B$ から来られない点」の集まりです。ここから $f$ と $g$ を交互に当てて、行き先をたどる。

全部の和を $C={\bigcup }_{n\ge 0}{C}_n$ とおきます。答えの全単射はこう決まる。

$$h(x)=f(x)(x\in C),h(x)=g^{-1}(x)(x\notin C)$$

なぜうまく定まるのか

$x\notin C$ のとき $g^{-1}(x)$ が使えるのは、$x\notin C_0$ だからです。$C_0$ の外は $g(B)$ に入っているので、逆像が $1$ 点に決まる。

単射性を見ます。$C$ の中どうしなら $f$ が単射、外どうしなら $g^{-1}$ が単射。問題は $x\in C$、$y\notin C$ で $f(x)=g^{-1}(y)$ となる場合です。

このとき $y=g(f(x))$ で、$x\in C_n$ なら $y\in C_{n+1}\subseteq C$ になる。$y\notin C$ に反します。

全射性も同じ形で出ます。$b\in B$ をとり、$g(b)\in C$ かどうかで場合を分ける。入っていれば $g(b)\in C_{n+1}$ で $b\in f(C_n)$、入っていなければ $h(g(b))=b$ です。

鎖による証明

ケーニヒが $1906$ 年に与えた別証明があります^[1]。要素を $1$ つとり、$f$ と $g$ を前後にたどって両側の列を作る。

$$\cdots \to g^{-1}(a)\to a\to f(a)\to g(f(a))\to \cdots$$

$f$ と $g$ が単射なので、この列は要素ごとに $1$ 本に決まります。$A\cup B$ が鎖に分割される。

鎖は $4$ 種類しかありません。左端が $A$ で止まるもの、$B$ で止まるもの、両側に無限に伸びるもの、輪になるもの。

$A$ で止まる鎖では $f$ を使い、$B$ で止まる鎖では $g$ の逆を使う。両側無限と輪では、どちらを選んでも鎖の中で $1$ 対 $1$ になります。

鎖ごとに決めた対応をつなげば、$A$ 全体から $B$ 全体への全単射が完成します。

選択公理は要らない

無限の話なので選択公理が要りそうに見えますが、要りません^[2,3]。

上の $2$ つの証明はどちらも、選ぶ場面を持たない。$C_n$ も鎖も、$f$ と $g$ から一意に決まります。

デデキントが $1887$ 年に、ベルンシュタインが $1898$ 年の学位論文で、それぞれ選択公理なしの証明を与えました^[2]。

排中律は使います。プラディックとブラウンが $2019$ 年に、直観主義集合論ではこの定理から排中律が導けることを示しました^[3]。

名前が長い理由

この定理の名前は、発見の経緯がそのまま残ったものです^[1,3]。

カントール・ベルンシュタイン、シュレーダー・ベルンシュタイン、カントール・シュレーダー・ベルンシュタイン。呼び方が $3$ 通りあるのは、この事情によります。

例：実数とベキ集合

$\mathbb{R}$ と $\mathcal{P}(\mathbb{N})$ の濃度が等しいことを、この定理で示せます。

$\mathcal{P}(\mathbb{N})\to \mathbb{R}$ の単射は、部分集合を $0$ と $1$ の列と見て $3$ 進小数にすれば作れる。$3$ 進にするのは、桁の重複を避けるためです。

逆向きは、実数を $2$ 進小数にして $1$ が立つ桁の集合を返せばよい。両向きに単射があるので、全単射があります。

具体的な全単射を書き下すのは面倒です。存在だけなら、この定理で片づく。

例：直線と平面

$\mathbb{R}$ と ${\mathbb{R}}^2$ も同じ濃度になります。

$\mathbb{R}\to {\mathbb{R}}^2$ は $x\mapsto (x,0)$ で単射。逆向きは、$2$ つの小数の桁を交互に並べて $1$ つの実数にする。

桁の並べ方には注意が要ります。$0.4999\dots$ と $0.5000\dots$ のような重複表示を片方に固定しないと、単射になりません。

単射さえ作れれば、あとは定理にまかせられる。全単射を直接構成する必要がありません。

例：有限集合では鳩の巣

有限集合なら、この定理は鳩の巣原理から出ます。$|A|\le |B|$ と $|B|\le |A|$ から $|A|=|B|$ になり、単射は自動的に全射です。

無限集合ではこの推論が通りません。$\mathbb{N}$ から偶数全体への $n\mapsto 2n$ は単射ですが、全射ではない。

真部分集合と全体が同じ濃度になりうる。これが無限集合の特徴で、デデキントはこの性質を無限の定義に採用しました。

濃度の比較可能性は別の話

この定理は、濃度の順序 $\le$ の反対称性を主張します。任意の $2$ つが比較できることは主張しません^[2]。

どの $2$ 集合についても $|A|\le |B|$ か $|B|\le |A|$ が成り立つ、という主張は三分律と呼ばれます。こちらは選択公理と同値です。

比較可能性まで含めて濃度が全順序になるのは、選択公理を認めたあとの話です。定理の主張はそこまで踏みこんでいません。

よくある誤り

両向きの単射を作るだけで、全単射の存在が言える。濃度の議論で最初に手が届く道具になります。

参考文献

^[1] が $2$ つの証明と閉区間の具体例、^[2] が歴史と選択公理をめぐる整理、^[3] が不動点定理を使う別証明と直観主義論理での位置づけ、^[4] が濃度の比較と可算性の基本事項です。