逆向数学（四）

4.3 算术超限递归

算术理解允许我们通过应用一些算术可定义的操作有限次来构造对象。这种证明方法的自然概括是允许这样的迭代一直持续到第一个无限序数 ω，然后进入超限。通过超限递归构造数学对象当然是集合论的标准部分，由替换公理方案许可。算术超限递归的公理方案是一种算术模拟，其中可以应用的运算符 Φ(X) 必须是算术上可定义的，并且其中可以迭代该运算符的良序必须是可数的。尽管有这些限制，算术超限递归还是相当强大的。将其添加到 RCA0 会产生系统 ATR0，这是一个比 ACA0 强大得多的系统，它不仅可以证明经典分析定理，还可以证明有关 Borel 和解析集的描述性集合论的许多结果。

为了定义算术超限递归，我们必须首先理解在这种情况下良序的含义。二元关系 R⊆N×N 被称为自反关系，如果对于所有 x,y ∈ N，如果 (x,y) ∈ R 则 (x,x) ∈ R 且 (y,y) ∈ R。如果 R 是自反关系，那么我们定义 field(R)={x:(x,x)∈R}。我们还写 x≤Ry 当且仅当 (x,y)∈R，并且 x＜Ry 当且仅当 (x,y)∈R 并且 (y,x)∉R。可数线性排序是一种自反关系，它也是传递的（如果 x≤Ry 且 y≤Rz，则 x≤Rz）、反对称（如果 x≤Ry 且 y≤Rx，则 x=y）和总计（如果 x ,y∈field(R)，则 x≤Ry 或 y≤Rx)。我们将 LO(R) 写为公式的缩写，断言 R 是可数线性排序。如果 R 是自反关系，则 R 不包含无限下降链，则 R 是有根据的：对于所有 f:N→field(R) ，存在 n∈N 使得 f(n+1)≮Rf(n)。我们将 WF(R) 写为断言 R 有充分根据的公式的缩写。可数良序是可数线性阶 R，也是有根据的。我们将 WO(R) 写为断言 R 是可数良序的公式的缩写，即 LO(R)∧WF(R)。

定义算术超限递归的下一步是层次结构的概念：通过重复应用运算符从某个初始集合构建的集合系统。给定一个公式 φ(n,Y)，令 Hφ(X,Y) 为断言 X 是可数线性排序且 Y 是所有对 (n,j) 的集合，使得 j∈field(X) 的公式和 φ(n,Yj)，其中

Yj={(m,i):i＜Xj∧(m,i)∈Y}。

这个定义背后的想法是，Y 是集合的层次结构，是通过沿着排序 X 迭代由公式 φ 定义的运算符而产生的，而 Yj 是在迭代的 j 层构造的集合。算术超限递归的公理方案由该方案的所有实例的通用闭包组成

∀X(WO(X)→∃YHφ(X,Y))

其中 φ(n,Y) 是算术值。系统 ATR0 由 RCA0 公理加上算术超限递归公理方案的所有实例组成。

考虑到公理的性质，与 ATR 等价的定理都与可数良序有某种显式或隐式的联系也就不足为奇了。其中最基本的一个，部分是由于它在许多反转的证明中的作用，是看似无害的声明 CWO，即任何两个可数良序都是可比较的：一个必须始终与另一个的初始片段同构。自从 1880 年代初期康托尔的著作中出现序数以来，序数就一直与点集理论（在最基本的情况下是实数集）联系在一起（Ferreirós 2007：第六章）。康托在证明康托-本迪克森定理时使用了可数序数，即每个闭集都是完美集和可数集的并集。该定理实际上相当于 Π11 理解（第 4.4 节），但描述性集合论中的其他定理只需要算术超限递归。其中一个结果是完美集合定理，即每个闭集都包含一个完美子集。另一个是卢津分离定理，即任何两个不相交的解析集都可以被完美集分离。该定理在描述性集合论中被标准使用，以证明苏斯林定理，即 Borel 集合正是那些其补集也是解析的解析集合（Kechris 1995：14）。因此，Suslin 定理也可以在 ATR0 中得到证明，尽管它并不等同于 ATR0。

4.4 Π11 理解

大五系统中的最后一个是 Π11-CA0，其特征公理是 Π11 理解方案。二阶算术语言中的公式 φ 为 Π11，如果其形式为 ∀Xθ，其中 X 是集合变量，θ 是算术公式。如果公式 φ 的形式为 ∃Xθ，其中 θ 是算术性的，X 是设定变量，则它是 Σ11。每个 Π11 公式都等价于一个 Σ11 公式的求反，每个 Σ11 公式等价于一个 Π11 公式的求反。 Π11 推导式由以下形式的所有公式的通用闭包组成

