解答例 1

$f:A\rightarrow B$, $g:B\rightarrow A$ を単射とする.

集合の列 $(A_n)$, $(B_n)$ を次のように帰納的に定義する. \begin{alignat*}{3} & A_1 = A\setminus g(B), &\quad & B_1 = B\setminus f(A), && \\ & A_{n+1} = g(B_n), &\quad & B_{n+1} = f(A_n). &\quad & (n=1, 2, 3, \ldots) \end{alignat*} $A_1=\emptyset$ ならば, $A=g(B)$ となり, $g$ は全単射である. 同様に, $B_1=\emptyset$ ならば, $B=f(A)$ となり, $f$ は全単射である. 以下, $A_1$, $B_1$ はともに空集合でないと仮定する. そのとき, すべての番号 $n$ に対して, $A_n$, $B_n$ は空でない.

任意の番号 $m$, $n$ に対して, $$ m < n \Longrightarrow A_m\cap A_n = \emptyset,\,B_m\cap B_n = \emptyset $$ が成り立つ. 以下, そのことを $n$ に関する数学的帰納法により示す. $n=2$ のとき, \begin{align*} A_2 &= g(B_1)\subseteq g(B), \\ B_2 &= g(A_1)\subseteq f(A) \end{align*} なので, $A_1\cap A_2=\emptyset$, $B_1\cap B_2=\emptyset$ である. 一般の場合について, $1\leq m< n$ を満たす全ての番号 $m$ に対して $A_m\cap A_n = \emptyset$, $B_m\cap B_n = \emptyset$ が成り立つと仮定する. $2\leq m< n+1$ を満たす全ての番号 $m$ に対して, $f$, $g$ の単射性より, \begin{align*} x\in A_m\cap A_{n+1} &\Longrightarrow x = f(y_1) = f(y_2)\,(\exists y_1\in B_{m-1},\,\exists y_2\in B_n), \\ &\Longrightarrow y_1=y_2\in B_{m-1}\cap B_n, \\ y\in B_m\cap B_{n+1} &\Longrightarrow y=f(x_1)=f(x_2)\,\,(\exists x_1\in A_{m-1},\,\exists x_2\in A_n) \\ &\Longrightarrow x_1=x_2\in A_{m-1}\cap A_n \end{align*} であるから, $A_m\cap A_{n+1}=\emptyset$, $B_m\cap B_{n+1}=\emptyset$ でなければならない. また, \begin{align*} A_{n+1} &= g(B_n)\subseteq g(B), \\ B_{n+1} &= g(A_n)\subseteq f(A) \end{align*} なので, $A_1\cap A_{n+1}=\emptyset$, $B_1\cap B_{n+1}=\emptyset$ である.

さて, $$ A_{\infty} = A\setminus\bigcup_{n=1}^{\infty}A_n,\quad B_{\infty} = B\setminus\bigcup_{n=1}^{\infty}B_n,\quad $$ とおくと, $$ A = A_{\infty}\cup\bigcup_{n=1}^{\infty}A_n,\quad B = B_{\infty}\cup\bigcup_{n=1}^{\infty}B_n $$ のように集合の直和に分解される.

$f$, $g$ が単射であることから, $n=1$, $2$, $3$, $\ldots$ に対して, 制限写像 \begin{alignat*}{2} f\mid A_n: A_n&\longrightarrow B_{n+1},&\quad x&\longmapsto f(x), \\ g\mid B_n: B_n&\longrightarrow A_{n+1},&\quad y&\longmapsto g(y) \end{alignat*} は全単射である. さらに, 制限写像 $$ f\mid A_{\infty}: A_{\infty}\longrightarrow B_{\infty},\quad x\longmapsto f(x) $$ が定まって全単射になることがいえれば, 全単射 $h:A\rightarrow B$ が $$ h(x) = \begin{cases} f(x), & \mbox{$x\in A_{2n-1}$ ($n=1$, $2$, $\ldots$) のとき} \\ g^{-1}(x), & \mbox{$x\in A_{2n}$ ($n=1$, $2$, $\ldots$) のとき} \\ f(x), & \mbox{$x\in A_{\infty}$ のとき} \end{cases} $$ によって定まり, 証明は完了する.

そこで, 以下, $f\mid A_{\infty}$ が定まって全単射になることを示す.

$x\in A_{\infty}$ ならば $f(x)\in B_{\infty}$ である. なぜなら, 明らかに $f(x)\not\in B_1$ であり, 各 $n=1$, $2$, $\ldots$ に対して, $f$ の単射性から $$ f(x)\in B_{n+1} \Longrightarrow f(x)=f(x_0)\,(\exists x_0\in A_n) \Longrightarrow x=x_0\in A_n $$ となるからである. したがって, $f\mid A_{\infty}$ が定まる. 単射であることは明らかである.

