3.4. ZF 中的有限性

我们现在简要讨论 $ZF$ 中有限性概念的多样性.

定义 3.4.0.1. 定义以下十四种有穷性.

1.	$isFin_{I} (x)$ : $x$ 的任意不空子集族有包含关系下的极大/极小元 (注意补集存在, 只需要取一边, 这里以极大为例), $\forall s (\exists t \in s \land \forall t \in s (t \subseteq x) \to \exists t \in s \forall r \in s (\neg t ⫋ r))$ . 此谓词 $Π_{1}$ .
2.	$isFin_{I a} (x)$ : $x$ 不是两个非 $I$ 有穷集的不交并, $\neg\exists y \exists z (y \cap z = \emptyset \land x = y \cup z \land \neg isFin (y) \land \neg isFin (z))$ . 此谓词 $Π_{1}$ .
3.	$isFin_{II} (x)$ : $x$ 的任意不空子集族若在包含关系下成为一个链, 则有包含关系下的极大/极小元 (注意补集存在, 同样只需要取一边, 这里以极大为例), $\forall s (\exists t \in s \land \forall t \in s (t \subseteq x) \land \forall t \in s \forall r \in s (t \subseteq r \lor r \subseteq t) \to \exists t \in s \forall r \in s (\neg t ⫋ r))$ . 此谓词 $Π_{1}$ .
4.	$isFin_{III} (x)$ : 不存在 $℘ (x)$ 到 $℘ (x)$ 真子集的双射, $\exists p (p = ℘ (x) \land isDFin (p))$ . 它显然又等价于 $\neg\exists p \exists q \exists f (p = ℘ (x) \land q \subseteq p \land q \neq = p \land isBijOn (f, p, q))$ , 因此此谓词 $Δ_{2}^{ZF}$ .
5.	(Dedekind 有限) $isFin_{I V} (x)$ : 不存在 $x$ 到 $x$ 真子集的双射, $isDFin (x)$ . 此谓词 $Π_{1}$ .
6.	$isFin_{V} (x)$ : $x = \emptyset$ , 或者不存在 $┌ 2 ┐ \times x$ 到 $x$ 的双射; $x = \emptyset \lor \neg\exists p \exists f (p = x \times {{\emptyset}, \emptyset} \land isBijOn (f, x, p))$ . 此谓词 $Π_{1}$ .
7.	$isFin_{V I} (x)$ : $x = \emptyset$ , 或者 $x$ 是单点集, 或者不存在 $x \times x$ 到 $x$ 的双射; $x = \emptyset \lor \exists y \in x (x = {y}) \lor \neg\exists p \exists f (p = x \times x \land isBijOn (f, x, p))$ . 此谓词 $Π_{1}$ .
8.	$isFin_{V II} (x)$ : $isFin_{I} (x) \lor \neg\exists r (isWOOn (r, x))$ . 此谓词 $Π_{2}$ .
9.	$isFin_{Δ_{1}} (x)$ : $isFin_{I a} (x)$
10.	$isFin_{Δ_{2}} (x)$ : $x$ 的可线序化的分划必有穷, $\forall p \forall r (x = ⋃ p \land \forall a \in p \forall b \in p (a \cap b = \emptyset) \land isLOOn (r, p) \to isFin (p))$ . 此谓词 $Π_{1}$ . (注意 $isFin$ 是 $Δ_{1}^{ZF}$ 的谓词)
11.	$isFin_{Δ_{3}} (x)$ : $x$ 的可线序化的子集必有穷, $\forall p \forall r (p \subseteq x \land isLOOn (r, p) \to isFin (p))$ . 此谓词 $Π_{1}$ .
12.	$isFin_{Δ_{4}} (x)$ : 不存在 $x$ 到 $ω$ 的满射, $\neg\exists f \exists w (w = ω \land isSurjOn (f, x, w))$ . 此谓词 $Π_{1}$ .
13.	$isFin_{Δ_{5}} (x)$ : 不存在 $x$ 到 $Succ (x)$ 的满射, $\neg\exists f \exists y (y = x \cup {x} \land isSurjOn (f, x, y))$ . 此谓词 $Π_{1}$ .
14.	$isFin_{D} (x)$ : $x = \emptyset$ , 或者 $x$ 是单点集, 或者 $x$ 是两个势严格小的集合的并集; $x = \emptyset \lor \exists y \in x (x = {y}) \lor \exists y \exists z (x = y \cup z \land \neg\exists f (isBijOn (f, x, y) \lor isBijOn (f, x, z)))$ . 此谓词 $Σ_{2}$ . (这是 Howard & Yorke 引入的, 并不是 Dedekind 有穷性)

我们指出以下加强有穷性的典范方案: 若 $℘ (x)$ 满足 $Q$ 有穷性 (这里 $Q$ 是任意 $isFin$ 的下标), 则称 $x$ 满足 $Q^{''}$ 有穷性, 同样记为 $isFin_{Q^{''}}$ .

显然, 这些有穷性应当按强度有一个排序. 我们首先要指出三个重要引理, 但是并不去分情况证明 (否则要写的内容就太多了! )

引理 3.4.0.2 ( $ZF$ , 有穷性记号的势不变性). 任给有穷性记号 $Q$ , 若存在 $x$ 到 $y$ 的双射, 则 $isFin_{Q} (x) \leftrightarrow isFin_{Q} (y)$ .

引理 3.4.0.3 ( $ZF$ , 有穷性记号基本引理). 任给有穷性记号 $Q$ , 集合 $x$ 和 $y$ , 总有 $isFin_{Q} (x) \leftrightarrow isFin_{Q} (x \cup {y})$ .

引理 3.4.0.4 ( $ZF$ , 自然数有穷引理). 任给有穷性记号 $Q$ , 所有自然数都是 $Q$ 有穷的, 且 $ω$ 不是 $Q$ 有穷的.

