用户名:
    密码:
转播到腾讯微博

你的位置:首页 > 哥德尔专辑,逻辑学

唐芳芳:不完全性与形式语言
录入: 哲学网编辑部 发表时间: 2013-08-27 点击: 4757 次 我要收藏

一、引言
谈到哥德尔不完全性定理,有人说它动摇了逻辑基础①,也有人说它揭示了逻辑的局限性(Dawson),甚至有人认为它表明数学的一致性不能证明(克莱因,第263—270页)。这些说法是否有充分的根据?本文仔细考察了哥德尔不完全性定理的涵义,试图对这些说法进行辩驳。
哥德尔不完全性定理涉及形式语言的一些术语,因此要正确理解该定理的内涵,首先要了解形式语言的基本特点以及一些相关的重要概念。一阶逻辑和形式算术都属于一阶语言。形式语言是一种有结构的形式化的语言:它必须明确说明所有初始词,其中一些初始词称为“常项”②(Tarski,1983,p.168);明确给出形成规则来引入新的词;表达式要么是初始词,要么是由已引入的词通过形成规则引入的;每一个表达式的结构都是唯一的,仅由表达式的结构就可以确定其中哪些是句子;明确指出所有公理,即不需证明可以直接断定的句子;有明确的纯形式的推理规则,即一种结构演算,将一些已经断定的句子进行结构上的转换,得到另一些新断定句子。在形式化的语言中,“可证”、“证明”这样的句法概念获得了精确性和简明性。“可证”的句子是由公理经推理规则得到的句子。具体地说,如果有这样一个有限序列:初始句子是公理,接下来的句子要么是公理要么是对它前面的句子(即已断定的句子)用推理规则得到的,那么这个序列的最后一个句子就是“可证”的,或称为“定理”,该序列就被称为一个“证明”。如果初始句还可以是一些规定下来的句子,称为前提,那么这个序列的最后一个句子就是由该前提“可演绎的”。这样,“证明”或“演绎”就是一个能行的过程:每一步都是有根据的,毫不含糊,不能凭空想象,并且这个过程可以在有限步骤内结束。
一种纯粹形式的、没有赋予任何意义的语言并不是我们感兴趣的。建立一个形式化的学科或理论,常常是为了刻画某个具体的对象。例如形式算术就是为了刻画自然数模型而建立的。因此,形式语言不仅包括以上描述的形式化的公理系统,还应包括语义说明。对于一个具体的形式语言,应赋予初始词以合适的意义;表达式的涵义根据其结构和初始词的意义就能唯一地确定;给出标准来唯一地确定一个句子的真假;所选择的公理是真句子;所选择的推理规则要保证:将其应用于真句子所得的仍是真句子。一般地,我们可以通过模型将语言中的每一个句子映射到真假上。例如,一阶语言的模型是一个赋值结构,它由非空个体域、对常项的解释和对变元的赋值构成。其中,由个体域、对常项的解释所构成的二元组称为一阶结构。自然数模型是一种一阶结构,其个体域是自然数集合,所解释的是“加”、“乘”、“后继”、“零”等常项。一阶逻辑的公理在所有赋值结构中都是真的,即是恒真的或者说是有效的;形式算术的公理在自然数模型中为真。如果对任意模型,当一些句子在其中为真时,另一些句子在该模型中也是真的,则称后者为前者的“语义推论”,或称前者逻辑蕴涵后者。
二、两个哥德尔定理中的“完全性”
本文认为,说哥德尔定理动摇了逻辑基础,这大概是混淆了哥德尔的两个著名定理——哥德尔完全性定理和哥德尔不完全性定理中的完全性。
这两个定理中的完全性是两回事。哥德尔不完全性定理是说足够强的一阶理论是不完全的,这里说的“完全性”是指一阶理论的性质;而哥德尔完全性定理证明了一阶逻辑具有完全性,该“完全性”是指一阶逻辑的性质。一阶理论可以看作是在一阶逻辑的基础上增加一组用一阶语言陈述的非逻辑公理得到的。形式算术就是一种一阶理论,它所增加的非逻辑公理就是用一阶语言陈述的关于算术的皮亚诺公理。
首先,一阶逻辑的完全性要求恒真的句子可证,而一阶理论的完全性要求偶然真的句子(在某个特定的模型③ 中是真的句子)可证。(张清宇、郭世铭、李小五,第402—403页)恒真的和偶然真的句子所刻画的常项是不同的。形式语言中有两种常项(参见王路,2003年,第245页),第一种常项是某门科学特有的词语;第二种是在一切科学领域都要遇到的词语。例如,算术的“加”和“乘”等是第一种常项,它们是算术中特有的词,在算术中有固定意思;“不”、“与”、“或者”等逻辑联结词和“对所有的”这样的量词是第二种常项,它们是具有一般逻辑特征的词,具有普遍的性质。恒真的句子刻画第二种常项的性质,表达一种普遍的规律。偶然真的句子刻画第一种常项的性质,表达某门科学特有的规律。一阶逻辑作为各门科学的基础,要刻画第二种常项的性质。一阶理论研究某门科学中特有的规律,要刻画第一种常项的性质。研究恒真还是研究偶然真,是逻辑与理论的重要区别。“可证”概念所要抓住的真是“恒真”还是“偶然真”,是逻辑完全性和理论完全性的最根本区别。
其次,一阶逻辑的完全性考察一阶逻辑对推理的刻画,一阶理论的完全性考察其所增加的那组非逻辑公理的性质。一阶逻辑的完全性要求“可演绎”这个句法概念和“语义推论”这个语义概念是重合的;特别地,要求一阶逻辑的“可证”的句子集合和“有效”句子集合是相同的,要求任何在一阶逻辑的基础上增加一组非逻辑公理所得的理论的“可证”句子集合就是这组非逻辑公理的“语义推论”集合。一般认为逻辑是研究推理的。一阶逻辑通过清晰地区分出句法和语义两个方面来研究推理。对推理的句法研究,即研究表达式之间的“可证”或“可演绎”关系,所依据的是表达式的句法结构,或者说是表达式本身的形式,把表达式仅仅看作符号串,意义都被抽掉了。对推理的语义研究,即研究在推理过程中的表达式之间是否有“语义推论”关系:前提是真的,结论一定是真的。对推理语义的研究围绕“真”展开,句子经语义解释获得唯一确定的涵义和真值。一阶逻辑的完全性是探讨对推理的句法刻画和语义刻画之间的关系的元逻辑研究,使我们能够从二者之间的相互联系来认识推理的特征,从而考察一阶逻辑的特征,而并不考察某个特定的前提集,不涉及某个特定的模型的性质。一阶理论的完全性考察该理论所选择的一组非逻辑公理(或公理模式)的性质而不是推理的性质,它要求这组非逻辑公理的演绎封闭集合是极大和谐的,要求在一阶逻辑的基础上增加这组非逻辑公理得到的理论的“可证”句子集,就是在该理论要刻画的模型上为真的所有句子的集合。
最后,一阶逻辑的完全性要求在其基础上增加有限条公理而得到的所有和谐的(即无矛盾的)一阶理论,都有模型。一阶逻辑一定具有完全性,这是哥德尔完全性定理告诉我们的。一阶理论的完全性要求该理论的模型有某些特殊的性质:这些模型都是初等等价的。简单地说,用一阶语言不能分辨这些模型;该理论不可能恰有两个可数模型。一阶理论的模型不一定有这样的性质,例如形式算术存在一个与自然数模型并不初等等价的可数模型。
哥德尔不完全性定理中的“完全性”是一阶理论的性质,与以研究推理和关心普遍性为特征的逻辑的性质无关。哥德尔的另一个定理——哥德尔完全性定理已经证明了一阶逻辑是完全的,所有恒真的句子在一阶逻辑中都是可证的,一阶逻辑对推理的句法刻画和语义刻画是重合的:一方面一阶逻辑是可靠的,它的“可证”的句子一定是有效的,能行的“演绎”过程能保证从真的前提一定得出真的结论;另一方面,一阶逻辑有强大的推理能力,能够用“证明”这种能行的方式得到所有的有效式。因此,我们可以把一阶逻辑看作研究推理的有力工具,看作逻辑的典范。哥德尔完全性定理标志着一阶逻辑的成熟,从此人们可以放心地用一阶逻辑作为各门科学研究的基础。因此,哥德尔定理并没有动摇逻辑的基础。
三、哥德尔不完全性定理的涵义
本文认为,哥德尔不完全性定理揭示的是形式系统的根本局限性,而不是逻辑的局限性。
哥德尔不完全性定理表述为:如果形式算术是和谐的,那么存在一个一阶句子是在形式算术中不可判定的,即该句子和其否定式在形式算术中都不可证。这也等于说,存在一个在自然数模型中真的句子在形式算术中不可证。进一步,即使我们把不可判定句子作为一条新公理加入形式算术中,使得该句子在新系统中可证,但只要新系统的公理集仍是“合理的”,就可以在这个新系统中构造另一个不可判定句子,从而这个新系统仍然是不完全的。④ 形式语言要求公理集是“合理的”,即要求公理集是有穷的,或者至少有能行的方法来确定一个给定的表达式是不是公理。不完全性定理并不是说形式算术不能有一个完全的和谐的扩张,而是说形式算术增加合理的新公理并不能抓住自然数模型中的所有真命题。把所有在自然数模型中为真的句子都增加到形式算术的公理集所得到的当然是形式算术的完全扩张。但是这样的完全扩张是平凡的,该“理论”的“证明”不是一个能行的过程,因此不是数学家感兴趣的。不完全性的结论还可以应用于包括形式算术的数学形式系统,即任何包括形式算术的数学形式系统都存在不可判定句子。又由于形式算术不可避免地成为任何一个数学分支的形式系统的核心部分,因而不能把整个数学理论压缩在某个单一的形式系统中,“任何形式系统都无法包罗全部数学”⑤。哥德尔不完全性定理的贡献在于揭示了足够强的数学子系统是不可完全的。哥德尔发现“可证”是一个能用加法和乘法借助量词来表达的谓词,因此能在既含加法又含乘法的数学形式系统中仿造说谎者悖论构造一个句子,说自身在该系统中不可证。该句子在形式算术中不可判定。可见,形式算术的不完全性的原因在于它的形式系统足够丰富,能把“可证”等句法概念在系统自身中表达出来,而不在于一阶逻辑。所以说,哥德尔不完全性定理揭示的是形式化方法的局限性,不是逻辑的局限性。
哥德尔证明不完全性定理时已认识到“真”在形式算术中不可定义,(王浩,第114页)或者说受了真这个概念的直觉的指引。(Tarski,1944,p.373)然而在哥德尔论文的证明中没有明确出现“真”这个概念,大概是因为当时“真”的定义还不清楚,很多数学家都避免使用这样的概念。与之同时期的塔尔斯基的工作提供了构造了真这个概念的正确的定义的方法,也让我们从另一个角度理解不完全现象。
首先,塔尔斯基指出,只有在形式语言这样严格地说明了结构的语言中,才有可能得到严格精确的真之定义。接着,为了避免跟“真”这个词的使用有关的语义悖论,塔尔斯基区分出对象语言和元语言。在一门演绎科学的基础上建立形式语言作为我们研究的语言,即对象语言,真这个概念的外延是对象语言中的句子。真之定义不能在所研究的语言本身中构造,而应在元语言中构造。元语言包括一般逻辑词,对象语言表达式的名字和对象语言表达式本身(或与对象语言表达式有相同意思的表达式),用这几类词可以构造正确的真之定义,即符合以下的模式:x是真的,当且仅当p,其中x是句子的名字,p是句子本身。最后,塔尔斯基得出重要结论:当元语言比对象语言“本质丰富”⑥ 的时候,可以在元语言中构造真句子的正确定义;如果元语言不比对象语言本质丰富,这样的真之定义就不能构造。因为,如果元语言不比对象语言本质丰富,元语言就可以解释到对象语言中,元语言的每个句子都对应于一个对象语言的句子并与之等价,这样,对于元语言的每一个句子,与之等价的句子的名字都包含在元语言中。此时,可以得到真之不可定义定理:无论真句子类以何种方式在元理论中定义,我们都可以从这个定义得到满足以下条件的一个句子x:x不是真的,当且仅当p,其中p是对象语言的一个句子,x是该句子的名字。(Tarski,1983,pp.247—250)或者说,在元语言和对象语言同样丰富时,如果真可以在元语言中定义,就能找到对象语言的一个句子x,x在元语言中对应的句子恰断定x不是真的,从而在元语言中重新构造一个类似于说谎者的悖论。根据真之不可定义定理,我们可以直接得到哥德尔不完全性定理。可以构造一个与形式算术同样丰富的元语言,并将这样的元语言解释到形式算术中,在该元语言中不能定义“真”,但能定义“可证”,因此可以构造出一个句子x,满足以下条件:x不可证,当且仅当p,其中x是句子的名字,p是句子本身。进一步,在比形式算术本质丰富的元语言中,可以构造真之定义,因此对于该句子x,我们得到:x是真的,当且仅当p。根据以上两个事实,易知x不可证,当且仅当x是真的。再由真之定义得到的定理,可以得出x是真的,但x不可证,并且,x的否定也不可证,这样,x就是一个不可判定的句子。(ibid,pp.275—276)
由塔尔斯基和哥德尔的分别独立⑦ 的工作可知,“真”和“可证”这两个概念决不是重合的,“可证”这个句法概念不能抓住复杂得多的“真”这个语义概念。“可证”在元语言中有纯结构的定义:可证的句子要么有如此这般的形式,要么是从有如此这般结构的表达式经一次或多次的结构转换得到的。但是对于许多形式语言而言,除了一阶逻辑等个别形式语言外,“真”并没有与之等价的纯结构的定义,因为有“真”句子不可证,真句子类和可证句子类不能重合。用哥德尔的方法,我们可以为足够强的形式系统构造出不可判定的句子x,假设该形式系统是一致的(即无矛盾)。但这并不等于说该句子在任何理论中都不可判定。由塔尔斯基的真之定义的成果,在比该形式系统更高阶的因而具有真之定义的元理论的基础上,能确定该不可判定句子x是真的,并能证明该句子。进一步,塔尔斯基还指出,如果把比原形式系统中的所有变元更高阶的变元引入该形式系统中,那么在原形式系统中不可判定的句子x,在丰富了的形式系统中变得可判定。(Tarski,1983,p.276)哥德尔还有一个相关的否定性结果:哥德尔第二不完全性定理,它表明如果足够强的形式系统是一致的(即无矛盾的),那么这种一致性不能在形式系统自身中证明。但这不等于说该形式系统的一致性不能在其他形式系统中证明。根据塔尔斯基的真之定义,该形式系统的一致性能在比该系统更高阶的元理论的基础上证明。(ibid,p.274)
四、结论
哥德尔不完全性定理中的“完全性”是一阶理论的完全性,不是逻辑的完全性。一阶理论可以看作是在一阶逻辑的基础上“合理地”增加一组非逻辑公理得到的,是为了刻画某个特定的模型而建立的,这组非逻辑公理是从该模型的真句子中挑选出来的,可以看作描述该模型的事实。一阶理论的完全性要求该理论所要描述的模型的所有真句子都是“可证的”。哥德尔不完全性定理表明:在形式算术等足够强的数学形式系统中存在真句子不可证。这个结论不仅可以应用于数学形式系统,也可以应用于物理、生物形式系统:“合理地”增加一组用一阶语言描述某个物理或生物模型的事实的非逻辑公理得到的系统。只要这些系统足够丰富,能把“可证”等句法概念在系统自身中表达出来,它们就都是不完全的一阶理论。当然,在某些贫乏的形式语言中,例如一阶逻辑和无乘法的算术中,“真”是可以被“可证”刻画的,或者说“真”有一个等价的纯结构定义,但这依赖于这些科学本身的特性。所以说哥德尔不完全性定理揭示的是形式系统的局限性而不是逻辑的局限性,并未动摇逻辑的基础。
哥德尔的否定性结果并没有否定形式语言,它也是应用形式语言得到的结果。它通过分析某种具体的形式语言——形式算术而获得“可证”这个元数学概念的一个重要性质,获得对“真”与“可证”之间的关系的认识,而这样一种认识是用思辨的方法所得不到的。我们不能因为形式语言有局限性就否定它。
首先,只有建立一门演绎科学的形式语言,“证明”这一元数学概念才得到精确严格的定义,“完全性”问题才得到明确的表述,才能对这门科学进行元理论的研究,包括对“完全性”和“可证”概念的研究。其次,形式语言对语义学的科学基础的建立有重要作用。塔尔斯基的语义学是在关于形式语言的真之语义定义基础上发展起来的,这一成果也展示了形式语言的优点。塔尔斯基通过对自然语言中“真”这个概念的分析,指出自然语言是语义封闭的,具有“普遍性”,它包括它自身的表达式的名字和“真”这样的语义词,因此在自然语言中可以构造出悖论。为了避免语义悖论,塔尔斯基区分了对象语言和元语言两个不同的层次:对象语言是我们所研究的语言,我们所要定义的真句子是对象语言的句子,而真句子的定义要用元语言来表述。塔尔斯基以形式语言作为我们所研究的语言,为形式语言构造真之定义。因为形式语言精确无歧义,并且具有结构,意义能够通过它的结构反映出来,只有在形式语言中“真”这样的语义概念的严格说明才有可能:根据形式语言的表达式的结构,可以递归地定义“满足”这个语义概念,再借助“满足”在元语言中构造真这个概念的正确定义,只要元语言比对象语言本质丰富。因此,虽然对于许多形式语言,我们都不能给出真的纯结构定义,但是可以根据塔尔斯基提供的方法,在比该语言本质丰富的元语言中构造一个形式正确、实质恰当的真之语义定义。根据真之定义,塔尔斯基得出一系列定理,表明真句子集是一致的且完全的,这为与“真”相关的语义悖论的解决提供了新的思路。有了塔尔斯基的真之理论,谨慎的哲学家也“终于敢谈真了”。(王路,1999年,第417—418页)
进一步,塔尔斯基还得到一系列重要结果:如果元语言比对象语言本质丰富,则可以在元语言中构造真这个概念的定义;如果元语言跟对象语言同样丰富,则不能在该元语言中构造真这个概念的定义。根据塔尔斯基的重要结果,我们可以直接得到哥德尔不完全性定理,并且得出:对于包含算术的演绎科学,有些直觉概念不能在该科学中定义,但如果该科学可以通过引入更高阶变元的方式丰富起来,则这些概念可以在丰富了的语言中定义;对于足够强的形式系统(假设该系统是一致的),只要能通过引入更高阶变元的方式来丰富它,用哥德尔提供的方法构造的在原系统中不可判定的句子,在丰富了的形式系统中就变得可判定了;原系统的一致性在系统本身中不能证明,而在丰富了的形式系统中也可以证明了。塔尔斯基的真之定义展示了语言层次的区分,使人们对语言有了进一步认识:要精确地研究语言,有必要把语言区分出一系列层次,每一层跟上一层的关系正如对象语言和元语言之间的关系。因此,我们可以把塔尔斯基的真之理论看作是展示用形式语言进行哲学探索的一个正面例子,它体现了形式语言的精确无歧义、有结构、能区分出一系列层次等特点对进行精确的语义研究所起的重要作用,也为认识论和自然语言的精确研究提供了基础。因此,如果认为形式语言有局限性,因而不能为我们提供可靠的知识基础,这种看法是错误的。
【注释】
① 尹传红在《智慧巨人.隐夫子.偏执狂》中说:“爱因斯坦对哥德尔怀有特殊的敬意,他赞扬哥德尔是‘自亚里士多德以来比任何人都有力地动摇了逻辑基础’的人物”。(http://www.ewen.cc/books/bkview.asp?bkid=70475&cid=155734)
② 这里的形式语言参照塔尔斯基的说明,不仅包括符号、公理系统,还包括语义。塔尔斯基所说的常项不是通常说的常元,而是逻辑联结词、量词以及有固定意思的词。
③ 一个理论可以有许多模型,但我们关注的是其中的某一个,因为许多理论都是为了刻画某个数学模型而建立的。
④ 根据哥德尔—罗塞尔定理(Gdel-Rosser Theorem)(形式算术的任何递归无矛盾的扩张都不完全,扩张中全部公理的哥德尔数集是递归集则称扩张是递归的),对于通过添加公理得到的PA的任何和谐的扩张PA*,只要PA*公理集有算法可以识别,都是不完全的。
⑤ 此结论从康托的对角线法已可以得出,但它并未排除某些相当强的子系统具有完全性的可能。(王浩,第114页)
⑥ 严格地说是元语言的阶高于对象语言的阶。表达式的阶是塔尔斯基真之理论的重要概念,类似于逻辑类型。
⑦ 塔尔斯基对其工作的独立性做了说明。(cf.Tarski,1983,p.277)哥德尔不完全性定理是1930年9月正式宣布的,它的正式发表时间是1931年。塔尔斯基提出构造真之定义的方法的论文《形式语言中的真这个概念》虽发表于1933年,但其于1931年3月已经被提交。并且,塔尔斯基于1930年11月发表的一篇论文中已经提出该构造方法,虽然当时该方法不是用于真之定义而是用于其它目的。可见,塔尔斯基并不是在得知哥德尔不完全性定理之后才进行真之定义的构造的。

【参考文献】
[1] 克莱因,1997年:《数学:确定性的丧失》,李宏魁译,湖南科学技术出版社。
[2] 刘晓力,2000年:《理性的生命——哥德尔思想研究》,湖南教育出版社。
[3] 王浩,2002年:《哥德尔》,康宏逵译,上海译文出版社。
[4] 王路,1999年:《走进分析哲学》,三联书店。
2003年:《逻辑的观念》,商务印书馆。
[5] 张家龙,1993年:《数理逻辑发展史——从莱布尼茨到哥德尔》,社会科学文献出版社。
[6] 张清宇、郭世铭、李小五,1997年:《哲学逻辑研究》,社会科学文献出版社。
[7] Dawson Jr.,John W.,1999,“Godel and the limit of logic”,in Scientific American,Vol.280,Issue 6,Jun.
[8] Goldstern,M.and Judah,Haim,1995,The Incompleteness Phenomenon,Wellesley,MA:A K Peters,Ltd..
[9] Sangalli,A.,1993年:《算术的不完全性》,余敏安译,戴宗铎校,载《数学译林》第12卷第2期:第134—138页。
[10] Smullyan,R.,1992,Cdel's Incompleteness Theorems,New York:Oxford University Press.
[11] Tarski,Alfred,1944,“The semantic conception of truth:and the foundations of semantics”,in Philosophy and Phenomenological Research,Vol.4,No.3:pp.341—376.
[12] 1983,“The concept of truth in formalized languages”,in Logic,Semantics,Metamathematics,second edition,Hackett Publishing Company.
(原载《哲学研究》2007年12期。录入编辑:乾乾)

文章的脚注信息由WordPress的wp-posturl插件自动生成


分享到:

标签 :
版权声明:版权归 哲学网:哲学学术门户网站,Philosophy,哲学家,哲学名言大全 所有,转载请注明出处!

转载请保留链接: http://www.zhexue.org/f/logic/5791.html

已有 0 条评论 腾讯微博
关于我们 | 图站地图 | 版权声明 | 广告刊例 | 加入团队 | 联系我们 |
哲学网编辑部 未经授权禁止复制或建立镜像,采用Wordpress架构,采用知识共享署名进行许可
官方邮箱:admin#zhexue.org (#换成@)索非制作|优畅优化|阿里云强力驱动
ICP证号:沪 ICP备13018407号
网站加载1.008秒
知识共享许可协议