ZF集合论 II —— 无穷公理、序数

序数 (Ordinals)

传递集与序数的定义

定义：传递集 (transitive)

一个集合 $x$ 是传递集当且仅当对于 $x$ 的每一个元素，都是 $x$ 的子集.

传递集的例子如下：

\[ 0,\left\lbrace 0\right\rbrace, \left\lbrace 0, \left\lbrace 0\right\rbrace \right\rbrace \]

如果 $x = \left\lbrace x \right\rbrace$ ，那么 $x$ 是传递集，但是这个集合实际上是一个非常古怪的研究对象. 它和正则公理有关（在后续会详细说明）.

传递集的传递来源于 $\in$ 关系的传递性，记 $x$ 为传递集等价于满足如下的语句：

\[ \forall y (y\in x\to y \subset x) \]

这个语句等价于

\[ \forall u\forall v (u\in v\in x\to u\in x) \]

定义：序数

$x$ 是一个序数，如果 $x$ 是传递集且在 $\in$ 的意义下良序.

例如，

\[ \left\lbrace 0, \left\lbrace 0 \right\rbrace \left\lbrace \left\lbrace 0 \right\rbrace \right\rbrace \right\rbrace \]

不是序数，因为 $0\in \left\lbrace 0 \right\rbrace, \left\lbrace 0 \right\rbrace \in \left\lbrace \left\lbrace 0 \right\rbrace \right\rbrace$ ，但是 $0\notin \left\lbrace \left\lbrace 0 \right\rbrace \right\rbrace$ ，也就是不满足传递性. $\square$

序数的性质

序数的性质 (Kunen)

如果 $x$ 是一个序数，且 $y\in x$ ，那么 $y$ 是一个序数且 $y=\mathrm{pred}(x,y)$ .
如果 $x,y$ 均为序数且 $x\cong y$ ，那么 $x=y$ .
如果 $x,y$ 均为序数，那么三种情形之一成立：$x=y,x\in y, y\in x$ .
如果 $x,y$ 和 $z$ 都是序数，$x\in y$ 且 $y\in z$ ，那么 $x\in z$ .
如果 $C$ 是一个仅包含序数的非空集，那么 $\exists x\in C \forall y\in C (x\in y \lor x=y)$ .

(1) 先验证 $y$ 传递，且 $\in_y$ 将 $y$ 良序.

先验证 $y$ 传递，$\forall u\forall v$ 满足 $u\in v\in y$ 时，由 $v\in y\in x$ 及 $x$ 传递可知 $v\in x$ ，再由 $u\in v\in x$ 可知 $u\in x$ ，从而 $u,v,y\in x$ . 由 $\in_x$ 是 $x$ 上的全序，从 $u\in v\in y$ 可得 $u\in y$ ，因此 $y$ 传递.

再证 $\in_y$ 将 $y$ 良序，由 $y\in x$ 以及 $x$ 传递可知 $y\subset x$ ，于是 $\in_y$ 是 $\in_x$ 在 $y$ 上的限制，因此良序保持.

(4) 就是传递性，显然.

序数的性质 (Jech)

$0=\varnothing$ 是一个序数；
如果 $\alpha$ 是一个序数且 $\beta \in \alpha$ ，那么 $\beta$ 是一个序数；
如果 $\alpha \neq \beta$ 是一个序数，且 $\alpha \subset \beta$ ，那么 $\alpha\in \beta$ .
如果 $\alpha$ 和 $\beta$ 均为序数，那么要么 $\alpha \subset \beta$ ，要么 $\beta \subset \alpha$.

(4) 证明：反证
令 $\gamma = \alpha\cap \beta$ ，则 $\alpha \subset \beta$ 或者 $\beta \subset \alpha$ ，若不然，则

\[ \gamma \neq \alpha, \gamma \neq \beta \]

又 $\gamma \subset \alpha$ 且 $\gamma \subset \beta$ ，故根据 (3) 可以知道

