递归函数(九)
对此问题的否定回答表明 deg�(�) 与其他度的关系唯一地决定了 � 相对于 �� 的不可解度。最近的研究已经指向这个方向(例如,参见 Slaman 2008)。尽管如此,在 2020 年更新此条目时,问题 3.2 仍然是可计算性理论中的一个重要未解决的问题,其起源可以追溯到上面概述的图灵、波斯特和克莱恩的原始基础工作。
3.6 算术和分析层次结构
多一度��和图灵度��有时被称为层次结构,因为它们确定了�(�)(即自然数子集)的相对可计算性的排序。在 20 世纪 40 年代和 50 年代的一系列论文中,克莱尼(1943 年开始)和莫斯托斯基(1947 年开始)意识到,也可以根据一阶或二阶算术语言中定义集合 �⊆� 的最简单谓词的逻辑复杂性,对 �(�) 施加另一种排序。这个想法导致了所谓的算术和分析层次结构,它们都可以理解为根据集合的定义(或描述)复杂性对集合进行分类。正如我们将看到的,由此产生的分类与相对于 �� 就相对可计算性而言确定的分类相关。它们在形式上也与计算复杂性理论(例如多项式层次结构)和描述集理论(例如波雷尔和射影层次结构)中研究的其他可定义层次结构相似。
3.6.1 算术层次
回想一下,根据第 3.3 节中给出的定义,关系 �⊆�� 只有在其特征函数 ��(�→) 是可计算函数的情况下才被称为可计算的,并且只有在它是可计算函数的范围的情况下才被称为可计算可枚举的。为了引入算术层次,采用可计算和可计算可枚举关系的替代表征形式是有用的,其形式类似于第 1.3 节中讨论的证明理论算术可表示性概念的语义类似物。
回想一下,一阶算术语言��包含原始符号{<,′,+,×,0},分别用于表示自然数和第一个自然数 0 上的小于关系、后继、加法和乘法函数。一阶算术公式是使用变量、命题连接词和一阶量词∀�,∃�由这些表达式构建的公式,其中变量的范围是自然数�。另外回想一下,一阶算术的标准模型是结构�=⟨�,0,<,�,+,×⟩,其中��的符号接受了它们的预期解释。最后,我们说一个��公式�(�→)定义了一个关系�⊆��,以防�={⟨�1,…,��⟩:�⊨�(�1,…,��)}。[31] 例如 �<�∨�=�定义小于或等于关系≤,∃�(�+�=�)定义偶数,而
∀�∀�(�×�=�→�=�(0)∨�=�)
定义素数。
定义 3.14:如果 �� 的公式 ��(��→) 仅包含有界一阶量词(即,对于不包含 �� 的 ��-项,形式为 ∃�(�<�∧…) 和 ∀�(�<�→…) 的量词),则称该公式属于类 Δ00。如果一个公式对于 ��(�→,�→)∈Δ00 具有形式 ∃�→�(�→,�→),则称该公式属于类 Σ10;如果一个公式对于 ��(�→,�→)∈Δ00 具有形式 ∀�→�(�→,�→),则称该公式属于类 Π10。最后,如果公式 �(�→) 在语义上等同于 Σ10 公式 �(�→) 和 Π10 公式 �(�→),即,�⊨�(�→) 当且仅当 �⊨�(�→) 当且仅当 �⊨�(�→) 对全部 �→∈�� 都成立,则称该公式属于 Δ10 类。
按照量词复杂性将公式的这种句法分类扩展到可以用给定类中的公式定义的自然数上的集合和关系是标准做法。因此,例如,�<�∨�=� 是 Δ00 公式,因此称 �×� 上的关系 ≤ 为 Δ00。另一方面,虽然 ∃�(�+�=�) 是 Σ10 公式,但偶数集也由 ∃�<�(�=0∨�+�=�) 定义。因此,由于后一个定义存在,该集合也被归类为 Δ00,该定义在算术层次结构衡量的意义上更简单。
将此类分类与可计算性理论概念联系起来的第一步如下:
命题 3.8:
关系 �⊆�� 是可计算枚举的当且仅当存在定义 �(�→) 的 Σ10 公式。
关系 �⊆�� 是可计算的当且仅当存在定义 �(�→) 的 Δ10 公式。
命题 3.8 可以通过直接证明来证明,对于每个部分递归函数 ��(�→),都可以构造一个相应的 ��-公式 ��(�→),其逻辑结构模仿前者定义中的步骤。这可以通过使用算术可定义的有限序列编码形式化原始递归并使用无界存在量词表示最小化来实现(例如,参见 Kaye 1991:第 3 章)。但也可以通过证明 Σ10 存在一个所谓的通用公式来以统一的方式获得命题 3.8。为了指定这样的公式,首先注意到可以有效地枚举所有具有�+1个自由变量的Δ00公式为�0�+1(�,�→),�1�+1(�,�→),...,然后将相应的Σ10公式枚举定义为�0�(�→)=∃��0(�,�→),�1�(�→)=∃��1(�,�→),...。然后我们有以下内容:
定理3.9(Kleene 1943):对于所有�,存在一个Σ10公式��,1(�,�→),使得对于所有具有k个自由变量���(�→)的Σ10公式,以下双条件
��,1(�,�→)↔���(�→)
在标准模型�中对所有�→∈��成立。
定理 3.9 可以通过首先观察 Σ10 公式 ���(�→) 的真值等价于对于某些 �∈� �⊨���(�,�→) 来证明。接下来请注意,第 2.1.2 节中记录的观察序列足以表明所有 Δ00 可定义关系都是原始递归的。因此,我们可以考虑一种算法,该算法在输入 �,�→ 时使用 � 构造 ���(�,�→),然后无界搜索 � 使得 ���(�,�→) 成立。通过对丘奇论题的引用(当然,可以用显式构造代替),存在一个可计算函数 �(�) ,对于该函数,我们有以下公式:
�⊨���(�→) 当且仅当 ��(��(�(�),�→,�))↓
为了构造定理 3.9 所承诺的公式 ��,1(�,�→),请注意,语法算术化的标准技术使我们能够获得 Δ10 公式 ��(�,�→,�),它定义了第 2.2.2 节中介绍的 Kleene �-谓词 ��(�,�→,�)。我们最终可以定义 ��,1(�,�→)=∃���(�(�),�→,�)。命题 3.8 的第一部分现在通过设 � 使得 dom(���(�→))=� 然后取 ��,1(�0,�→)∈Σ10 其中 �0 使得 �(�0)=� 得到。这通常被表述为所谓的枚举定理,可以与定理 3.2 进行比较:
命题 3.9:关系 �⊆�� 是可计算可枚举的当且仅当存在一个数 �(称为 � 的 c.e. 指标),使得 � 由 ∃���(�,�→,�) 定义。
命题 3.8 的第二部分可得出,如果 � 是递归的,则 � 和 �― 都是 c.e。因此,如果 � 是 � 的 c.e. 指标,则 �― 由 ¬∃���(�,�→,�) 定义,这等同于 Π10 公式,因为 ��(�,�→,�)∈Δ10。
因此,公式类 Δ10 和 Σ10 为可计算和可计算可枚举集提供了另一种算术表征。这些类还定义了算术层次结构的最低级别,其完整通用定义如下:
定义 3.15:为了简化符号,类 Σ00 和 Π00 都用作类 Δ00 的替代名称。如果公式的形式为 ∃�→�(�→,�→),其中 �(�→,�→)∈Π�0,则称其属于类 Σ�+10;如果公式的形式为 ∀�→�(�→,�→),其中 �(�→,�→)∈Σ�0,则称其属于类 Π�+1。如果公式 �(�→) 在语义上等同于 Σ�+10 公式 �(�→) 和 Π�+10 公式 �(�→),则称其属于类 Π�+10。
因此,只要公式的形式为
∃�→1∀�→2∃�→3…��→��(�→1,�→2,�→3,…,�→�)
(其中量词类型有� 个交替,并且如果� 为偶数,则� 为 ∀,如果� 为奇数,则� 为 ∃),则公式为 Σ�0。类似地,Π�0 公式的形式为
∀�→1∃�→2∀�→3…��→��(�→1,�→2,�→3,…,�→�)。
符号 Σ�0、Π�0 和 Δ�0 也标准用于表示可通过相应句法类中的公式定义的集合和关系类。例如,从命题 3.8 的第二部分可知 PRIMES 为 Δ10(因为它是可计算的),从第一部分可知 HP 和 � 为 Σ10(因为它们是 c.e.)。因此,它们的补数 ��― 和 �― 都是 Π10。不难看出 TOT 是 Π20,因为 ��(�) 是全数,可以用上面介绍的 � 谓词的算术化公式表示为 ∀�∃��1(�,�,�)。类似地,FIN 是 Σ20 可定义的,因为 ��(�) 仅对有限多个参数定义,可以表示为 ∃�∀�∀�(�<�→¬�1(�,�,�))。
一阶逻辑的 Prenex 范式定理的一个结果是,对于��≡∃或∀,每个��-公式�(�→)都可证明等价于形式�1�1�2�2…���(�→,�→)之一(例如,Boolos、Burgess 和 Jeffrey 2007:第 19.1 章)。因此,在可证明等价性之前,对于某个�∈�,每个这样的公式都是 Σ�0 或 Π�0。由于在定义 3.15 中允许量词块为空是惯例,因此
Σ�0⊆Δ�+10⊆Σ�+10
和
Π�0⊆Δ�+10⊆Π�+10。
这些包含是严格的,这是所谓的层次定理的结果,其简单形式可以表述如下:
定理 3.10(Kleene 1943):对于所有 �≥1,存在一个集合 �⊆�,它是 Π�0 可定义的,但不是 Σ�0 可定义的,因此对于任何 �<�,它既不是 Σ�0 也不是 Π�0 可定义的。因此,�― 是 Σ�0 可定义的,但不是 Π�0 可定义的,因此对于任何 �<�,它既不是 Σ�0 也不是 Π�0 可定义的。
再次可以通过直接句法构造来证明定理 3.10。例如,基于通用 Σ10 谓词 ��,1(�→) 的定义,可以证明对于算术层次结构的每个级别 Σ�0,都有一个 Σ�0 公式 ��,�(�,�→),它在标准模型中定义 Σ�0 满足,即
对于所有 �(�→)∈Σ�0 和 �→∈��,�⊨��,�(⌜�(�)⌝,�→)↔�(�→)
(其中我们还定义了哥德尔编号以与上面介绍的 Σ�0 公式的索引一致)。现在考虑 Π�0 公式 �(�)=¬�2,�(�,�)∈Π�0,并让 � 成为 �(�) 定义的集合。标准对角线论证表明,� 不能是 Σ�0 可定义的,并且如果 Σ�0 公式枚举中的 ⌜�2,�(�,�)⌝=�,则 ¬�2,�(�,�) 是 Π�0 公式,无法证明等同于 Σ�0 公式(例如,参见 Kaye 1991:第 9.3 章)。因此,正如 Kleene (1943: 64) 所观察到的,层次定理的部分意义在于它说明了如何将说谎者悖论形式化,以产生塔斯基关于真值不可定义性定理的分层形式(参见自指条目)。
我们还可以根据算术层次结构的级别定义一个完备性概念,如下所示:如果 � 是 Σ�0 可定义的,则 � 是 Σ�0 完备的,并且对于所有 Σ�0 可定义的 �,我们有 �≤��(对于 Π�0 完备也类似)。不难证明,除了多一完备之外, � 也是 Σ10 完备的。类似地, �― 是 Π10 完备的, ��� 是 Σ20 完备的, ��� 是 Π20 完备的。这些观察结果可以归入一个更一般的结果,该结果将算术层次结构与图灵度联系起来,从中也可以得到定理 3.10 作为推论。
定理 3.11(1944 年后):
� 是 Σ�+10 可定义的当且仅当 � 在某个 Π�0 可定义集合中可计算枚举,当且仅当 � 在某个 Σ� 可定义集合中可计算枚举。
∅(�) 对所有 �>0 都是 Σ�0 完全的。
当且仅当 � 在 ∅(�) 中可计算枚举时,� 是 Σ�+10 可定义的。
当且仅当 �≤�∅(�) 时,� 是 Δ�+10 可定义的。
定理 3.11 的各个部分都遵循先前的定义以及命题 3.2 和 3.7。特别要注意的是,从定理 3.11 的 ii 和 iv 部分以及命题 3.7 的 vii 部分可以得出,∅(�) 是 Σ�0−Π�0 类中集合的一个例子,由此还可得出 ∅(�)―∈Π�0−Σ�0。这一观察结果反过来又加强了层次定理 (3.10),因为它表明 Δ�0⊊Σ�0 和 Δ�0⊊Π�0 如图 3 所示。

