反射序数

反射是一个非递归记号。它表示非递归序数，其特点是并不会表示其极限之下的所有序数。它具有深厚的集合论背景

数学定义

前排提醒：对数学定义不感冒或者看不懂的读者可以跳到后面

为了说明反射序数的性质，我们先要对一阶逻辑的结构进行更加细致的讨论。下面我们根据命题中无界量词的性质，给出公式的层次：

满足如下条件之一的集合论公式称为${\mathrm{\Delta }}_0$公式

1. 它不包含无界量词
2. 它形如$\phi \wedge \psi ,\phi \vee \psi ,\mathrm{\neg }\phi ,\phi \to \psi ,\phi \leftrightarrow \psi$,其中$\phi ,\psi$为${\mathrm{\Delta }}_0$公式
3. 它形如$(\mathrm{\exists }x\in y)\phi$或$(\mathrm{\forall }x\in y)\phi$,其中$\phi$为${\mathrm{\Delta }}_0$公式

${\mathrm{\Delta }}_0$公式中的所有量词都是有界的。对于那些包含无界量词的公式，我们给出如下的递归定义：

${\mathrm{\Sigma }}_n$公式及${\mathrm{\Pi }}_n$公式定义如下：

1. ${\mathrm{\Sigma }}_0$公式及${\mathrm{\Pi }}_0$公式为${\mathrm{\Delta }}_0$公式。
2. 如果$\phi$为${\mathrm{\Pi }}_n$公式，则$\mathrm{\exists }{x}_1\cdots \mathrm{\exists }{x}_m\phi$为${\mathrm{\Sigma }}_{n+1}$公式。
3. 如果$\phi$为${\mathrm{\Sigma }}_n$公式，则$\mathrm{\forall }{x}_1\cdots \mathrm{\forall }{x}_m\phi$为${\mathrm{\Pi }}_{n+1}$公式。

反射序数是具有某种特殊反射性质的序数。下面我们给出反射的定义：

L为可构造宇宙，$L_{\alpha }$在X上反射了公式$\phi$,是说$L_{\alpha }\models \phi \Rightarrow \mathrm{\exists }\beta \in (X\cap \alpha )L_{\beta }\models \phi$.

我们进一步给出如下定义：

若$L_{\alpha }$在X上反射了所有的${\mathrm{\Pi }}_n({\mathrm{\Sigma }}_n)$公式，则称α是X上的${\mathrm{\Pi }}_n({\mathrm{\Sigma }}_n)$序数。

特别的，若$L_{\alpha }$在所有序数上反射了所有的${\mathrm{\Pi }}_n({\mathrm{\Sigma }}_n)$公式，则称α是${\mathrm{\Pi }}_n({\mathrm{\Sigma }}_n)$序数。

关于反射序数有如下的重要结论：

α是X上的${\mathrm{\Pi }}_n$反射序数，等价于α是X上的${\mathrm{\Sigma }}_{n+1}$反射序数

也就是说，我们只需要研究集合上的${\mathrm{\Pi }}_n$反射序数即可。进一步的有

α是X上的${\mathrm{\Pi }}_0$反射序数，等价于α是X上的${\mathrm{\Pi }}_1$反射序数，等价于α是X上的极限点。

在一些资料中，会出现${\mathrm{\Pi }}_0$反射等价于全体序数的说法。这是错误的。事实上，如果我们想要写出全体序数，应该写出$Ord$。

我们还有结论：α是X上的${\mathrm{\Pi }}_2$反射序数，等价于α是X上的容许序数。

结构讲解

基本符号

onto

onto 是反射模式的核心。它的作用对象是一个集合，同时也输出一个集合。例如： ${\mathrm{\Pi }}_1\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}$全体序数，得到的是全体极限序数构成的集合；${\mathrm{\Pi }}_2\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}$全体序数构成的集合，得到的是全体容许序数构成的集合。

方便起见，我们把${\mathrm{\Pi }}_n\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}X$简写为 n-X 。这里的 n 是自然数， X 是被操作的集合。特殊地，当 X 为全体序数，我们直接将它省略不写，此时的结果直接记为 n 。也就是说，在反射模式中， 1 可以用来表示${\mathrm{\Pi }}_1\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}$全体序数的集合的结果，以此类推。

∩