\[ \gamma\in \alpha, \gamma \in \beta \]

从而 $\gamma \in \gamma$ ，这和 $\in$ 为良序是矛盾的. $\square$

定理：所有序数组成的类是真类

\[ \neg \exists z\forall x (x\text{ is an ordinal }\to x\in z) \]

假设所有序数组成的类是集合，设为 $ON$ ，根据 Jech 序数性质 (2) ，$ON$ 也是序数，那么 $ON \in ON$ ，这和 $\in$ 是良序是矛盾的. $\square$

序数和良序集的关系

定理

如果 $\left\langle A,R \right\rangle$ 是一个良序集，那么存在唯一的序数 $C$ 使得
$$ \left\langle A,R \right\rangle\cong C. $$

首先同构的两个序数必相等，因此唯一性成立，考虑存在性，令

\[ B = \left\lbrace a\in A : \exists x \text{ 是序数使得 } \left\langle \mathrm{pred}(A,a,R),R \right\rangle\cong x \right\rbrace \]

构造 $B$ 上的函数 $f$ ，令 $f(a)= x$ ，记 $C = \mathrm{ran}(f) \subset ON$ ，根据替换公理，可知 $C$ 为集合，可以验证 $C$ 是传递的，从而 $C$ 为序数. 不难看到 $f$ 就是 $\left\langle B,R \right\rangle$ 和 $C$ 之间的同构. 若 $a\in B$ ，$a'\in A$ 满足 $a' R a$ ，则 $a' \in B$ .

分两种情形讨论：
➀ $B=A$ ，存在性得证.

➁ $B \neq A$ ，这时 $B$ 是 $A$ 的真子集，取 $A \setminus B$ 的 $R$ 最小元 $b$ ，则 $B = \mathrm{pred}(A,b,R)$ ，于是由 $\left\langle B,R \right\rangle \cong C$ 可知 $b\in B$ ，矛盾！ $\square$

我们将这个唯一的序数记为 $C = \mathrm{type}(\left\langle A,R \right\rangle)$ . 我们称其为序型.

对于序数，由于其特殊性质，做如下的符号约定：

符号约定

用希腊字母代表序数，例如 $\alpha,\beta,\gamma$ .
用 $\alpha< \beta$ 来代替 $\alpha \in \beta$ .
用 $\alpha \leqslant \beta$ 代替 $\alpha\in \beta\lor \alpha = \beta$ .

序数的上确界

定义：序数的确界

如果 $X$ 是一个序数的集合，那么
$$ \mathrm{sup}(X) = \bigcup X $$
如果 $X\neq 0$ ，有
$$ \min (X) = \bigcap X. $$

后继

定义：后继

\[ S(\alpha) = \alpha\cup \left\lbrace \alpha \right\rbrace. \]

如下的表格展示了递推的关系：

\[ \begin{array}{cccc} 0 & S(0) & S(S(0)) & S(S(S(0))) \\ \hline 0 & \left\lbrace 0 \right\rbrace & \left\lbrace 0, \left\lbrace 0 \right\rbrace \right\rbrace & \left\lbrace 0, \left\lbrace 0 \right\rbrace, \left\lbrace 0, \left\lbrace 0 \right\rbrace \right\rbrace \right\rbrace \end{array} \]

我们可以发现，从自然数的角度来看，这不就是一个自然数的一一对应吗？所以有如下的定义：

定义：自然数（通俗理解）

\[ 1=S(0),2=S(1),3=S(2),\cdots \]

也就是

\[ 1= \left\lbrace 0 \right\rbrace,2 = \left\lbrace 0,1 \right\rbrace, 3 = \left\lbrace 0,1,2 \right\rbrace \cdots \]

当然，这还只是一个通俗的定义，我们还需要引入一些概念.

定义：后继序数 (successor)、极限序数 (limit ordinal)

$\alpha$ 是一个后继序数，如果 $\exists \beta (\alpha = S(\beta))$ .

