查看“︁反射序数”︁的源代码

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

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

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

满足如下条件之一的集合论公式称为<math>\Delta_0</math>公式

# 它不包含无界量词
# 它形如<math>\varphi\land\psi,\varphi\lor\psi,\neg\varphi,\varphi\rightarrow\psi,\varphi\leftrightarrow\psi</math>,其中<math>\varphi,\psi</math>为<math>\Delta_0</math>公式
# 它形如<math>(\exists x\in y)\varphi</math>或<math>(\forall x\in y)\varphi</math>,其中<math>\varphi</math>为<math>\Delta_0</math>公式

<math>\Delta_0</math>公式中的所有量词都是有界的。对于那些包含无界量词的公式，我们给出如下的递归定义：

<math>\Sigma_n</math>公式及<math>\Pi_n</math>公式定义如下：

# <math>\Sigma_0</math>公式及<math>\Pi_0</math>公式为<math>\Delta_0</math>公式。
# 如果<math>\varphi</math>为<math>\Pi_n</math>公式，则<math>\exists x_1\cdots\exists x_m\varphi</math>为<math>\Sigma_{n+1}</math>公式。
# 如果<math>\varphi</math>为<math>\Sigma_n</math>公式，则<math>\forall x_1\cdots\forall x_m\varphi</math>为<math>\Pi_{n+1}</math>公式。

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

L为[[可构造宇宙]]，<math>L_\alpha</math>在X上反射了公式<math>\varphi</math>,是说<math>L_\alpha\models\varphi\Rightarrow\exists\beta\in(X\cap\alpha)L_\beta\models\varphi</math>.

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

若<math>L_\alpha</math>在X上反射了所有的<math>\Pi_n(\Sigma_n)</math>公式，则称α是X上的<math>\Pi_n(\Sigma_n)</math>序数。

特别的，若<math>L_\alpha</math>在所有序数上反射了所有的<math>\Pi_n(\Sigma_n)</math>公式，则称α是<math>\Pi_n(\Sigma_n)</math>序数。

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

α是X上的<math>\Pi_n</math>反射序数，等价于α是X上的<math>\Sigma_{n+1}</math>反射序数

也就是说，我们只需要研究集合上的<math>\Pi_n</math>反射序数即可。进一步的有

α是X上的<math>\Pi_0</math>反射序数，等价于α是X上的<math>\Pi_1</math>反射序数，等价于α是X上的极限点。

在一些资料中，会出现<math>\Pi_0</math>反射等价于全体序数的说法。这是错误的。事实上，如果我们想要写出全体序数，应该写出<math>Ord</math>。

我们还有结论：α是X上的<math>\Pi_2</math>反射序数，等价于α是X上的容许序数。

== 结构讲解 ==

=== 基本符号 ===

==== onto ====
onto 是反射模式的核心。它的作用对象是一个集合，同时也输出一个集合。例如： <math>\Pi_1\ \mathrm{onto}</math>全体序数，得到的是全体极限序数构成的集合；<math>\Pi_2\ \mathrm{onto}</math>全体序数构成的集合，得到的是全体容许序数构成的集合。

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

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

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

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

=== <math>\Pi_1</math>反射 ===

==== 1- 的作用 ====
<math>\Pi_1\ \mathrm{onto}</math> 一个集合的效果，是取出这个集合中所有的极限点。所谓的极限点，就是前极限序数个元素的上确界。

现在我们可以来推导一下 1 ，也即<math>\Pi_1\ \mathrm{onto}</math>全体序数的构成。

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

前ω个序数的上确界为ω，前<math>\omega\times2</math>个序数的上确界为<math>\omega\times2</math> ……

事实上， 1 就等于全体极限序数的集合<math>\{\omega,\omega\times2,\dots,\omega^2,\dots,\omega^\omega,\dots\Omega,\dots\}</math> 。

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

继续递推，还能得到

<math>1-1-1= \{\omega^3,\omega^3\times2,\dots,\omega^\omega,\dots,\Omega,\dots\}</math>

<math>1-1-1-1=\{\omega^4,\omega^4\times2,\dots,\omega^\omega,\dots,\Omega,\dots\}</math>

……直到——

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

但，<math>(1-)^\omega</math>呢？

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

自然地，我们可以推导出<math>(1-)^\omega=\{\omega^\omega,\omega^\omega\times2,\dots,\omega^{\omega+1},\dots,\Omega,\dots\}</math>，即<math>\omega^\omega</math>的倍数的集合。

<math>(1-)^\alpha</math>，就是<math>\omega^\alpha</math> 的倍数的集合，<math>\min\ (1-)^\alpha=\omega^\alpha</math>。

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