评注. 自然数有穷引理是有穷性记号基本引理和数学归纳法的显然推论.

我们接着给出 $ZF$ 中有穷性的强度顺序列表. 这个列表中每一步推断都是不可逆的, 但是证明不可倒过来推断需要做非常多的独立性命题论证 (这相当于是在证明这两个记号的 $E$ 命题独立于 $ZF$ ), 我们不详细叙述.

定理 3.4.0.5 ( $ZF$ ). 我们宣称下列命题. (连续 $\to$ 指的是每一步均可弱化, 请勿理解为默认略去右结合括号的单个命题. )

1.	$I$ 是标准有限/Kuratowski 有限.
2.	$I \to I a \to II \to III \to V^{''} \to Δ_{5} \to I V \to V \to V I \to V II \to V I I^{''}$
3.	$II \to Δ_{3} \to I V \to D \to V II$
4.	$V^{''} \to V I^{''} \to V$
5.	$I = II I^{''} = V^{''''}$ , $III = I V^{''}$
6.	$Δ_{1} = I a$ , $Δ_{2} = II$ , $Δ_{4} = III$ , $I V$ 当且仅当不存在 $ω$ 到 $x$ 的单射.

证明. 逐一验证.

1.

$I$ 是标准有限/Kuratowski 有限: 来证明 $isFin (x) \to isFin_{I} (x) \to isKFin (x)$ .

1.

$isFin (x) \to isFin_{I} (x)$ : 如果 $x$ 已经与自然数 $n$ 有了双射, 由有穷性记号的势不变性, 我们只要对自然数 $n$ 验证 $isFin_{I} (n)$ . 查找自然数有穷引理的证明即可.

2.

$isFin_{I} (x) \to isKFin (x)$ : 如果 $x$ 已知 $I$ 有穷, 来验证它同样 Kuratowski 有穷; 换言之, 给定一个 $s \subseteq ℘ (x)$ 满足诸条件, 我们要验证 $s = ℘ (x)$ . $s \subseteq ℘ (x)$ 带进 $I$ 有穷的条件可见其极大元必须是 $x$ (否则它可以并一个单点集, 从而与极大性矛盾), 我们只要继续验证 $\forall y \subseteq x (y \in s)$ . 分离 $s_{y} = {t \in s ∣ t \subseteq y} \subseteq ℘ (x)$ , 我们断言其极大元恰好是 $y$ , 从而总有 $y \in s_{y} \subseteq s$ ; 这一断言的证明过程也是完全相同的.

2.

$I \to I a$ : 证逆否, 若 $x$ 不是 $I a$ 有穷的, 则 $x$ 是两个不标准有限 (进而特别地不空) 集的不交并, 因此 $x$ 有一个不标准有限的真子集, $x$ 也就不可能标准有限.

3.

$I a \to II$ : 反证, 若 $x$ 有一个不空子集族链 $s$ 无极大元, 但同时又有 $x$ 的两个不交子集必至少有一个标准有限. 因为 $s$ 不空, 任取 $t \in s$ , 有 $t$ 与 $(⋃ s) \ t$ 是 $x$ 的两个不交子集. 若后者标准有限, 则可归纳证明 $s$ 有极大元, 因此只能是前者标准有限, 即 $\forall t \in s (isFin (t))$ , 替代公理模式进而给出从 $s$ 到 $ω$ 的一个子集 $s^{'}$ 的保序双射 (取 $t \in s$ 双射到的 $n$ ). 如果 $s^{'}$ 是 $I$ 有穷的, 则 $s^{'}$ 有极大元, 即 $s$ 有极大元, 矛盾, 故必有 $s^{'}$ 不是 $I$ 有穷的, 再注意到 $s^{'} \subseteq ω$ , 用替代公理模式就能得知存在 $s^{'}$ 到 $ω$ 的保序双射 (任给 $n \in s^{'}$ 存在 $m \in ω$ 使得 $n$ 是第 $m$ 个数), 换言之 $s$ 到 $ω$ 有保序双射. 假定 $s = {t_{n} ∣ n \in ω}$ 从小到大排好, 我们令 $y = ⋃_{n \in ω} (t_{2 n + 1} \ t_{2 n})$ , $z = ⋃_{n \in ω} (t_{2 n + 2} \ t_{2 n})$ , 则 $y \cap z = \emptyset$ , 且容易验证二者均是标准无穷集, 矛盾.

4.

$II \to III$ : 我们利用 $III = Δ_{4}$ 证逆否, 即若存在 $x$ 到 $ω$ 的满射, 则存在 $x$ 的不空子集族链无极大元. 显然若 $f : x \to ω$ 是满射, 只需取不空子集族单调升链 $f^{- 1} (┌ n ┐)$ , 不难验证其无极大元; 注意这个子集族由替代公理模式得证是集合.

5.

$III \to V^{''}$ : 证逆否, 若存在 $℘ (x)$ 到 $┌ 2 ┐ \times ℘ (x)$ 的双射, 则存在 $℘ (x)$ 到其真子集 $p$ 的双射; 直接取 ${\emptyset} \times ℘ (x)$ 的逆像即可.

6.

$V^{''} \to Δ_{5}$ : 证逆否, 若存在 $x$ 到 $Succ (x)$ 的满射, 则存在 $℘ (x)$ 到 $┌ 2 ┐ \times ℘ (x)$ 的双射. 事实上由 Cantor-Bernstein-Schroeder 定理不妨设 $f : x \to Succ (x)$ 是双射, 我们知道 $f^{- 1} : ℘ (Succ (x)) \to ℘ (x)$ 同样是双射, 同时我们还有自然的双射 $g : ┌ 2 ┐ \times ℘ (x) \to ℘ (Succ (x)), (\emptyset, t) \mapsto t, ({\emptyset}, t) \mapsto t \cup {x}$ , 两个双射合起来即得.

7.

$Δ_{5} \to I V$ : 证逆否, 若存在 $x$ 到其真子集 $y$ 的双射, 则存在 $x$ 到 $Succ (x)$ 的满射; 把 $y$ 双射到 $x$ , 然后把 $x \ y$ 全部打到 ${x}$ 单点上即可.

8.

$I V \to V$ : 证逆否, 若存在 $x$ 到 $┌ 2 ┐ \times x$ 的双射, 则存在 $x$ 到其真子集 $y$ 的双射; 同样直接取 ${\emptyset} \times x$ 的逆像即可.

9.

$V \to V I$ : 证逆否, 若 $x$ 至少有两个点且有 $x \times x$ 到 $x$ 的双射, 则存在 $x$ 到 $┌ 2 ┐ \times x$ 的双射; 把这两个点双射为 $┌ 2 ┐$ , 然后用 Cantor-Bernstein-Schroeder 定理.

10.

$V I \to V II$ : 证逆否, 若 $x$ 上有良序且标准无穷, 则 $x$ 至少有两个点且有 $x \times x$ 到 $x$ 的双射; 这时 $x$ 同构于某无穷序数, 对此序数使用 Godel Pairing Function 即得.

11.

$V II \to V I I^{''}$ : 若 $x$ 标准有穷则 $℘ (x)$ 亦标准有穷, 若 $x$ 不可良序化则 $℘ (x)$ 亦不可良序化.

12.

$II \to Δ_{3}$ : 我们利用 $II = Δ_{2}$ 证逆否, 即若 $x$ 有无穷子集可线序化则 $x$ 有无穷可线序化分划. 这个分划以线序化的无穷子集中的每个单点和这无穷子集的补集构成, 其上线序自然继承 (把补集弄到最小元或最大元的地方即可).

13.

$Δ_{3} \to I V$ : 我们利用 $I V$ 当且仅当不存在 $ω$ 到 $x$ 的单射证逆否, 即若有 $ω$ 到 $x$ 的单射, 则有 $x$ 的无穷可线序化子集; 这是平凡的, 因为单射的像集甚至是无穷可良序化子集.

14.

$I V \to D$ : 证逆否, 若 $x$ 既非空集也非单点集, 且 $y \cup z = x$ 推出有 $x$ 到 $y$ 的双射或有 $x$ 到 $z$ 的双射, 来证明有 $x$ 到其真子集的双射. 由于 $x$ 不空, 取 $a \in x$ ; 现在 $x \ {a}$ 是 $x$ 的真子集, 且 ${a} \cup (x \ {a}) = x$ . 由于 $x$ 不是单点集, $x$ 到 ${a}$ 无双射, 故 $x$ 到 $x \ {a}$ 有双射, 即为所求.

15.

$D \to V II$ : 证逆否, 若 $x$ 无穷且可良序化, 则 $x$ 既非空集也非单点集, 且 $y \cup z = x$ 能推出有 $x$ 到 $y$ 的双射或有 $x$ 到 $z$ 的双射. $x$ 既非空集也非单点集是显然的, 因为我们在这前提下不妨设 $x$ 是个无穷序数 $θ \geq ω$ . 由于 $ZF$ 可证 $ℵ_{α} + ℵ_{β} = ℵ_{max (α, β)}$ , 结论是显然的.

16.

$V^{''} \to V I^{''}$ : 这是因为 $V \to V I$ .

17.

$V I^{''} \to V$ : 若 $℘ (x)$ 是 $V I$ 有穷的, 由于 $℘ (x)$ 至少是单点集, 要不然 $x = \emptyset$ (此时 $℘ (x) = {\emptyset}$ 是单点集), 要不然不存在 $℘ (x) \times ℘ (x)$ 到 $℘ (x)$ 的双射; 我们证明后情况发生时同样不存在 $┌ 2 ┐ \times x$ 到 $x$ 的双射. 反证, 若存在 $┌ 2 ┐ \times x$ 到 $x$ 的双射, 则同样有 $┌ 2 ┐^{┌ 2 ┐ \times x}$ 到 $┌ 2 ┐^{x}$ 的双射, 前者自然双射于 $(┌ 2 ┐^{x})^{┌ 2 ┐}$ 而自然双射于 $℘ (x)^{(2)}$ , 后者自然双射于 $℘ (x)$ , 于是构造完成.

18.

$I = II I^{''}$ : 分两个方向证明.

1.

$I \to II I^{''}$ : 由于熟知 $I^{''} = I$ , 直接由 $I \to III$ 有 $I = I^{''} \to II I^{''}$ .

2.

$II I^{''} \to I$ : 利用 $Δ_{4} = III$ 施行反证, 若 $x$ 无穷, 即对任意自然数 $n$ 均不存在 $n$ 到 $x$ 的双射, 我们证明存在 $℘ (x)$ 到 $ω$ 的满射. 归纳不难证明对任意自然数 $n$ 均存在 $x$ 的真子集 $y_{n}$ 与之双射, 于是我们直接令满射 $f : ℘ (x) \to ω$ 为 $y \mapsto n$ 若 $y$ 双射于 $n$ ( $n \neq = \emptyset$ ), 或 $y \mapsto \emptyset$ 若 $y = \emptyset$ 或不存在 $n \in ω$ 双射于 $y$ .

19.

$III = I V^{''}$ : 由定义显然.

20.

$Δ_{1} = I a$ : 由定义显然.

21.

$Δ_{2} = II$ : 分两个方向证明.

1.

$Δ_{2} \to II$ : 如果 $x$ 的任意可线序化的分划均有穷, 我们来证明其不空子集族链 $C \subseteq ℘ (x)$ 必有最大元. 对 $y \in C$ 考察 $C_{y} = {z \in C ∣ z ⫋ y}$ , 则有 $x$ 的分划 ${y \ ⋃ C_{y} ∣ y \in C} \cup (x \ ⋃ C)$ , 其上线序可指定为 $\forall y \in C ((x \ ⋃ C) < y \ ⋃ C_{y})$ 且 $y_{1} \ ⋃ C_{y_{1}} < y_{2} \ ⋃ C_{y_{2}}$ 当且仅当 $y_{1} ⫋ y_{2}$ . 于是这分划有穷, 自然有 $C$ 有穷, 进而可以取到最大元.

2.

$II \to Δ_{2}$ : 证逆否, 如果有一个 $x$ 的可线序化的分划 $P$ 无穷, 我们来构造其不空子集族链 $C \subseteq ℘ (x)$ 使之没有最大元或没有最小元. 对 $y \in P$ 考虑 $P_{y} = ⋃_{z \in P, z < y} z$ . 由于 $P$ 无穷, 其上的线序 $<$ 必然不是双良序 (注意 $ZF$ 中已有标准有限等价于近标准有限), 于是存在 $P$ 的子集 $Q$ 构成 $<$ 关系下的无穷升链或无穷降链, 对应的 $C = {P_{y} ∣ y \in Q}$ 就没有极大元或极小元.

22.

$Δ_{4} = III$ : 分两个方向证明.

1.

$III \to Δ_{4}$ : 利用 $I V$ 当且仅当不存在 $ω$ 到 $x$ 的单射 (从而 $III$ 当且仅当不存在 $ω$ 到 $℘ (x)$ 的单射) 反证, 若存在 $x$ 到 $ω$ 的满射 $f$ , 取对应的单射 $f^{- 1} : ℘ (ω) \to ℘ (x)$ 在 $ω \subseteq ℘ (ω)$ 上的限制即得 $ω$ 到 $℘ (x)$ 的单射.

2.

$Δ_{4} \to III$ : 同理反证, 若存在 $ω$ 到 $℘ (x)$ 的单射 $f$ , 通过取并集不妨设 $n < m \to f (n) ⫋ f (m)$ , 我们构造 $x$ 到 $ω$ 的满射 $g$ ; 若 $y \in x$ , 令 $n \neq = \emptyset$ 且 $y \in f (n) \land \forall m \in ω (n < m \to y \neq \in f (m))$ 时 $g (y) = n$ , $y \in f (\emptyset) \land \forall m \in ω (m \neq = \emptyset \to y \neq \in f (m))$ 或 $\forall n \in ω \exists m \in ω (n < m \land y \in f (m))$ 或 $\neg\exists n \in ω (y \in f (n))$ 时 $g (y) = \emptyset$ 即可.

23.

$I V$ 当且仅当不存在 $ω$ 到 $x$ 的单射: 分两个方向证明.

1.

$I V$ 推出此命题: 反证, 若存在 $ω$ 到 $x$ 的单射 $f$ , 则 $x$ 和其真子集 $x \ {f (\emptyset)}$ 之间有自然的双射: $f (n) \mapsto f (Succ (n))$ , 其余点不动.

2.

此命题推出 $I V$ : 同反证, 若存在 $x$ 到其真子集 $y$ 的双射 $f$ , 我们来构造 $ω$ 到 $x$ 的单射. 注意到 $y$ 是真子集, 任取一点 $a \in x \ y$ , 然后重新考察 $f$ 在 $x_{0} = y \cup {a} \subseteq x$ 上的限制 $F$ . 我们先用归纳法证明对每个 $n \in ω \ {\emptyset}$ 存在 $x_{0}$ 的子集 $x_{n}$ 与 $n$ 双射, 且存在点 $a_{n} \in x_{n}$ 使得 $F$ 限制在 $x_{n} \ {a_{n}}$ 上的像集是 $x_{n} \ {a}$ ; 直观上这直接通过令 $x_{n} = {a, F (a), F (F (a)), ...}$ 即可实现. 最后只需论证 $n \mapsto a_{n} = x_{n} \ x_{n - 1}$ 是 $ω \ {\emptyset}$ 到 $x$ 的单射, 这通过归纳给出的描述不难实现.

24.

$I = V^{''''}$ : 显然 $I = II I^{''} \to V^{''''}$ , 我们只需证明 $V^{''''} \to I$ , 换言之就是证明: 如果集合 $x$ 无穷, 则 $┌ 2 ┐ \times ℘ (℘ (x))$ 与 $℘ (℘ (x))$ 等势.

引理 3.4.0.6 (Lauchli). $x$ 无穷则 $∣ ℘ (FinSub (x)) ∣ = ∣ (℘ (FinSub (x)))^{ω} ∣$ .

证明. 我们来定义如下两种从 $℘ ([x]^{n})$ (这里 $n$ 是自然数) 到自己的映射 (下面 $k$ 同样是自然数):

1.	$g_{n, k} (a) = {y \in [x]^{n} ∣\forall z \in [x]^{k} (y \subseteq z \to \exists t \in a (t \subseteq z))}$ ;
2.	$d_{n, k} (a) = g_{n, k} (a) \ a$ .

我们断言它们有如下性质.

1.	$\forall a \subseteq [x]^{n} (a \subseteq g_{n, k} (a))$ ;
2.	$g_{n, k} \circ g_{n, k} = g_{n, k}$ ;
3.	$k \leq l \to \forall a \subseteq [x]^{n} (g_{n, k} (a) \subseteq g_{n, l} (a))$ .

来证明第一条. 如果 $y \in a$ , 我们证明 $y \in g_{n, k} (a)$ , 也就是证明 $\forall z \in [x]^{k} (y \subseteq z \to \exists t \in a (t \subseteq z))$ , 显然这 $t$ 就是 $y$ 自己.

来证明第二条. 第一条已经说明 $g_{n, k} (a) \subseteq g_{n, k} (g_{n, k} (a))$ , 只需证明倒过来的方向; 假定 $y \in g_{n, k} (g_{n, k} (a))$ , 我们要证明 $y \in g_{n, k} (a)$ . 拆掉定义我们已知 $\forall z \in [x]^{k} (y \subseteq z \to \exists t^{'} \in g_{n, k} (a) (t^{'} \subseteq z))$ , 也就是 $\forall z \in [x]^{k} (y \subseteq z \to \exists t^{'} (t^{'} \subseteq z \land \forall z^{'} \in [x]^{k} (t^{'} \subseteq z^{'} \to \exists t \in a (t \subseteq z^{'}))))$ , 而我们要证明 $\forall z \in [x]^{k} (y \subseteq z \to \exists t \in a (t \subseteq z))$ ; 给 $z$ 并有 $y \subseteq z$ , 条件给我们一个莫名其妙的 $t^{'} \subseteq z$ , 我们继续把 $z^{'}$ 取为 $z$ , 则 $t^{'} \subseteq z^{'} = z$ , 于是存在 $t \in a$ 使得 $t \in z^{'} = z$ , 这就是我们要的 $t$ .

来证明第三条. 同样证明 $\forall z \in [x]^{k} (y \subseteq z \to \exists t \in a (t \subseteq z))$ 则 $\forall z \in [x]^{l} (y \subseteq z \to \exists t \in a (t \subseteq z))$ , 这是因为后面这个大小为 $l$ 的 $z$ 可以取一个大小为 $k$ 的子 $z$ 放进条件里得到 $t$ 来作为原本这个 $z$ 的子集. 这里可以选是因为这样的子 $z$ 只有有穷多个.

现在我们接着定义 $d_{n, k}^{j}$ 为 $d_{n, k}$ 迭代复合 $j$ 个所得的函数, 当然 $d_{n, k}^{0}$ 就是恒等函数. 这个定义也就是 $d_{n, k}^{j + 1} = d_{n, k} \circ d_{n, k}^{j} = (g_{n, k} \circ d_{n, k}^{j}) \ d_{n, k}^{j}$ , 由第一条我们就可以倒过来说 $d_{n, k}^{j} = (g_{n, k} \circ d_{n, k}^{j}) \ d_{n, k}^{j + 1}$ , 这是第四条.

断言. 如果 $d_{n, k}^{j}$ 的值域不是单点集, 则 $j \leq n$ .

证明. 我们需要使用有穷版本的 Ramsey 定理. 对 $n \leq k$ 、 $y \subseteq x$ 和 $a \subseteq [x]^{n}$ , 当 $∣ y ∣ \leq n$ 时定义下列谓词:

1.	$ψ (y, a, z)$ 定义为 $z \subseteq x \ y \land \forall w \in [z]^{n - ∣ y ∣} (y \cup w \in a)$ ;
2.	$φ (y, a)$ 定义为 $\forall m \in ω \exists z \subseteq x (m \leq ∣ z ∣ \land ψ (y, a, z))$ .

注意到 $y \in a \subseteq [x]^{n}$ 时任给 $z \subseteq x \ y$ 都有 $ψ (y, a, z)$ , 换言之此时任给 $y \in a$ 都有 $φ (y, a)$ . 我们断言: 如果 $φ (y, d_{n, k} (a))$ , 则存在 $y^{'} ⊊ y$ 使得 $φ (y^{'}, a)$ ; 这立即推出不可能有 $φ (\emptyset, d_{n, k} (a))$ .