$\alpha$ 是一个极限序数，如果 $\alpha\neq 0$ 且 $\alpha$ 不为后继序数.

定义：自然数

$\alpha$ 是一个自然数，如果
$$ \forall \beta \leqslant \alpha( \beta =0 \lor \beta \text{ 是一个后继序数}) $$

无穷公理、自然数

无穷公理

公理 7 ： 无穷公理

\[ \exists x (0 \in x\land \forall y \in x(S(y)\in x)) \]

这个公理描述了一个这样的集合 $x$ ：若 $0\in x$ 且对于任意 $y\in x$ ，都有其后继 $S(y)\in x$ ，那么我们称 $x$ 是一个归纳集 (induction set).

可以证明，自然数集是最小的归纳集.

自然数集

定义：自然数集

$\omega$ 为自然数集.

$\omega$ 是一个序数，且 $\omega$ 是一个极限序数.

Peano 公理

Peano 公理已在一阶逻辑的算数部分提过，在此略过.

序数的运算

序数加法

定义：加法

我们定义加法：
$$ \alpha+\beta = \mathrm{type}(\alpha\times \left\lbrace 0 \right\rbrace \cup \beta \times \left\lbrace 1 \right\rbrace,R) $$
其中 $R$ 为以下 $3$ 个集合的并：

$\left\lbrace \left\langle \left\langle \xi,0 \right\rangle, \left\langle \eta,0 \right\rangle \right\rangle: \xi < \eta < \alpha \right\rbrace$ ；
$\left\lbrace \left\langle \left\langle \xi,1 \right\rangle, \left\langle \eta,1 \right\rangle \right\rangle: \xi < \eta < \beta \right\rbrace$ ；
$[(\alpha\times \left\lbrace 0 \right\rbrace)\times (\beta \times \left\lbrace 1 \right\rbrace)]$.

这个定义看着有点让人摸不着头脑，这里稍微多说明一下。

首先，Kunen 教材用一个例子说明这个定义：将 $2$ 个苹果和 $3$ 个香蕉放在一起，那么就有 $5$ 个水果. 这个就是定义的一个通俗说法，在这个定义中，区分不同种类的方法就是有序对中的第二个数.

对于 $R$ ，为什么要是这三个集合的并？第一个集合保证了 $\alpha$ 中元素对 $0$ 的一个序关系，第二个集合类似是 $\beta$ 对 $1$ 的序关系. 最后一个集合是 $\alpha+\beta$ 一个整体的良序.

其中的核心就是“怎么数”的问题，$2+3$ 就是先数 $2$ 个，再数 $3$ 个，$\alpha+\beta$ 就是先数 $\alpha$ 再数 $\beta$ ，那么就有

\[ \left\langle 0,0 \right\rangle < \left\langle 1,0 \right\rangle < \cdots < \left\langle 0,1 \right\rangle < \left\langle 1,1 \right\rangle < \cdots \]

定理：加法性质

对于任意的 $\alpha, \beta, \gamma$ ，

$(\alpha+\beta)+\gamma = \alpha+(\beta+\gamma)$ ；
$\alpha+0 = \alpha$；
$\alpha+1 = S(\alpha)$ ；
$\alpha+S(\beta) = S(\alpha+\beta)$.
如果 $\beta$ 是极限序数，那么 $\alpha+\beta = \sup\left\lbrace \alpha+\xi: \xi< \beta \right\rbrace$ .

但是需要注意的是，序数加法并不满足交换律，例如：

\[ \begin{aligned} & 1+ \omega = \omega \\ & \omega+1 = S (\omega) \end{aligned} \]

这个地方相对比较难理解，就通过图示进行说明.

首先，序数本质上和自然数还是不一致的，加法运算得到的是一个良序集的序型，因此，对于运算结果的理解，最重要的还是要落到同构的意义.

