Cantor–Bernsteinの定理

同義語：Cantor–Bernstein theoremCantor-Bernsteinの定理Cantor–Schröder–Bernsteinの定理Cantor–Schröder–Bernstein theoremSchröder–Bernsteinの定理Schröder–Bernstein theorem

概要

前提知識: 単射, 全単射, 濃度

二つの集合の大きさを比べるとき、一方から他方への単射があれば「$A$ は $B$ 以下の大きさ」とみなす。この比べ方が大小関係として筋が通るためには、「$A$ は $B$ 以下で、$B$ も $A$ 以下なら、$A$ と $B$ は同じ大きさ」でなければならない。Cantor–Bernsteinの定理 は、互いへの単射があれば両者の間に全単射が実際に作れることを主張し、この要請に答える。
定理の価値は、全単射を直接書き下すのが難しい場面で、二つの単射を別々に作るだけで済ませられる点にある。たとえば閉区間 $[0,1]$ と半開区間 $[0,1)$、実数全体 $\mathbb R$ と自然数の冪集合 $\mathcal P(\mathbb N)$ は、それぞれ単射を往復させるだけで同じ大きさだと分かる。証明は選択公理を使わず、得られる全単射は与えられた二つの単射から具体的に組み立てられる。
この記事では、閉包を使う Dedekind 流の証明と、元の「親をたどる鎖」に分解する証明の二通りで定理を示し、鎖の分解から単射の往復の構造を読み取る。最後に、全単射に構造の保存まで求めると定理が成り立たないことを、順序・位相・群の例で確かめる。

定理の主張

以下ではZFC公理系から選択公理を除いた体系 $\mathsf{ZF}$ で議論する。写像 $f\colon A\to B$ と $S\subset A$ について、$f[S]:=\{f(a)\mid a\in S\}$ を $S$ の像と書く。$g\colon B\to A$ が単射のとき、$a\in g[B]$ に対して $g(b)=a$ となる $b\in B$ はただ一つであり、これを $g^{-1}(a)$ と書く。

Cantor–Bernsteinの定理

集合 $A,B$ と単射 $f\colon A\to B$、$g\colon B\to A$ が与えられたとき、全単射 $h\colon A\to B$ が存在する。さらに $h$ は、各 $a\in A$ について
$$ h(a)=f(a)\quad\text{または}\quad\bigl(a\in g[B]\text{ かつ }h(a)=g^{-1}(a)\bigr) $$
となるように選べる。証明に選択公理は使わない。

二つの証明

証明は二通り与える。「証明1：閉包による証明」の節では部分集合への単射についての補題に帰着させ、「証明2：親をたどる鎖による証明」の節では元を鎖に分けて鎖ごとに全単射を作る。

集合 $A$ から $B$ への単射があることを $|A|\le|B|$、全単射があることを $|A|=|B|$ と書くと（濃度）、定理は
$$ |A|\le|B|\ \text{かつ}\ |B|\le|A|\ \Longrightarrow\ |A|=|B| $$
と言い換えられる。単射の合成は単射なので $\le$ は反射律と推移律を満たす前順序であり（前順序の例「集合の大きさの比べ方」）、定理はこの前順序から対等で割った大小関係が反対称律を満たすこと、すなわち濃度の大小が半順序であることを保証する。
主張の後半は、$h$ が各点で「$f$ で送るか、$g$ で戻すか」のどちらかで決まることを述べている。どちらを使うかの振り分けを、選択によらず一つの集合として定義できることが証明の要点である。

証明1：閉包による証明

まず、集合とその部分集合の間の特別な場合を示す。

挟み込みの補題

$Y\subset X$ とし、単射 $\varphi\colon X\to X$ が $\varphi[X]\subset Y$ を満たすとする。このとき全単射 $k\colon X\to Y$ が存在し、各 $x\in X$ について $k(x)=\varphi(x)$ または $k(x)=x$ である。

最小の閉じた集合で振り分ける