图 3:算术层次结构。[可提供图 3 的扩展文本描述。]
定理 3.11 的 iv 部分也可以理解为推广命题 3.4(即 Post 定理)。具体来说,它将 Δ�+10 可定义集表征为那些 � 这样的集合,使得 � 和 �― 在某些 Σ�0 完全集(例如 ∅(�))中均可计算枚举。限制为 �=1 的情况,此观察结果还可用于提供 Δ20 可定义集的独立计算表征,扩展了命题 3.8 对 Σ10 可定义集和 Δ10 可定义集给出的表征。
定义 3.16:如果存在一个可计算的有限集序列 {��:�∈�},并且
�∈�当且仅当 lim���(�)=1
其中 lim���(�)=1 表示 lim����(�) 存在且等于 1,则集合 � 被称为极限可计算的。
如果 � 是 c.e.,那么很明显 � 是极限可计算的。因为如果 � 是可计算函数 ��(�) 的范围,那么我们可以将 �� 取为 {��(0),…,��(�)} ,在这种情况下 �0⊆�1⊆�2⊆… 在极限可计算性的一般情况下,集合序列 {��:�∈�} 可以被认为是 � 的近似值,它不需要以这种方式单调增长,而是可以同时增长和收缩,只要总有一个阶段 � 使得对于所有 �≤�, �∈�� 如果 �∈� 并且 �∉�� 如果 �∉�。根据 Putnam (1965) 的说法,极限可计算集也可以描述为所谓的反复试验谓词 - 即,可以通过遵循猜测程序来确定其成员资格,该程序最终收敛到形式为 �∈�? 的问题的正确答案。
以下内容传统上被称为极限引理:
定理 3.12(Shoenfield 1959):以下内容是等价的:
� 是极限可计算的。
�≤�∅′
我们已经看到,命题 3.11 的第四部分将可归结为 ∅′ 的图灵集描述为 Δ20 可定义集。因此,定理 3.12 通过证明 Δ20 可定义集和极限可计算集的一致性,扩展了命题 3.8 中给出的可计算(即 Δ10 可定义)和可计算可枚举(即 Σ10 可定义)集的特征。
3.6.2 分析层次
克莱尼在一系列论文(1955a、b、c)中引入了现在所谓的分析层次,这些论文直接建立在他于 1943 年引入的算术层次的基础上。他的近端动机是提供所谓超算术集(即那些可以通过构造序数从图灵跳跃的超限迭代计算出来的集合)的可定义性理论特征。另一方面,莫斯托夫斯基(1947)已经注意到自然数集的算术层次与描述集理论中研究的点集层次的结果(即波兰空间(完整、可分离度量化空间,如实数、康托空间或贝尔空间)元素集)之间的相似之处,这些结果源于 20 世纪初波雷尔、勒贝格、卢辛和苏斯林的工作。从克莱恩指导的博士论文开始,艾迪生(1954)通过表明克莱恩的初始工作也可用于提供该传统中几个经典结果的有效版本,改进了莫斯托夫斯基的比较。我们在此介绍有关分析层次的基本定义以及一些结果,以说明它如何与这些其他发展相联系。
定义 3.17:二阶算术语言��2扩展了一阶算术语言��,添加了二元关系符号∈,以及集合变量�,�,�,…,集合量词∃�和∀�。��2 的标准模型是结构⟨�,�(�),0,<,�,+,×,∈⟩。因此,集合量词的预期范围是�(�)(即�的幂集),而�∈�的预期解释是数字�∈�是集合�的成员,其中�∈�(�)。 (有关��2及其在数学形式化中的应用的更多信息,请参阅“逆向数学”条目。)
请注意,在一般情况下,��2的公式�(�1,…,��,�1,…,��)可能同时具有自由数变量�1,…,��和自由集变量�1,…,��。如果�⊆��×�(�)�由这样的公式定义,则称其为解析的。 Kleene (1955a) 证明了解析关系的范式定理,该定理表明,如果 � 是解析的,则它可以通过形式为 ��2 公式来定义
∀�1∃�2∀�3…����(�1,�2,�3,…,��)
或
∃�1∀�2∃�3…����(�1,�2,�3,…,��)
其中 �(�→) 仅包含数字量词,并且 � 是 ∀ 还是 ∃ 取决于 � 是偶数还是奇数。因此,可以将��2-公式和它们定义的集合分为以下几类:
定义 3.18:
我们用 Σ01 和 Π01 表示不包含集合量词的 ��2-公式类(即所谓的算术公式)。如果 ��2 公式的形式为 ∃��(�),其中 �∈Π�1,并且如果关系由 Σ�+11-公式定义,则该公式属于 Σ�+11 类。同样,如果 ��2-公式的形式为 ∀��(�),其中 �∈Σ�1,并且如果关系由 Π�+11-公式定义,则该公式属于 Π�+11 类。如果一个关系既能用 Σ�1 公式定义,又能用 Π�1 公式定义,则该关系是 Δ�1 可定义的。
因此,与算术层次结构的情况一样,我们有
Σ�1⊆Δ�+11⊆Σ�+11
和
Π�1⊆Δ�+11⊆Π�+11。
此外,还可以证明算术集的枚举定理的一个版本,该版本可用于获得层次定理的以下推广:
定理 3.13(Kleene 1955a):对于所有 �≥1,存在一个集合 �⊆�,它是 Π�1 可定义的,但不是 Σ�1 可定义的,因此对于任何 �<�,它也不是 Σ�1 和 Π�1 可定义的。因此,�― 是 Σ�1 可定义的,但不是 Π�1 可定义的,并且对于任何 �<�,既不是 Σ�1 也不是 Π�1 可定义的。