3.6. 大可数序数

这一节介绍一些简单的大可数序数的构造, 更多的内容可参看大数维基.

Veblen 层级

我们回顾一下正规函数的定义.

定义 3.6.0.1. 对 $f:{\omega }_1\to {\omega }_1$, 若它满足以下两条件, 则称它是正规的:

1.	$\alpha <\beta \to f(\alpha )<f(\beta )$
2.	$\alpha ={\lim }_{\gamma <\alpha }\gamma \to f(\alpha )={\lim }_{\gamma <\alpha }f(\gamma )$

今后我们默认提到的所有函数都是正规的.

我们先考察单变元的正规函数的增长速度.

定义 3.6.0.2. 若 $f(\alpha )=\alpha$, 则称 $\alpha$ 是 $f$ 的不动点. 全体不动点的集合记为 $\mathrm{Fix}(f)$.

很容易意识到, 它的第一个不动点就刻画了它的某种增长速度的上确界, 因为它恰好抹去了 $f$ 在其下方的一切想要快速增长的努力. 我们来证明任何正规函数都有很多不动点.

定理 3.6.0.3. $\mathrm{Fix}(f)$ 是闭无界集.

证明. 首先证明闭. 若单增不动点列有极限 ${\lim }_{n\in \omega }{\alpha }_n=\alpha$, 则 $f(\alpha )={\lim }_{n\in \omega }f({\alpha }_n)={\lim }_{n\in \omega }{\alpha }_n=\alpha$. 然后证明无界. 若有 $\beta$, 则定义 ${\alpha }_0=\beta ,{\alpha }_{n+1}=f({\alpha }_n)$, 令 $\alpha ={\lim }_{n\in \omega }{\alpha }_n$, 则 $f(\alpha )={\lim }_{n\in \omega }f({\alpha }_n)={\lim }_{n\in \omega }{\alpha }_{n+1}={\lim }_{n\in \omega }{\alpha }_n=\alpha$, 因此 $\alpha$ 是大于 $\beta$ 的不动点.

$\square$

我们特别地记 $f$ 的第一个不动点为 ${\mathrm{inacc}}_1(f)$. 显然, 由于闭无界集的序型总是 ${\omega }_1$, 我们可以来枚举 $f$ 的不动点, 这个想法反复迭代就形成了以下定义.

定理 3.6.0.4 (Veblen 层级). 任给正规函数 $f$, 我们如下递归地定义一个新的二元函数:

1.	$f(0,-)=f$
2.	$f(\beta ,-)=\mathrm{Enum}({\bigcap }_{\gamma <\beta }\mathrm{Fix}(f(\gamma ,-)))$

则对任意的 $\beta$, 这个 $f(\beta ,-)$ 都是正规的. 它将称作 $f$ 给出的 Veblen 层级.

证明. 这是因为可列个闭无界集的交集总是闭无界集, 从而其列举总是正规函数.

$\square$

我们来讨论这个二元函数到底保持了什么序.

定理 3.6.0.5. $f(\alpha ,\xi )<f(\beta ,\zeta )$ 的充要条件是:

1.	$\alpha <\beta$ 且 $\xi <f(\beta ,\zeta )$, 或
2.	$\alpha =\beta$ 且 $\xi <\zeta$, 或
3.	$\alpha >\beta$ 且 $f(\alpha ,\xi )<\zeta$.

证明. 分类讨论. $\alpha =\beta$ 显然, 余下两情形对偶. $\alpha <\beta$, 则 $\xi <f(\beta ,\zeta )\leftrightarrow f(\alpha ,\xi )<f(\alpha ,f(\beta ,\zeta ))=f(\beta ,\zeta )$.

$\square$

自然地, 我们会想考虑 $f(-,\alpha )$, 但它并不总是正规的. 幸运的是, 我们可以选取一个较好的 $\alpha$ 使得它确实正规.

定义 3.6.0.6. 对正规函数 $f$, 我们称第一个使得 $f(\alpha )>\alpha$ 的 $\alpha$ 为 $f$ 的关键点, 记为 $\mathrm{crit}(f)$.

定理 3.6.0.7. $f(-,\mathrm{crit}(f))$ 是一个正规函数, 我们记之为 $f^{\ast }$.

证明. 记 $\delta =\mathrm{crit}(f)$. 显然归纳可证 $\forall \alpha <\delta (f(\alpha ,\beta )=\beta )$ 且 $\forall \alpha (f(\alpha ,\delta )>\delta )$.

为了证明 $f(-,\delta )$ 单调, 注意 $\alpha <\beta \to f(\alpha ,\delta )<f(\alpha ,f(\beta ,\delta ))=f(\beta ,\delta )$. 为了证明 $f(-,\delta )$ 连续, 我们考虑 $\gamma ={\lim }_{\alpha <\gamma }\alpha$ 和 $\beta ={\lim }_{\alpha <\gamma }f(\alpha ,\delta )$, 然后试着证明 $\beta =f(\gamma ,\delta )$.

