Schröder–Bernstein 定理

谁指向它（入边）

推出 1

• 单射 / 满射 / 双射 ⟹ 本页推出
  两个方向的单射 $\implies$ 双射

  设 $f : A \to B$、$g : B \to A$ 都是单射。把 $A$ 分成两半，一半用 $f$、一半用 $g^{-1}$，拼出一个双射。

  ① 造一串集合。 令

  $$A_0 := A \setminus g(B), \qquad A_{n+1} := g(f(A_n))$$

  （直观：$A_0$ 是「$B$ 管不到」的那部分，剩下的在 $f$ 与 $g$ 之间来回倒。）令

  $$A^{*} := \bigcup_{n=0}^{\infty} A_n, \qquad A^{\sharp} := A \setminus A^{*}$$

  ② 定义 $h : A \to B$。

  $$h(a) := \begin{cases} f(a), & a \in A^{*} \\ g^{-1}(a), & a \in A^{\sharp} \end{cases}$$

  要说明：$a \in A^{\sharp}$ 时 $a \in g(B)$，所以 $g^{-1}(a)$ 有意义。事实上若 $a \notin g(B)$ 则 $a \in A_0 \subseteq A^{*}$，与 $a \in A^{\sharp}$ 矛盾。

  ③ $h$ 是单射。 分三种情况：同在 $A^{$}A∗ 上由 $f$ 单射；同在 $A^{\sharp}$ 上由 $g$ 单射；一边一个时，$h(A^{$}) = f(A^{*}) 而

  $$f(A^{*}) = \bigcup_{n} f(A_n) = \bigcup_{n} g^{-1}(A_{n+1}) \subseteq g^{-1}(A^{*} \setminus A_0)$$

  与 $h(A^{\sharp}) = g^{-1}(A^{\sharp})$ 不相交 —— 因为 $A^{\sharp} \cap (A^{*} \setminus A_0) = \emptyset$。

  ④ $h$ 是满射。 若 $b \in B$：令 $a = g(b) \in A$。若 $a \in A^{\sharp}$，则 $h(a) = g^{-1}(a) = b$；若 $a \in A^{$}a∈A∗，则 $a \in A_n$ 对某个 $n \ge 1$（因为 $a = g(b)$ 落在 $g(B)$ 里），于是 $a = g(f(a'))$ 对某个 $a' \in A_{n-1} \subseteq A^{$}，由 $g$ 单射得 $f(a') = b$，即 $h(a') = b$。

  综上 $h$ 是双射，故 $|A| = |B|$。$\blacksquare$

定义引用 1

• 单射 / 满射 / 双射 → 本页定义引用

  前提与结论都由单射 / 双射写成。