我们先来证明这个断言. 事实上我们只需证明任给 $m \geq k$ 我们都有 $y^{'} ⊊ y$ 和 $z \in [x]^{m}$ 使得 $ψ (y^{'}, a, z)$ ; 鉴于 $y$ 的真子集只有有穷多个而 $m$ 有无穷多个, 鸽巢原理指出一定就有一个 $y^{'} ⊊ y$ 见证对任意大的 $m$ 此事成立, 换言之 $φ (y^{'}, a)$ .

有穷 Ramsey 定理指出任给 $m, i, j \in ω$ , 当 $i \leq m$ 且 $j \geq 1$ 时都存在最小的 $N = N_{m, i, j} \geq m$ 使得任何 $[N]^{i}$ 的 $j$ 染色都有 $N$ 的 $m$ 大小的同质子集. 具体到这个证明中, 已有 $m \geq k$ , 我们取 $m^{'} = max {N_{m, i, 2} ∣0 \leq i \leq n}$ , 再取 $m^{''} = N_{m^{'}, k - ∣ y ∣, 2^{∣ y ∣}}$ . $φ (y, d_{n, k} (a))$ 中取 $m$ 为此 $m^{''}$ , 我们得到 $s \subseteq x$ 使得 $m^{''} \leq ∣ s ∣$ 且 $ψ (y, d_{n, k} (a), s)$ , 换言之 $s \subseteq x \ y$ 且 $\forall w \in [s]^{n - ∣ y ∣} (y \cup w \in d_{n, k} (a))$ .