这里的∩指交集。没错，就是那个大家熟知的交集， $A\cap B$表示同时属于集合 A 和集合 B 的元素。交集也是反射模式中的一种重要运算。同样是为了方便起见，我们将∩简写为空格。 ∩在反射式中的运算优先级与onto相同，并且从右向左计算。例如： 2 1-2表示${\mathrm{\Pi }}_2\cap ({\mathrm{\Pi }}_1\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}{\mathrm{\Pi }}_2)$的集合； 2-3 1-3 2-3表示${\mathrm{\Pi }}_2\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}({\mathrm{\Pi }}_3\cap ({\mathrm{\Pi }}_1\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}({\mathrm{\Pi }}_3\cap ({\mathrm{\Pi }}_2\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}{\mathrm{\Pi }}_3))))$的集合。

$\mathrm{m}\mathrm{i}\mathrm{n},\mathrm{2}\mathrm{n}\mathrm{d},\mathrm{3}\mathrm{r}\mathrm{d}$以及$n\mathrm{t}\mathrm{h}$

反射模式研究的集合中的元素都是序数。因此，我们可以把这些序数从小到大进行排序，并用$\mathrm{2}\mathrm{n}\mathrm{d}X,\mathrm{3}\mathrm{r}\mathrm{d}X,n\mathrm{t}\mathrm{h}X$来分别表示集合 X 中从小到大的第 2 、第 3 以及第 n 个元素。不过，对于 X 中的第 1 个元素，我们一般不叫它$\mathrm{1}\mathrm{s}\mathrm{t}X$，而是叫它min X 。在不引起歧义的情况下，也可以把这个min省略，直接用 X 来指代 X 中的第一个元素。在会引起歧义的场合，则用 (X) 来代表 min X 。不建议使用$\omega \mathrm{t}\mathrm{h}$之类的“第超限序数个”的表达。

aft

将序数从小到大排序，排在后面的就是更大的序数。因此， $A\mathrm{a}\mathrm{f}\mathrm{t}B$表示“集合 A 中大于序数 B 的元素”。将这一表达与$\min ,\mathrm{2}\mathrm{n}\mathrm{d},\mathrm{3}\mathrm{r}\mathrm{d}$等结合起来，可以得到$\min A\mathrm{a}\mathrm{f}\mathrm{t}B$(可直接简写为$\min A\mathrm{a}\mathrm{f}\mathrm{t}B$)、 $2\mathrm{n}\mathrm{d}A\mathrm{a}\mathrm{f}\mathrm{t}B$等，分别表示“集合 A 中最小的大于序数 B 的元素”和“集合 A 中第二个大于序数 B 的元素”。

${\mathrm{\Pi }}_1$反射

1- 的作用

${\mathrm{\Pi }}_1\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}$ 一个集合的效果，是取出这个集合中所有的极限点。所谓的极限点，就是前极限序数个元素的上确界。

现在我们可以来推导一下 1 ，也即${\mathrm{\Pi }}_1\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}$全体序数的构成。

具体地，我们需要遍历全体极限序数α ，并找到前α个序数的上确界。

前ω个序数的上确界为ω，前$\omega \times 2$个序数的上确界为$\omega \times 2$ ……

事实上， 1 就等于全体极限序数的集合$\{\omega ,\omega \times 2,\dots ,{\omega }^2,\dots ,{\omega }^{\omega },\dots \mathrm{\Omega },\dots \}$ 。

类似地， 1 中的前ω个序数的上确界是$\sup \{\omega ,\omega \times 2,\omega \times 3,\dots \}={\omega }^2$，1 中的前$\omega \times 2$个序数的上确界是$\sup \{\omega ,\omega \times 2,\dots ,{\omega }^2,{\omega }^2+\omega ,\dots \}={\omega }^2\times 2$……因此，$1-1=\{{\omega }^2,{\omega }^2\times 2,\dots ,{\omega }^3,\dots ,{\omega }^{\omega },\dots ,\mathrm{\Omega },\dots \}$，是${\omega }^2$ 的倍数的集合。

继续递推，还能得到

$1-1-1=\{{\omega }^3,{\omega }^3\times 2,\dots ,{\omega }^{\omega },\dots ,\mathrm{\Omega },\dots \}$

$1-1-1-1=\{{\omega }^4,{\omega }^4\times 2,\dots ,{\omega }^{\omega },\dots ,\mathrm{\Omega },\dots \}$

……直到——

$(1-{)}^{\omega }$

