更改

==== 构造序数 = 递归序数 ====

==== 构造序数 = 递归序数 ====

可数序数有两种自然刻画："'''构造序数'''"（能被某个机械记号系统命名，见 [[#6.1|5.8.1]]）与"'''递归序数'''"（某个可计算良序的长度——即存在一个可计算的大小关系，把一堆自然数排成该长度的"无限队列"）。

可数序数有两种自然刻画："'''构造序数'''"（能被某个机械记号系统命名，见 [[#|5.8.1]]）与"'''递归序数'''"（某个可计算良序的长度——即存在一个可计算的大小关系，把一堆自然数排成该长度的"无限队列"）。

* '''Markwald–Spector 定理（1954/1955）'''：两种刻画恰好等价——构造序数 ⟺ [[递归序数]]<ref name="rogers1967" /><ref name="moschovakis2010" />。

* '''Markwald–Spector 定理（1954/1955）'''：两种刻画恰好等价——构造序数 ⟺ [[递归序数]]<ref name="rogers1967" /><ref name="moschovakis2010" />。

'''[[Turing跳跃]]（Turing jump）'''：对任何集合 A，把"哪些以 A 为神谕的程序会停机"这一问题本身收集成一个集合，记作 A′（读作"A 撇"）。可以证明：A′ 以 A 为神谕仍不可计算——每跳一次，都得到一个严格更难的"相对版停机问题"。特别地，从空集 <math>\emptyset</math> 出发跳一次得到的 <math>\emptyset'</math>，正是通常意义下的停机问题（[[#图灵停机问题（1936）|5.7.3]]）。

'''[[Turing跳跃]]（Turing jump）'''：对任何集合 A，把"哪些以 A 为神谕的程序会停机"这一问题本身收集成一个集合，记作 A′（读作"A 撇"）。可以证明：A′ 以 A 为神谕仍不可计算——每跳一次，都得到一个严格更难的"相对版停机问题"。特别地，从空集 <math>\emptyset</math> 出发跳一次得到的 <math>\emptyset'</math>，正是通常意义下的停机问题（[[#图灵停机问题（1936）|5.7.3]]）。

'''沿构造序数"盖楼"'''：现在从 <math>H_0 = \emptyset</math> 出发，沿构造序数（见 [[#6.1|5.8.1]]）逐层往上盖：

'''沿构造序数"盖楼"'''：现在从 <math>H_0 = \emptyset</math> 出发，沿构造序数（见 [[#通用序数记号系统ω_1^{CK}|5.8.1]]）逐层往上盖：

: <math>H_{\alpha+1}</math> = (<math>H_\alpha</math>)′　（后继层：再跳一次，复杂度升一级）   

: <math>H_{\alpha+1}</math> = (<math>H_\alpha</math>)′　（后继层：再跳一次，复杂度升一级）   

: <math>H_\lambda = \cup_n H_{\lambda_n}</math>　（极限层：把下面各层沿一条可计算上升的序列 <math>\lambda_0 < \lambda_1 < \lambda_2 < \ldots</math> 并起来——'''沿哪条序列取并由 <math>\lambda</math> 的代号给出'''，[[#6.1|5.8.1]] 里"记号携带程序编号"的约定在此派上用场）

: <math>H_\lambda = \cup_n H_{\lambda_n}</math>　（极限层：把下面各层沿一条可计算上升的序列 <math>\lambda_0 < \lambda_1 < \lambda_2 < \ldots</math> 并起来——'''沿哪条序列取并由 <math>\lambda</math> 的代号给出'''，[[#通用序数记号系统ω_1^{CK}|5.8.1]] 里"记号携带程序编号"的约定在此派上用场）

在某一层 <math>H_\alpha</math> 中可计算的集合，称为'''[[超算术的]]（hyperarithmetical, HYP）'''。这栋楼的前几层串起熟悉的图景：'''只盖有穷多层，得到的恰好是通常的算术层级'''——穷尽一阶算术（量词只作用于自然数）可定义的全部集合；盖到第 <math>\omega</math> 层（<math>\omega</math> 即 [[#6.1|5.8.1]] 中最小的无穷序数），得到的集合已足以一举判定[[皮亚诺公理]]体系的全部真语句——包括所有皮亚诺公理体系证明不了的真命题（对照 [[#哥德尔第一不完备定理（1931）|5.7.4]] 的不完备性）；而楼并不停在这里，它沿构造序数一直盖到 <math>\omega_1^CK</math> 为止。HYP 因此是真正高于算术层级的层级——至于它究竟高到哪一步（恰好等价于一个"二阶量词"的定义能力），正是 [[#超算术集与有效描述集合论|5.8.4]] 的主题<ref name="moschovakis2010" />。

在某一层 <math>H_\alpha</math> 中可计算的集合，称为'''[[超算术的]]（hyperarithmetical, HYP）'''。这栋楼的前几层串起熟悉的图景：'''只盖有穷多层，得到的恰好是通常的算术层级'''——穷尽一阶算术（量词只作用于自然数）可定义的全部集合；盖到第 <math>\omega</math> 层（<math>\omega</math> 即 [[#通用序数记号系统ω_1^{CK}|5.8.1]] 中最小的无穷序数），得到的集合已足以一举判定[[皮亚诺公理]]体系的全部真语句——包括所有皮亚诺公理体系证明不了的真命题（对照 [[#哥德尔第一不完备定理（1931）|5.7.4]] 的不完备性）；而楼并不停在这里，它沿构造序数一直盖到 <math>\omega_1^CK</math> 为止。HYP 因此是真正高于算术层级的层级——至于它究竟高到哪一步（恰好等价于一个"二阶量词"的定义能力），正是 [[#超算术集与有效描述集合论|5.8.4]] 的主题<ref name="moschovakis2010" />。

问题来了：同一序数 <math>\alpha</math> 在系统中有'''无穷多个代号'''，用不同代号构造出的 <math>H_\alpha</math> 会不会不同？

问题来了：同一序数 <math>\alpha</math> 在系统中有'''无穷多个代号'''，用不同代号构造出的 <math>H_\alpha</math> 会不会不同？