∃X∀n(n∈X↔φ(n))

其中 φ 是 Π11，其中 X 不是自由的，尽管 φ 可能包含其他自由集和数字变量。 Π11-CA0 的公理是 RCA0 的公理加上 Π11 推导式的所有实例。虽然我们还可以定义相应的 Σ11 推导式，但事实证明这是不必要的，因为 Σ11 推导式的每个实例在 RCA0 中都可证明与 Π11 推导式的一个实例等效。

为了扩展 ATR0（§4.3）中可证明的完美集合的结果，需要 Π11 推导式。历史上最著名的此类结果是康托-本迪克森定理，该定理指出每个闭集都是完美集和可数集的并集。 Kreisel (1959) 证明了 F=Fp∪Fc 形式的可计算闭集的存在，使得 Fp 是完美的且 Fc 可数，但 Fp 和 Fc（的代码）是 Π11，但不是 Δ11。这表明，为了证明 Cantor-Bendixson 定理，需要 Π11 推导式，事实上，Cantor-Bendixson 定理在 ACA0 上可证明与 Π11 推导式等价（Simpson 2009：定理 VI.1.6，第 219-220 页）。

描述性集合论中与 Π11 推导式等价的其他重要结果包括 Kondô–Addison 定理（每个协解析关系都可以通过协解析函数统一化）、Silver 定理（每个协解析等价关系包含可数个或 2ℵ0-多个等价类）以及确定性具有 Σ01∧Π01 收益集的游戏。 群论中的许多结果也需要 Π11-CA，包括可数有序群的顺序类型和可数交换群的结构理论。 Solomon (2001) 表明 Mal'tsev 定理在 RCA0 上等价于 Π11-CA，而 Friedman、Simpson 和 Smith (1983) 则表明每个可数交换群是一个可整群和一个可整群的直和。减少组。

Π11-CA0 是逆向数学中标准研究的最强系统，尽管已经发现了更强的逆系统。一个这样的例子是 Π12 推导式与关于最大滤波器的可数空间的一般拓扑的陈述之间的等价性（Mummert & Simpson 2005）。其他陈述，例如确定性公理，甚至更强（Montalbán & Shore 2012）。然而，对于逆向数学中研究的大多数数学陈述来说，即使是 Π11-CA0 也是一个比证明它们所需的更强的系统。

5. 基础程序和逆向数学

5.1 可计算数学、构造性数学和 RCA0

RCA0 中的数学与许多广泛的构造性数学方法有很多共同之处，最显着的是 Bishop 传统中的构造性分析、俄罗斯构造性数学和可计算分析（在旧文本中也称为递归分析）。然而，也存在重要的差异，主要集中在排中律 (LEM) 的使用上，作为经典逻辑中表述的理论，RCA0 满足该律。

丘奇的论文是形式系统 RCA0 与构造性数学传统之间联系的核心。在构造性数学的背景下，这表明每个构造性函数在外延上等价于递归函数，即存在一个图灵机，它在每个输入上停止并产生与构造性函数相同的输出。使用 Kleene 的 T 谓词和 U 函数，我们可以将其形式化为

∀f∃e∀n∃p(T(e,n,p)∧U(p)=f(n))。

正如第 1.3 节所述，对可计算函数的构造概念的解释可以追溯到 20 世纪 40 年代可计算性理论的早期历史。由于 CT 可以被理解为二阶算术语言的形式陈述，因此我们可以考虑它与二阶算术经典子系统的关系。 CT 与 RCA0 一致，因为 RCA0 的公理在由所有且仅由可计算集组成的 ω 模型 REC 中得到满足（第 3.4 节）。然而，它与暗示不可计算集存在的更强系统不一致。

俄罗斯的构造性数学继承了马尔可夫的传统，接受了构造性过程是算法的思想，因此将丘奇论文的一个版本融入到他们的方法中（Kushner 2006）。毕肖普的建构性分析遵循了一条不同的道路：它拒绝排中律，但既不接受布劳威尔在其“创造主体”论点中的新分析基础，也不接受与俄罗斯建构主义者的可计算性理论的密切联系。正如毕肖普所说，他“对构造性数学的本质抱有绝对最小的哲学偏见”（Bishop 1967：ix），并继续断言“没有我们必须遵守的教条”。因此，毕肖普的体系与经典数学、直觉数学以及丘奇的论点是一致的。