一方面, $\beta \in {\bigcap }_{\alpha <\gamma }\mathrm{ran}(f(\alpha ,-))=\mathrm{ran}(f(\gamma ,-))$, 而由 $f(\gamma ,-)$ 在 $\delta$ 之下是常函数知 $f(\gamma ,\delta )$ 是 $\mathrm{ran}(f(\gamma ,-))\backslash \delta$ 的最小元, 因此 $f(\gamma ,\delta )\le \beta$.

另一方面, $\delta <f(\gamma ,\delta )\to f(\alpha ,\delta )<f(\alpha ,f(\gamma ,\delta ))=f(\gamma ,\delta )$, 故 $\beta ={\lim }_{\alpha <\gamma }f(\alpha ,\delta )\le f(\gamma ,\delta )$. 两方综合即证.

$\square$

接下来, 我们来看下一个序数, 它指出经由 Veblen 层级延拓后的函数增长速度的上确界.

定义 3.6.0.8. 我们记 $f^{\ast }$ 的第一个不动点为 ${\mathrm{inacc}}_2(f)$. 记 $f_{\ast }=f^{\ast }(1,-)$, 则 ${\mathrm{inacc}}_2(f)=f_{\ast }(0)$.

定理 3.6.0.9. $f_{\ast }(\alpha )$ 总是极限序数.

证明. 反证. 若有 $f_{\ast }(\gamma )=\alpha +1$, 则 $f^{\ast }(\alpha +1)=\alpha +1$, 即有 $f(\alpha +1,\delta )=\alpha +1$, 由定义又有 $f(\alpha ,\alpha +1)=\alpha +1$. 由 $f(\alpha ,\delta )>\alpha$ 可知 $f(\alpha ,\delta )\ge \alpha +1=f(\alpha ,\alpha +1)$, 故有 $\alpha +1\le \delta$, 这和 $\alpha +1=f(\alpha +1,\delta )>\delta$ 矛盾.

$\square$

定理 3.6.0.10. 如果 $\alpha ,\beta <f_{\ast }(\gamma )$, 则 $f(\alpha ,\beta )<f_{\ast }(\gamma )$. 特别的, $\alpha ,\beta <{\mathrm{inacc}}_2(f)$ 时总有 $f(\alpha ,\beta )<{\mathrm{inacc}}_2(f)$.

证明. 取 $ϵ=\max (\alpha ,\beta )+1$, 由 $f_{\ast }(\gamma )$ 极限知 $ϵ<f_{\ast }(\gamma )$, 于是 $f(\alpha ,\beta )<f(\alpha ,f(\beta ,\delta ))<f(\alpha ,f(ϵ,\delta ))=f(ϵ,\delta )<f(f_{\ast }(\gamma ),\delta )=f^{\ast }(f_{\ast }(\gamma ))=f_{\ast }(\gamma )$.

$\square$

当然, 我们还要说明 ${\mathrm{inacc}}_2(f)$ 下面的序数都是可达到的.

定理 3.6.0.11. 若 $\theta$ 满足 $\mathrm{crit}(f)<\theta <{\mathrm{inacc}}_2(f)$, 则存在 $\alpha ,\beta <\theta$ 使得 $f(\alpha ,\beta )\ge \theta$.

证明. 我们直接把 $\beta$ 取为 $\delta =\mathrm{crit}(f)$. 如果 $\forall \alpha <\theta$ 均有 $f(\alpha ,\delta )=f^{\ast }(\alpha )<\theta$, 则 $f^{\ast }(\theta )\le \theta$, 然而显然又有 $f^{\ast }(\theta )\ge \theta$, 故 $f^{\ast }(\theta )=\theta$, 换言之 ${\mathrm{inacc}}_2(f)$ 不是 $f^{\ast }$ 最小的不动点, 矛盾.

$\square$

今后, 对 $f(\alpha )=\phi (\gamma )={\omega }^{\gamma }$ 的情况, 产生的这个 $\phi (\alpha ,\beta )$ 将被称为 Veblen 函数. ${\mathrm{inacc}}_1$ 将被记为 ${ϵ}_0$, ${\mathrm{inacc}}_2$ 将被记为 ${\Gamma }_0$, 称作 Feferman–Schutte 序数. 事实上, $\phi (1,\alpha )$ 记为 ${ϵ}_{\alpha }$, $\phi (2,\alpha )$ 记为 ${\zeta }_{\alpha }$, 但它们都被 ${\Gamma }_0$ 轻松杀掉了.

${\Gamma }_0$ 还有一个重要的刻画: 它允许我们在其下采用某种 Veblen 函数构成的正则形式.

定理 3.6.0.12. 任给 $\alpha <{\Gamma }_0$, 存在唯一的有穷序数列 ${\beta }_0,{\gamma }_0,{\beta }_1,{\gamma }_1,...,{\beta }_{k-1},{\gamma }_{k-1}$ 满足以下条件:

1.	$\alpha =\phi ({\beta }_0,{\gamma }_0)+\phi ({\beta }_1,{\gamma }_1)+...+\phi ({\beta }_{k-1},{\gamma }_{k-1})$
2.	$\phi ({\beta }_0,{\gamma }_0)\ge \phi ({\beta }_1,{\gamma }_1)\ge ...\ge \phi ({\beta }_{k-1},{\gamma }_{k-1})$
3.	$\forall i\in k({\gamma }_i<\phi ({\beta }_i,{\gamma }_i))$

这将称作 $\alpha$ 的 Veblen 正则形式.

证明. 如 Cantor 正则形式的证明一般归纳. 在分离出 $\alpha ={\omega }^{\delta }\cdot n+\beta$ 后注意到一定存在 ${\beta }_0<{\Gamma }_0$ 和 ${\gamma }_0<\phi ({\beta }_0,{\gamma }_0)$ 使得 ${\omega }^{\delta }=\phi ({\beta }_0,{\gamma }_0)$ 即可. 显然 ${\omega }^{\delta }=\phi (0,\delta )$, 所以唯一的可能反例是 $\forall {\beta }_0<{\Gamma }_0$ 都有 $\phi ({\beta }_0,\delta )=\delta$, 这时会得出 $\delta ={\Gamma }_0$ 产生矛盾.

$\square$

延展与超穷的 Veblen 层级

注意到 Veblen 层级其实就是把一元正则序列变成了二元的, 我们自然想要它变成至少是任意 $n$ 元的. 这一节的后面, 我们甚至可以让它变成超穷元的. 不妨要求 $\mathrm{crit}(f)=0$.

先来看有穷元的 $\phi :{\omega }_1^{<\omega }\to {\omega }_1$. 由于左边的良序还是不清楚的, 我们额外证明一些事实以使得归纳成立.

定理 3.6.0.13. 存在 ${\mathbf{Ord}}^{<\omega }$ 上的典范良序 ${<}_C$, 它限制在每个无穷基数 $\kappa$ 对应的 ${\kappa }^{<\omega }$ 上时序型均为 $\kappa$.

证明. $({\alpha }_0,...,{\alpha }_{m-1}){<}_C(\beta +0,...,{\beta }_{n-1})$ 当且仅当: ${\alpha }_0+...+{\alpha }_{m-1}+m<{\beta }_0+...+{\beta }_{n-1}+n$, 或者存在 $k$ 使得 $\forall i\in k({\alpha }_i={\beta }_i)$ 且 ($k=m$ 或 ${\alpha }_k<{\beta }_k$). 验证留做习题.

$\square$

定义 3.6.0.14. 给定正规函数 $f:{\omega }_1\to {\omega }_1$, 总可以延拓定义域得到 $f:{\omega }_1^{<\omega }\to {\omega }_1$, 它按照以下规则递归地定义:

1.	$f(\gamma )=f(\gamma )$
2.	$f(0,...,0,{\gamma }_0,...,{\gamma }_{n-1})=f({\gamma }_0,...,{\gamma }_{n-1})$
3.	$f({\gamma }_0,...,{\gamma }_{n-1},0,...,0,-)=\mathrm{Enum}({\bigcap }_{\beta <{\gamma }_{n-1}}\mathrm{Fix}(f({\gamma }_0,...,\beta ,-,0,...,0)))$, 这里 ${\gamma }_{n-1}>0$.

它将称作 $f$ 给出的延展 Veblen 层级.

定理 3.6.0.15. 延拓后的 $f$ 良定义, 且 $f({\gamma }_0,...{\gamma }_{n-1},-)$ 总是正则函数.

证明. 不难验证 $0\le \beta <{\gamma }_{n-1}$ 时确实有 $$\begin{gathered} ({\gamma }_0,...,{\gamma }_{n-1},0,...,0,-){>}_C({\gamma }_0,...,\beta \\ ,-,0,...,0) \end{gathered}$$.

$\square$

评注. $\phi (1,0,-)$ 又被称为 $\Gamma$ 函数, 其实就是 $\phi (1,0,0)={\Gamma }_0$ 的延续. 它已经被延展 Veblen 函数轻松杀掉了.

于是, 我们自然想考查这个延展 Veblen 层级的增长速度的上确界.

定义 3.6.0.16. ${\mathrm{inacc}}_3(f)=\sup \{f(1),f(1,0),f(1,0,0),...\}$. 特别的, 记 $$\begin{gathered} {\mathrm{inacc}}_3 \\ (\phi )=\mathrm{SVO} \end{gathered}$$, 即小 Veblen 序数 (Small Veblen Ordinal).

定理 3.6.0.17. 任给一串 $$\begin{gathered} {\gamma }_0,...,{\gamma }_{n-1}<{\mathrm{inacc}}_3 \\ (f) \end{gathered}$$, 均有 $f({\gamma }_0,...,{\gamma }_{n-1})<{\mathrm{inacc}}_3(f)$. 反之, 任给 $\gamma <{\mathrm{inacc}}_3(f)$, 均存在 ${\gamma }_0,...,{\gamma }_{n-1}<{\mathrm{inacc}}_3(f)$ 使得 $\gamma <f({\gamma }_0,...,{\gamma }_{n-1})$.

证明.

$\square$

序数坍塌