逆向数学（二）

单调收敛定理或柯尼希引理等经典数学定理暗示不可计算集合存在的发现是迈向逆向数学的重要一步。这是因为这样的结果通常提供的信息不仅仅是不可计算集合的存在：它们表明存在特定复杂性的不可计算集合，位于算术或分析层次结构中的某个点。例如，Specker 的证明表明，有理数有界序列的极限的存在意味着图灵机的 K 组代码的存在，该组 K 代码在每次输入时都会停止。这是从单调收敛定理到算术理解的逆转的基本思想。

20 世纪 50 年代，人们对​​使用可计算性理论（当时称为递归函数理论）和可定义性理论的工具产生了进一步的兴趣，更广泛地研究本世纪早期的基础程序，例如直觉主义、有限主义和谓语主义。所有这些都被认为或多或少地涉及建构主义，这自然导致尝试根据可定义的集合类别或自然数和实数的函数来分析它们。最基本的是将可计算实数类识别为构造性数学模型（Mostowski 1959）。 Grzegorczyk (1955)、Kondô (1958) 和 Mostowski (1959) 也对算术集进行了研究，为 Weyl (1918) 的谓词主义提供了自然模型（§5.4）。继 Bernays（1935）之后，更多的柏拉图主义理论与更具包容性的可计算性或可定义性概念相关联（Dean & Walsh 2017：2.2-2.3）。也许这一运动的顶峰是 Kreisel 在 1960 年提出的将谓词可定义集合与超算术集合类（第 5.5 节）等同起来的尝试性提议，以及他对康托尔-本迪克森定理的相关工作，他证明当其量词受到限制时，该定理是错误的到超算术集（Kreisel 1959）。克赖塞尔的结果可以被理解为康托-本迪克森定理的递归反例，甚至是超算术反例。将结果内在化，证明了康托-本迪克森定理与 Π11 推导式公理方案之间的等价性（第 4.4 节）。

Errett Bishop 在 20 世纪 60 年代的工作也对逆向数学产生了影响。 1967 年毕肖普出版了《构造性分析基础》之后，人们对构造主义的兴趣重新燃起，并大力倡导构造性数学方法，从而引发了关于构造性数学局限性的新研究。 20世纪70年代和80年代发现的许多经典定理的递归反例后来被转化为从这些定理反转到非构造性集合存在原理的证明。例如，Brown 和 Simpson (1986) 将可分离 Banach 空间的 Hahn-Banach 定理反转为弱 König 引理 (§4.1)，其基于 Metakides、Nerode 和 Shore (1985) 提出的 Hahn-Banach 定理的递归反例），反过来又受到主教本人建造的Hahn -Banach定理的Brouwerian反例的启发。

1.4反向数学的早期发展

尽管有许多先例，但具有特定的正式环境和方法论的逆向数学是一门独特的学科，直到1970年代中期才出现。它的出现可以很精确地追溯到哈维·弗里德曼（Harvey Friedman）在1974年温哥华国际数学家大会上的演讲。题为“某些二阶算术及其使用的系统”，并在ICM的会议记录中发表（Friedman 1975），弗里德曼的论文提出了反向数学的愿景，它与此条目主要部分中所述的成熟程序非常接近。 。形式的设置是二阶算术及其子系统，以及五大子系统（RCA0，WKL0，ACA0，ATR0和π11-CA0）及其特征公理都存在。

弗里德曼（Friedman）的ICM论文与五大巨头的成员呈现了一系列等价，基本理论RCA仅证明了可计算集的存在。在所研究的陈述中，是从Dedekind的Stetigkeit和Irnationale Zahlen（1872）的最后一章中的基本定理的形式化，所有这些都可以证明相互等同于彼此，以及算术理解的公理方案，Modulo，Modulo基础理论RCA RCA。 Specker的证据表明，存在可计算的有界数序列的有理数序列，其限制计算停止问题被转化为证明，证明真实线的顺序完整性和顺序紧凑性等于算术上可确定的集合。

从技术层面上讲，弗里德曼（Friedman）（1975）论文的形式主义与当代反向数学实践中使用的形式主义之间的最大差异是，他的基本理论RCA包括完整的归纳方案（π1∞-ind）。弗里德曼随后在1976年表明，他的1975年论文的等价可以证明是在较弱的基础理论中，称为RCA0，其中完整的诱导方案被无量词的诱导代替。但是，在削弱归纳原则的过程中，弗里德曼从前论文中使用的基础理论的定义大大改变了基础理论的定义。所得系统的RCA0本质上是原始递归算术的二阶版本。虽然正式不同，但这确实导致了一个从理论上证明的系统非常接近现在标准的基础理论RCA0（§3）。

