3,094
个编辑
更改
跳到导航
跳到搜索
第552行：
第552行： − + 第563行：
第563行： − − [[文件:Kleene记号系统O.png|缩略图|'''图5'''：[[Kleene's O|Kleene 记号系统 O]] 的树状结构示意。每个自然数都是某个序数的代号——规则：<math>\mid 1\mid = 0</math>（最底层）；<math>\mid 2^x\mid = \mid x\mid + 1</math>（后继，沿着"2 的幂"链向上）；<math>\mid 3\cdot5^e\mid = lim_n\mid\phi_e(n)\mid</math>（'''极限'''——'''记号里携带基本序列程序的编号 e，这正是 SRT 大显身手的地方'''）。所有构造序数都在这棵树上生长；树顶是 <math>\omega_1^CK</math>（无法被任何机械记号触及的边界）。]] 第578行：
第576行： + + +
→通用序数记号系统与\omega_1^{CK}
* '''代号与所指'''：记号系统里的每个自然数 <math>a</math> 都是一个'''代号'''，它所指的序数记作 <math>|a|</math>。一个序数 <math>\alpha</math> 的'''后继'''（successor）就是 <math>\alpha+1</math>（0 的后继是 1，<math>\omega</math> 的后继是 <math>\omega+1</math>）。'''极限序数'''（limit ordinal，下文统记作 <math>\lambda</math>）则是既非 0 也非任何序数之后继的序数——它不能靠"+1"走到，只能被一列递增的序数"逼近"，最典型的例子是 <math>\omega</math>（<math>0, 1, 2, 3, \ldots</math> 无限数完之后的那一步：任何自然数都不是它的"前一个"）。
* '''代号与所指'''：记号系统里的每个自然数 <math>a</math> 都是一个'''代号'''，它所指的序数记作 <math>|a|</math>。一个序数 <math>\alpha</math> 的'''后继'''（successor）就是 <math>\alpha+1</math>（0 的后继是 1，<math>\omega</math> 的后继是 <math>\omega+1</math>）。'''极限序数'''（limit ordinal，下文统记作 <math>\lambda</math>）则是既非 0 也非任何序数之后继的序数——它不能靠"+1"走到，只能被一列递增的序数"逼近"，最典型的例子是 <math>\omega</math>（<math>0, 1, 2, 3, \ldots</math> 无限数完之后的那一步：任何自然数都不是它的"前一个"）。
* '''前驱与基本序列'''：后继代号 <math>x</math> 的'''前驱'''（predecessor）记 <math>P(x)</math>——所指序数被"+1"之前那个序数的代号。极限代号 <math>x</math> 的'''基本序列（fundamental sequence）'''是一条可机械取出的递增代号列 <math>x_0</math>, <math>x_1,x_2,\ldots</math>，所指序数 <math>|x_0| < |x_1| < \ldots</math> 逐渐逼近 <math>|x|<m/ath>。
* '''前驱与基本序列'''：后继代号 <math>x</math> 的'''前驱'''（predecessor）记 <math>P(x)</math>——所指序数被"+1"之前那个序数的代号。极限代号 <math>x</math> 的'''基本序列（fundamental sequence）'''是一条可机械取出的递增代号列 <math>x_0</math>, <math>x_1,x_2,\ldots</math>，所指序数 <math>|x_0| < |x_1| < \ldots</math> 逐渐逼近 <math>|x|</math>。
* <math>S_1</math> 的语法（<math>S_1</math> 是下文定理要构造的那个"通用"'''序数记号系统'''，Kleene 1938 为它设计的编码方案；后文的记号系统 O 沿用同一语法）：0 的代号固定为 1；代号 <math>a</math> 的后继的代号写成 '''<math>2^a</math>'''；极限序数的代号写成 '''<math>3\cdot 5^e</math>'''，并约定 <math>|3\cdot5^e| = \lim|\phi_e(n)|</math>（程序 <math>e</math> 逐个吐出逼近该极限的记号列，<math>\phi</math>ₑ 是编号为 <math>e</math> 的程序，见 §2.2）。取这三种质因数形态（1、2 的幂、3<math>\times5</math> 的幂）纯属编码技巧：对代号做质因数分解，就能机械判定它是 0 的代号、后继代号还是极限代号。
* <math>S_1</math> 的语法（<math>S_1</math> 是下文定理要构造的那个"通用"'''序数记号系统'''，Kleene 1938 为它设计的编码方案；后文的记号系统 O 沿用同一语法）：0 的代号固定为 1；代号 <math>a</math> 的后继的代号写成 '''<math>2^a</math>'''；极限序数的代号写成 '''<math>3\cdot 5^e</math>'''，并约定 <math>|3\cdot5^e| = \lim|\phi_e(n)|</math>（程序 <math>e</math> 逐个吐出逼近该极限的记号列，<math>\phi</math>ₑ 是编号为 <math>e</math> 的程序，见 §2.2）。取这三种质因数形态（1、2 的幂、3<math>\times5</math> 的幂）纯属编码技巧：对代号做质因数分解，就能机械判定它是 0 的代号、后继代号还是极限代号。
: <math>\psi(x) = 2^\psi(P(x))</math> （<math>x</math> 是后继序数的代号时，<math>P(x)</math> 是前驱代号）
: <math>\psi(x) = 2^\psi(P(x))</math> （<math>x</math> 是后继序数的代号时，<math>P(x)</math> 是前驱代号）
: <math>\psi(x) = 3\cdot5^e</math> （<math>x</math> 是极限序数的代号时，<math>e</math> 是"逐点翻译基本序列"那个程序的编号）
: <math>\psi(x) = 3\cdot5^e</math> （<math>x</math> 是极限序数的代号时，<math>e</math> 是"逐点翻译基本序列"那个程序的编号）
第三行的 <math>e</math> 值得拆开细看——'''<math>\psi</math> 的定义需要用到 <math>\psi</math>，循环正藏在 e 的代码里'''。设 <math>\lambda</math> 是 <math>S</math> 能命名的某个极限序数（就是上文说的那种"既非 0 也非后继、只能被逼近"的序数，例如 <math>\omega</math>），<math>x</math> 是它在 <math>S</math> 中的代号；<math>S</math> 是合法记号系统，故 <math>x</math> 自带一条可计算的基本序列 <math>x_0,x_1,x_2,\ldots</math>——一列递增的代号，所指序数逐渐逼近 <math>\lambda</math>。按上面交代的语法，极限序数的代号必须写成 <math>3\cdot 5^e</math> 的形态，所以 <math>\psi(x)</math> 必须形如 <math>3\cdot5^e</math>，其中 <math>e</math> 是这样一个程序的编号：
第三行的 <math>e</math> 值得拆开细看——'''<math>\psi</math> 的定义需要用到 <math>\psi</math>，循环正藏在 e 的代码里'''。设 <math>\lambda</math> 是 <math>S</math> 能命名的某个极限序数（就是上文说的那种"既非 0 也非后继、只能被逼近"的序数，例如 <math>\omega</math>），<math>x</math> 是它在 <math>S</math> 中的代号；<math>S</math> 是合法记号系统，故 <math>x</math> 自带一条可计算的基本序列 <math>x_0,x_1,x_2,\ldots</math>——一列递增的代号，所指序数逐渐逼近 <math>\lambda</math>。按上面交代的语法，极限序数的代号必须写成 <math>3\cdot 5^e</math> 的形态，所以 <math>\psi(x)</math> 必须形如 <math>3\cdot5^e</math>，其中 <math>e</math> 是这样一个程序的编号：
顺带分辨两行的差异：第二行 <math>\psi(x) = 2^\psi(P(x))</math> 是'''值依赖值'''的循环，且 <math>P(x)</math> 指向更小的序数，本质上是良基的（"良基"：不存在无穷下降链，所以"沿序数从小到大做归纳"是合法的）；第三行则是'''编号依赖编号'''的循环（<math>e</math> 的代码里嵌着 <math>\psi</math> 的编号），良基性救不了它——必须 SRT。
顺带分辨两行的差异：第二行 <math>\psi(x) = 2^\psi(P(x))</math> 是'''值依赖值'''的循环，且 <math>P(x)</math> 指向更小的序数，本质上是良基的（"良基"：不存在无穷下降链，所以"沿序数从小到大做归纳"是合法的）；第三行则是'''编号依赖编号'''的循环（<math>e</math> 的代码里嵌着 <math>\psi</math> 的编号），良基性救不了它——必须 SRT。
[[文件:Kleene记号系统O.png|缩略图|'''图5'''：[[Kleene's O|Kleene 记号系统 O]] 的树状结构示意。每个自然数都是某个序数的代号——规则：<math>\mid 1\mid = 0</math>（最底层）；<math>\mid 2^x\mid = \mid x\mid + 1</math>（后继，沿着"2 的幂"链向上）；<math>\mid 3\cdot5^e\mid = lim_n\mid\phi_e(n)\mid</math>（'''极限'''——'''记号里携带基本序列程序的编号 e，这正是 SRT 大显身手的地方'''）。所有构造序数都在这棵树上生长；树顶是 <math>\omega_1^CK</math>（无法被任何机械记号触及的边界）。]]
在 <math>S_1</math> 的基础上，Kleene 进一步构造了带树状[[偏序关系]]的'''序数记号系统 O（Kleene's O）'''——"偏序"（partial order）指只在部分代号对之间定义的"小于"关系（O 中记作 <O，反映所指序数的大小）。O 是通用且极大的：每个可被任何合法记号系统命名的序数（称为'''构造序数'''，constructive ordinal）在 O 中都有代号。全体[[递归序数|构造序数]]的[[上确界]]（supremum：不小于它们中任何一个的最小序数）
在 <math>S_1</math> 的基础上，Kleene 进一步构造了带树状[[偏序关系]]的'''序数记号系统 O（Kleene's O）'''——"偏序"（partial order）指只在部分代号对之间定义的"小于"关系（O 中记作 <O，反映所指序数的大小）。O 是通用且极大的：每个可被任何合法记号系统命名的序数（称为'''构造序数'''，constructive ordinal）在 O 中都有代号。全体[[递归序数|构造序数]]的[[上确界]]（supremum：不小于它们中任何一个的最小序数）