然而，RCA0 系统并不是任何这些建构主义观点的忠实形式化：它所嵌入的经典逻辑是一个不可逾越的障碍。中间值定理提供了一个很好的例子来说明原因。虽然中间值定理在 RCA0 中是可证明的，但该证明本质上依赖于通过排中律进行的案例区分，因此不能建设性地证明（Bridges & Richman 1987：5）。这限制了我们使用 RCA0 中的可证明性作为构造性可证明性标记的能力。更复杂的是，在 RCA0 中，归纳仅限于 Σ01 谓词，而建构主义者则倾向于接受在归纳使用中不受限制的量词复杂性。

在某些方面，正如 Simpson (2010) 所建议的那样，Aberth (1980) 和 Pour-El & Richards (1989) 等著作中提出的可计算分析比建设性分析提供了与 RCA0 更好的匹配。这确实有一个基本的结果，因为正如 Beeson (1985) 所说，

有一种连贯的数学哲学，在这种哲学下，递归数学代表了数学宇宙的真理。如果持这种观点，那么该主题的意义就超出了仅仅提供反例的意义。 [… ]丘奇论文中的世界是一个有趣的地方，充满惊喜（就像任何外国一样），但无论如何也不会太混乱而无法维持生命。

彻底的建构主义者并不认为自然数构成一个完整的无限整体，而在可计算分析中，可计算理论的标准机制（确实做出了这一假设）被视为基础（Pour-El & Richards 1989：VII）。因此，在 RCA0 中使用经典逻辑是没有问题的。递归理解，其特征公理，似乎是为可计算数学量身定做的。因此，更容易说 RCA0 中的可证明性意味着可计算分析中的真理，尽管对归纳原理的限制确实意味着就可计算数学而言，RCA0 是一个不必要的限制系统。此外，递归反例（§1.3）——以及由此逆转的集合存在原则，断言不可计算集合的存在——在可计算数学的背景下有一个明确的解释，即证明它们是错误的。 然而，Π11 语句应从该分析中排除，因为任何真实的 Π11 语句在 ω 模型 REC 中都为真，因此可计算为真，无论它在 RCA0 中是否可证明。有关这一点的进一步讨论，请参阅 (Eastaugh 2019: 157, 171–172)。

5.2 有限论和RCA0

形式系统 RCA0 还与另一个重要的基础程序——希尔伯特有限论有联系。 希尔伯特的计划是通过使用纯有限方法证明其一致性来确保坎托尔无穷数学的地位。这反映了希尔伯特的两层认识论，其中有限组合陈述占有特殊的地位，因为与理想的、无限数学的抽象元素不同，它们关注“超逻辑的离散对象，直观地作为所有思想之前的直接经验而存在”（Hilbert 1922） ：163）。

对于希尔伯特来说，真实（有限的、内容的）命题包括数值方程，以及可以通过命题连接词（否定、合取、析取、蕴涵）从方程形成的更复杂的陈述。此外，此类陈述的通用闭包也具有有限的含义，因为我们可以将它们视为一种模式：∀xφ(x)，其中 φ 是无量词的，意味着对于任何给定的数字 ¯n，我们可以在有限的方式 φ(¯n)。将此类语句称为算术语言的Π01 句子虽然不合时宜，但在技术上是有帮助的。与此相反，理想的陈述没有确定的意义：它们只是象征性的，

[ …] 本身没有任何意义，而只是受我们规则支配的事物，必须被视为理论的理想对象。 （Hilbert 1928 [1967: 470]，强调原文）

根据希尔伯特的观点，这些理想对象对于恢复逻辑的一般原理（包括排中律）是必要的，因为他认为没有它们分析的发展是不可能的。

因此，希尔伯特开展了一项计划，以在有限的基础上证明理想数学的有效性。由于理想数学可以在逻辑演算中形式化，例如怀特海和罗素的《数学原理》中发展的数学，希尔伯特纲领的目的就变成了证明形式化数学分析理论和集合论的一致性。为此，希尔伯特和他的合作者开发了证明理论的工具，包括 ε-演算。在概念方面，真正的命题类似于物理学中的实验观察，可以证实或反驳一个理论。在这个类比中，理想数学就像一种给出一般定律的物理理论，只有个别实例才能被验证。因此，理想数学应该比真实数学保守：任何可以通过理想方法证明的真实命题也应该以有限方式证明。