方便起见，我们把重复的 1- 合并合并。把重复的操作用括号括起来，上标表示重复次数。这样， 1-1-1 可以写作$(1-{)}^3$ ， 1-1-1-1 可以写作$(1-{)}^4$ 。对于这种有限次的 1- ，我们都可以递归地得到它代表的集合。

但，$(1-{)}^{\omega }$呢？

我们首先需要定义$(1-{)}^{\omega }$。较一般地，对于$(1-{)}^{\alpha }$ ，其中 α为极限序数的情况，我们只需要取交集，即定义 $(1-{)}^{\alpha }=\bigcap _{\beta <\alpha }(1-{)}^{\beta }$。

自然地，我们可以推导出$(1-{)}^{\omega }=\{{\omega }^{\omega },{\omega }^{\omega }\times 2,\dots ,{\omega }^{\omega +1},\dots ,\mathrm{\Omega },\dots \}$，即${\omega }^{\omega }$的倍数的集合。

$(1-{)}^{\alpha }$，就是${\omega }^{\alpha }$ 的倍数的集合，$\min (1-{)}^{\alpha }={\omega }^{\alpha }$。

$(1-{)}^{1,0}$等

上标只能放序数的情形是简单的，一个“${\omega }^{\alpha }$的倍数”就直接解决了。如何让情形变得更有趣呢？我们可以借用veblen函数的不动点进位模式，在上标上引入多个数字，来表示不同层级的不动点。

我们定义$(1-{)}^{1,0}=\{\alpha |\alpha =\min (1-{)}^{\alpha }\}$。根据上一节的结论，我们可以知道$\min (1-{)}^{\alpha }={\omega }^{\alpha }$。因此， $(1-{)}^{1,0}$是全体 $\epsilon$序数的集合，即 $\{{\epsilon }_0,{\epsilon }_1,\dots ,{\epsilon }_{\omega },\dots ,{\zeta }_0,\dots ,\mathrm{\Omega },\dots \}$。

可以继续对 $(1-{)}^{1,0}$进行 1- 的操作，得到的集合记为 $(1-{)}^{1,1}$。$(1-{)}^{1,1}$应当是全体“下标为极限序数的$\epsilon$ 序数”的集合，即$(1-{)}^{1,1}=\{{\epsilon }_{\omega },{\epsilon }_{\omega \times 2},\dots ,{\epsilon }_{{\omega }^2},\dots ,{\zeta }_0,\dots ,\mathrm{\Omega },\dots \}$。

更一般地，我们在上标上使用weak veblen函数，记 $1-(1-{)}^{\mathrm{\#},\alpha }$ 为$(1-{)}^{\mathrm{\#},\alpha +1}$。于是，我们还可以有 $(1-{)}^{1,2},(1-{)}^{1,\omega },(1-{)}^{1,{\epsilon }_0},\dots$ 。在上标遇到极限序数时，我们也仍取交集。

直到我们遇见了新的不动点。我们定义 $(1-{)}^{2,0}=\{\alpha |\alpha =\min (1-{)}^{1,\alpha }\}$。借用veblen函数的模式，我们还能把定义推广到 $(1-{)}^{1,0,0}$等等并且还能在此基础上进行扩展。理论上，只要扩展足够强力，所有的递归序数都能像这样被表示出来。

值得一提的是，本条目折叠不动点采用了veblen函数式的写法。事实上，是存在OCF式的写法的。读者可以参见条目Σ1稳定序数。

${\mathrm{\Pi }}_2$反射和容许序数

${\mathrm{\Pi }}_2\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}$任意集合的作用，暂时是难以说明的，所以我们先从${\mathrm{\Pi }}_2\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}$全体序数开始。这里不加证明地给出以下结论：${\mathrm{\Pi }}_2$ 反射作用于全体序数的集合，得到的是全体容许序数的集合。

所谓容许序数，可以大致地理解为无法通过比它小的序数进行递归运算得到的序数。所谓的“无法通过比它小的序数进行递归运算得到的序数”，换用另一个更直观的概念，就是“不存在长度小于它的、递归表达的基本列的序数”。也就是说，如果我们找到了某个序数的一条长度小于它本身的基本列，就能立刻断言它不是容许序数。这为我们排除很多容许序数的备选提供了一条可行的方案。

最小的容许序数是Church-Kleene序数，记为${\omega }_1^{CK}$，在这里我们把它写作$\mathrm{\Omega }$ ——没错，就是在OCF中出现的那个。