上图是对 $1+\omega$ 得到的结果的理解，我们将 $1$ 放在结果良序集的开始，那么我们实际在数的时候，也就是错开了一位，我们还是能将其与 $\omega$ 作同构.

但是对于 $\omega+1$ ，根据上图，我们是在 $\omega$ 的后面加上了这么一个元素，此时它理应与 $S(\omega)$ 同构. （最主要的原因还是在无穷之前数这个元素还是无穷之后）.

你可能还是会觉得：后者难道不也能有一一对应吗？但是这里我们要强调，这是序数的加法，而非基数的加法，无穷集当中，序数和基数是有本质区别的.

有了加法，定义乘法就比较容易了，定义乘法 $\alpha\cdot \beta$ 表示把 $\alpha$ 数 $\beta$ 次，也就是

\[ \alpha+ \alpha+\cdots+ \alpha \]

上述共有 $\beta$ 个 $\alpha$ .

定义：乘法

\[ \alpha\cdot \beta = \mathrm{type}(\beta\times \alpha, R) \]

其中 $R$ 是 $\beta\times \alpha$ 序关系，满足：

\[ \left\langle \xi,\eta \right\rangle R \left\langle \xi',\eta' \right\rangle \leftrightarrow (\xi< \xi' \lor (\xi = \xi'\land \eta< \eta')) \]

乘法同样不满足交换律，例如：

\[ \begin{aligned} & 2 \cdot \omega = \omega \\ & \omega\cdot 2 = \omega + \omega \end{aligned} \]

定理：乘法性质

对于任意的 $\alpha,\beta,\gamma$ ：

$\alpha\cdot (\beta\cdot \gamma) = (\alpha\cdot \beta)\cdot \gamma$ .
$\alpha\cdot 0 = 0$ ;
$\alpha\cdot 1=1$ ;
如果 $\beta$ 是一个极限序数，$\alpha\cdot \beta= \sup\left\lbrace \alpha\cdot \xi: \xi< \beta \right\rbrace$ ;
$\alpha\cdot(\beta+\gamma) = \alpha\cdot \beta+ \alpha\cdot \gamma$ .

注意分配律的顺序，另一方向的分配律是不成立的：

\[ (1+1)\cdot \omega = \omega \neq 1\cdot \omega+ 1\cdot \omega = \omega+ \omega \]

例题

$$ \alpha+\beta = \omega\cdot \omega+1 $$
有无穷多组 $(\alpha,\beta)$ 满足上式，试着全部找出来.

首先显然有

\[ \begin{cases} \alpha = \omega\cdot \omega, \\ \beta = 1 \end{cases}, \begin{cases} \alpha = \omega\cdot \omega +1 , \\ \beta = 0 \end{cases} \]

且二者中间不可能再有 $\omega\cdot \omega +1$ 的后继了. 由于 $\omega\cdot \omega$ 为极限序数，因此仅需考虑 $\beta$ 为极限序数 $\omega\cdot \omega$ 及其后继的情形.

若 $\beta = \omega\cdot \omega$ ，那么对于 $\alpha$ ，$\alpha< \beta$ 时，$\alpha+\omega\cdot \omega =\omega\cdot \omega$ ，与结果不符，若 $\alpha=\beta$ ，则 $\alpha+\beta = \omega\cdot \omega+\omega\cdot \omega$ ，也与结果不符.

若 $\beta = \omega\cdot \omega+1$ ，那么 $\alpha < \omega\cdot \omega$ 时，$\alpha+ \beta = \omega\cdot \omega+1$ ，因此所有 $\alpha < \omega\cdot \omega, \beta= \omega\cdot \omega+1$ 的情形都是其解. $\square$

例题

设 $\alpha$ 为序数，证明：如果对任意序数 $\beta$ ，都有
$$ \alpha+\beta = \beta+\alpha $$
则 $\alpha = 0$ .

找充分大的序数 $\beta$ ，使得 $\alpha+\beta = \beta$ ，于是由

\[ \alpha+ \beta = \beta + \alpha \]

可得 $\beta = \beta+\alpha$ ，进而由计算机集合论与逻辑第六次作业中的性质可得 $\alpha = 0$ .

那么问题来了，如何构造这样充分大的序数？我们结合乘法来操作，令 $\beta = \omega\cdot \alpha$ 即可. $\square$

有限序列

有限序列的定义

定义

$A^n$ 是从 $n$ 到 $A$ 所有函数的集合.
$A^{< \omega} = \bigcup \left\lbrace A^n: n\in \omega \right\rbrace$ .

尽管 $A^2$ 和 $A\times A$ 并不是一样的东西，但是它们之间有一个双射，考虑

\[ \begin{aligned} \eta : A^2 \to A\times A, \eta(f) = \left\langle f(0),f(1) \right\rangle \end{aligned} \]

对于 $A^n$ ，其中 $f$ 为从 $n$ 到 $A$ 的函数，那么这个函数还能看为一个长为 $n$ 的序列：

\[ f(0),f(1),\cdots,f(n-1) \]

这个定义的合理性仍然需要证明，在没有幂集公理的条件下，它并不 trivial ，利用替换公理，考虑如下的语句 $\varphi(n,y)$ ：

\[ \forall s (s\in y \leftrightarrow s\text{ 是从 }n \text{ 到 } A\text{ 的函数}) \]

由于在同构的意义下 $A^{n+1}$ 和 $A^n \times A$ 是一致的，从而利用归纳法，有

\[ \forall n \in \omega \exists y \varphi(n,y) \]

成立，唯一性由外延公理保证. 最后 $A^{< \omega}$ 用并集公理保证存在性. $\square$

定义：有限序列

对于每个 $n$ ，$\left\langle x_0,\cdots,x_{n-1} \right\rangle$ 是满足如下性质的 $\mathrm{dom}(s)=n$ 的函数 $s$ ：
$$ s(0)=x_0,s(1)=x_1,\cdots,s(n-1)=x_{n-1}. $$

有限序列的拼接 (concatenate)

对于一个函数 $s$ ，如果 $\mathrm{dom}(s)=\alpha$ 为序数，那么就是长为 $\alpha$ 的有限序列，如果 $\mathrm{dom}(t)=\beta$ ，那么就可以将 $s$ 和 $t$ 拼接在一起，形成新的函数 $s^\frown t$ ，长度为 $\alpha+\beta$ ，更严格的定义如下：

定义：有限序列拼接

如果 $s$ 和 $t$ 是满足 $\mathrm{dom}(s)=\alpha$ 且 $\mathrm{dom}(t)=\beta$ 的函数，那么定义域为 $\alpha+\beta$ 的函数 $s^\frown t$ 定义为：

$(s^\frown t)\upharpoonright \alpha = s$ ；
$(s^\frown t)(\alpha+\xi) = t(\xi),\forall \xi< \beta$ .

这个定义比较直接，不多作介绍.

对已定义符号的说明

现在对于已定义的符号，我们作一些说明. 我们自始至终实际上都在强调形式逻辑语言的基本地位，但是在这段学习当中，实际上我们引入了很多符号但是却没有作说明.

首先是 $=,\in$ 符号，这些是我们规定好的在这个框架中的关系符号，也就是说仅有两种原子公式：

$x=x$ ；
$x\in x$ .

此时，我们对之前没有细说的一些符号作补充，例如 $x \subset y$ ，实际上就是如下公式的缩写：

\[ \forall z (z\in x \to z\in y) \]

对于 $\left\lbrace : \cdots \right\rbrace$ 这个符号，也需要作特别的说明，对于

\[ \left\lbrace x: \varphi(x,y_1,\cdots,y_n) \right\rbrace \]

它就是唯一的满足如下公式的集合 $z$ ：

\[ \forall x (x\in z \leftrightarrow \varphi(x,y_1,\cdots,y_n)) \]