根据 Tait (1981) 将有限性推理作为原始递归推理的分析，RCA0 相对于 PRA (§4.1) 的 Π02 保守性呈现出与希尔伯特保守性纲领相关的哲学维度。泰特提出了两个主张，现在通常被称为泰特的论文。首先，有限函数 f:N→N 正是原始递归函数。第二个是有限可证明的Π01（即真实）句子正是在正式系统PRA中可证明的句子。由上述保守性定理，这些也正是RCA0中可证明的Π01语句，而且RCA0所能证明的全部可计算函数正是原始递归函数。尽管 RCA0 在某种意义上显然是一个无限系统，其中可以对无限对象进行大量数学推理，但由于保守性定理及其推论，它也有一些声称可以简化为有限系统，因此也许在某些情况下有限主义者可以接受的工具性方式。这种有限还原论将在§5.3 中进一步讨论。

泰特的论文得到了广泛讨论并被广泛接受，尽管一路上也不乏批评。这些批评可以大致分为两种类型：历史性的和概念性的，尽管它们有时是相互交织的。在概念方面，有两类抱怨者：一类认为泰特的分析过于自由主义，如 Ganea (2010)，另一类则认为泰特的分析过于保守。 Kreisel (1958, 1970) 是后者的一个突出例子，他认为有限主义可证明性应该与 PA 中的可证明性等同起来。 Kreisel 和 Tait 之间分歧的核心是函数 f:N→N 的状态，这些函数是可计算的，但不是原始递归的，因此虽然可以说本质上是有限的，但仍然违反了 Tait 认为的有限主义边界。

这种函数的典型例子是阿克曼-彼得函数。 1928 年由希尔伯特学派成员 Wilhelm Ackermann 发现，他的论文提供了有限一致性证明的第一个实质性例子，随后由 Péter (1935) 简化，然后由 Robinson (1948) 进一步简化。 Ackermann-Péter 函数通过双重递归定义定义为

π(0,x)=x+1,π(i+1,0)=π(i,1),π(i+1,x+1)=π(i,π(i+1,x) ）。

对于阿克曼-彼得函数本质上是否有限，甚至希尔伯特是否认为如此，当代观点存在分歧。在捍卫有限性可证明性与 PA 中的可证明性一致的观点的过程中，Kreisel（1970）指出希尔伯特在 Hilbert 1926 中对阿克曼函数的明确讨论，作为希尔伯特认为该函数本质上是有限的证据。泰特（Tait，1981）采取相反的立场，认为克赖塞尔的观点是基于对希尔伯特的误读，希尔伯特本人并不认为阿克曼函数是有限的简单函数，而是相对于非有限类型的系统而言是有限的。最近，Zach (1998) 得出结论，虽然在 20 年代初希尔伯特并没有认为他的有限论超越了原始递归，但有理由相信后来的希尔伯特，尤其是他的合作者伯奈斯，采取了不同的观点并认为Ackermann-Péter 函数以及通过高级类型递归定义的其他函数本质上是有限的。有关这些问题的进一步讨论，请参阅 Tait 2002；扎克 2003；和院长 2015 年。

5.3 有限还原论和WKL0

根据Tait（1981）提出的以及§5.2中对RCA0和有限论的讨论所集中的两个论文，有限函数正是原始递归函数，而有限定理正是PRA中可证明的Π01句子。假设人们在确定有限主义数学的范围和极限方面承认泰特论文的正确性，并且哥德尔的不完备性定理对真正实现将所有无限数学简化为有限数学的希尔伯特梦想构成了不可逾越的障碍，那么问题仍然存在关于通过希尔伯特还原可以在多大程度上恢复理想数学。 Simpson（1988）提出了他所谓的希尔伯特纲领的部分实现。辛普森的思想沿袭了 20 年代中期以来希尔伯特的思想，其中给出无限数学一致性的有限证明的程序被证明无限数学相对于实数数学的保守性的程序所取代：也就是说，证明如果一个有限有意义的陈述承认一个理想的证明，那么它也是有限真实的。

哥德尔的不完备性定理似乎表明，这种保守性计划不可能成功，至少如果我们接受所有有限推理都可以在固定的公理系统 T（例如 PRA）中形式化的话。无论我们在有限数学和无限数学之间划清界限，有限数学都无法证明其自身的一致性，更不用说无限数学的一致性了。辛普森接受关于不完备性定理对希尔伯特纲领影响的这一公认智慧，但他认为我们仍然可以部分实现希尔伯特纲领。辛普森提出的有限还原论方案依赖于 WKL0 相对于 PRA 的 Π02 保守性（§4.1）。这个想法是，任何有意义的有意义的（即π01）句子可以在理想中证明，无限制系统wkl0在PRA中也可以证明，因此，通过Tait的论文，有资料证明。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。