$S\subset X$ が $\varphi$ で閉じている とは $\varphi[S]\subset S$ となることとする。$X\setminus Y$ を含み $\varphi$ で閉じた $X$ の部分集合全体を $\mathcal C$ とおく。$X\in\mathcal C$ なので $\mathcal C$ は空でなく、
$$ D:=\bigcap\mathcal C $$
は $X$ の部分集合として分出公理で作れる。$D$ は $X\setminus Y$ を含み、$\varphi$ で閉じている（$x\in D$ なら、各 $S\in\mathcal C$ について $x\in S$ から $\varphi(x)\in S$、よって $\varphi(x)\in D$）。したがって $D$ は $\mathcal C$ の最小元である。
次の主張を示す：$x\in D$ かつ $x\notin X\setminus Y$ なら $x\in\varphi[D]$。そうでないとすると、$D':=D\setminus\{x\}$ は $X\setminus Y$ を含む。また $y\in D'$ なら $\varphi(y)\in D$ であり、$x\notin\varphi[D]$ なので $\varphi(y)\neq x$、すなわち $\varphi(y)\in D'$ である。よって $D'\in\mathcal C$ となり、$D'\subsetneq D$ が $D$ の最小性に反する。
写像 $k\colon X\to X$ を
$$ k(x):=\begin{cases}\varphi(x)&(x\in D)\\ x&(x\notin D)\end{cases} $$
で定める。
値は $Y$ に入る。 $x\in D$ なら $k(x)=\varphi(x)\in\varphi[X]\subset Y$。$x\notin D$ なら $x\notin X\setminus Y$ なので $k(x)=x\in Y$。
単射である。 まず、$x\in D$、$y\notin D$ なら $k(x)\neq k(y)$ である。実際 $k(x)=\varphi(x)\in D$（$D$ は閉じている）、$k(y)=y\notin D$ である。したがって $k(x)=k(y)$ なら $x,y$ はともに $D$ に属するか、ともに属さない。前者なら $\varphi(x)=\varphi(y)$ と $\varphi$ の単射性から $x=y$、後者なら $x=k(x)=k(y)=y$ である。
$Y$ の上への写像である。 $y\in Y$ とする。$y\notin D$ なら $k(y)=y$。$y\in D$ なら $y\notin X\setminus Y$ なので、上の主張から $y=\varphi(d)$ となる $d\in D$ があり、$k(d)=y$ である。$\square$

閉包で振り分けた写像を $g$ で戻す

$X:=A$、$Y:=g[B]$、$\varphi:=g\circ f\colon A\to A$ とおく。$\varphi$ は単射の合成なので単射であり、$\varphi[A]=g[f[A]\!]\subset g[B]$ である。lem-cb-sandwich により全単射 $k\colon A\to g[B]$ で、各 $a$ について $k(a)=g(f(a))$ または $k(a)=a$ となるものがある。$g$ は $B$ から $g[B]$ への全単射なので、$h:=g^{-1}\circ k\colon A\to B$ は全単射である。$k(a)=g(f(a))$ なら $h(a)=f(a)$、$k(a)=a$ なら $a=k(a)\in g[B]$ で $h(a)=g^{-1}(a)$ である。$\square$

lem-cb-sandwich の集合 $D$ は、$D_0:=X\setminus Y$、$D_{n+1}:=\varphi[D_n]$ とおいたときの合併 $\bigcup_{n\in\omega}D_n$ に等しい（合併は $X\setminus Y$ を含み $\varphi$ で閉じているので $D$ を含み、逆に帰納法で各 $D_n\subset D$）。基数の記事の定理「Cantor–Bernstein の定理：単射の往復から全単射」の証明は、この列を直接使って同じ全単射を作っている。また $D$ は冪集合 $\mathcal P(X)$ 上の単調写像 $S\mapsto(X\setminus Y)\cup\varphi[S]$ の最小不動点であり、Knaster–Tarskiの定理の例「Cantor–Schröder–Bernstein の定理」はこの見方で定理を説明している。

系：挟まれた集合

挟まれた集合の濃度

