我们说一个理论是给定形式语言的一个句子集。在数学基础研究中,人们所关注的理论往往是一个公理集,也即能行可判定或递归的句子集。一个理论(公理集)T是一致的,即不存在一个有穷的证明见证从T可以演绎出矛盾。我们可以用一则的算术句子来表达T的一致性,记作Con(T)。
根据对可靠性(soundness)的一般解读,证明理论Σ一致性,只需要证明存在它的一个语义模型。而根据完备性,如果Σ一致,它的语义模型总能找到。而语义模型的构造是相对比较直观的。例如,我们通过证明标准自然数结构N=(N,0N,SN,+N,·N)是皮亚诺算术的模型就证明了皮亚诺算术的一致性。因此,通过寻找语义模型来证明一致性或独立性是有效、可靠且符合直观的方法。当然,这也有赖于经典命题逻辑和一阶谓词逻辑具有可靠性和完备性这样良好的性质。
形式主义者期望找到一个能够涵盖所有数学实践的形式系统,并证明它的一致性。希尔伯特纲领要求从有穷数学出发证明包括集合论在内的数学的一致性。或者退一步,我们至少希望那个大一统的数学公理系统能够证明自己的一致性。如果这种系统及其一致性证明被发现,将无疑成为通过数学方法解决数学自身基础问题的经典范例。上述通过构造自然数结构来证明皮亚诺算术一致性的证明显然不是期望将皮亚诺算术作为全部数学唯一基础的人可以接受的,更不是形式主义者可以接受的,因为该证明甚至要求自然数集这个无穷对象存在。哥德尔第二不完备性定理(Gödel’s 2nd incompleteness theorem)更严格地证明了这种一致性结果是无法得到的。人们一般将哥德尔第二不完备性定理解读为:
定理 3.1(哥德尔第二不完备性定理)任何一个包含皮亚诺算术的数学公理系统都证明不了自己的一致性,除非它是不一致的。
如果我们接受这种解读,那么在给定公理系统内部证明自己甚至更强系统的一致性的企图是不可能实现的。特别地,我们无法期望能证明存在一个我们所承认的全部数学的一个模型。所以,一种一劳永逸地为数学奠定安全基础的梦想是无法实现的。
另一方面,哥德尔第二不完备性定理也提示我们,如果一个理论T2可以证明理论T1的一致性,即T2⊢Con(T1),那么T2一定比T1在某种意义上严格地强。
定义 3.2 令理论T2至少包含罗宾逊算术(Robinson arithmetic,也记作Q)。我们定义理论T2在证明论意义上严格强于理论T1(记作T1◁T2),当且仅当T2⊢Con(T1)。
上述定义中提到的,罗宾逊算术是罗宾逊(Robinson,Raphael M.)在(Robinson,1950)提出的皮亚诺算术的一个有穷可公理化片段,实质上就是PA减去算术归纳公理模式。
此外,本书中写道“理论T2包含理论T1”时,不仅仅指集合意义上的包含。有时候,T1和T2是不同的形式语言中的系统,我们仍然可以宣称它们有包含关系。例如,我们会说策梅洛集合论(ZC)[1]包含了皮亚诺算术(PA)。因为,我们可以通过定义将算术概念翻译为集合论概念,并在ZC中证明所有翻译成集合论句子的PA公理。
理论间的翻译
理论间翻译(interpretation)的严格定义如下:
定义 3.3 给定语言(其中是ni元谓词符号,是mj元函数符号)、以及理论T2。我们称定义在上的函数π0是一个从到T2中的翻译,当且仅当
(1)
(2)对每个
(3)对每个
其中,φ∀(x),φi(x1,...,xni),ψj(x1,...,xmi,y)是公式,至多含有写明的自由变元。并且对任意j<M,
注意,我们定义的翻译π0为语言中每个有待语义解释的符号(包括量词∀)赋予了一则公式。然而,这不仅仅是从“语言到语言”的翻译,而是从“语言到理论”的翻译。因为,我们需要理论T2来检验它对函数符号的翻译是否合理,翻译后的表达式是否满足“存在唯一性”。给定初始符号的翻译π0,我们就可以递归地定义对所有公式的翻译π:
(1)对不含函数符号的原子公式,令
(a) π(x=y)=dfx=y;
(b)
(2)若原子公式中包含函数符号,令是其中出现的第一个仅含一个函数符号的词项,令
其中y取未出现过的新变元符号。
(3)对布尔组合,如¬α,α→β,令
(a) π(¬α)=df¬π(α);
(b) π(α→β)=dfπ(α)→π(β)。
(4)对形如∀zα和∃zα,令
例如,如果我们用ψf来翻译一元函数符号f,用ψg来翻译二元函数符号g,那么
这样,我们就可以把语言中的每个公式翻译成语言的公式了。由此,我们也就可以比较在两个不同语言中表述的理论了。
定义 3.4 给定语言以及理论T1和理论T2。我们说T1可以被翻译到T2中,当且仅当存在从到T2的翻译π0,使得对任意句子σ有
为方便起见,我们也会说理论T2包含T1,或T2在解释力上不弱于T2。
根据哥德尔第二不完备性定理,◁在包含基本算术理论的一致理论中不是自反的。也容易证明,◁在这些理论中是传递的。由此,◁将诸公理系统排列成一个严格偏序。例如,PA◁Z2◁ZC◁ZF。在这个序列上的每一个公理系统的一致性都可以在更强的公理系统中得到证明。例如,ZF ⊢Con(PA)。但同时,我们也无法排除任何一种较弱的公理系统一致而较强的就不一致的情况。因为,根据哥德尔第二不完备性定理,即使在ZF中,我们也无法证明Con(PA)→Con(ZF)(除非ZF本身不一致)。否则,由ZF ⊢Con(PA)就可以得到ZF ⊢Con(ZF)。也就是说,无法排除PA一致而ZF不一致的可能性。而在这种情况下,ZF中可证的命题将没有任何说服力,包括Con(PA)。这样看来,◁序本身无法为其中任何一则公理系统的一致性提供辩护,只是告诉我们哪些公理系统比另一些更“危险”。而后者似乎是冗余的信息,因为越强的系统(不仅仅是证明论意义上)总是越危险。
◁的传递性和有穷主义算术
假设T1,T2,T3都是至少包含有穷主义数学的理论,且有T3⊢Con(T2)以及T2⊢Con(T1)。
在T3中:假设¬Con(T1),即存在一个从T1到x /=x的证明。通过一则原始递归的变换,我们可以得到一个从T2到¬Con(T1)的证明,故T2⊢¬Con(T1),因而¬Con(T2),与Con(T2)矛盾,故Con(T1)。
所以,T3⊢Con(T1)。
注意,证明中我们假设那些理论至少包含有穷主义数学。至于具体哪种公理系统满足希尔伯特所接受的有穷主义,历史上多有争论。斯寇伦(Skolem,Thoralf)在(Skolem,1923)刻画了一种名为原始递归算术(PRA)的公理系统来刻画有穷主义数学这个概念。PRA的语言包括无穷多的函数符号,用来代表所有的原始递归函数。人们后来发现,它的语言可以没有量词,甚至不需要逻辑连接词,整个PRA公理可以看作是由一集能行可判定的形如t1=t2的句子组成的。例如,1=0+1,4=2·2,等等。PRA是被广为接受的一种有穷主义公理系统。
现在,人们也常用作为PRA带量词的版本。指罗宾逊算术Q加上归纳原理模式,即对所有公式φ的归纳原理:φ(0)→∀x(φ(x)→φ(Sx))→∀xφ(x)。在中可以证明,所有原始递归函数都是递归全函数,并且的无量词推论也都是PRA可证的。因此,在本书中默认有穷主义算术公理系统就是。
而另一方面,虽然我们无法证明Con(PA)→Con(ZF)(如果ZF或PA是一致的话),但自20世纪中叶以来,一系列具有下述形式的相对一致性结果被发现:
其中,往往T2在解释力上包含T1,因而,这种结果能够为我们提供一些“正面信息”,即T2比T1多出的那部分不会导致新的矛盾。
类似◁关系,相对一致性似乎也暗示了理论之间的一种强弱关系。如果Con(T1)→Con(T2),那么T1在某种意义上至少不弱于T2。但如果站在算术实在论的立场上,Con(Ti)总是非真即假。如果单纯以Con(T1)→Con(T2)是否为真来判断两个理论的“强度”,由此产生的序关系就是平凡的{0,1}上的大小关系了。这显然无法揭示诸公理系统之间细微的差别。
要能挖掘出一个相对一致性结果Con(T1)→Con(T2)中的“正面信息”,其证明至少要能在一个不强于T1,T2的公理系统中得到。因为,从较强的系统出发的证明让人无法辨别,“T2相对T1多出来的部分不会导致新的不一致”是由于我们本就可以证明Con(T2)还是由于那些“多出来的部分”已经在元系统中被蕴涵了。
定义 3.5 给定至少包含有穷主义算术的理论T0,以及公理化理论T1,T2。定义,当且仅当
T0⊢Con(T2)→Con(T1)。
定义T1T2,当且仅当
容易证明,是非严格的偏序关系,是等价关系。显然,随着T0的加强,所对应的等价类的数量就越少,越难以区分不同理论之间一致性强度的差别。因此,我们默认取各方都能接受的有穷主义算术系统作为比较理论一致性强度的基础理论。
定义 3.6(证明论意义上的相对一致性) 我们称(证明论意义上)理论T2相对T1一致(记作T1≤T2),当且仅当
我们称T1与T2是(证明论意义上)等一致的(equiconsistent,记作T1≡T2),当且仅当(www.daowen.com)
T1≤T2且T2≤T1。
值得庆幸的是,绝大多数相对一致性证明的确是有穷主义算术可证明的,甚至包括ZF的扩张那样较强的集合论公理系统。
令人比较费解的是,根据完备性和可靠性,某个理论的一致性等价于存在该理论的模型。即使是对诸如Con(ZF)→Con(ZFC)的相对一致性证明,似乎也应该在假设存在ZF模型的基础上找一个ZFC的模型。但我们甚至无法期望能在ZF中证明存在一个ZFC模型,更何况这个相对一致性证明甚至可以在中完成!要知道,不能证明任何无穷对象存在。
事实上,我们一般理解的哥德尔完备性定理可以看作是公理化集合论(如ZFC)的内定理,又或者至少是在二阶算术系统(如WKL0)中可证的。而二阶算术语言中的“模型”(一个自然数集)已经不太直观了。而比WKL0更弱的系统如果一致的话,则无法得到哥德尔完备性定理。一阶算术公理系统自然也不行。这意味着在其中有可能得到一个一致性证明而无法证明其存在相应模型。
其实,要证明Con(T1)→Con(T2),只需要证明¬Con(T2)→¬Con(T1)。也即,假设存在一则从T2到矛盾例式的一个有穷证明,我们希望能由此得到一个从T1到矛盾例式的证明。如果我们能找到一个原始递归的变换,将每个从T2的证明转换成一个T1中的相关证明,那么这个相对一致性结果就是有穷主义算术(如PRA或)中可证的了。
另一方面,如果仔细分析可靠性的证明不难看出,对一致性的证明本质上是寻找一种关于语言中公式的性质,并通过归纳法证明所有系统可证的公式都具备这种性质而一些公式并不具有这种性质,从而得到那些公式不可证的结论。“M是……的模型”正是这样一种性质。完备性只是告诉我们,如果允许谈论无穷对象的话,当我们需要证明不可证时,我们总能找到这类符合直观的性质。在有穷主义的相对一致性证明中,诉诸模型是不必要的。事实上,哥德尔第二不完备性定理本身也看以被看作是在有穷主义算术中可证的一组相对一致性结果,即对任意可公理化且包含皮亚诺算术的理论T,有
Con(T)→Con(T+¬Con(T))。
哥德尔第二不完备性定理的证明的确未借助模型直观,或者说“T+¬Con(T)”的模型总是不直观的非标准模型(non-standard model)。但在更多的情况下,借助模型的直观有助于人们发现那些有穷主义的证明。甚至可以说,绝大多数关于自然的数学命题的相对一致性证明的发现都需要借助模型的直观,除了那些本质上就是哥德尔第二不完备性定理的变体的证明。[2]这种巧合对反实在论者来说是需要予以特别说明的。
冯·诺伊曼(von Neumann,John)早在(von Neumann,1929)中证明了集合论基础公理(axiom of foundation)的相对一致性,即Con(ZF-)→Con(ZF)。我们用ZF-表示ZF除去基础公理得到的公理系统。我们知道,集合论谈论的对象全是集合及其属于关系。集合论基础公理的直观意义是:每个非空集合X中都存在一个在属于关系下的极小元y,即X中没有元素再属于y。基础公理可以用集合论形式语言表述为
基础公理保证了不存在x∈x这样的情况。并且,我们可以通过归纳法证明关于全体集合满足某个性质,如∀xφ(x)。
集合论归纳证明
用归纳法证明∀xφ(x),一般先反设{x|¬φ(x)}非空。由基础公理,存在该集合族的极小元x满足¬φ(x),而x的元素、其元素的元素等都满足φ。由此,如果我们能够证明x也满足φ的话,就矛盾了,因而{x|¬φ(x)}是空集。
冯·诺伊曼在证明中定义了我们现在称之为冯·诺伊曼层谱(von Neumann hierarchy)的对集合论宇宙的排列:
定义 3.7(冯·诺伊曼层谱) 定义序数上的映射α→Vα如下:
(1) V0=dfØ;
(2) Vβ+1=dfP(Vβ);
(3)若α是极限序数,Vα=df∪β<αVβ。
我们称这是在(超穷)序数上递归定义。在每个后继步骤中,我们定义Vβ+1是已有的集合族Vβ的所有子集组成的集合族P(Vβ)={X|X⊂Vβ},又称作Vβ的幂集。相比在有穷自然数上的递归定义,在序数上的递归定义增加了对极限序数情况下定义的子句。这使得我们可以达到对Vω的定义以及之后的Vω+1,Vω+2等,其中,ω是比所有自然数(有穷序数)大的最小的序数,也即最小的极限序数。在现代集合论中,一般又将其定义为所有自然数组成的集合。其存在性由无穷公理(axiom of infinity)断言。[3]科恩认为,冯·诺伊曼层谱的定义给予我们两点提示:
第一,序数在这些公理化问题中扮演了根本性的角色……第二……在集合论中处理基础问题时,人们总是有某种根植于直观中的哲学基础或信念,而后者会提示定理的技术发展。在这则案例中的直观是:人们必须只允许集合从那些已有的集合中堆积或“构造”出来。(Cohen,2002)
我们将看到,科恩提到的这种直谓主义(predicativism)直观在后文中将介绍的哥德尔可构成集类(class of constructible sets)的构造中也扮演了重要的角色。
我们可以将Vα看作累积到第α步所得到的所有集合的类,那么将所有这些Vα“并”起来,所得到的就是WF=∪α∈ONVα={x|∃α∈ON(x∈Vα)},即良基集类(class of well-founded sets)。接下来,冯·诺伊曼需要在ZF-中证明所有ZF公理在WF中成立[4],并由此得到ZF的一致性。ZF公理在WF中成立的具体证明参见(郝兆宽、杨跃,2014,7.4-7.5节)。这里主要讲解在什么意义上,我们说“ZF公理在WF中成立”以及何以由此得出Con(ZF-)→Con(ZF)是有穷主义算术可证的。
在集合论中,人们常常会谈论一些非常庞大的类(class)。例如,所有序数组成的类ON,WF以及我们常用来表示所有集合组成的类V。这些类往往由一则集合论公式定义,例如V={x|x=x}。而当我们说“a是良基集”或a∈WF时,我们实际上在说一则以a为唯一自由变元的集合论公式φWF(a),也即WF={a|φWF(x)}。因此,集合论中的类就是可以被看作是满足某个公式的所有集合组成的。
φWF(a)定义
我们可以定义a∈WF为公式φWF(a)的缩写,而后者可以被写作
∃α(α∈ON ∧x∈Vα),
其中,α∈ON是
的缩写。(3.2)中,“α是传递的”是∀x(x∈α∀y(y∈x→y∈α))的缩写,而“∈是α上的良序”是
的缩写。其中,前一个合取支的意思是属于关系∈在α上是传递关系;而后一个合取支的意思是属于关系∈在α上是良基的,也即α的每个非空子集都有∈的极小元。由此也可以推出,∈关系在α上是反对称的、反自返的。
但这些类庞大到几乎可以囊括所有集合,以至于本身不能再被当作是集合。否则便会导致罗素悖论。我们称这些类为真类(proper class)。
布拉利-福尔蒂悖论
布拉利-福尔蒂悖论(Burali-Forti paradox)是罗素悖论的一个变种。假设所有序数组成的类ON是一个集合。由分离公理(separation axiom),ON*={x∈ON|x /∈x}也是一个集合。我们可以证明:对任意序数α∈ON有α /∈α。因此,ON*=ON。根据序数的定义,我们又有集合ON∈ON。又由ON*定义,ON /∈ON*。矛盾。
容易证明,ON是WF的一个子类,因而WF也是一个真类。我们不能将WF作为一个对象(集合),并声称它是ZF的模型。那么,我们又是在什么意义上说“ZF公理在WF中成立”?
例如,当我们说外延公理(axiom of extensionality)[5]在WF中成立时,我们说的其实是
显然,这也是一则集合论句子,我们称之为外延公理的相对化(relativization)。容易看出,它的意思是:对任意良基集X,Y,如果它们的良基集元素一样,那么它们就是同一个集合。这与我们关于“外延公理在WF中成立”的直观是一致的。事实上,给定任何一个像WF这样的类A,也就是给定一则定义公式φA,我们可以递归地得到任何一个集合论φ公式在A中的相对化φA,所需要做的就是每当出现∀xψ这样的子公式时,我们将其变为∀x(φA(x)→ψ)。也即将量词的论域限制为类A。而当我们说“ZF在WF中成立”时,我们实际上对每一条ZF中的公理σ,断言了它在WF下的相对化,即集合论句子σWF。所以,“ZF在WF中成立”实际上对应于公理集合论语言中的一组无穷多的句子,无法在集合论语言中用一句句子表达出来。
另一方面,这些句子组成了一个能行可判定的集合ZFWF。我们可以把一阶算术语言作为元语言,并在其中讨论ZF-,ZF,ZFWF及其可证公式。由此,在有穷主义算术系统IΣ01中就可以证明,如果ZF可以推出矛盾,那么ZFWF乃至ZF-也能得出矛盾,即ZF是相对ZF-一致的。
有穷主义的Con(ZF-)→Con(ZF)证明
令ZFWF={σWF|σ∈ZF}。这是一个能行可判定的集合,正如ZF是能行可判定的一样。通过哥德尔编码,它就对应于一集递归的自然数集。因此,如果我们将一阶算术语言作为我们的元语言,甚至Q作为我们的元理论的话,我们就可以找到一则算术公式φZFWF(x),使得对任意自然数n∈N,如果n编码了一句ZFWF句子,那么Q ⊢φZFWF(n),否则,Q ⊢¬φZFWF(n)。
类似地,所有ZF-/ ZFWF可证的公式组成了一个能行可枚举集。也即,我们可以找到的算术公式provZF-(x)/ provZFWF(x),使得若α是ZF / ZFWF可证的公式而┍α┑是它的哥德尔编码,就有Q ⊢ provZF-(┍α┑)/ Q ⊢provZFWF(┍α┑)。
回想一下,我们对“ZF在WF中成立”的“断言”是在ZF-中得到的。更准确地说,对任何一则句子σ∈ZFWF,我们有ZF-⊢σWF。由此,对任意句子σ,若ZFWF⊢σ,则ZF-⊢σWF。把它通过哥德尔编码翻译到算术语言就是∀x[provZFWF(x)→provZF-(πWF(x))]。不难验证,这句句子是可证的。[6]特别地,
注意,(v1/=v1)WF就是v1/=v1。同时,也不难证明,对任意公式α,若ZF ⊢α,则ZFWF⊢αWF。[7]特别地,公式v1/=v1的相对化(v1/=v1)WF=(v1/=v1),因而
显然,Con(ZF-)就是¬provZF-(┍v1/=v1┑),因而
基础公理的相对一致性证明为该公理的辩护提供了基础,即至少添加该公理不会导致新的不一致,而这是有穷主义数学就能保证的。同时,冯·诺伊曼认为,基于下述直观,我们甚至应该接受WF就是全部集合的宇宙。虽然其他集合论公理ZF-可能无法排除诸如x∈x的情况,但人们实际能接触到的集合,总是从空集或一些对象组成的有穷集合出发,通过将这些集合堆积迭代得到的,也即在WF中的,它们都满足基础公理。库能(Kunen,Kenneth)以更清晰的方式重新表述了冯·诺伊曼的直观。他声称:
【是否假设】基础公理于数学是无关紧要的,因为对任何有数学意义的(of mathematical interest)陈述φ,都有φWF↔φ成立。所以,如果ZFC ⊢φ,那么ZFC-⊢φWF,因而ZFC-⊢φ。(Kunen,2013,p. 117)
当然,“有数学意义的”是一个模糊的表述。对此,库能给出了下述观察,表明人们实践上能考虑到的数学构造全都可以在WF中完成。
定理 3.8 在ZFC-中可以证明:每个群都同构于一个WF中的群;每个拓扑空间同胚于一个WF中的拓扑空间;并且基数幂运算κ,λ→κλ对WF绝对。[8]
对基础公理的辩护基于有穷主义的相对一致性证明以及其他有关数学定理。虽然它最终仍要诉诸对“有数学意义的”直观和经验,但仍然是对数学公理的辩护中比较成功的案例。接下来,读者将看到,类似的辩护理由对哥德尔可构成集类L却不成立。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。