RCA0的现代形式首先在Friedman，Simpson和Smith（1983）的有影响力的论文中印刷，而N作为n序的半序，递归理解公理方案和σ01感应方案。因此，到1983年，逆向数学基本上是我们今天所知道的，甚至取决于使用“反向数学”的使用，弗里德曼在斯蒂芬·辛普森（Stephen Simpson）（2009：35）组织的AMS特别会议上创造了弗里德曼（Friedman）。

1980年代和1990年代随后的主要发展是相反的数学成为计算性理论的主要子场，这在很大程度上是由于斯蒂芬·辛普森（Stephen Simpson）和他的博士生的工作。他们系统地研究了数百个定理的相反数学状态，分布在许多不同的数学领域，从功能分析到组合，交换代数到衡量理论，秩序理论再到一般拓扑。该研究计划的许多果实都在辛普森的教科书《二阶算术子系统》中进行了调查，该系统于1999年首次发布。第二版在2009年发表。

2。二阶算术及其子系统

2.1二阶算术的语言

二阶算术L2的语言是一种两排语言，它增强了一阶算术的语言，从Peano算术等系统中熟悉，其第二种变量代表了一组自然数。第一种x0，x1，x2，…的变量称为数字变量，旨在在自然数上进行范围，而第二种的变量x0，x1，x1，x2，…被称为集合变量，旨在范围范围超过一组集。自然数。二阶算术的非逻辑符号是：常数符号0和1；二进制函数符号+和×；和二进制关系符号＜和∈。数值项是数字变量为0或1，或具有T1+T2或T1×T2的形式，其中T1和T2是数值项（第二类的唯一项是设置变量）。原子公式的形式为t1 = t2，t1＜t2或t1∈X，其中t1和t2是数值项，x是任何集合变量。二阶算术可以使用任何针对两组语言的标准经典证明系统提出。集合的身份关系定义为共依据性：

x=y⇔∀n（n∈X↔n∈Y）。

2.2二阶算术语义

“二阶算术”这个名称可能会令人困惑。首次遇到它，人们可能很容易地认为它的名字意味着它使用了二阶逻辑，从逻辑主义和数学结构主义等数学哲学中的其他环境中，这是熟悉的。在二阶逻辑的所谓标准语义（有时也称为完整语义）中，二阶量词被解释为在一阶域的整个powerset上。例如，在二阶Peano算术PA2的模型M中，即以二阶逻辑制定的Peano算术配方，二阶量化器的范围为p（| M |），其中| m | | 是一阶量词的范围。从Dedekind的分类定理来看，系统PA2只有一个模型，直到同构。这意味着，至少对于二阶语义含量⊨2，PA2在语义上完成：对于每个φ∈L2，无论是PA2⊨2φ或PA2⊨2Ipp还是）。

因此，重要的是要注意，尽管它的名字，但用于二阶算术语言L2的语言中使用的语义不是标准的二阶语义，而是一般或亨金语的语义，换句话说，换句话说，订单逻辑。 L2结构是形式的有序元组

m =⟨M，SM，0m，1m，+m，×m，＜m⟩，

其中m是数字变量范围以上的域，SM是M的一组子集，该子集在集合变量范围内，0m和1m是M，+M和×M的区分元素，是m上的二进制操作，而＜m是一个M和SM的二进制关系始终被认为是脱节和非空的。

由于二阶量化器的范围可以是任何非空置SM⊆P（| M |），因此有许多非同构L2结构。添加公理不会改变这种情况：二阶算术Z2的形式系统（在§2.3中引入）及其子系统都有许多非同构模型。偏离二阶逻辑的标准语义实际上是反向数学的重要组成部分，因为为了证明原理T0并不意味着另一个原理T1，必须证明有一个模型m，使得m⊨t0和m⊭t1。如果我们认为的每个子系统都有相同的独特模型，那将是不可能的。

L2结构提供了一个基本示例

r =⟨Ω，rec，0,1，+，走气，＜⟩。

其中rec = {x：x是可计算的}。这里ω是标准的自然数0,1,2，…，符号0,1，+，走气具有其标准解释。 因此，R是所谓的ω模型，其一阶部分是标准自然数。 因此，ω模型完全通过其二阶部分彼此区分。在R的情况下，其二阶部分由REC组成，REC是所有可计算的自然数集集合的集合。由于不同的ω模型仅在其二阶零件中彼此不同，因此它们经常被这些零件的名称所述。因此，本文的其余部分将称为r rec，其二阶部分由算术零件组成的ω模型A将称为Arith，依此类推。

