第二節 算術

無論是弗雷格的邏輯主義還是希爾伯特的形式主義，都可以看作廣義上的還原主義，即把某種看似不合理的、復雜的、較強的理論還原為某種合理的、簡單的、較弱的理論。弗雷格的目的是把算術（包括自然數和實數理論）還原為邏輯，而希爾伯特的目的是把整個古典數學還原為有窮主義數學。雖然弗雷格的理想遭到羅素悖論的打擊，希爾伯特的方案被哥德爾不完全性定理推翻，但是有可能分別部分地實現邏輯主義或形式主義，前者是新弗雷格主義，后者是反推數學。為了考察這種部分實現的程度，這一小節簡要介紹算術分層。[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。