紧接着，第二个容许序数是 ${\omega }_2^{CK}$，在这里写作${\mathrm{\Omega }}_2$。它无法通过包括$\mathrm{\Omega }$ 在内的比它小的序数通过递归运算得到，这意味着${\mathrm{\Omega }}_2$不是$\mathrm{\Omega }\times 2,{\mathrm{\Omega }}^2,{\epsilon }_{\mathrm{\Omega }+1},\phi (\mathrm{\Omega },1)$之类的东西，而是远远在它们之上的存在。

再然后，还会有${\mathrm{\Omega }}_3,{\mathrm{\Omega }}_4,\dots ,{\mathrm{\Omega }}_{\omega +1},\dots ,{\mathrm{\Omega }}_{\mathrm{\Omega }+1},\dots$它们一同组成了容许序数的集合。

值得注意的是，上面一句话跳过了${\mathrm{\Omega }}_{\omega },{\mathrm{\Omega }}_{\mathrm{\Omega }}$，而单独列出了${\mathrm{\Omega }}_{\omega +1}$和 ${\mathrm{\Omega }}_{\mathrm{\Omega }+1}$。这是因为 ${\mathrm{\Omega }}_{\omega }$和${\mathrm{\Omega }}_{\mathrm{\Omega }}$ 并非容许序数——这一点可以通过“找长度小于它本身的基本列”来实现。

更进一步地，$\mathrm{O}\mathrm{F}\mathrm{P}={\psi }_I(0)$存在一条长度为ω的基本列$\{\mathrm{\Omega },{\mathrm{\Omega }}_{\mathrm{\Omega }},{\mathrm{\Omega }}_{{\mathrm{\Omega }}_{\mathrm{\Omega }}},\dots \}$，它也是非容许的。

事实上，对于大多数的${\mathrm{\Omega }}_{\alpha }$，其中 α为极限序数， α的基本列总是会成为我们我们的突破口，让我们找到${\mathrm{\Omega }}_{\alpha }$的一条长度小于自身的基本列。

顺便一提，对于所有的后继序数α，${\mathrm{\Omega }}_{\alpha }$都毫无疑问是容许序数。

$1-2,(1-{)}^{1,0}2$等

1-2 ，即取出集合 $2=\{\mathrm{\Omega },{\mathrm{\Omega }}_2,\dots ,{\mathrm{\Omega }}_{\omega +1},\dots ,{\mathrm{\Omega }}_{\mathrm{\Omega }+1},\dots \}$中所有的极限点。

2 中的前ω 个序数的上确界是$\sup \{\mathrm{\Omega },{\mathrm{\Omega }}_2,\dots \}={\mathrm{\Omega }}_{\omega }$，所以 ${\mathrm{\Omega }}_{\omega }\in 1-2$；

2 中的前 $\omega \times 2$个序数的上确界是${\mathrm{\Omega }}_{\omega \times 2}$，所以${\mathrm{\Omega }}_{\omega \times 2}\in 1-2$……

如此一来， 1-2 就是“ ${\mathrm{\Omega }}_{\alpha }$，其中α为极限序数”的集合。需要注意的是，这样的序数大多数都是非容许的。这意味着 1-2 这个集合中的大部分元素甚至不属于 2 。我们对 2 这个集合进行了$1\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}$ 的操作，得到了一个性质更差的集合，这种事在反射里，是相当常见的。

接着是 1-1-2 。我们取集合 1-2 的极限点，可以得到“${\mathrm{\Omega }}_{\alpha }$，其中α 为${\omega }^2$的倍数”的集合。同样地，我们可以通过取交集得到$(1-{)}^{\omega }2,(1-{)}^{{\omega }^2}2$乃至 $(1-{)}^{\mathrm{\Omega }}2$。由于$\mathrm{\Omega }=\min 2$ ，所以$(1-{)}^{\mathrm{\Omega }}2$ 又可以写作 $(1-{)}^{(2)}2$ 。这里在上标上省略了min ，并且在外面加了一层括号用以和序数 2 区分。

于是我们来到了 $(1-{)}^{1,0}2$。类似$(1-{)}^{1,0}$的定义，$(1-{)}^{1,0}2=\{\alpha |\alpha =(1-{)}^{\alpha }2\}$。不难发现，$(1-{)}^{1,0}2$的每一个元素α 都满足 $\alpha ={\mathrm{\Omega }}_{\alpha }$ ，因此，$(1-{)}^{1,0}2$是全体 OFP的集合。$\{{\psi }_I(0),{\psi }_I(1),\dots ,{\psi }_I(\mathrm{\Omega }),\dots ,{\psi }_I(I),\dots \}$.

