第二节 算术

无论是弗雷格的逻辑主义还是希尔伯特的形式主义，都可以看作广义上的还原主义，即把某种看似不合理的、复杂的、较强的理论还原为某种合理的、简单的、较弱的理论。弗雷格的目的是把算术（包括自然数和实数理论）还原为逻辑，而希尔伯特的目的是把整个古典数学还原为有穷主义数学。虽然弗雷格的理想遭到罗素悖论的打击，希尔伯特的方案被哥德尔不完全性定理推翻，但是有可能分别部分地实现逻辑主义或形式主义，前者是新弗雷格主义，后者是反推数学。为了考察这种部分实现的程度，这一小节简要介绍算术分层。[5]

首先，简要说明可解释性、保守扩张和相对一致性等基本概念。如果存在从语言L1的公式到语言L2的公式的映射，使得L1的理论T1的公理都映为L2的理论T2的公理或定理，并且这个映射保持逻辑结构，也就是说，所有T1的定理都被映为T2的定理，则称T2可以解释T1或者T1在T2中是可解释的。任给L1的公式ϕ，如果ϕ是L2的理论T2的定理，则ϕ也是L1的理论T1的定理，称T2是T1的保守扩张。一般地，如果T2在T1的保守扩张中是可解释的，则称T2可以还原为T1。如果T2还原为T1，则T1和T2具有相对一致性，即如果T1是一致的，则T2也是一致的。在某些情况下，相反的结论也成立，即如果T1和T2具有相对一致性，则T2可以还原为T1。

一般来说，Robinson算术被看作最弱的算术系统，简记为Q。这个系统最早由Robinson提出，他的目的是确定哥德尔不完全性定理成立的范围；后来证明，哥德尔不完全性定理适用于任何解释Robinson算术的理论。Robinson算术的语言包括零、后继函数′、加法函数和乘法函数。它的公理包括：

﹁x′=0

x′=y′→x=y

y=0∨∃x（y=x′）

x+0=0

x+y′=（x+y）′

x×0=0

x×y′=（x×y）+x

注意，许多运算规律都无法在Robinson算术中证明。例如，加法和乘法的交换律、结合律和分配律。

Nelson和Wilkie证明，包含运算规律的Robinson算术在Robinson算术中是可解释的。为了证明这些运算规律，需要用到数学归纳法。事实上，运用无量词的数学归纳法就可以证明这些运算规律。如果在Robinson算术的基础上增加如下无量词的归纳公理：

ϕ（0）∧∀x（ϕ（x）→ϕ（x′））→∀xϕ（x），其中ϕ（x）不包含量词。

则称其为Nelson-Wilkie算术或多项式函数算术，简记为Q2。Nelson和Wilkie分别证明，Nelson-Wilkie算术在Robinson算术中是可解释的。因此，可以把它们二者看作相同的层次。

如果在Robinson算术语言的基础上增加幂函数↑，并且增加如下公理：

x↑0=0

x↑y′=（x↑y）′

则称其为Kalmar算术或幂函数算术，简记为Q3。Kalmar最早提出了这个系统，目的也是把哥德尔不完全性定理表述在更弱的理论中。如果再增加超幂函数⇑及其相关的公理，则称其为Gentzen算术或超幂函数算术，简记为Q4。已经证明，切割消去定理的证明需要用到Gentzen算术。类似地，如果增加越来越多的原始递归函数，则可以得到越来越强的算术系统Q5、Q6、Q7等。最后得到的算术被称为Grzegorczyk算术，简记为Qω。Grzegorczyk证明，这个算术系统恰好包含所有原始递归函数。

无量词公式又被称为△00公式。相应地，无量词归纳公理又被称为△00归纳公理。如果Ψ形如∀x1…∀xnϕ，其中ϕ是△00公式，则称Ψ是∏01公式。如果Ψ形如∃x1…∃xnϕ，其中ϕ是△00公式，则称Ψ是Σ01公式。如果Ψ形如∀x1…∀xn∃y1…∃ynϕ，其中ϕ是△00公式，则称Ψ是∏02公式。如果Ψ形如∃x1…∃xn∀y1…∀ynϕ，其中ϕ是△00公式，则称Ψ是Σ02公式。类似地，还可以定义∏03公式、Σ03公式、∏04公式、Σ04公式等等。

如果把Nelson-Wilkie算术中的无量词归纳公理替换为如下Σ01归纳公理：

ϕ（0）∧∀x（ϕ（x）→ϕ（x′））→∀xϕ（x）

其中ϕ（x）是Σ01公式，则称其为Parsons算术，简记为IΣ01。事实上，原始递归函数的存在性和唯一性证明需要用到Σ1归纳公理。因此，Qω在IΣ01中是可解释的。后来，Charles Parsons又证明，IΣ01在Qω的保守扩张中也是可解释的。在此基础上，如果把Σ01归纳公理替换为Σ02归纳公理，则称其为Ackermann算术，简记为IΣ02。Wilhelm Ackermann最先发现了非原始递归的递归函数，即Ackermann函数。Ackermann函数的存在性和唯一性证明需要用到Σ02归纳公理。类似地，如果替换为越来越强的归纳公理，则可以得到越来越强的算术系统IΣ03、IΣ04、IΣ05等。最后得到的算术被称为一阶算术，简记为P1。

