3,094
个编辑
更改
跳到导航
跳到搜索
第684行：
第684行： − + − +
→构造序数 = 递归序数
==== 构造序数 = 递归序数 ====
==== 构造序数 = 递归序数 ====
可数序数有两种自然刻画："'''构造序数'''"（能被某个机械记号系统命名，见 [[#|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" />。
这是经典集合论事实"第二数类的两种刻画等价"的可计算版本；两个方向的证明都以 SRT 为归纳枢纽<ref name="moschovakis2010" />。
这是经典集合论事实"第二数类的两种刻画等价"的可计算版本；两个方向的证明都以 SRT 为归纳枢纽<ref name="moschovakis2010" />。