$A\subset B\subset C$ で $|A|=|C|$ なら、$|B|=|C|$ である。

包含写像 $B\to C$ は単射である。$|A|=|C|$ から全単射 $C\to A$ があり、これに包含 $A\to B$ を合成すると単射 $C\to B$ が得られる。thm-cb-main により $|B|=|C|$ である。$\square$

証明2：親をたどる鎖による証明

二つ目の証明は、$A$ と $B$ の元を「$f$ と $g$ で交互に送る鎖」に並べ、鎖ごとに全単射を作る。こちらの証明からは、単射の往復がどんな形をしているかが読み取れる。
$A$ と $B$ が共通の元をもつ場合にも区別できるよう、印を付けて
$$ P:=(A\times\{0\})\cup(B\times\{1\}) $$
とおき、$(a,0)$ を「$A$ 側の元」、$(b,1)$ を「$B$ 側の元」と呼ぶ。写像 $t\colon P\to P$ を
$$ t(a,0):=(f(a),1),\qquad t(b,1):=(g(b),0) $$
で定める。$t$ は $A$ 側を $B$ 側へ、$B$ 側を $A$ 側へ送り、$f,g$ が単射なので $t$ も単射である。$t(y)=x$ のとき $y$ を $x$ の親と呼ぶ。$t$ が単射なので、各元の親は高々一つである。親をもたない元の集合を
$$ S:=P\setminus t[P]=\bigl((A\setminus g[B])\times\{0\}\bigr)\cup\bigl((B\setminus f[A])\times\{1\}\bigr) $$
とおく。$t$ の $n$ 回の合成 $t^n$（$t^0$ は恒等写像）は $\omega$ 上の再帰で定まる。

鎖の始点は一つに決まる

$s,s'\in S$、$m,n\in\omega$ について $t^m(s)=t^n(s')$ なら、$m=n$ かつ $s=s'$ である。