无二阶量词公式被称为△10公式。如果Ψ形如∀X1…∀Xnϕ，其中ϕ是△10公式，则称Ψ是∏11公式。如果Ψ形如∃X1…∃Xnϕ，其中ϕ是△10公式，则称Ψ是Σ11公式。如果Ψ形如∀X1…∀Xn∃Y1…∃Ynϕ，其中ϕ是△10公式，则称Ψ是∏12公式。如果Ψ形如∃X1…∃Xn∀Y1…∀Ynϕ，其中ϕ是△10公式，则称Ψ是Σ12公式。类似地，还可以定义∏13公式、Σ13公式、∏14公式、Σ14公式等。

如果把一阶皮亚诺算术表述在二阶逻辑中，则得到二阶算术，简记为P2。实质上，二阶算术是把一阶算术的归纳公理：

ϕ（0）∧∀x（ϕ（x）→ϕ（x′））→∀xϕ（x）

变成两条公理：

∃X∀x（Xx↔ϕ（x）），

∀X（X0∧∀x（Xx→Xx′）→∀xXx）

前者是概括公理，后者是二阶归纳公理。在P1中，可以直接用ϕ（x）进行归纳；而在P2中，先用概括公理把ϕ（x）变成X，再用X进行归纳。因此，在P2中，有什么样的概括就有什么样的归纳；通过限制概括公理，可以限制归纳公理。如果把概括公理限制为直谓概括公理，即概括公理中的ϕ（x）是△10公式，则得到直谓算术，简记为ACA0。其中，ACA表示算术概括公理（Arithmetic Comprehension Axiom），直谓概括公理也被称为算术概括公理，下标0表示二阶归纳公理。直谓算术是一阶算术的保守扩张。如果把概括公理限制为∏11概括公理，即概括公理中的ϕ（x）是∏11公式，则得到非直谓算术，简记为∏11-CA0。绝大多数的数学定理都可以在非直谓算术中得到证明。类似地，还可以得到∏12-CA0、∏13-CA0、∏14-CA0等。

类似于一阶算术P1和二阶算术P2，还可以得到三阶算术P3、四阶算术P4、五阶算术P5等，最后直到Pω，后者类似于罗素的类型论。

一般认为，公理集合论是目前最为实用的数学基础。下面简要介绍集合论分层，并且比较算术分层和集合论分层。

集合论的语言是在一阶逻辑的基础上增加属于符号∈，简记为Z。Z的公理包括以下内容：

外延公理：∀z（z∈x↔z∈y）→x=y。

空集公理：∃x∀y（y∈x↔y≠y）。

无序对公理：∃x∀y（y∈x↔y=u∨y=v）。

附加公理：∃x∀y（y∈x↔∃z（z∈u∧y∈z））。

并集公理：∃x∀y（y∈x↔y∈u∧ϕ（y））。

分离公理：∃x∀y（y∈x↔y∈u∧ϕ（y））。

无穷公理：断定无穷集的存在，简记为∞。

幂集公理：∃x∀y（y∈x↔∀z（z∈y→z∈u）），简记为。

由外延公理、空集公理和附加公理所构成的理论被称为Szmielew-Tarski集合论，简记为ST。如果把Szmielew-Tarski集合论表述在二阶直谓逻辑中，则得到直谓集合论，简记为PST。如果在Szmielew-Tarski集合论中增加分离公理，则得到一般集合论（General Set Theory），简记为GST。如果Z的分离公理中的ϕ（y）是∏1n公式，则简记为∏1n-Z。如果减去Z中的幂集公理，则简记为Z-。表示断定无穷集的幂集存在的公理，，与类似。如果把Z中的幂集公理替换为断定无穷集的幂集存在的公理，则简记为，与类似。

表1-1说明，Szmielew-Tarski集合论可以解释Nelson-Wilkie算术；直谓集合论可以解释Kalmar算术；一般集合论可以解释一阶算术；不包含幂集公理的集合论可以解释二阶算术。

表1-1 算术分层与集合分层

---

[1] 本节主要参考Stewart Shapiro，Foundation without Foundationalism：A Case for Second-order Logic（New York：Oxford University Press，1991），pp.61-96。

[2] 这是公式对二阶变元代入自由，与项对一阶变元代入自由类似。

[3] 亨金子模型的定义与通常子模型的定义类似。

[4] k（g）|D′表示函数k（g）在D′上的限制。

[5] 本节主要参考John Burgess，Fixing Frege（Princeton：Princeton University Press，2005），pp.49-75。