尽管许多经典的数学原理（例如中间值定理IVT）在REC中是正确的，但其他经典的数学原理不是最小的上限公理lub，这等同于算术理解（§4.2）。由此我们可以得出结论，IVT不需要润滑。该模型还允许我们演示一个不完整的实例。我们将在§3中介绍的基本理论RCA0在REC中是正确的，并且由于Rec⊭Lub，因此，它遵循RCA0⊬Lub的一阶逻辑的音质定理。从这个意义上讲，反向数学是对不完整的研究：它研究了定理的层次结构，其等效于某些设定的存在原则，但不能通过基本理论或层次结构中的严格弱原则证明（Simpson 2010； East augh，East augh， 2019）。

2.3二阶算术公理

二阶算术或Z2的形式系统具有以下L2公式的通用闭合。

PA-，用于离散有序半环的公理：

n+1≠0

m+1 = n+1→m = n

m+0 = m

m+（n+1）=（m+n）+1

M×0 = 0

m×（n+1）=（m×n）+m

m＜0

m＜n+1↔（m

感应公理：（0∈X∧∀n（n∈X→N+1∈X））→∀n（n∈X）

理解方案：∃x∀n（n∈X↔φ（n））

其中φ（n）是任何具有x不自由的L2形式，但可能具有其他自由集和数量变量。

通过应用理解方案（π1∞-CA）和诱导公理（IND），Z2可以证明感应方案，该方案由该方案组成

（φ（0）∧∀n（φ（n）→φ（n+1）））→∀nφ（n）

其中φ（n）是任何L2形式。

二阶算术有时被称为一阶分析理论，因为设置变量可以解释为跨实际数字。许多较旧的演示文稿采用功能性演算，其中设置变量被k-ary函数的变量FK替换为f：nk→n。 Grzegorczyk，Mostowski和Ryll-Nardzewski（1958）提出了这样一个系统，其中还包括一个确定的描述操作员，以及他们称为LeśniewskiSchemata的理解方案的形式。通常，有关这些变体系统的结果从一个变体系统从一个到另一个变化的结果仅进行较小的调整。

二阶算术的子系统是一个公理系统t，其中每个公理φ∈T都是Z2中可证明的L2句子。在已经研究的二阶算术的许多子系统中，有五个在相反的数学中至关重要，并且被称为“五大”。其中的第一个是系统RCA0，这是反向数学的标准基础理论。五巨头的其他成员（WKL0，ACA0，ATR0和π11-CA0）是RCA0的适当扩展，并且每个均与基础理论RCA0相当于分析，代数，无限逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑，逻辑。和拓扑。这些系统中的每一个都比前面的系统具有更大的证据理论强度，因为它们证明了在上述系统中无法证明的定理：WKL0证明了定理比RCA0更多，ACA0比WKL0证明，ATR0比ATR0更多，而ATR0比ACA0（ACA0）更重要。和π11-CA0比ATR0多。请注意，通过包含的顺序排序与一致性强度排序不同：虽然五巨头的大多数成员都证明了先前系统的一致性，但在RCA0和WKL0的情况下，这并不成立，这与保守性结果相当在§4.1中进行了讨论。

这些系统名称末尾的“ 0”下标意味着归纳原理受到限制。在ACA0和更强的系统（如ATR0和π11-CA0）的情况下，此限制仅涉及仅包含诱导公理（IND），而不是诱导方案（π1∞-IND）。因此，他们只能证明感应方案的实例可以证明存在相应的集合：例如，ACA0可以证明涉及公式是算术公式的任何实例（即，它不包含任何集合量词），尽管π11-CA0可以证明涉及公式为π11的诱导方案的任何实例。在系统弱的情况下，例如RCA0和WKL0，诱导公理太弱了，无法在数学上进行很多数学上的操作。因此，它们是由σ01感应方案增强的，σ01感应方案是对σ01公式的限制（π1∞-ind），其中x（x）的x tem x（x）是x是一个数字变量，θ仅包含绑定的数字量词设置量词，尽管它可能包含自由和绑定的数字以及设置变量。

在接下来的两个部分中，我们将仔细研究五个大子系统，包括在每个巨大的子系统中都可以完成的数学，但在较弱的子系统中不进行，以及对其模型理论和证明理论的一些启发性细节特性。反向数学和可计算理论之间的密切联系意味着，参考递归函数的条目的相关部分有时会很有用。

3。基础理论

3.1递归理解