对 $y$ 的每个子集 $y^{'}$ , 我们定义 $a (y^{'}) = {t \in [s]^{k - ∣ y ∣} ∣\exists t^{'} \subseteq t (y^{'} \cup t^{'} \in a)}$ , 此时必有 $⋃_{y^{'} \subseteq y} a (y^{'}) = [s]^{k - ∣ y ∣}$ . 取定 $t \in [s]^{k - ∣ y ∣}$ , 我们证明必有 $y^{'} \subseteq y$ 和 $t^{'} \subseteq t$ 使得 $y^{'} \cup t^{'} \in a$ ; 首先, $k \geq n$ 说明 $∣ t ∣ = k - ∣ y ∣ \geq n - ∣ y ∣$ , 于是我们可以随便选一个 $t$ 的大小为 $n - ∣ y ∣$ 的子集 $u$ , 根据 $ψ (y, d_{n, k} (a), s)$ 我们就有 $y \cup u \in d_{n, k} (a)$ , 于是 $y \cup u$ 本身不属于 $a$ , 但任何包含它的 $x$ 的大小为 $k$ 的 $x$ 子集都有 $a$ 中元素为其子集; $t \cup y$ 恰好是一个这样的东西, 于是有 $a$ 中元素 $v$ 为其子集, 显然 $v = (t \cap v) \cup (y \cap v)$ , 括号里就是我们要的 $t^{'}$ 与 $y^{'}$ .

现在鉴于 $m^{''} = N_{m^{'}, k - ∣ y ∣, 2^{∣ y ∣}} \leq ∣ s ∣$ , $y^{'} \subseteq y$ 又恰有 $2^{∣ y ∣}$ 个, 一定有同质子集 $s^{'} \in [s]^{m^{'}}$ 使得 $[s^{'}]^{k - ∣ y ∣}$ 被染成同色, 换言之有 $y^{'} \subseteq y$ 使得 $[s^{'}]^{k - ∣ y ∣} \subseteq a (y^{'})$ , 注意此时已有 $s^{'} \subseteq x \ y^{'}$ . 我们定义 $b = {w^{'} \in [s^{'}]^{n - ∣ y^{'} ∣} ∣ y^{'} \cup w^{'} \in a}$ , $b^{'} = [s^{'}]^{n - ∣ y^{'} ∣} \ b$ , 则它们又给出 $[s^{'}]^{n - ∣ y^{'} ∣}$ 的二色划分, 鉴于 $∣ s^{'} ∣ = m^{'} \geq N_{m, n - ∣ y^{'} ∣, w}$ 我们又得到同质子集 $z \in [s^{'}]^{m}$ , $[z]^{n - ∣ y^{'} ∣}$ 或者是 $b$ 的子集或者是 $b^{'}$ 的子集.

我们说明这 $z$ 就是断言所要的, 让 $ψ (y^{'}, a, z)$ 成立的 $z$ . 这也就是要证明 $[z]^{n - ∣ y^{'} ∣}$ 一定是 $b$ 的子集, 而我们其实只需证明它与 $b$ 交不空; 注意到 $[z]^{k - ∣ y ∣} \subseteq [s^{'}]^{k - ∣ y ∣} \subseteq a (y^{'})$ , 任何 $z$ 的大小为 $k - ∣ y ∣$ 的子集都有与 $y^{'}$ 之并属于 $a$ 的子集, 而我们这里最终得到的子集就见证了一开始所要的交集不空. 当然还要证明 $y^{'} ⊊ y$ , 这是因为 $y^{'} = y$ 时, $ψ (y, d_{n, k} (a), s)$ 显然说明 $ψ (y^{'}, d_{n, k} (a), z)$ , 又有 $ψ (y^{'}, a, z)$ , 但 $d_{n, k} (a)$ 与 $a$ 不交, 这只能说明 $[z]^{n - ∣ y ∣}$ 空, 但这是不可能的.

证完了里面这层断言, 我们来证明一开始想要的断言. 任取

y \in d_{n, k}^{j} (a)

,

∣ y ∣ = n

说明任给

z \subseteq x \ y

都有

ψ (y, d_{n, k}^{j} (a), z)

, 于是

x

无穷就说明

φ (y, d_{n, k}^{j} (a))

; 重复用上断言我们将得到一列

y = y_{j} ⊋ y_{j - 1} ⊋ ... ⊋ y_{0}

, 于是

n = ∣ y_{j} ∣ \geq j

.

$□$

作为这个断言的推论, 我们立即知道

d_{n, k}^{n} = g_{n, k} \circ d_{n, k}^{n}

, 这是第五条.

现在我们来定义 $f_{n, k} : ℘ ([x]^{n}) \to ℘ ([x]^{k}), a \mapsto {y \in [x]^{k} ∣\exists z \in a (z \subseteq y)}$ , 并令 $I_{n, k} = {a \in [x]^{n} ∣ g_{n, k} (a) = a}$ , 最后令 $\overset{ˉ}{f}_{n, k} = f_{n, k} ↾ I_{n, k}$ . 显然 $k \leq l$ 时 $I_{n, l} \subseteq I_{n, k}$ , 这是第六条. 我们额外证明 $\overset{ˉ}{f}_{n, k}$ 单: 假定 $g_{n, k} (a_{1}) = a_{1}$ 而 $g_{n, k} (a_{2}) = a_{2}$ , 若 $\overset{ˉ}{f}_{n, k} (a_{1}) = f_{n, k} (a_{1}) = f_{n, k} (a_{2}) = \overset{ˉ}{f}_{n, k} (a_{2})$ , 则 $a_{1} \subseteq g_{n, k} (a_{2}) = a_{2}$ 而 $a_{2} \subseteq g_{n, k} (a_{1}) = a_{1}$ , 换言之 $a_{1} = a_{2}$ .

我们终于准备好来定义单射 $F : (℘ (FinSub (x)))^{ω} \to ℘ (FinSub (x))$ 了: 对 $A = {a_{s} \subseteq FinSub (x) ∣ s \in ω}$ , 令 $k (s, n, j) = 2^{s} \cdot 3^{n} \cdot 5^{j}$ , $F (A) = s \in ω ⋃ n \in ω ⋃ (0 \leq j \leq n ⋃ f_{n, k (s, n, j)} \circ g_{n, k (s, n, n)} \circ d_{n, k (s, n, n)}^{j} (a_{s} \cap [x]^{n}))$

只需验证

F

单. 方便起见, 记

a_{s, n} = a_{s} \cap [x]^{n}

,

a_{s, n, j} = g_{n, k (s, n, n)} \circ d_{n, k (s, n, n)}^{j} (a_{s, n})

,

b_{s, n, j} = f_{n, k (s, n, j)} (a_{s, n, j})

, 则构造即为

F (A) = ⋃_{s \in ω} ⋃_{n \in ω} (⋃_{0 \leq j \leq n} b_{s, n, j})

. 鉴于

b_{s, n, j} \subseteq [x]^{k (s, n, j)}

且

k (s, n, j)

作为函数单, 我们其实知道

b_{s, n, j} = F (A) \cap [x]^{k (s, n, j)}

. 第二条说

a_{s, n, j} \in I_{n, k (s, n, n)}

,

j \leq n

和第六条又说

a_{s, n, j} \in I_{n, k (s, n, j)}

, 于是事实上

b_{s, n, j} = \overset{ˉ}{f}_{n, k (s, n, j)} (a_{s, n, j})

, 不妨倒过来写成

a_{s, n, j} = \overset{ˉ}{f}_{n, k (s, n, j)}^{- 1} (b_{s, n, j})

. 第四和第五条说

a_{s, n} = a_{s, n, 0} \ (a_{s, n, 1} \ (... (a_{s, n, n - 1} \ a_{s, n, n})))

, 而

a_{s} = ⋃_{n \in ω} a_{s, n}

, 这给出了从

F (A)

算出

A

的完整方案.

$□$

现在我们不但要证明

┌ 2 ┐ \times ℘ (℘ (x))

与

℘ (℘ (x))

等势, 其实还要证明

℘ (ω) \times ℘ (℘ (x))

与

℘ (℘ (x))

等势. 我们记

InfSub (x) = ℘ (x) \ FinSub (x)

, 则

℘ (℘ (x))

显然与

℘ (FinSub (x)) \times ℘ (InfSub (x))

等势; Lauchli 引理弱化一下说

℘ (FinSub (x))

与

(℘ (FinSub (x)))^{2}

等势, 而显然又有

℘ (FinSub (x))

被

℘ (ω)

单射, 于是显然.

$□$

评注. 其实这里还有三个没被比较的有穷性: $Δ_{3}^{''}$ , $Δ_{5}^{''}$ 和 $D^{''}$ . 注意很多有穷性都表述为某个对象的不存在, 且证明中也常常反证, 我们在直觉主义集合论里理应把这些证明视作对应的无穷性之间的强弱关系.

显然, 如果我们有选择公理 (任何集合均可良序化), 则最强的 $I$ 有穷和最弱的 $V I I^{''}$ 有穷都是等价的, 所以这个有穷性层级就全部坍塌了; 我们现在倒过来考虑这个层级在哪里坍塌能引发全部的坍塌.

定义 3.4.0.7. 我们简写下列关于有穷性的命题.

1.	$E (Q_{1}, Q_{2})$ : 两个有穷性 $Q_{1}$ 与 $Q_{2}$ 等价, $\forall x (isFin_{Q_{1}} (x) \leftrightarrow isFin_{Q_{2}} (x))$ .
2.	$C (Q)$ : $Q$ 有穷的非空集族上存在选择函数, $\forall x (\forall y \in x \exists z \in y \land isFin_{Q} (x) \to \exists f \exists z (z = ⋃ x \land isFunOn (f, x, z) \land \forall y \in x (f (y) \in y)))$ .
3.	$C^{-} (Q)$ : $Q$ 有穷的标准无穷非空集族上存在部分选择函数, $\forall x (\forall y \in x \exists z \in y \land isFin_{Q} (x) \land \neg isFin (x) \to \exists f \exists z \exists w (w \subseteq x \land \neg isFin (w) \land z = ⋃ w \land isFunOn (f, w, z) \land \forall y \in w (f (y) \in y)))$ .

这些定义首先直接给出一些显然的事实.

定理 3.4.0.8 ( $ZF$ ). 我们给出以下事实, 不加证明.

1.	$C (I)$ 且 $C^{-} (I)$ .
2.	任给有穷性 $Q$ 总有 $E (I, Q) \to C (Q)$ 且 $C (Q) \to C^{-} (Q)$ .
3.	任给有穷性满足 $Q_{1} \to Q_{2}$ , 总有 $C (Q_{2}) \to C (Q_{1})$ 且 $C^{-} (Q_{2}) \to C^{-} (Q_{1})$ .

这立即指出, 我们可以将有穷性的强度列表复制两份并反转箭头方向, 作为对应的 $C (Q)$ 和 $C^{-} (Q)$ 的强度列表; 而且还能平行地指出 $C (Q) \to C^{-} (Q)$ 这一系列箭头. 这一整张表上可加入还有许多, 例如 $Q_{1} \to Q_{2}$ 但 $C^{-} (Q_{2}) \to C (Q_{1})$ 有哪些可能, $Q_{1} \to Q_{2}$ 但 $C (Q_{1}) \to C^{-} (Q_{2})$ 有哪些可能, 诸多 $E (Q_{1}, Q_{2})$ 的强度, 以及诸多推断的独立性等等; 笔者也不确定这张表现在可以做到多完善, 但想来并非所有能问的问题都已被解答. 我们只是指出一些已知与 $A C$ 等价的命题.

定理 3.4.0.9 ( $ZF$ ). $A C$ 与下列命题中的每一个都等价: $E (I, D)$ , $E (I, V I)$ , $E (V, V I)$ , $E (V I, V II)$ , $C (V II)$ , $C (V I I^{''})$ .

证明. $A C$ 推出这一系列命题中的每个; 已知 $I \to D$ , $I \to V I$ , $V \to V I$ , $V I \to V II$ 和 $C (V I I^{''}) \to C (V II)$ , 因此只需证明下列命题:

1.

$C (V II) \to A C$ : 我们显然不是冲着选择公理 $A C$ 去的, 而是冲着良序原则 $W O$ 去的. 我们指出以下重要引理.

引理 3.4.0.10 ( $ZF$ ). 若 $C (Q)$ 且 $℘ (x)$ 是 $Q$ 有限的, 则 $x$ 可良序化.

证明. 若

℘ (x)

是

Q

有限的, 则

℘ (x) \ {\emptyset}

仍然是

Q

有限的, 于是

C (Q)

指出存在其选择函数

F : ℘ (x) \ {\emptyset} \to x

, 接下来的过程照抄

A C \to W O

的证明即可.

$□$

现在假定

C (V II)

, 我们来证明每个集合都可良序化. 反证, 若

x

不可良序化, 则

℘ (x)

必须也不可良序化, 于是

℘ (x)

是

V II

有限的, 这由引理又说明

x

是可良序化的, 矛盾.

2.

$(D \to I) \to A C$ : 我们需要一个中间形式.

定义 3.4.0.11. 令 $CN 4$ 为以下命题: $\forall x \forall y (\exists f (isInjOn (f, ω, y)) \to \exists f (isBijOn (f, x \cup y, x) \lor isBijOn (f, x \cup y, y)))$ .

我们来证明

(D \to I) \to CN 4

且

CN 4 \to W O

.

1.

$(D \to I) \to CN 4$ : 注意到 $x \cup y = x \cup y$ 直接满足 $D$ 无穷的使用条件, 只需证明此时 $x \cup y$ 是 $I$ 无穷的 (即不能被任何自然数双射到). 否则, $y \subseteq x \cup y$ 也会是 $I$ 有穷的, 这与 $y$ 是 $I V$ 无穷的矛盾.

2.

$CN 4 \to W O$ : 任给集合 $x$ , 我们证明它可良序化. 如果 $x$ 是 $I$ 有穷集则显然可良序化. 对任意 $I$ 无穷集合 $x$ , 我们取 $y$ 为其 Hartogs 数, 则自然有 $ω \leq y$ , 于是 $x \cup y$ 或者与 $y$ 双射或者与 $x$ 双射. 如果是后者, 则限制后我们会得到 $y$ 到 $x$ 的单射, 与 Hartogs 数的定义矛盾; 因此必然有 $x \cup y$ 与 $y$ 双射, 从而 $x \cup y$ 可良序化, 自然 $x$ 可良序化.

3.

$(V I \to I) \to A C$ : 首先我们给出一个引理.

引理 3.4.0.12 ( $ZF$ ). 如果 $x$ 是集合, $y$ 是可良序化的集合, $x \cap y = \emptyset$ 且 $x \cup y$ 双射于 $x \times y$ , 则 $x$ 单射到 $y$ 或 $y$ 单射到 $x$ .

证明. 假定

x \times y = x^{'} \cup y^{'}

且

x

与

x^{'}

双射、

y

与

y^{'}

双射、

x^{'} \cap y^{'} = \emptyset

. 如果存在

a \in x

使得

\forall b \in y ((a, b) \in x^{'})

, 则

b \mapsto (a, b)

给出

y

到

x^{'}

的单射; 否则

\forall a \in x \exists b_{a} \in y ((a, b_{a}) \in y^{'})

, 则

a \mapsto (a, b_{a})

给出

x

到

y^{'}

的单射.

$□$

因此, 我们不妨证明

I

无穷集合

x

与其 Hartogs 数

y

总有

x \cup y

双射于

x \times y

, 这结合引理和

y

不单射到

x

就说明

x

单射到

y

, 从而

x

可良序化. 注意显然有

x \cup y

到

x \times y

的单射, 由 Cantor-Bernstein-Schroeder 定理只需再构造一个

x \times y

到

x \cup y

的单射. 注意

x \cup y

同样显然是

I

无穷集, 条件就让它双射于

(x \cup y)^{(2)}

, 后者自然双射于

x^{(2)} \cup (┌ 2 ┐ \times (x \times y)) \cup y^{(2)}

, 而

x \times y

自然单射到这个集合, 即证.

4.

$(V I \to V) \to A C$ : 注意到上个证明中我们事实证明了以下断言: 若 $x \cup y$ 双射于 $(x \cup y)^{(2)}$ , 此处 $y$ 是 $x$ 的 Hartogs 数, 则 $x$ 可良序化. 要证明任何 $I$ 无穷集合 $x$ 都可良序化, 我们考虑证明任意 $x$ 均可嵌入一个更大的集合 $a$ 中, 且 $a$ 满足 $a \cup b$ 双射于 $(a \cup b)^{(2)}$ , 此处 $b$ 是 $a$ 的 Hartogs 数, 从而 $a$ 可良序化, 从而 $x$ 可良序化. 观察到以下事实.

断言 (杨). 任给 $I$ 无穷集合 $x$ , 若 $x \cap ω = \emptyset$ , 则总有 $z = ℘ (x \cup ω)$ 满足 $z$ 与 $┌ 2 ┐ \times z$ 双射.

证明. 显然只要造

┌ 2 ┐ \times z

到

z

的单射. 我们令

(\emptyset, x^{'} \cup s) \mapsto x^{'} \cup {\emptyset} \cup {2 n + 2∣ n \in s}

而

({\emptyset}, x^{'} \cup s) \mapsto x^{'} \cup {{\emptyset}} \cup {2 n + 3∣ n \in s}

即可, 这里

2 n + 2

是自然数运算.

$□$

现在对

I

无穷集合

x

, 不妨设

x \cup ω = \emptyset

, 用断言将

x

嵌入

z

中, 假设

z

的 Hartogs 数是

y

, 又不妨设

z \cap y = \emptyset

, 于是

┌ 2 ┐ \times (z \cup y)

自然双射于

z \cup y

, 于是由

V I \to V

知

(z \cup y)^{(2)}

同样双射于

z \cup y

, 于是

z

可良序化, 进而

x

可良序化, 证毕.

5.

$(V II \to V I) \to A C$ : $V I$ 无穷推出 $V II$ 无穷和 Godel Pairing Function 共同保证了任意 $I$ 无穷集合 $x$ 均满足 $x \times x$ 双射于 $x$ , 也就是说 $(V II \to V I) \to (V I \to I)$ .

$□$

名字空间

视图

3.4. ZF 中的有限性