ZF集合论 III —— 超限归纳

本章考虑类 (class)，其形式如下：

\[ \left\lbrace x: \varphi(x) \right\rbrace \]

其中 $\varphi$ 可以有除了 $x$ 以外的自由变量.

本章对类的表示统一采用直立的粗体字母，例如 $\mathbf{ABCD}$ .

类和递归

首先，我们将之前已讨论过的序数的类和所有集合的类重新定义一遍：

定义

\[\begin{aligned}&\mathbf{V} = \left\lbrace x: x=x \right\rbrace \\ & \mathbf{ON}= \left\lbrace x: x\text{ is an ordinal} \right\rbrace. \end{aligned}\]

这两个类是我们曾讨论过的包含所有集合的类以及包含所有序数的类.

一般而言，公式和类基本没有区别，除了它们的表示方法有所不同. 在类中，我们也可以将以前的一些符号沿用过来，例如：

\[ \mathbf{ON}\cap y = \left\lbrace x\in y : x \text{ is an ordinal} \right\rbrace \]

之前定义的前段和函数都可以再理解为一个类.

超限归纳与超限递归

超限归纳

接下来我们讨论超限归纳法，这也是这一节的重点.

定理：超限归纳法 (Kunen)

如果 $\mathbf{C}\subset \mathbf{ON}$ ，且 $\mathbf{C}\neq 0$ ，那么 $\mathbf{C}$ 有最小元.

在 Kunen 集合论当中，这个和序数的性质 7.3(5) 是几乎一致的，只不过这里我们讨论的不是集合，而是类. 利用序数的性质，对 $\alpha\in \mathbf{C}$ ，如果 $\alpha$ 不是 $\mathbf{C}$ 中的最小元，那么就在 $\alpha\cap \mathbf{C}$ 中存在最小元 $\beta$ ，此时 $\beta$ 就是 $\mathbf{C}$ 中的最小元. $\square$

但是这里有一个比较显著的差别是：我们讨论的集合是 ZFC 框架下的对象，在集合的情形下，我们可以用一个语句来表达，但是在类的语境下，它不是 ZFC 的对象，此时不能用语句来表达，而是应该用定理模式来表述.

定理：$\star$ 超限归纳法 (Jech) ¹

令 $\mathbf{C}$ 为一个序数的类，且满足如下假设：

$0\in \mathbf{C}$ ；
如果 $\alpha\in \mathbf{C}$ ，那么 $\alpha+1\in \mathbf{C}$ ；
如果 $\alpha$ 为非 $0$ 极限序数，且对于所有满足 $\beta< \alpha$ 的序数 $\beta$ 都有 $\beta\in \mathbf{C}$ ，那么 $\alpha\in \mathbf{C}$ .

那么 $\mathbf{C}$ 就是 $\mathbf{ON}$ .

证明：假设 $\alpha$ 为满足是序数且 $\alpha\notin \mathbf{C}$ 的最小序数，那么此时它不能是后继序数，否则根据 2. 可知 $\alpha$ 不为满足 $\alpha\notin \mathbf{C}$ 的最小序数. 因此 $\alpha$ 必须为非 $0$ 的极限序数.

但是由于它是满足 $\alpha\notin \mathbf{C}$ 的最小序数，因此所有满足 $\beta< \alpha$ 的序数 $\beta$ 都属于 $\mathbf{C}$ ，利用 3. 可知 $\alpha\in \mathbf{C}$ ，矛盾！$\square$

看起来非常简单，但是实际上这个 $\mathbf{C}$ 代表了公式，这就给我们一个启示，如果我们的性质可以用公式表示，那么利用超限归纳法，就可以扩展到所有的序数上去. 下面给一个更易用的形式：

超限归纳法

令 $\varphi(x)$ 为一个性质，假设对所有的序数 $\alpha$ ，都有：

如果对所有的 $\beta < \alpha$ 都有 $\varphi(\beta)$ ，那么 $\varphi(\alpha)$ ，

那么 $\varphi(\alpha)$ 对所有的序数 $\alpha$ 成立.

超限归纳证明操作

“对 $\alpha$ 使用超限归纳法”的含义实际上就是上述较为易用的形式，在 Kunen 的书中即为：

\[ (\forall \beta< \alpha \psi(\beta)) \to \psi (\alpha)\tag{1.1} \]

若成立，则 $\forall \alpha \psi(\alpha)$ 成立.

为什么这个更为易用的形式与 Kunen 和 Jech 的超限归纳法是等价的？因为如果存在 $\alpha$ 使得 $\psi(\alpha)$ 不成立，那么 $\neg \psi(\alpha)$ 构成的类具有最小元 $\alpha\neq 0$ ，那么对比 $\alpha$ 小的序数利用 (1.1) 可得 $\psi(\alpha)$ 成立，这就出现了矛盾.

因此，在实际的证明中，我们直接使用这个更为易用的形式就好.

超限递归

类的函数

这里再强调有关类的函数，并集运算函数类可以写为：

\[ \mathbf{UN} = \left\lbrace \left\langle \left\langle x,y \right\rangle,z \right\rangle: z = x\cup y \right\rbrace \]