反向数学中使用的二阶算术子系统通常是通过用较弱的公理代替理解方案（π1∞-CA）来定义的。这些子系统中最基本的最基本称为RCA0，其中RCA代表“递归理解公理”，而0下标表示其归纳原理受到限制。 RCA0的公理由基本公理组成；递归（或Δ01）理解方案，由形式的所有公式的通用封闭组成

∀n（φ（n）↔ψ（n））→∃x∀n（n∈X↔φ（n））

其中φ（n）是σ01形式，ψ（n）是π01形式，两者都可能具有额外的自由数和设置变量。以及σ01诱导方案，这是对σ01形式的限制感应方案（π1∞-ind）。 “递归理解”的名称是指以下事实：ω的Δ01可定义子集恰好是递归的子集（在当代术语，可计算中），或者使用另一种可计算的延伸等效的特征（这是帖子的定理）。 RCA0是大多数反向数学的基本理论：给定的定理τ，在扩展RCA0的二阶算术子系统中可证明，当我们证明s的公理可以从τ中得到逆转，从RCA0+τ的公理。

系统中存在σ01诱导的存在允许人们得出许多熟悉的自然数的代数特性：加法和乘法的关联性和交换性，0和1分别是添加和乘法的身份元素，以及乘法的分布性元素超过。可以通过说RCA0证明系统（n，+，0,1，＜）是一个可取消的通勤有序的半序，可以总结这些结果。可以在Simpson（2009：65-66）的引理II.2.1中找到完整的细节。

3.2配对，序列和编码的基础知识

所有编码，多么复杂且多层，最终都建立在允许一个人对订购的对⟨a，b⟩或有限序列⟨a1，a2，…，自然数量按单个自然数字的技术编码的技术上n以某种方式使组件a和b或元素A1，…可以有效地从代码n中恢复AK。一种简单的编码方案定义了编码有序的数字⟨a，b⟩为数字（a+b）2+a的数字（a，b），其中m2缩写m×m。在RCA0中，我们可以验证对于任何a，b，a'，b'∈N，如果（a，b）=（a'，b'），则a = a'和b = b'。借助此配对函数，我们可以在n：二进制关系上定义二进制关系和单个参数函数，这只是一个集合x⊆n，因此对于所有n∈X，存在a，b≤n，因此n =（a， b），而单个参数函数f：n→n是n上的二进制关系，使得对于所有对（a，b）和（c，d）∈F，如果a = c，则b = d。

任意长度的编码序列需要更多的巧妙性，但是可以通过将上述想法扩展到编码数字对来实现。该方法使用Sunzi的定理按单个自然数来编码数字有限序列，以至于可以以可计算的方式从其数值代码中恢复任何有限序列。对于有限序列的任何代码以及指数，该索引处的序列值，该函数β：n×n→n被称为gödel的β函数。自然数的所有有限序列的集合被称为SEQ，可以通过递归理解证明存在。所有s∈Seq的集合，使得| s | = k用nk表示。

一旦我们有一个有限序列的编码方案，我们就可以代表rca0中的n- ary关系和函数。它还允许我们通过单个函数f：nn→nk编码n- ary函数的有限序列，fk⟩，fi（x）=（f（x））（i）。通过将递归理解和σ01诱导与有限序列的编码相结合，可以在RCA0中发展原始递归函数的理论。最后，请注意，可以通过让单个集合x来编码一个可数的集合⟨xn：n∈N⟩

xi = {m：（i，m）∈X}。

由于功能，关系，实数等通过集进行编码，因此该技术还允许一个人编码单个集合等对象的可数序列。

3.3整数，理性和实数

为了按自然数编码整数和合理数字，只需要按单个数字编码数字对的能力。整数由对（a，b）∈n×n对表示，其中对（a，b）的预期解释为a -b。我们首先定义了n×n上加法，减法和乘法的以下操作，以及较小的和平等的关系。

（m，n）+z（p，q）=（m+p，n+q），（m，n）-z（p，q）=（m+q，n+p），（m，n ）仇士（p，q）=（m·p+n·q，m·q+n·p），（m，n）＜z（p，q）↔m+q＜n+p，（m ，n）= z（p，q）↔m+q = n+p。

定义绝对值操作| n | z，也很有用

|（m，n）| z = {（m，n）如果n≤m，（n，m），则否则。

如果我们单独将这些操作作为定义整数，那么许多不同的对将定义相同的整数。例如，整数-17由对（0,17），（17,34），（124,141）表示表示。因此，我们将整数z的集合定义为由关系= z引起的等价类别的＜n至最高成员组成。 RCA0能够证明Z的存在，并证明系统（Z，+Z，µz，＜Z，= Z，0Z，1Z）是一个有序的交换环。

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