📂집합론

칸토어-베른슈타인 정리 증명

정리 ¹

집합 $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$ 이라고 가정해보자. 이는 곧 $f^{n}(x_{1}) = f^{m}(x_{2})$ 를 만족시키는 어떤 $x_{1}, x_{2} \in (A \setminus B)$ 가 존재한다는 것이다. 그러면 $$ \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$ 는 대등하다.

■