反射序数
更多操作
反射是一个非递归记号。它表示非递归序数,其特点是并不会表示其极限之下的所有序数。它具有深厚的集合论背景
数学定义
前排提醒:对数学定义不感冒或者看不懂的读者可以跳到后面
根据命题中无界量词的性质,给出公式的层次:
满足如下条件之一的集合论公式称为 公式:
- 它不包含无界量词
- 它形如 ,其中 为 公式
- 它形如 或 ,其中 为 公式
公式中的所有量词都是有界的。
公式及 公式定义如下:
- 公式及 公式为 公式。
- 如果 为 公式,则 为 公式。
- 如果 为 公式,则 为 公式。
反射的定义:
L 为可构造宇宙, 在 X 上反射了公式 ,是说 。若 在 X 上反射了所有的 公式,则称 α 是 X 上的 序数。特别的,若 在所有序数上反射了所有的 公式,则称 α 是 序数。
或者说,一个序数 被称为 上的 ,当且仅当 。
关于反射序数有如下的重要结论:
- α 是 X 上的 反射序数,等价于 α 是 X 上的 反射序数(也就是说,我们只需要研究集合上的 反射序数即可)
- α 是 X 上的 反射序数,等价于 α 是 X 上的 反射序数,等价于 α 是 X 上的极限点
- α 是 X 上的 反射序数,等价于 α 是 X 上的容许序数
注:在一些资料中,会出现 反射等价于全体序数的说法。这是错误的。事实上,如果我们想要写出全体序数,应该写出 (或 )
结构讲解
基本符号
onto
onto 是反射模式的核心。它的作用对象是一个集合,同时也输出一个集合。例如: ,得到的是全体极限序数构成的集合;构成的集合,得到的是全体容许序数构成的集合。
方便起见,我们把 简写为 n-X 。这里的 n 是自然数, X 是被操作的集合。特殊地,当 X 为全体序数,我们直接将它省略不写,此时的结果直接记为 n 。也就是说,在反射模式中, 1 可以用来表示 的结果,以此类推。
即: 定义为所有 X 上的 Γ-反射序数的集合。
∩
这里的 ∩ 指交集。没错,就是那个大家熟知的交集, 表示同时属于集合 A 和集合 B 的元素。交集也是反射模式中的一种重要运算。同样是为了方便起见,我们将 ∩ 简写为空格。 ∩ 在反射式中的运算优先级与 onto 相同,并且从右向左计算。例如: 2 1-2 表示 的集合; 2-3 1-3 2-3 表示 的集合。
以及
反射模式研究的集合中的元素都是序数。因此,我们可以把这些序数从小到大进行排序,并用 来分别表示集合 X 中从小到大的第 2 、第 3 以及第 n 个元素。不过,对于 X 中的第 1 个元素,我们一般不叫它 ,而是叫它 min X 。在不引起歧义的情况下,也可以把这个 min 省略,直接用 X 来指代 X 中的第一个元素。在会引起歧义的场合,则用 (X) 来代表 min X 。不建议使用 之类的“第超限序数个”的表达。
aft
将序数从小到大排序,排在后面的就是更大的序数。因此, 表示“集合 A 中大于序数 B 的元素”。将这一表达与 等结合起来,可以得到 、 等,分别表示“集合 A 中最小的大于序数 B 的元素”和“集合 A 中第二个大于序数 B 的元素”。
反射
1- 的作用
一个集合的效果,是取出这个集合中所有的极限点。所谓的极限点,就是前极限序数个元素的上确界。
现在我们可以来推导一下 1 ,也即 全体序数的构成。
具体地,我们需要遍历全体极限序数 α ,并找到前 α 个序数的上确界。
前 ω 个序数的上确界为 ω,前 个序数的上确界为 ……
事实上, 1 就等于全体极限序数的集合 。
类似地, 1 中的前 ω 个序数的上确界是 ,1 中的前 个序数的上确界是 ……因此,,是 的倍数的集合。
继续递推,还能得到
……直到:
方便起见,我们把重复的 1- 合并合并。把重复的操作用括号括起来,上标表示重复次数。这样, 1-1-1 可以写作 , 1-1-1-1 可以写作 。对于这种有限次的 1- ,我们都可以递归地得到它代表的集合。
但,呢?
我们首先需要定义 。较一般地,对于 ,其中 α 为极限序数的情况,我们只需要取交集,即定义 。
自然地,我们可以推导出 ,即 的倍数的集合。
,就是 的倍数的集合,。
等
上标只能放序数的情形是简单的,一个“ 的倍数”就直接解决了。如何让情形变得更有趣呢?我们可以借用 Veblen 函数的不动点进位模式,在上标上引入多个数字,来表示不同层级的不动点。
我们定义 。根据上一节的结论,我们可以知道 。因此,是全体 序数的集合,即 。
可以继续对 进行 1- 的操作,得到的集合记为 。 应当是全体“下标为极限序数的 序数”的集合,即。
更一般地,我们在上标上使用 weak Veblen 函数,记 为 。于是,我们还可以有 。在上标遇到极限序数时,我们也仍取交集。
直到我们遇见了新的不动点。我们定义 。借用 Veblen 函数的模式,我们还能把定义推广到 等等并且还能在此基础上进行扩展。理论上,只要扩展足够强力,所有的递归序数都能像这样被表示出来。
值得一提的是,本条目折叠不动点采用了 Veblen 函数式的写法。事实上,是存在 OCF 式的写法的。读者可以参见条目 Σ1 稳定序数。
反射和容许序数
任意集合的作用,暂时是难以说明的,所以我们先从 开始。这里不加证明地给出以下结论: 反射作用于全体序数的集合,得到的是全体容许序数的集合。
所谓容许序数,可以大致地理解为无法通过比它小的序数进行递归运算得到的序数。所谓的“无法通过比它小的序数进行递归运算得到的序数”,换用另一个更直观的概念,就是“不存在长度小于它的、递归表达的基本列的序数”。也就是说,如果我们找到了某个序数的一条长度小于它本身的基本列,就能立刻断言它不是容许序数。这为我们排除很多容许序数的备选提供了一条可行的方案。
最小的容许序数是 Church-Kleene 序数,记为 ,在这里我们把它写作 ——没错,就是在 OCF 中出现的那个。
紧接着,第二个容许序数是 ,在这里写作 。它无法通过包括 在内的比它小的序数通过递归运算得到,这意味着 不是 之类的东西,而是远远在它们之上的存在。
再然后,还会有 它们一同组成了容许序数的集合。
值得注意的是,上面一句话跳过了 ,而单独列出了 和 。这是因为 和 并非容许序数——这一点可以通过“找长度小于它本身的基本列”来实现。
更进一步地, 存在一条长度为 ω 的基本列 ,它也是非容许的。
事实上,对于大多数的 ,其中 α 为极限序数, α 的基本列总是会成为我们我们的突破口,让我们找到 的一条长度小于自身的基本列。
顺便一提,对于所有的后继序数 α, 都毫无疑问是容许序数。
等
1-2 ,即取出集合 中所有的极限点。
2 中的前 ω 个序数的上确界是 ,所以 ;
2 中的前 个序数的上确界是 ,所以 ……
如此一来, 1-2 就是“,其中 α 为极限序数”的集合。需要注意的是,这样的序数大多数都是非容许的。这意味着 1-2 这个集合中的大部分元素甚至不属于 2 。我们对 2 这个集合进行了 的操作,得到了一个性质更差的集合,这种事在反射里,是相当常见的。
接着是 1-1-2 。我们取集合 1-2 的极限点,可以得到“,其中 α 为 的倍数”的集合。同样地,我们可以通过取交集得到 乃至 。由于 ,所以 又可以写作 。这里在上标上省略了 min ,并且在外面加了一层括号用以和序数 2 区分。
于是我们来到了 。类似 的定义,。不难发现, 的每一个元素 α 都满足 ,因此, 是全体 OFP 的集合。.
过后,同样也有 。不过,不管 的上标的层级多深,只要它还是不动点的形式,它就是非容许的。
递归不可达序数
前排提示:关于 I 及多元 I 函数在 OCF 中的折叠规则,参见词条递归不可达序数
我们不妨思考一下,若一个极限序数 α 足以使得 为容许序数的话,它需要满足什么条件呢?
首先,α 是容许序数;其次, 。即满足上述条件的 α 属于 2 和 1-2 的交集,记为 。
根据 ZFC 公理体系,我们可以直接证明 2 和 1-2 的交集存在元素,我们将其命名为递归不可达序数。最小的递归不可达序数记作 I ,次小的是……就和 差不多。
总之,。注意到这里也没有列出 , 并非容许序数。
接下来,我们还可以对 2~1-2 进行若干次 1-,例如 。推导过程和 1-2 是一致的,注意 1-2~1-2 表示的实际上是 。
自然是全体 IFP,也就是满足 的序数构成的集合。
容许点
对“容许点”的定义,即:
序数 为函数 的容许点,等同于 是 的不动点且为容许序数。
于是我们可以看到, 是函数 的容许点;I 是函数 的容许点。
更一般地,若函数 的值域是集合 A ,那么 的容许点组成的集合是 。
在更以后的地方,提到的某函数的“马洛点”“ K 点”等“ X 点”概念也都指代“某序数是 X 序数且是该函数的不动点”。
I(1,0) 等二元 I 函数
函数 的容许点是什么呢?认为是 M 的读者可能受到了 IMK 经常被一同提起的影响。实际上,函数的最小的容许点仅仅是 I(1,0) 。受到《大数入门》的影响,部分读者会认为 I(1,0) 与 IFP 等同,实则并非如此。
根据前面提到的“若函数 的值域是集合 A ,那么 的容许点组成的集合是 。”的规则,不难知道,函数 的全体容许点的集合是 。
的次小的容许点是 I(1,1) 。这里,二元 I 的最后一位实质上相当于 或者 I 的下标。于是, 。 同样是非容许的。
是函数 的不动点,记作 。最小的 也并非 I(2,0) 。 I(2,0) 是函数 的容许点。多元 I 函数的这种进位方式,称为容许点进位。
……
像这样继续往前,自然会遇到 ,我们期望它是 。如果我们仍用定义 时的交集来定义它会怎么样呢?下面才会真正开始涉及真伪的争端……
psd. 和 real.
的定义方式与 是类似的。即:
这意味着 以及 α 为后继序数时, 都存在一条长度为 ω 的基本列,这使得 非容许。这与前面的 的性质是截然相反的。最小的同时满足“ α 是极限序数”和“ 容许”的序数是函数 的容许点,记作 。
对于 等“高位为极限序数的二元 I 函数”的情形,都可以像这样定义。对于绝大多数极限序数 β 和后继序数 α, 都不是容许序数。
对于使用交集定义的 ,一般称作 。即
现在让我们思考一下一个序数如果要是 ,它需要具备哪些性质。根据上面的结论,我们可以推出:
为容许序数 等函数的不动点
首先关注后面的条件。利用类似 Veblen 函数的“闭包”机制,可以证明,α 为这些函数的不动点等同于 。那么,整个条件就变为了“α 是 序数且 为容许序数”。这正是我们要刻画的 的模样。
像这样直接跳过 一族序数似乎不太好。我们希望能有一个简单的反射式子来表示它们,并且最好这个简单的式子就是 。这就引出了下面的 的定义:
定义完了 之后,我们会发现 实际上就是 。如此一来就建立了 psd. 和 real. 的联系。
重要:psd. 和 real. 的形式类似、性质则相当不同,容易引起不必要的争端。因此,本条目在之后提及 和类似的 等序数时,若不使用前缀,则默认为 psd. 定义。因此,可以直接写 。
多元 I 函数
顺着 继续往上,使用容许点进位的规则和 psd. 定义,有:
是 的最小的容许点, ;
是 的最小的容许点,;
是全体 序数。 ;
……
像这样,我们可以确定任意的 的景象。当 α 为后继序数时, 是全体 序数中的容许序数;当 α 为极限序数时, 就是全体 序数。
上标增加到一定程度,自然就会出现不动点。与 类似地,我们把满足 的序数集合记作 。
我们可以像这样用二元 I 函数来表示它 :
即 是全体 的不动点。最小的这样的不动点该如何用多元 I 表示? I(1,0,0) 吗?不要忘了 I 的容许点进位规则。它应该是 。次大的不动点自然就是了。所以,有:
是函数 的容许点,也就是全体 序数中的容许序数。在这里, 的强度借助不动点,有了一个提升。
后面的多元 I 并没有新的附加规则,只需要牢记容许点进位即可。如
……
递归马洛序数
前排提示:关于 M 在 OCF 中的折叠规则,参见词条递归 Mahlo 序数
进一步增加 的上标的深度之后,我们会被一道新的不可逾越之壁所阻挡。正如同 无法通过单纯的 1- 操作得到一样, 也无法通过单纯的 操作得到。我们把这样的 M 称作递归马洛序数。
递归马洛序数有无穷多个。我们把第二个,第三个……递归马洛序数分别记为 ,就像这样:
当然了, 也不是递归马洛序数。它甚至不是容许序数——所有的递归马洛序数都是容许序数。
对递归马洛序数的集合进行 1- 反射,可以得到:
即 1-2-2 是全体 “,其中 α 为极限序数”所构成的集合。自然地,我们有 。根据定义,它是全体满足 的集合,也就是 MFP ,函数 的不动点。
那么,函数 的容许点又如何呢?根据前文所讲的容许点的性质,可以知道,这个函数的全体容许点构成了集合 。后面 类似前文所述的多元 I 函数,这里不再赘述。
接下来,会有一个序数能折叠 。也就是,任意深度的 操作到 2-2 这个集合上,都得不到它。这个序数就是 ,即 。
还可以更深入地了解一下 这个大序数的性质。暂时把它记作 X 吧。
首先, X 要能折叠 操作,所以它至少要是递归马洛序数,即 ;
然后,需要考虑一下这样的 X 相对于普通的递归马洛序数有哪些不同之处。 X 能折叠出函数 的容许点,而这些容许点有什么特性呢?回到容许点的定义,可以知道,这些容许点都是 的不动点,也即 。
所有的 自然也是 1-2-2 。那么,就得到了 同时是 2-2 和 1-2-2 的结论。更进一步的证明显示, 与 等价——这可不是一句无意义的废话。我们对 的定义实际上是 ,这里证明了交集和最左侧的 onto 运算次序可以交换。
我们称这样既是递归马洛序数,又是函数 不动点的序数,称为该函数的 M 点。
更深的反射
tips:这里的任意深度可以理解为,你有一个强度穷尽所有递归序数的扩展 Veblen 函数,这里你的上标则拥有任意强度的你的扩展 Veblen。
可以对 继续进行 1- 和 操作,得到更大的序数。同样地,我们会有 ,,以及折叠它们的 。 也等同于 。我们可以对其不断进行 操作。
操作的上标也可以进一步加深。自然地,有一个大序数折叠它。这就是 2-2-2 ,我们将其称为不可转换序数,记作 N。即:
类似的, 是函数 的N点。
在 之后,又可以加深 操作的层级,并引入一个更大的序数折叠这一操作。这样得到的就是 2-2-2-2 了。这个序数过于“不整”,以至于它并没有一个专有的名字和符号。
到这里,足以勾勒出一个对 的印象了。我们可以这样理解 集合 X 的行为:
是对 的折叠。
可以发现,这个集合 X 越强, 所折叠的操作也越强。而反过来,如果这个 X 本身性质不够好的话,也会“连累” 的强度一起变弱。
那么,通往 2-2-2-2-2 的路也明确了。类似地,还能继续得到 ,直至 。这里的 也使用 psd. 定义,即
而 是理想状态的 。思路和 是类似的。
注意:在 这里实际上存在一个大坑。正如前文所说的,当 X 的性质不够好的时候,会“连累” 一起变弱。而这里的 就是一个性质不够好的集合。这使得 其实很弱,并不是 。不过,我们仍可以通过另一种思路得到它 。即定义“ 点”为 sup{不动点,容许点,M 点,N 点,……},那么 折叠“取 点”的操作。不过,出于书写符号的方便,仍把 记作 。
等
现在,可以对它们进行 2- 反射以继续前进了。也就是:
折叠任意深度的
折叠“取 点”的操作。
上标上的序数可以一直增加,每次经过极限序数的时候都会碰到一点关于 psd. 和 real. 的破事。不过,对于不想搭理这些破事的读者,记住 psd. 规则和“real. 相当于 +1”就已经足够了。
接下来,还会有 ,,以及 和 ……这样做的极限就是 了。
注意到上一句话的用词是“极限”而不是“不动点”。这样用词是因为这里也有 的定义问题。对于 ,有如下定义:
简而言之, 只要求对于所有 ,在 α 的下方都存在一个 的序数,对 α 自身的性质未作出要求;而 要求 α 自身就是 序数。
显然不是容许序数。可以用类似 OFP 的方式为它找到一条长度为 ω 的递归基本列。
不想搭理破事的读者依旧可以把 理解为 ,它折叠“取 点”的操作。这里就不展开细说了。
然后,是 以及这样做的极限 。上标的规则没什么变化。进一步加深上标,就会得到 之类的东西。
是时候,把这些恼人的上标也送去折叠了。
递归弱紧致序数
折叠 2- 操作的序数称为递归弱紧致序数,写作 K 。全体递归弱紧致序数构成的集合也是 反射作用于全体序数得到的集合,在反射模式中记作 3 。即
所有的递归弱紧致序数,都同时是容许序数、递归不可达序数、递归马洛序数、不可转换序数……等等等等。
可以对 3 这个集合施加、 反射操作,继续枚举:
。 是所谓的 KFP 构成的集合。 是函数 的容许点。 折叠任意深度的 ,它们也是函数 的马洛点。 折叠任意深度的,它们也是函数 的 N 点。 是满足“对于任意 ,都存在 使得 ”的全体序数 α 构成的集合,它也是集合 与集合 1-3 的交集。
是集合 3 与集合 1-3 的交集,折叠任意深度的 。与 类似,它也可以被理解为全体“足以使得 是递归弱紧致序数的极限序数 α”所构成的集合,以及函数 的 K 点。
从 3 到 ,我们相当于把从 Ord 到 3 的路又走了一遍。
再走第二遍的话,我们就会路过 ,最终到达 。再走第三遍,到达 。
花吃奶的劲突破超限序数,到达 。
而 2-3 可以折叠任意深度的 。正如我们上一篇所说的, 2-X 折叠 的操作。 X 本身强得可怕的时候, 2-X 就会更加强得可怕。
以上,还只是 反射能形成的丰富结构中最靠前的一部分。
从 到 再到
继续构造一个函数 用来表示“第 α 个 2-3 ”,然后继续前进。中间又会经过 ,而 是这个函数的 K 点。
然后,是 之类的东西。
什么折叠任意深度的 呢?注意到从 2-3 到这里的过程相当于从 Ord 到 2-3 ,所以它应该是 ,也就是 的 2-3 点。
利用“取 2-3 点”的操作,又可以有 等等。
在这之后, 2-2-3 能折叠任意深度的 ,也就是“取 2-3 点”这么一个操作。
2-2-2-3 折叠任意深度的 。这一部分和前面的 2-2-2 没什么不同,只是底层由“ 1- 反射”变为了“ 操作”。直到 。
。在它下面的每一个 β ,都存在一个 序数小于它。
接下来考虑一个能折叠任意深度的 的序数。这个序数能折叠 2- 的操作,所以是一个 序数;同时,它又至少是 2-3。因此,这个序数至少是 3 和 2-3 的交集。依旧可以证明,这个条件已经足够了。也就是 。
,这是“计数 的函数”的容许点。
,这是“计数 的函数”的马洛点。
,这是“计数 的函数”的 K 点。
……
折叠任意深度的 。这里是一个易错点。根据前面提到的“2-3 折叠”可以知道。折叠 的应该是“计数 的函数”的 2-3 点,也就是 ,而并非 。
。
折叠任意深度的 。
……
然后,有 折叠任意深度的 。它是“计数 的函数”的 点。这是我们第一次在“XX 点”的概念中涉及到交集。 要折叠的正是这个“取 点”的概念。
再取一次 点看看。。
折叠任意深度的 。 折叠任意深度的 。 折叠任意深度的 。再才有 折叠任意深度的 。 是“计数 的函数”的 点。 折叠任意深度的 。 折叠任意深度的 。 折叠任意深度的 。
稍微理一下这一段的逻辑:我们对一个表达式不断地进行 2- 的操作,折叠 2- 操作的是最前面有个“3 ”(注意空格)的表达式;然后对这个有“3 ”的表达式再不断进行 2- 操作,再折叠它……最终形成一条 的链条。每一次最基础的 2- 操作,都要折叠一次“取自己点”的操作。好一个折叠再折叠。
延伸这个链条到超限序数,就能看到 还有 。
现在,终于可以打开 的大门了。 集合 X 的行为实际上与 很像。我们有 是对 的折叠。
更进一步地,我们可以给出 的行为: 是对 的折叠。
理论上,现在我们畅通无阻、直通 了。
反射式的展开操作规则
是否存在一套简单的规律以便我们判断某一个反射式折叠了什么操作?答案是肯定的。并且这一规律奇妙地与 PrSS 存在联系。具体操作分为以下几步:
第一步,替换。把反射式中间的空格和 - 都替换为逗号,然后倒序排列。例如 先变为 2,4,2,3,4 ,再倒序排列为 4,3,2,4,2 ;
第二步,补项。若第一项为 k ,在前面补上 ;若式子中后一项减前一项的差 >1,也在中间补上连续自然数,使得任意一项都不超过前一项 +1 ,这样,序列就变为了一个标准的 PrSS 序列。补上的项需要做好标记。上一步得到的 4,3,2,4,2 在这里补项为 ;
第三步,展开。按照 PrSS 规则展开序列,复制坏部的时候需要连标记一并复制,但坏根除外。上一步的结果在这里展开为 ;
最后一步,还原。去掉被标记的项,倒序回来,将逗号还原为空格和 -,此时的结果就是原来的反射式要折叠的结构。上一步的展开结果还原为 ,即 。
于是我们得到: 折叠任意深度的 。