$(1-{)}^{1,0}2$ 过后，同样也有$(1-{)}^{2,0}2,(1-{)}^{1,0,0}2,\dots$。不过，不管 $(1-{)}^{a,b,c,\dots }2$的上标的层级多深，只要它还是不动点的形式，它就是非容许的。

递归不可达序数

我们不妨思考一下，若一个极限序数α足以使得${\mathrm{\Omega }}_{\alpha }$为容许序数的话，它需要满足什么条件呢？

首先，α是容许序数；其次， $\alpha \in 1-2$ 。即满足上述条件的α属于 2 和 1-2 的交集，记为 $\alpha \in 21-2$。

根据ZFC公理体系，我们可以直接证明 2 和 1-2 的交集存在元素，我们将其命名为递归不可达序数。最小的递归不可达序数记作 I ，次小的是$I_2$……就和 $\mathrm{\Omega },{\mathrm{\Omega }}_2$差不多。

总之，$21-2=\{I,I_2,\dots ,I_{\omega +1},\dots ,I_{I+1},\dots ,I(1,0),\dots \}$。注意到这里也没有列出 $I_{\omega }$ ，$I_{\omega }$ 并非容许序数。

接下来，我们还可以对 2~1-2 进行若干次 1- ，例如$1-21-2=\{I_{\omega },I_{\omega \times 2},\dots ,I_I,\dots ,\mathrm{I}\mathrm{F}\mathrm{P},\dots \}$。推导过程和 1-2 是一致的，注意 1-2~1-2 表示的实际上是 $1\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o}(21-2)$。

$(1-{)}^{1,0}21-2$ 自然是全体IFP，也就是满足 $\alpha =I_{\alpha }$的序数构成的集合。

容许点

对“容许点”的定义，即：

序数 $\mathrm{\Theta }$为函数$f(\alpha )$ 的容许点，等同于$\mathrm{\Theta }$ 是 $f(\alpha )$的不动点且为容许序数。

于是我们可以看到，$\mathrm{\Omega }$是函数$f(\alpha )={\omega }^{\alpha }$ 的容许点；I 是函数 $f(\alpha )={\mathrm{\Omega }}_{\alpha }$ 的容许点。

更一般地，若函数$f(\alpha )$的值域是集合 A ，那么$f(\alpha )$的容许点组成的集合是$21-A$ 。

在更以后的地方，提到的某函数的“马洛点”“ K 点”等“ X 点”概念也都指代“某序数是 X 序数且是该函数的不动点”。

I(1,0) 等二元I函数

函数$f(\alpha )=I_{\alpha }$的容许点是什么呢？认为是 M 的读者可能受到了 IMK 经常被一同提起的影响。实际上，函数$f(\alpha )=I_{\alpha }$的最小的容许点仅仅是 I(1,0) 。受到《大数入门》的影响，部分读者会认为 I(1,0) 与IFP等同，实则并非如此。

根据前面提到的“若函数$f(\alpha )$的值域是集合 A ，那么$f(\alpha )$的容许点组成的集合是$21-A$ 。”的规则，不难知道，函数 $f(\alpha )=I_{\alpha }$的全体容许点的集合是$21-21-2$。

$f(\alpha )=I_{\alpha }$的次小的容许点是 I(1,1) 。这里，二元 I 的最后一位实质上相当于$\mathrm{\Omega }$或者 I 的下标。于是，$(21-{)}^{2}2=21-21-2=\{I(1,0),I(1,1),\dots ,I(1,\omega +1),\dots \}$ 。 $I(1,\omega )$同样是非容许的。

$(1-{)}^{1,0}21-21-2$是函数 $f(\alpha )=I(1,\alpha )$的不动点，记作$I(1,a)\mathrm{F}\mathrm{P}$ 。最小的 $I(1,a)\mathrm{F}\mathrm{P}$ 也并非 I(2,0) 。 I(2,0) 是函数 $f(\alpha )=I(1,\alpha )$的容许点。多元 I 函数的这种进位方式，称为容许点进位。

……

像这样继续往前，自然会遇到 $(21-{)}^{\omega }2$，我们期望它是$\{I(\omega ,0),I(\omega ,1),\dots \}$。如果我们仍用定义$(1-{)}^{\omega }$时的交集来定义它会怎么样呢？下面才会真正开始涉及真伪的争端…