集合$A$と$B$について、以下の2つの命題を証明する。 (1) $A$から$B$への単射が存在するための必要十分条件は、$B$から$A$への全射が存在すること。 (2) $A$から$B$への単射$f$が存在し、かつ$A$から$B$への全射$g$が存在すれば、$A$から$B$への全単射が存在する、つまり$A$と$B$は対等であること。ただし、$f$と$g$は同じ写像とは限らない。

1. 問題の内容

集合$A$と$B$について、以下の2つの命題を証明する。

(1) $A$から$B$への単射が存在するための必要十分条件は、$B$から$A$への全射が存在すること。

(2) $A$から$B$への単射$f$が存在し、かつ$A$から$B$への全射$g$が存在すれば、$A$から$B$への全単射が存在する、つまり$A$と$B$は対等であること。ただし、$f$と$g$は同じ写像とは限らない。

2. 解き方の手順

(1)

* $A$から$B$への単射が存在すると仮定する。単射を$f: A \rightarrow B$とする。このとき、関数$g: B \rightarrow A$を以下のように定義する。

$b \in B$に対し、

* $b \in \text{Im}(f)$のとき、$g(b) = a$ ($f(a) = b$となる$a \in A$)

* $b \notin \text{Im}(f)$のとき、$g(b) = a_0$ (任意の$a_0 \in A$)

$g$が全射であることを示す。任意の$a \in A$に対して、$f(a) \in B$であり、$g(f(a)) = a$である。したがって、$g$は全射である。

* $B$から$A$への全射が存在すると仮定する。全射を$g: B \rightarrow A$とする。このとき、関数$f: A \rightarrow B$を以下のように定義する。

$a \in A$に対し、$f(a) = b$ ($g(b) = a$となる$b \in B$)。$g$は全射なので、$g(b) = a$となる$b$は存在する。もし複数の$b$が存在するなら、その中の一つを任意に選ぶ。

$f$が単射であることを示す。$f(a_1) = f(a_2)$とすると、$b_1 = f(a_1)$, $b_2 = f(a_2)$であり、$b_1 = b_2$。$g(b_1) = a_1$かつ$g(b_2) = a_2$であり、$b_1 = b_2$なので、$a_1 = a_2$。したがって、$f$は単射である。

(2)

* $A$から$B$への単射$f: A \rightarrow B$が存在し、$A$から$B$への全射$g: A \rightarrow B$が存在すると仮定する。

* ベルンシュタインの定理（またはシュレーダー・ベルンシュタインの定理）を使用する。この定理は、$A$から$B$への単射と、$B$から$A$への単射が存在すれば、$A$と$B$の間に全単射が存在することを述べている。

* $f: A \rightarrow B$は単射なので、条件を満たしている。全射$g: A \rightarrow B$が存在するということは、$|B| \le |A|$であり、$A$から$B$への単射$f$が存在するということは、$|A| \le |B|$である。

* $A$から$B$への単射$f: A \rightarrow B$が存在する。次に、$B$から$A$への単射$h: B \rightarrow A$を構成する。

$A$から$B$への全射$g: A \rightarrow B$が存在するので、$B$から$A$への関数$h: B \rightarrow A$を以下のように定める。各$b \in B$に対して、$h(b) = a$ (ここで $a \in A$ は $g(a) = b$ である)。$g$は全射なので、$g(a) = b$ となるような$a \in A$が存在する。もし$g(a_1) = g(a_2) = b$なら、そのような$a$の中から一つを任意に選ぶ。

この方法で構成された関数$h: B \rightarrow A$は一般には単射とは限らない。

* 全射$g: A \to B$ を利用して、$B$から$A$への単射を構成する。各$b \in B$に対して、集合 $g^{-1}(b) = \{ a \in A \mid g(a) = b \}$ を考える。$g$は全射なので、$g^{-1}(b) \neq \emptyset$ である。各$b \in B$に対して、$g^{-1}(b)$から一つ要素を選び、それを$h(b)$と定義する。この$h: B \to A$ は単射となる。なぜなら、$h(b_1) = h(b_2)$ なら、$g(h(b_1)) = b_1$ かつ $g(h(b_2)) = b_2$ であるから、$b_1 = g(h(b_1)) = g(h(b_2)) = b_2$ となる。

* したがって、$A$から$B$への単射$f$と、$B$から$A$への単射$h$が存在するため、ベルンシュタインの定理より、$A$から$B$への全単射が存在する。つまり、$A$と$B$は対等である。

3. 最終的な答え

(1) $A$から$B$への単射が存在するための必要十分条件は、$B$から$A$への全射が存在する。

(2) $A$から$B$への単射$f$が存在し、かつ$A$から$B$への全射$g$が存在すれば、$A$から$B$への全単射が存在する。つまり、$A$と$B$は対等である。