📂集合論

カントール-ベルンシュタインの定理の証明

定理 ¹

集合$A$、$B$について、$A$が$B$の部分集合と同値で、$B$が$A$の部分集合と同値であれば、$A$と$B$は同値である。

---

• 二つの集合が同値であることは、両集合間に全単射が存在することを意味する。

証明

戦略：$x$に関数$f$を$k$回適用するのを$f^{k}(x)$のように表現しようとする。そうすれば、全ての$k \in \mathbb{N}$に対して$f^{k}(x) = f \left( f^{k-1}(x) \right)$のように表現できるだろう。この視点から、$f^{0}$は関数$f$を全く適用しない関数、言わば恒等関数と考えることができる。

まず、集合$A$の部分集合$B$に対して、単射$f: A \to B$が存在する場合は、全単射$h : A \to B$も存在することを示そうとする。もし$B=A$であれば、何らかの単射$f$が恒等関数$h:=f^{0}$を持つので、これ以上示すことはないので、$B \subsetneq A$の場合だけ考えればいい。

---

Part 1. $n \ne m$ならば$f^{n}(A \setminus B) \cap f^{m}(A \setminus B) = \emptyset$

$m < n$の時に$f^{n}(A \setminus B) \cap f^{m}(A \setminus B) \ne \emptyset$が成り立つと仮定してみよう。これはすなわち、何か$x_{1}, x_{2} \in (A \setminus B)$が存在して$f^{n}(x_{1}) = f^{m}(x_{2})$を満たすことを意味する。そこで $$\begin{align*} f^{n-m}(x_{1}) =& f^{m-m}(x_{2}) \\ =& f^{0}(x_{2}) \\ =& x_{2} \end{align*}$$ ここで、$f^{0}(x_{2}) \in B$とは$x_{2} \in B$を意味する。しかし、これは$x_{2} \in (A \setminus B)$に矛盾する。同様の方法で、$m > n$の時にも$f^{n}(A \setminus B) \cap f^{m}(A \setminus B) \ne \emptyset$が成立することを示すことができる。

---

Part 2. $h(A) = B$

集合$C$を以下のように定義しよう。 $$\begin{align*} C:=& \bigcup_{n \ge 0} f^{n} (A \setminus B) \\ h(z):=& \begin{cases} f(z) & , z \in C \\ z &,z \in A\setminus C\end{cases} \end{align*}$$ $C$と$z \in A$に対して関数$h$を上記のように定義すると、$A \setminus B \subset C$かつ、$f (C) \subset C$である。関数の像に関する和集合の性質により $$\begin{align*} h(A) =& (A\setminus C) \cup f (C) \\ =& \left[ A \setminus \bigcup_{n \ge 0} f^{n} (A \setminus B) \right] \cup f \left( \bigcup_{n \ge 0} f^{n} (A \setminus B) \right) \\ =& \left[ A \cap \left( \bigcup_{n \ge 0} f^{n} (A \setminus B) \right)^{c} \right] \cup \bigcup_{n \ge 1} f^{n} (A \setminus B) \\ =& \left[ A \cup \bigcup_{n \ge 1} f^{n} (A \setminus B) \right] \cap \left[ \left( \bigcup_{n \ge 0} f^{n} (A \setminus B) \right)^{c} \cup \bigcup_{n \ge 1} f^{n} (A \setminus B) \right] \\ =& A \cap \left[ \bigcup_{n \ge 0} f^{n} (A \setminus B) \cap \left( \bigcup_{n \ge 1} f^{n} (A \setminus B) \right)^{c} \right]^{c} \\ =& A \cap \left[ f^{0}(A \setminus B) \right]^{c} \\ =& A \cap ( A \setminus B)^{c} \\ =& A \setminus (A \setminus B) \\ =& B \end{align*}$$ つまり、$h(A) = B$であり、$h$は全射である。ここで、$f$は単射なので、$h$も単射になり、結果として全単射である。

---

Part 3. $h$は全単射である

$$A_{0} \subset A \\ B_{0} \subset B$$ 定理の前提によると、二つの全単射$f_{0} : A \to B_{0}$と$g_{0} : B \to A_{0}$が存在すると、$f(x) = g_{0} \left( f_{0} (x) \right)$として定義された関数$f$は単射である。Part 1と2に従えば、全単射$h : A \to A_{0}$が存在する。したがって、$g_{0}^{-1} \circ h : A \to B$は全単射である。従って、$A$と$B$は同値である。

■