$y\in B_{\infty}$ を任意にとると, $y\not\in B_1$ であるから, $y\in f(A)$ である. よって, ある $x\in A$ が存在して, $f(x)=y$ となる. もし仮に, ある番号 $n$ が存在して $x\in A_n$ であるとすると, $y=f(x)\in B_{n+1}$ となり, $y\in B_{\infty}$ に矛盾する. ゆえに, $x\in A_{\infty}$ でなければならない. したがって, $f\mid A_{\infty}$ は全射である.

解答例 2

$f:A\rightarrow B$, $g:B\rightarrow A$ を単射とする.

$a\in A$ と $b\in B$ について, $b=f(a)$ が成り立つとき, $a$ を $b$ の親と呼び, $b\succ a$ で表すことにする. また, $a=g(b)$ が成り立つとき, $b$ を $a$ の親と呼び, $a\succ b$ で表す.

$f$, $g$ は単射だから, 親は存在すれば一意的である. よって, 各 $a\in A$ に対し, 親を次々と並べた列 \begin{align*} &a=a_0 \succ b_1\succ a_1\succ b_2\succ a_2\succ \cdots, \\ &a = g(b_1),\, b_1=f(a_1),\,a_1=g(b_2),\,b_2=f(a_2),\,\ldots \end{align*} はただ1つ定まり, 次のいずれかの型になっている. \begin{alignat}{2} &a=a_0\succ b_1\succ a_1\succ b_2\succ a_2\succ \cdots &\quad& (\mbox{無限列}), \tag{1} \\ &a=a_0\succ b_1\succ a_1\succ\cdots\succ b_{n-1}\succ a_n &\quad& (\mbox{$a_n$ の親は存在しない}), \tag{2} \\ &a=a_0\succ b_1\succ a_1\succ\cdots\succ a_{n-1}\succ b_n &\quad& (\mbox{$b_n$ の親は存在しない}). \tag{3} \end{alignat} 同様に, 各 $b\in B$ に対し, 親を次々と並べた列 \begin{align*} &b = b_0 \succ a_1\succ b_1\succ a_2\succ b_2\succ \cdots, \\ &b = f(a_1),\, a_1=g(b_1),\,b_1=f(a_2),\,a_2=g(b_2),\,\ldots \end{align*} はただ1つ定まり, 次のいずれかの型になっている. \begin{alignat}{2} &b = b_0\succ a_1\succ b_1\succ a_2\succ b_2\succ \cdots &\quad& (\mbox{無限列}), \tag{4} \\ &b = b_0\succ a_1\succ b_1\succ\cdots\succ b_{n-1}\succ a_n &\quad& (\mbox{$a_n$ の親は存在しない}), \tag{5} \\ &b = b_0\succ a_1\succ b_1\succ\cdots\succ a_{n-1}\succ b_n &\quad& (\mbox{$b_n$ の親は存在しない}). \tag{6} \end{alignat} そこで, (1) の型の列になる $A$ の元 $a$ 全体を $A_{\infty}$, (2) の型の列になる $A$ の元 $a$ 全体を $A_A$, (3) の型の列になる $A$ の元 $a$ 全体を $A_B$ とおく. 同様に, (4) の型の列になる $B$ の元 $b$ 全体を $B_{\infty}$, (5) の型の列になる $B$ の元 $b$ 全体を $B_A$, (6) の型の列になる $B$ の元 $b$ 全体を $B_B$ とおく. すると, \begin{alignat*}{2} A &= A_{\infty}\cup A_A\cup A_B, & \quad & (\mbox{直和}) \\ B &= B_{\infty}\cup B_A\cup B_B, & \quad & (\mbox{直和}) \end{alignat*} のように分解される. また, $$ f(A_{\infty}) = B_{\infty},\quad f(A_A) = B_A,\quad g(B_B)=A_B $$ の成り立つことが直ちにわかる. $f$, $g$ は単射であるから, 制限写像 \begin{alignat*}{2} f\mid A_{\infty}&:A_{\infty}\longrightarrow B_{\infty},&\quad x&\longmapsto f(x), \\ f\mid A_A&:A_A\longrightarrow B_{\infty},&\quad x&\longmapsto f(x), \\ g\mid B_B&:B_B\longrightarrow A_B,&\quad y&\longmapsto g(y) \end{alignat*} はいずれも全単射である. したがって, 写像 $h:A\rightarrow B$ を $$ h(x) = \begin{cases} f(x), & x\in A_{\infty}\cup A_A, \\ g^{-1}(x) & x\in A_B \end{cases} $$ によって定義すれば, $h$ は全単射になる.

最終更新日：2011年11月02日