这实际上就是一个函数：$\mathbf{UN}: \mathbf{V}\times \mathbf{V}\to \mathbf{V}$ . 和以前学过的函数类似，我们同样可以对其定义域作限制：$\mathbf{UN}\upharpoonright (a\times b)$ ，有：

\[ \left\lbrace \left\langle \left\langle x,y \right\rangle, z \right\rangle : z= x\cup y \land x\in a \land y\in b\right\rbrace \]

超限递归

除了归纳，我们实际上还经常使用递归的方法定义，一个常见的例子就是数列，以及阶乘运算：

\[ \begin{cases} 0! = 1 \\ (n+1)! = n!\cdot (n+1) \end{cases} \]

这是序数 $\omega$ 上的递归. 而更广义的递推实际上就是我们接下来要引入的超限递归.

接下来引入超限递归：

定理：超限递归定理 (Kunen)

对于 $\mathbf{F}: \mathbf{V}\to \mathbf{V}$，存在一个唯一的 $\mathbf{G}:\mathbf{ON}\to \mathbf{V}$ 使得
$$ \forall \alpha\in \mathbf{ON} [\mathbf{G}(\alpha) = \mathbf{F}(\mathbf{G}\upharpoonright \alpha)]. $$

证明：对唯一性，它不难证明，因为若 $\mathbf{G}_1$ 和 $\mathbf{G}_2$ 均满足该式，那么可以利用超限归纳法证明 $\forall \alpha(\mathbf{G}_1(\alpha) = \mathbf{G}_2 (\alpha))$ .

对存在性，首先 $\mathbf{G}(0) = \mathbf{F}(0)$ 成立，若 $\mathbf{G}(\beta)(\beta<\alpha)$ 都已经存在，我们需要考虑定义

\[ \mathbf{G}(\alpha) = \mathbf{F}(\mathbf{G}\upharpoonright \alpha) \]

这就需要说明 $\mathbf{G}\upharpoonright \alpha$ 是集合.

我们称 $g$ 是一个 $\delta$ -逼近，当且仅当 $g$ 为以 $\delta$ 为定义域的函数且满足如下语句：

\[ \forall \alpha< \delta [g(\alpha)= \mathbf{F}(g \upharpoonright \alpha)]. \]

考虑 $\varphi(x,y)$ 为公式“若 $x$ 是序数，则 $y$ 是 $x$-逼近，若 $x$ 不是序数，则 $y=0$ ”. 那么不难看到

\[ \forall x \exists ! y \varphi(x,y) \]

令

\[ \mathbf{F} = \left\lbrace (x,y)\mid \varphi(x,y) \right\rbrace. \]

$\square$

序数减法和乘方

序数减法

定义：序数减法

定义 $\beta-1$ 为
$$ \beta-1 = \begin{cases}\beta, & \beta\text{ is a limit or }0, \\ \gamma, & \beta = S(\gamma).\end{cases} $$

序数乘方

定义：序数乘方

$\alpha^\beta$ 通过对 $\beta$ 作用递归来定义，基于如下的递归条件：

$\alpha^0=1$.
$\alpha^{\beta+1}=\alpha^\beta\cdot \alpha$.
如果 $\beta$ 为极限序数，$\alpha^\beta = \sup\left\lbrace \alpha^\xi: \xi< \beta \right\rbrace$.

在这里，我们不能将其与之后将说明的基数指数混淆，例如 $2^\omega = \omega$ ，这和我们在基数当中学到的连续统势是不一样的.

例题

例题1

设 $\alpha$ 是非零极限序数，证明：
$$ 1^\alpha + 2^\alpha = 3^\alpha $$

首先 $1^\alpha = 1$ 是显然成立的. 考虑如下的命题：

$\alpha$ 是极限序数，则存在序数 $\beta$ 使得 $\alpha = \omega\cdot \beta$ .

那么有

\[ 2^\alpha = (2^\omega)^\beta = \omega^\beta \]

同理可得 $3^\alpha = \omega^\beta$ . 因此根据 $1+ \omega^\beta = \omega^\beta$ 可得结论成立. $\square$

例题2

设非 0 序数 $\alpha$ 的范式如下：
$$ \alpha = \omega^{\beta_1}\cdot k_1 + \cdots + \omega^{\beta_n}\cdot k_n $$
其中 $n,k_1,\cdots,k_n$ 是正整数，$\alpha \geqslant \beta_1 > \cdots > \beta_n$ .

(1) 证明：$\alpha< \omega^{\beta_1+1}$.

(2) 证明：若序数 $\gamma \geqslant \omega^{\beta_1+1}$ ，则 $\alpha+ \gamma = \gamma$.

(1) 证明：

考虑放缩，放缩思路其实相对比较简单，将其中较小的项按如下的方法放大：

\[ \omega^{\beta_i}\cdot k_i < \omega^{\beta_{i}+1} \leqslant \omega^{\beta_{i-1}} \]

有的教材也称之为超穷归纳法. ↩

ZF集合论 III —— 超限归纳

类和递归

超限归纳与超限递归

超限归纳

超限归纳证明操作

超限递归

类的函数

超限递归

序数减法和乘方

序数减法

序数乘方

例题

评论