$m\le n$ としてよい。$t^m(s)=t^m(t^{n-m}(s'))$ に $t$ の単射性を $m$ 回使うと $s=t^{n-m}(s')$ となる。$n>m$ なら $s\in t[P]$ となり $s\in S$ に反するので、$n=m$ であり、$s=s'$ である。$\square$

$P$ を次の三つに分ける。
$$ \begin{aligned} P_A&:=\{t^n(s)\mid n\in\omega,\ s\in(A\setminus g[B])\times\{0\}\},\\ P_B&:=\{t^n(s)\mid n\in\omega,\ s\in(B\setminus f[A])\times\{1\}\},\\ P_\infty&:=P\setminus(P_A\cup P_B). \end{aligned} $$
$P_A$ は「親をたどると $A$ 側の始点に行き着く元」、$P_B$ は「$B$ 側の始点に行き着く元」、$P_\infty$ は「親がどこまでも続く元」である。lem-cb-unique-origin により $P_A\cap P_B=\emptyset$ である。

三つの部分は $t$ で保たれる

$t[P_A]\subset P_A$、$t[P_B]\subset P_B$、$t[P_\infty]\subset P_\infty$ である。
$P_\infty$ の元の親は存在し、それも $P_\infty$ に属する。
$x=t^n(s)\in P_A\cup P_B$（$s\in S$）が $s$ と反対の側にあることと、$n$ が奇数であることは同値である。

$t(t^n(s))=t^{n+1}(s)$ なので最初の二つは明らかである。$x\in P_\infty$ で $t(x)=t^n(s)\in P_A\cup P_B$ とすると、$t(x)\notin S$ から $n\ge1$ であり、単射性から $x=t^{n-1}(s)\in P_A\cup P_B$ となって矛盾する。
$x\in P_\infty$ なら、$S$ の元は $n=0$ として $P_A\cup P_B$ に入るので $x\notin S$、すなわち $x=t(y)$ となる $y$ がある。$y\in P_A\cup P_B$ なら 1 により $x\in P_A\cup P_B$ となるので、$y\in P_\infty$ である。
$t$ は一回ごとに側を入れ替えるからである。$\square$

鎖の始点で振り分ける

$a\in A$ について $x:=(a,0)$ とおき、$h\colon A\to B$ を次のように定める。

$x\in P_A\cup P_\infty$ なら $h(a):=f(a)$。
$x\in P_B$ なら、$x=t^n(s)$（$s\in(B\setminus f[A])\times\{1\}$）と書くと、$x$ は $s$ と反対の側にあるので lem-cb-pieces の 3 により $n$ は奇数で、特に $n\ge1$ である。よって $x=t(y)$、$y=t^{n-1}(s)=(b,1)$ と書け、$a=g(b)$ である。$h(a):=b=g^{-1}(a)$ とおく。
どちらの場合も、$(h(a),1)$ は $(a,0)$ と同じ部分に属する。前者では $(h(a),1)=t(x)$ で lem-cb-pieces の 1 により、後者では $(h(a),1)=t^{n-1}(s)\in P_B$ だからである。

単射である。 $h(a)=h(a')$ とすると、上の注意から $(a,0)$ と $(a',0)$ は $(h(a),1)$ と同じ部分に属する。それが $P_A\cup P_\infty$ なら $f(a)=f(a')$ から $a=a'$、$P_B$ なら $a=g(h(a))=g(h(a'))=a'$ である。
全射である。 $b\in B$ とし、$y:=(b,1)$ とおく。

$y\in P_A$ なら $y=t^n(s)$（$s$ は $A$ 側）で、$y$ は $s$ と反対の側なので $n\ge1$ である。$x:=t^{n-1}(s)=(a,0)\in P_A$ について $f(a)=b$ であり、$h(a)=f(a)=b$。
$y\in P_\infty$ なら lem-cb-pieces の 2 により親 $x\in P_\infty$ があり、$t$ は $A$ 側だけを $B$ 側へ送るので $x=(a,0)$ と書けて $f(a)=b$、$h(a)=b$。
$y\in P_B$ なら $t(y)=(g(b),0)\in P_B$ であり、定義から $h(g(b))=g^{-1}(g(b))=b$。
各 $a$ で $h(a)$ は $f(a)$ か $g^{-1}(a)$ なので、thm-cb-main の後半も成り立つ。$\square$

鎖を一つずつ見ると、$t$ の軌道は次の四つの形のどれかである。$P_A$ と $P_B$ の鎖は始点から $\mathbb N$ の形に伸び、$P_\infty$ の鎖は両方向に無限に伸びる $\mathbb Z$ の形か、有限の長さで閉じた輪になる（輪は $A$ 側と $B$ 側を交互に通るので長さは偶数）。

鎖の形	始まり	全単射 $h$ の作り方
$\mathbb N$ 型、始点が $A$ 側	$A\setminus g[B]$ の元	$A$ 側の元を $f$ で一つ先へ送る
$\mathbb N$ 型、始点が $B$ 側	$B\setminus f[A]$ の元	$A$ 側の元を $g^{-1}$ で一つ前へ戻す
$\mathbb Z$ 型	始点なし	$f$ で送る（$g^{-1}$ で戻してもよい）
偶数の長さの輪	始点なし	$f$ で送る（$g^{-1}$ で戻してもよい）

始点が $A$ 側の鎖で $g^{-1}$ を使うと始点の行き先がなくなり、始点が $B$ 側の鎖で $f$ を使うと始点が値として取られない。始点のない鎖ではどちらでもよく、$h$ は一般に一つには決まらない。

系：二つの単射に沿った分割

鎖による証明は、次の分割の形にまとめられる。

単射の往復による分割

単射 $f\colon A\to B$、$g\colon B\to A$ に対し、分割 $A=A_1\sqcup A_2$、$B=B_1\sqcup B_2$ で
$$ f[A_1]=B_1,\qquad g[B_2]=A_2 $$
となるものが存在する。

prf-cb-main-chains の記号で、$A_1:=\{a\in A\mid(a,0)\in P_A\cup P_\infty\}$、$A_2:=A\setminus A_1$、$B_1:=\{b\in B\mid(b,1)\in P_A\cup P_\infty\}$、$B_2:=B\setminus B_1$ とおく。その証明で見たとおり、$h$ は $A_1$ を $f$ によって $B_1$ の上へ、$A_2$ を $g^{-1}$ によって $B_2$ の上へ写す。したがって $f[A_1]=B_1$、$g[B_2]=A_2$ である。$\square$

逆に、この分割があれば $A_1$ 上で $f$、$A_2$ 上で $g^{-1}$ を使って全単射が得られるので、cor-cb-banach は定理と同じ内容を写像の分割として述べ直したものである。

例

閉区間と半開区間

$A=[0,1]$、$B=[0,1)$ とし、単射 $f\colon A\to B$、$f(x)=x/2$ と、包含写像 $g\colon B\to A$ をとる。鎖による証明に沿って全単射を求める。

$A\setminus g[B]=\{1\}$ から始まる鎖は $1\mapsto\tfrac12\mapsto\tfrac12\mapsto\tfrac14\mapsto\tfrac14\mapsto\cdots$（$f$ と $g$ を交互に適用）であり、$A$ 側の元は $1,\tfrac12,\tfrac14,\ldots$ である。
$B\setminus f[A]=(\tfrac12,1)$ の元 $b$ から始まる鎖は $b\mapsto b\mapsto\tfrac b2\mapsto\tfrac b2\mapsto\cdots$ であり、$A$ 側の元は $b,\tfrac b2,\tfrac b4,\ldots$ である。
$0$ は $f(0)=0$、$g(0)=0$ で長さ $2$ の輪をなす。
$(0,1]$ の各元は $b\cdot2^{-n}$（$b\in(\tfrac12,1]$、$n\in\omega$）とただ一通りに書けるので、これで $A$ のすべての元が尽くされる。始点が $A$ 側の鎖と輪では $f$、始点が $B$ 側の鎖では $g^{-1}$ を使うと
$$ h(x)=\begin{cases}x/2&(x=2^{-n},\ n\in\omega)\\ x&(\text{それ以外})\end{cases} $$
が全単射 $[0,1]\to[0,1)$ になる。$1,\tfrac12,\tfrac14,\ldots$ を一つずつ後ろへずらして $1$ の行き先を空け、ほかの点は動かさない。

実数全体と自然数の冪集合

$|\mathbb R|=|\mathcal P(\mathbb N)|$ を示す（$\mathbb N=\{0,1,2,\ldots\}$）。
$\mathcal P(\mathbb N)\to\mathbb R$ の単射。 $T\subset\mathbb N$ に対し
$$ \Phi(T):=\sum_{n\in T}\frac{2}{3^{n+1}} $$
とおく（3 進法で、$n+1$ 桁目が $T$ に $n$ が入るとき $2$、入らないとき $0$ の数）。$T\neq T'$ なら、対称差の最小元 $m$ をとり $m\in T\setminus T'$ としてよい。$m$ より前の桁は一致するので
$$ \Phi(T)-\Phi(T')\ \ge\ \frac{2}{3^{m+1}}-\sum_{n>m}\frac{2}{3^{n+1}}=\frac{2}{3^{m+1}}-\frac{1}{3^{m+1}}>0 $$
であり、$\Phi$ は単射である。
$\mathbb R\to\mathcal P(\mathbb N)$ の単射。 $\Psi(x):=\{q\in\mathbb Q\mid q< x\}$ とおく。$x< y$ なら $x< q< y$ となる有理数 $q$ があり、$q\in\Psi(y)\setminus\Psi(x)$ なので $\Psi\colon\mathbb R\to\mathcal P(\mathbb Q)$ は単射である。有理数全体は可算なので（可算集合の例「有理数全体の可算性」）全単射 $e\colon\mathbb Q\to\mathbb N$ があり、$U\mapsto e[U]$ は全単射 $\mathcal P(\mathbb Q)\to\mathcal P(\mathbb N)$ である。合成 $x\mapsto e[\Psi(x)]$ が求める単射である。
thm-cb-main により $|\mathbb R|=|\mathcal P(\mathbb N)|$ である。どちらの単射も素直に書けるが、両者を合わせた全単射を直接書き下すのは面倒である。

無理数全体と実数全体

$|\mathbb R\setminus\mathbb Q|=|\mathbb R|$ を示す。包含写像 $\mathbb R\setminus\mathbb Q\to\mathbb R$ は単射なので、ex-cb-reals の $|\mathbb R|=|\mathcal P(\mathbb N)|$ と合わせると、単射 $\mathcal P(\mathbb N)\to\mathbb R\setminus\mathbb Q$ を作ればよい。
$T\subset\mathbb N$ に対し $E(T):=\{(k+2)^2\mid k\in\mathbb N\}\cup\{(k+2)^2+1\mid k\in T\}$ とおき、$\Theta(T):=\Phi(E(T))$ とする。$T\mapsto E(T)$ は単射で $\Phi$ も単射なので、$\Theta$ は単射である。$n\in E(T)$ なら $c_n:=2$、そうでなければ $c_n:=0$ とおくと、$c_n$ は $\Theta(T)$ の 3 進展開の $n+1$ 桁目である。$j\ge2$ のとき番号 $j^2+2,\ldots,(j+1)^2-1$ はどれも $E(T)$ に入らないので、列 $(c_n)$ には $0$ が $2j-1$ 個続き、その直後の $c_{(j+1)^2}$ は $2$ である。
$\Theta(T)$ が有理数でないことを示す。

詳細

$\Theta(T)=p/q$（$p,q$ は整数、$q\ge1$）と仮定する。各 $m$ について $\tau_m:=\sum_{i\ge0}c_{m+i}3^{-(i+1)}$ とおくと $\tau_m\in[0,1]$ で、$3^m\Theta(T)-\tau_m=\sum_{n< m}c_n3^{m-n-1}$ は整数だから、$\tau_m$ は $\{0,\tfrac1q,\ldots,\tfrac qq\}$ のどれかである。したがって $m< m'$ で $\tau_m=\tau_{m'}$ となるものがある。桁が $0$ と $2$ だけの列については、上の $\Phi$ の単射性の議論により値が桁を決めるので、すべての $i\ge0$ で $c_{m+i}=c_{m'+i}$ となる。すなわち列 $(c_n)$ は番号 $m$ 以後、周期 $r:=m'-m$ で繰り返す。$j$ を $j^2> m$ かつ $2j-1\ge r$ となるようにとると、$c_{j^2+2},\ldots,c_{j^2+1+r}$ はすべて $0$ なので、周期性から番号 $j^2+2$ 以後の項はすべて $0$ となる。これは $c_{(j+1)^2}=2$ に反する。$\square$

よって $\Theta$ は単射 $\mathcal P(\mathbb N)\to\mathbb R\setminus\mathbb Q$ であり、thm-cb-main から $|\mathbb R\setminus\mathbb Q|=|\mathbb R|$ である。cor-cb-between の形で言えば、$\Theta[\mathcal P(\mathbb N)]\subset\mathbb R\setminus\mathbb Q\subset\mathbb R$ で両端が対等だから、間の集合も対等である。

自然数の対の全体

$(m,n)\mapsto2^m3^n$ は素因数分解の一意性から単射 $\mathbb N\times\mathbb N\to\mathbb N$ であり、$n\mapsto(n,0)$ は単射 $\mathbb N\to\mathbb N\times\mathbb N$ である。よって $|\mathbb N\times\mathbb N|=|\mathbb N|$ である。具体的な全単射は可算集合の命題「自然数の対の番号付け」で与えられているが、定理を使えば単射を二つ見つけるだけで済む。

反例：構造まで保つことは求められない

定理が与えるのは集合としての全単射だけである。互いに構造を保つ単射があっても、構造を保つ全単射があるとは限らない。各行は定理の条件を一つだけ変えたものである。

外す条件	反例	成り立たなくなること
逆向きの単射 $g$ がある	$A=\mathbb N$、$B=\mathbb R$、$f$ は包含写像	全単射が存在しない
求める全単射は順序を保たなくてよい	$A=[0,1]$、$B=(0,1)$、順序を保つ単射 $x\mapsto\frac{x+1}{3}$ と包含写像	順序同型が存在しない
求める全単射は連続でなくてよい	同じ $A,B$ と同じ二つの連続な単射	同相写像が存在しない
求める全単射は演算を保たなくてよい	$G=\mathbb Z/2\oplus\bigoplus_{n\ge1}\mathbb Z/4$、$H=\bigoplus_{n\ge1}\mathbb Z/4$ と下の単射準同型	群の同型が存在しない

反例の確かめ

1 行目：$\mathbb R$ は非可算なので（可算集合の定理「実数全体の非可算性」）、$\mathbb N$ との全単射はない。
2 行目：$x\mapsto\frac{x+1}{3}$ は $[0,1]$ を $[\tfrac13,\tfrac23]\subset(0,1)$ へ順序を保って単射に写す。$[0,1]$ には最大元 $1$ があり $(0,1)$ にはないので、順序同型はない（順序同型は最大元を最大元へ写す）。
3 行目：二つの写像はどちらも連続である。$[0,1]$ はコンパクト空間だが、$(0,1)$ は開被覆 $\{(\tfrac1n,1)\mid n\ge2\}$ が有限部分被覆をもたないのでコンパクトでない。コンパクト性は同相写像で保たれるので、両者は同相でない。
4 行目：$H\to G$ を $(x_1,x_2,\ldots)\mapsto(0,x_1,x_2,\ldots)$、$G\to H$ を $(\varepsilon,x_1,x_2,\ldots)\mapsto(2\varepsilon,x_1,x_2,\ldots)$（$\mathbb Z/2\to\mathbb Z/4$、$1\mapsto2$ は単射準同型）で定めると、どちらも単射準同型である。$H$ では位数 $2$ の元の成分はすべて $0$ か $2$ なので、その元は「成分 $2$ を $1$ に替えた元」の $2$ 倍である。$G$ の元 $(1,0,0,\ldots)$ は位数 $2$ だが、$2(\varepsilon,x_1,\ldots)=(0,2x_1,\ldots)$ の第 1 成分は常に $0$ なので、どの元の $2$ 倍でもない。「位数 $2$ の元はすべて $2$ 倍の形」という性質は群の同型で保たれるので、$G$ と $H$ は同型でない。

補足

全射による言い換えと選択公理

単射の代わりに全射が往復する場合、選択公理を仮定すれば同じ結論が得られる。全射 $p\colon A\to B$ に対し、選択公理により各 $b\in B$ の逆像 $p^{-1}(b)$ から元を一つずつ選ぶ写像 $s\colon B\to A$ があり、$p\circ s=\mathrm{id}_B$ なので $s$ は単射である。全射 $q\colon B\to A$ からも同様に単射 $A\to B$ が得られ、thm-cb-main から全単射がある。この議論は選択公理を本質的に使っており、thm-cb-main の証明とは性格が違う。

証明が使うもの

二つの証明はどちらも、$\omega$ 上の再帰（または部分集合の族の共通部分）と分出公理しか使わない。全単射 $h$ は $f$ と $g$ から一つの式で定義され、途中で何も選ばない。証明1 の集合 $D$ と証明2 の $P_A$ の $A$ 側は同じ集合である（どちらも $A\setminus g[B]$ から $g\circ f$ を繰り返して得られる元全体）。

参照箇所

Kun80 Chapter I, §10, Theorem 10.2（p. 27、主張）と Chapter I の演習 (8)（p. 43、$A_{n+1}=g[B_n]$、$B_{n+1}=f[A_n]$ による証明の筋書き）。
OLT26 Theorem 4.25（p. 72、主張）、§6.5 の Lemma 6.8 と Proposition 6.9（pp. 102–103、閉包による証明）。