我们定义<math>(1-)^{1,0}=\{\alpha|\alpha=\min\ (1-)^\alpha\}</math>。根据上一节的结论，我们可以知道<math>\min\ (1-)^\alpha=\omega^\alpha</math>。因此， <math>(1-)^{1,0}</math>是全体 <math>\varepsilon</math>序数的集合，即 <math>\{\varepsilon_0,\varepsilon_1,\dots,\varepsilon_\omega,\dots,\zeta_0,\dots,\Omega,\dots\}</math>。

可以继续对 <math>(1-)^{1,0}</math>进行 1- 的操作，得到的集合记为 <math>(1-)^{1,1}</math>。<math>(1-)^{1,1}</math>应当是全体“下标为极限序数的<math>\varepsilon</math> 序数”的集合，即<math>(1-)^{1,1}=\{\varepsilon_\omega,\varepsilon_{\omega\times2},\dots,\varepsilon_{\omega^2},\dots,\zeta_0,\dots,\Omega,\dots\}</math>。

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

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

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

=== <math>\Pi_2</math>反射和容许序数 ===
<math>\Pi_2~\mathrm{onto}</math>任意集合的作用，暂时是难以说明的，所以我们先从<math>\Pi_2~\mathrm{onto}</math>全体序数开始。这里不加证明地给出以下结论：<math>\Pi_2</math> 反射作用于全体序数的集合，得到的是全体容许序数的集合。

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

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

紧接着，第二个容许序数是 <math>\omega_2^{CK}</math>，在这里写作<math>\Omega_2</math>。它无法通过包括<math>\Omega</math> 在内的比它小的序数通过递归运算得到，这意味着<math>\Omega_2</math>不是<math>\Omega\times2,\Omega^2,\varepsilon_{\Omega+1},\varphi(\Omega,1)</math>之类的东西，而是远远在它们之上的存在。

再然后，还会有<math>\Omega_3,\Omega_4,\dots,\Omega_{\omega+1},\dots,\Omega_{\Omega+1},\dots</math>它们一同组成了容许序数的集合。

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

更进一步地，<math>\mathrm{OFP}=\psi_I(0)</math>存在一条长度为ω的基本列<math>\{\Omega,\Omega_\Omega,\Omega_{\Omega_{\Omega}},\dots\}</math>，它也是非容许的。

事实上，对于大多数的<math>\Omega_\alpha</math>，其中 α为极限序数， α的基本列总是会成为我们我们的突破口，让我们找到<math>\Omega_\alpha</math>的一条长度小于自身的基本列。

顺便一提，对于所有的后继序数α，<math>\Omega_\alpha</math>都毫无疑问是容许序数。

==== <math>1-2,~(1-)^{1,0}~2</math>等 ====
1-2 ，即取出集合 <math>2=\{\Omega,\Omega_2,\dots,\Omega_{\omega+1},\dots,\Omega_{\Omega+1},\dots\}</math>中所有的极限点。

2 中的前ω 个序数的上确界是<math>\sup\{\Omega,\Omega_2,\dots\}=\Omega_\omega</math>，所以 <math>\Omega_\omega\in1-2</math>；

2 中的前 <math>\omega\times2</math>个序数的上确界是<math>\Omega_{\omega\times2}</math>，所以<math>\Omega_{\omega\times2}\in1-2</math>……

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

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

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

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

==== 递归不可达序数 ====
我们不妨思考一下，若一个极限序数α足以使得<math>\Omega_\alpha</math>为容许序数的话，它需要满足什么条件呢？

首先，α是容许序数；其次， <math>\alpha\in1-2</math> 。即满足上述条件的α属于 2 和 1-2 的交集，记为 <math>\alpha\in2~1-2</math>。

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

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

接下来，我们还可以对 2~1-2 进行若干次 1- ，例如<math>1-2~1-2=\{I_\omega,I_{\omega\times2},\dots,I_I,\dots,\mathrm{IFP},\dots\}</math>。推导过程和 1-2 是一致的，注意 1-2~1-2 表示的实际上是 <math>1~\mathrm{onto}~(2~1-2)</math>。

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

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

序数 <math>\Theta</math>为函数<math>f(\alpha)</math> 的容许点，等同于<math>\Theta</math> 是 <math>f(\alpha)</math>的不动点且为容许序数。

于是我们可以看到，<math>\Omega</math>是函数<math>f(\alpha)=\omega^\alpha</math> 的容许点；I 是函数 <math>f(\alpha)=\Omega_\alpha</math> 的容许点。

更一般地，若函数<math>f(\alpha)</math>的值域是集合 A ，那么<math>f(\alpha)</math>的容许点组成的集合是<math>2~1-A</math> 。

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

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

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

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

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

……

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