← Arietids Learn · 交互演示目录
Schröder–Bernstein

追链板

沿 f 前进，再沿 g 回来
g 没打到的缺口 C0=A∖g[B]
f
用 f 推到 B D0=f[C0]
再用 g 拉回 A C1=g[D0]
g
上一层 B D0
新的 A 层 C1
f
再推到 B D1=f[C1]
下一次拉回 C2=g[D1]
g
上一层 B D1
不断重复 Cn+1=g[Dn]
f
对应的 B 层 Dn+1=f[Cn+1]
用 f 用 g 互不重叠的新层

构造账本

链是怎样生成的
0 从 A 的缺口开始 C0=A∖g[B] D0=f[C0] 只取 g 没打到的点。
1 从 B 拉回 C1=g[D0] D1=f[C1] 先经 g 回到 A，再经 f 推出去。
n 继续迭代 Cn+1=g[Dn] Dn+1=f[Cn+1] 每一层都与前面层分开。

1基础：只保留证明必需概念

若上面的符号不顺，先读这里。
A

单射就是不撞车

若 f(a1)=f(a2) 必推出 a1=a2，则 f 是单射。后面证明 h 单射时就靠这一步回推。

B

像集记号

若 X⊆A，则 f[X]={f(x) | x∈X}。g[B] 是 g:B→A 打到的那部分 A。

C

为什么从 C0 开始

C0=A∖g[B] 正是没有 g-原像的点。它们不能用 g-1，所以 h 必须用 f。

D

最后要证什么

定义 h:A→B 后，只需证明它既单射又满射。这样 h 就是双射，故 A 与 B 等势。

正式构造

C0=A∖g[B], Dn=f[Cn], Cn+1=g[Dn].
U=⋃n≥0Cn; h(a)=f(a) if a∈U, and h(a)=g-1(a) if a∉U.

记住一个动作：从 C0 出发，反复做 Cn --f→ Dn --g→ Cn+1。

始终记住的事实

位置每个 Ci⊆A，每个 Di⊆B。
配对Di=f[Ci]，所以 Di 由 Ci 通过 h=f 命中。
互斥各层互不重叠，因此 a∈U=⋃iCi 这一分支没有歧义。
补集若 a∉U，则 a∈g[B]，且 g 的单射性保证原像唯一。

阅读路线

  • 先把 C0 理解成 g-1 失败的地方。
  • 再追 C0→D0→C1→D1→...。
  • 最后把 A 分成 U 与 A∖U 来定义 h。

透彻自检

  • 为什么 a∉U 能保证存在 b 使 g(b)=a？
  • 为什么这个 b 唯一？
  • 为什么混合分支相撞会把 A∖U 的点推回 U？

常见误区

不要以为 h 全部等于 f 或全部等于 g-1。U 标出必须用 f 的区域，补集才是安全使用 g-1 的区域。

2定义 h

把 A 分成两块

U=⋃i=0∞Ci, A=U∪(A∖U).

U 是从 g 没打到的点追出来的链；补集里的每个点都等于唯一的 g(b)。

1 存在。 若 a∉U，则 a∉C0，所以 a∈g[B]。
2 唯一。 因为 g 单射，满足 g(b)=a 的 b 至多一个。
3 不抢 Di。 若这个 b∈Dn，则 a=g(b)∈Cn+1⊆U，矛盾。

1在 U 内

h(a)=f(a)

若 a∈Ci，直接送到 Di=f[Ci]。这正是从 C0 追出的那条链。

a∈Ci f f(a)∈Di

2在 U 外

h(a)=b, where g(b)=a

若 a∉U，则 a 在 g 的像里；又因 g 单射，这个 b 唯一。

b∈B g a=g(b)

3验证 h 是双射

单射：两个 A 点不会撞到同一个 B 点

假设 h(a1)=h(a2)。按 a1,a2 是否在 U 中，只剩三种情况。

都在 U 内f(a1)=f(a2)，由 f 单射得 a1=a2。
都在 U 外g(h(a1))=a1，g(h(a2))=a2，所以 a1=a2。
一内一外不可能相撞若 a2∈Cn，则 g(f(a2))∈Cn+1⊆U，与外侧分支矛盾。
a1∉U, a2∈Cn, h(a1)=h(a2) ⇒ a1=g(f(a2))∈Cn+1.

满射：每个 b∈B 都被命中

任取 b∈B。它要么在某个 Di 中，要么不在任何 Di 中。

若 b∈Dn则 b=f(a) 对某个 a∈Cn 成立，所以 h(a)=b。
若 b∉⋃iDi令 a=g(b)。此时 a∉U，补集分支给出 h(a)=b。
b∉⋃iDi, a=g(b) ⇒ a∉U ⇒ h(a)=g-1(a)=b.

English exam skeleton

  • Let C0=A∖g[B], Dn=f[Cn], and Cn+1=g[Dn].
  • Let U=⋃n≥0Cn.
  • Define h(a)=f(a) if a∈U, and h(a)=g-1(a) if a∉U.
  • For injectivity, split into three cases: both in U, both outside U, and mixed.
  • For surjectivity, each b∈B is either in some Dn, or has g(b)∉U.
  • Mastery standard / 透彻掌握: the answer is complete only if it justifies the two-branch definition, proves injectivity, and proves surjectivity.

Key English terms

  • injection: no two inputs have the same image.
  • image: f[X]={f(x):x∈X}.
  • preimage under g: the unique b such that g(b)=a.
  • partition of A: the split A=U∪(A∖U).
  • 10-second final check: define U, write the two-branch formula for h, then prove injective and surjective separately.

Grading checkpoints

  • Explain why g-1(a) is legal when a∉U: then a∈g[B], and injectivity of g gives uniqueness.
  • In the mixed injectivity case, show the collision would force an outside point into Cn+1⊆U, a contradiction.
  • For surjectivity, split b∈B into b∈Dn or b∉⋃nDn.
因此 h : A → B 既单射又满射。
两个单射 A ≤ B 与 B ≤ A 迫使 A ≈ B。
Source: local notes DM_C3.md, section 6；本页重构为交互式证明可视化。