Cantor-Bernstein-Schroederの定理
単射 f: X→Y と単射 g: Y→X が存在するならば， 全単射 h: X→Y が存在する．

即ち，|X|≦|Y| かつ |Y|≦|X| ならば |X|=|Y| である，ということ．この定理は選択公理を使わずに(ZFで)証明できる．

以下，この命題をCBSと書くことにする．

証明 f, gのどちらかが全射ならば明らかだから，どちらも全射でないとする．以下のように集合を定義する．

f, g が単射なので，異なる非負整数 m, n に対し X_m∩X_n = ∅, Y_m∩Y_n = ∅ である．また X = X⁺∪X^- = (∪X_n)∪X^-, Y = Y⁺∪Y^- = (∪Y_n)∪Y^- となる．

f(X⁺) = f(∪_n=0^∞ X_n) = ∪_n=1^∞ Y_n かつ f(X) = Y＼Y₀ = (∪_n=1^∞ Y_n)∪Y^- だから，f(X^-) = Y^- である．そこで h: X→Y を

x∈X_2n のとき h(x) := f(x)
x∈X_2n+1 のとき h(x) := g^-1(x)
x∈X^- のとき h(x):= f(x)

と定義すれば，これは明らかに全単射である．

この定理から，すぐに「双対版」が思いつく．

双対Cantor-Bernstein-Schroederの定理
全射 f: X→Y と全射 g: Y→X が存在するならば，全単射 h: X→Y が存在する．

この命題をCBS*で表すことにする．選択公理を使えば，CBS*はCBSから簡単に導くことができる．

つまりCBS*はZFCで証明可能．しかし，CBS*はZF(更に言えばZF+DC)で証明できないことが知られている．

藤田博司さんがそのことについて書かれています． http://www.math.sci.ehime-u.ac.jp/~fujita/notes.jp.htmlにあるPDF双対ベルンシュタイン定理についてを参照．また，ZFで「CBS*⇒選択公理」が成立するかどうかは未解決問題らしいです．

CBSでのhに条件を加えた命題を考える．

命題 単射 f: X→Y と単射 g: Y→X が存在するならば， 全単射 h: X→Y で h⊂f∪g^-1 を満たすものが存在する．

h⊂f∪g^-1 はf, g^-1, hを X×Y の部分集合とみなして考えるということ．

この命題をCBS+で表すことにする．当然これの双対版も考えられます．

命題

全射 f: X→Y と全射 g: Y→X が存在するならば，全単射 h: X→Y で h⊂f∪g^-1 を満たすものが存在する．

この命題をCBS+*で表すことにする．

CBSの証明の中で構成した全単射hは明らかに h⊂f∪g^-1 を満たす．故にCBS+はZFで証明可能である．一方CBS+*については次が成り立つ．

定理 選択公理 ⇔ CBS+*

証明 (⇒) f: X→Y と g: Y→X を全射とする．選択公理により f, g の右逆写像 u: Y→X, v: X→Y が存在する．即ち fu = id_Y, gv = id_X．このとき u^-1⊂f, v⊂g^-1 である．

単射 v: X→Y と単射 u: Y→X にCBS+を適用して 全単射 h: X→Y で h⊂v∪u^-1 を満たすものを取れば h ⊂ v∪u^-1 ⊂ f∪g^-1．

(←)全射 f: X→Y の右逆写像の存在を示す．Z := { 0 }∪Y∪(X×N)　(disjoint union) として写像 k: Z→Z を次で定める．

k(0) := 0
k(y) := 0　(y∈Y)
k(<x, 0>) := f(x)　(x∈X)
k(<x, n+1>) := <x, n>　(x∈X, n∈N)

明らかにkは全射である．そこで全射 k: Z→Z と全射 k: Z→Z にCBS+*を適用して 全単射 h: Z→Z で h⊂k∪k^-1 を満たすものを取る． 写像 h|_Y を考える．

(i) h|_Y⊂k^-1のとき
y∈Y に対し h(y)∈k^-1(y) となる． よって kh(y) = y．また，kの定義より k^-1(Y) = X×{ 0 } だから h(y)∈k^-1(y)⊂X×{0}である．故に，ある写像 g: Y→X を使って h(y)=<g(y), 0> と書ける．このとき任意のy∈Yに対し

y = kh(y) = k(<g(y), 0>) = f(g(y)) = fg(y)

即ちgはfの右逆写像．

(ii) h|_Y⊂k^-1でないとき
h⊂k∪k^-1 だからあるa∈Yが存在してh(a)=k(a)である．このときkの定義からh(a)=0となる．hは全単射だったから，実はこのようなaは唯一つしか存在しない．故に A := Y＼{ a } と置けば h|_A⊂k^-1 となる．そこでAについて(i)と同様の議論をすれば 写像 g: A→X で fg=id_A となるものが取れる．そこで元 b∈f^-1(a) を一つ取り g(a) := b として g: Y→X へ拡張すれば明らかにgがfの右逆写像である．

この←の証明では，CBS+*の「X=Yかつf=g」の場合しか使っていない．故に次のことが分かる．

系 選択公理
⇔全射 f: X→X に対し全単射 h: X→X で h⊂f∪f^-1を満たすものが存在する．