闲之寻味 / 科普 / 自我指涉

0 0

   

自我指涉

2014-01-26  闲之寻味

—(1)—谎言悖论

在科学史上,还没有一种悖论像自我指涉(self-reference)的悖论那样引起广泛的注意。自我指涉合法存在于人们日常语言中,数学基础上和认知科学里,随处可见,造成的矛盾在逻辑上无懈可击,历经了两千多年,对此除了尽量规避之外,至今专家们仍然没有妥善的解决方案。它构造矛盾的方法成为证明中的重要技巧,在一些令人惊异的重要定理中起着关键的作用。这个系列介绍这一类悖论,剖析哲人们对它的思考和因此带来的科学进步。

谎言悖论是历史上最早的自我指涉悖论,以致成为这类悖论的代名词。它来自于公元6世纪哲学家Epimenides的例子:“All Cretans are liars... One of their own poets has said so.

公元前4世纪欧几里德创建的麦加拉学派(Megarian school)里的哲学家Eubulides领会了其中的奥妙,将这例子改为简短的一句话:“这句话是假的。”这成了一个最为著名影响深远的悖论。【1】这话令人尴尬之处在于:如果你相信这话是真的,它明明说了这是句假话;如果你认可它是句假话,那又证明了它所说是真的。所以你无论怎么理解,都是错误的。

谎言悖论是一个语义的悖论,其核心的结构是自我指涉,在说道自己时,否定了自己,它的断言总是与自身矛盾,无论你怎么解读之所言,推及自己时就拧着了。这类的语句符合语法,在生活中也时有出现,人们常常做了不合逻辑的解读。

有人不以为然,日常中哪有这样说话的?瞎掰!先看下面的例子:

小赵说:“老张说的是瞎掰!”老张说:“小赵说的是假话。”

这是生活中常见的两人斗嘴,你倾向于哪方的解读都符合逻辑,没什么技术含量。无论事实上谁是谁非,怎么解读,它们组成的命题在逻辑上永远是对的,称为永真性命题,是逻辑真理。真理问题在后几篇细说。如果老张说了肯定小赵的话,那就要有点智商来解读了。

小赵说:“老张说的是瞎掰!”老张说:“小赵说的是真话。”

这小赵和老张互相针对说的话,谁是谁非?不同人的反应不同,往往决定于心境、经历和智力。如果在第三者转达他们话时,略加点形容,就更容易影响你的判断了。

小赵气愤地说:“老张说的是瞎掰!”老张尴尬地说:“小赵说的是真话。”

小赵媚笑着说:“老张说的是瞎掰!”老张呵呵笑说:“小赵说的是真话。”

小赵严肃地说:“老张说的是瞎掰!”老张点点头说:“小赵说的是真话。”

同样两人说的话,在转达时一字不变,只是形容的口气略有不同,多数读者的判断就受了叙述者的影响,倾向性从小赵说的是真话到后来成了假话变化。关于第三条,有人看到的是争吵,有人读到反讽。到底哪一种对?其实都不对!你要会逻辑才能明白。

人的判断是由感性和理性影响的,感性的认知不稳定,结论依自己情绪和旁人影响而定,理性关心是本质的内容。用来影响感觉的是艺术,科学是发掘本质的工具。科学研究判断是非,讲逻辑就要忽略形容词、副词等等表达情绪的言语。不受叙述口气的影响。

剥离了这些无关的东西,从逻辑上来看这两句话组成的意思,如果小赵的话是对的,老张是瞎掰,他说的“小赵说的是真话”这话是瞎掰了,那小赵的话就不对,这导致了矛盾。如果小赵说的是假话,老张说的是真话了,他说“小赵说的是真话”又和假设矛盾了。所以两人所说构成了悖论。它是间接的自我指涉。如果你的头脑不严谨,受其他暗示的影响,会片面地沿着某个思路而忽略了另一面。思想简单的人读不懂反讽,因为反讽需要进一步的逻辑解读。如果简单以字面相反来读反讽,那其实是缺乏解读能力,只能按照别人贴的标签或情绪暗示来理解文章,遇到悖论的情况就更会错误理解。

能够不受情绪干扰,根据逻辑来叙述正确解读语言所描述的事件,是一种理性的能力。让我们看下面的经典例子。

公元前6世纪Epimenides谎言悖论原版的叙述很靠近生活的语言,这常被一些人认为是最早的悖论,其实不然。【2

有个克里特岛诗人发誓说:“所有克里特岛人说的都是谎言”。

那他说的可信吗?表面看来应该可信,因为他是信誓旦旦地声明。人们常想,即使他也是撒谎,正因为他也是克里特岛的人,也不过是坐实了这句话。但这样的理解不是按逻辑,而是凭感觉。逻辑上,如果他说的这句话可信,他是克里特岛的人,根据这句话,那他说的也是谎言了,即是不可信的。这个矛盾否定了可信的解读,只剩下不可信的可能。

如果我们也能够在逻辑上否定不可信的情况,那才构成了悖论。因为逻辑上的排中律不允许有这样的状况。

但这故事严格地说并不构成悖论,而是具有确定含义的。这个诗人说他家乡人说的都是谎言,并不排斥这诗人说假话的可能。只要他家乡还有一个老实人,这诗人就是说假话。在这个情况下这段文字没有矛盾。唯有这样解读,这段的介绍文字才不自相矛盾,才有了确切的含义。所以它唯一合乎逻辑的解读是:叙述了一个诗人在撒谎的场景,诗人所说的话是他撒谎的证据。他说家乡的人都是这德行,逻辑上这只能证明他本人是如此,而不及他人。

在现实的生活中,这类的句式很多。经常看到中国人用中文写:“中文网上的话全是垃圾!”,或者“中国人没有诚信。”在辱骂包含着自己的群体时,常常如同克里特岛的诗人,逻辑上,他骂的是自己,而不及他想骂的大众。骂人也是要学文化有头脑的,不然被自己骂成了猪头都还洋洋自得,贻笑大方!

(待续)

【参考资料】

【1】WikipediaLiar paradox http://en.wikipedia.org/wiki/Liar_paradox

【2】WikipediaEpimenides paradox http://en.wikipedia.org/wiki/Epimenides_paradox

公元前4世纪希腊哲学家Eubulides是个有趣的人,他提出七个悖论【1】当时都很有名,亚里士多德和柏拉图用它们作为促进思考的饭后谈资。最有名的当然是谎言悖论,其中三个可以用这个故事来代表:

阿发忽略了走近他的人,把他当作陌生人。这个人是他的父亲。阿发是否忽略他的父亲,把他当作陌生人?

另两个的代表是:

当你有头发时显然不是秃头,拔掉一根头发不会让非秃头变成秃头,每一次拔掉一根头发时都是如此,为什么最后是秃头?

还有一个是这样的:

没有丢掉的东西你还拥有着,你没有丢掉头上的角,所以你头上还有角。

这例子曾被律师用到法庭的诘问上,法庭总是要求正面简单地回答问题,不允许多做解释。

起诉律师问:你最近不再打老婆了吧?请正面回答“是”或“不是”!那个从来没打过老婆的被告,该答哪个?

这些都曾是有关语义的悖论,分别是有关语句的含义,语义的模糊性和提问预设前提的问题。到了现代已经弄清楚,人们可以很好地解答这些问题,就不成为难题了,只是有时被用做语言陷阱,忽悠没知识的人。

在学术上,只有谎言悖论,因为自我指涉被广泛地用在自然语言里,还没有个妥善的解决方案。有人感到疑惑,谎言悖论不也就是说道自己才出问题的,把自己排除在外不就行了?没那么简单,自己说道自己叫做自我指涉(self-reference),是很常见合法的语句,有难以替代的表达能力,比如说:“这博文是中文写的”,“我说的是真话”,这些自我指涉的语句,不可能在生活中排除它。光是禁止谎言悖论这句话也不行,因为你会遇到无数个具有相同逻辑结构的悖论。只有充分了解它,你才不会被迷惑,才有可能考虑解决方案。

具有与谎言悖论相同逻辑结构的语义悖论,可以找出很多来,下面是近代引起学术界的关注,比较著名的几个悖论。

Grelling’s paradox【2】:Grelling解释说,“异质”(heterological)这词是指本身并不具有这个词所描述的属性,比如说:“名词”不是异质的,因为“名词”是名词;“德语”是异质的,因为中文的“德语”这个词并不是德语。那么:

“异质”是异质的吗? ( Is “heterological” heterological?

如果你回答:是,那它就具有它所描述的属性,这与它的定义矛盾;如果回答是:否,即它不具有它描述的属性,则按定义它该是异质的,又是一个矛盾。这是因为这句话也具有自我指涉结构,“异质”这个词可以用来描述所有的词,包括它自己,当它指向自己时,无论你回答“是“或”否“都导致矛盾。

Berry’s paradox【3】:这个通过数学的内容形成了一个自我指涉结构的悖论。为了方便大家阅读,我把它改写成中文的版本。

我们可以用语言来确定一个自然数,比如说“三加四”说的是7,“五的平方”是25。那么“不能用少于二十个汉字描述的最小的自然数”,这短语定义个自然数吗?

在引号里这段话的前十三个字“不能用少于二十个汉字描述的”是一个约束条件,它确定了自然数的一个子集。因为汉字是有限的,少于二十个汉字能够描述的自然数是有限的,而自然数有无穷多,所以,不能用少于二十个汉字描述的自然数,有无穷多个,这个子集不是空的。在非空的自然数子集里总有一个最小的数。所以这段话的描述定义了一个自然数,记它为z。又因为这段话只有19个汉字,所以z是用少于二十个汉字描述的自然数,它不应该属于这个“不能用少于二十个汉字描述的自然数”的子集,这就谈不上是这子集里的最小的数,也即是不符合这段话的描述。自然数z是由这段话来确定的,但它又不符合这段话的描述,这是个悖论。它通过检验自身的属性来否定自己。

Richard's paradox【4】:这个悖论仍然企图用语言描述来定义一个数,这回是实数了。这样的数很多,例如“圆周和直径之比”指的是π,“根号2”,“正弦45度”,“个位是3,十位是1的两位数”等等。将所有这类的描述按照字典的顺序,可以排列成一个表,称为Richard表。现在我们用下面的一段话来确定一个实数。

定义实数r:它是一个真小数,如果Richard表中第n个描述所确定的实数的第n位小数是0,那么这个实数r的第n位小数则为1,如果是其他情况则为0.

显然这段话通过具体给出每一位的数字来定义了实数r,所以它必须在这表中。但是仔细考察一下这段话的描述,发现这个数不可能在这表中,因为它如果是在表中,设是表中的第k个位置,按照r的定义,第k个位置的那句话所确定实数的第k位小数,与r不一样。这就构成了矛盾。

熟悉集合论的朋友应该可以看出,这个悖论用了Cantor证明实数不可数时著名的“对角线法”。它是通过否定每一个同类来否定自己。

语义悖论并不一定是直接地自我指涉,比如说下面不谈及自己的两句话也构成一个悖论。

下面那句话是对的。

上面那句话是错的。

这是个间接的自我指涉,叫做“自我指涉链”,用两段话来否定自己。不难想象这个链条可以拉伸的很长,通过很多段话不断传递才构成了自我否定。这样的现象在生活语言中和一些文章中都存在,只不过许多人不自觉地陷入了悖论,或者当了克里特岛诗人,说的话虽不能构成悖论却是在否定自己所言,反过来指向自己打了嘴巴。

用自己的头脑依照逻辑琢磨一遍这篇中例子的辩驳,找出它们与谎言悖论的关系。如果感到的只是忽悠,或是简单地认为违反了什么规则,那你就没动过脑子,或只是背了百科和百度。

学习悖论如果你止步于困惑,从而怀疑逻辑推理的作用,那你就没有走通这个过程,并不了解历史上真正智者已经带来的科学进步和光明。下面几个章节,将带你了解他们是怎么想的。

(待续)

【参考资料】

【1】WikipediaEubulides http://en.wikipedia.org/wiki/Eubulides

【2】WikipediaGrelling–Nelson paradox http://en.wikipedia.org/wiki/Grelling%E2%80%93Nelson_paradox

【3】WikipediaBerry paradox http://en.wikipedia.org/wiki/Berry_paradox

【4】WikipediaRichard's paradox http://en.wikipedia.org/wiki/Richard's_paradox

自我指涉(3)——什么是真理

上一节的语义悖论反映出自然语言表达的疵瑕和能力的不足。谎言悖论和Grelling's paradox让我们思考语义的基本概念:什么样的句子是“真”的。后两例,Berry’s paradoxRichard's paradox反映了语言表达“可定义”的能力问题。它们归结为:怎么定义句子为真的。

在哲学家和逻辑学者眼中,真理是用语言表达的观念。除去把真理当着形容词的神圣光环后,当我们问到真理时,它指怎么定义语言的陈述是真的。

对这个问题,亚里士多德的回答是:真理描述了实在的世界。他在“形而上学”里的名言是:“说是者为非,或说非者为是,则为假;说是者为是,非者为非,则为真。”这个经典的答案被生活和科学界广泛地接受,成为了常识。

两千年后理性主义兴起,斯宾诺莎、莱布尼茨、黑格尔和布拉德雷等认为,真理是与整个知识体系系统无矛盾的命题和理论。这受到用演绎推理的科学家们欢迎。但如此,真理的正确性只是相对于系统的假设而言,能对任何系统都保持绝对正确的真理只剩下重言式的命题。莱布尼茨认为有两种真理:“推理的真理和事实的真理,推理的真理是必然的,而事实的真理是偶然的。事实的真理依赖于经验,而推理的真理,即逻辑真理,来自天赋的内在原则。”二十世纪初,维特根斯坦更明确地提出逻辑真理就是重言式,重言式既不能为经验所证实,同样也不能为经验所否定。它与现实经验没有任何联系的。

重言式是无论怎么解释其命题变项,逻辑上永远为真的命题公式,它在形式逻辑中扮演重要的角色。将重言式的命题变项代入具体值的句子,比如说:“小张很受女孩喜欢,因为他有女孩缘。”“要发生的终究是要发生。”“科学是不容置疑的,因为所有错误的东西都不是科学的。”这些论断在逻辑上是自给的,怎么也不能说错,日常人们也好这么说。但是所有的重言式的例子都不需要依赖于现实,没有你想了解的真相,也就是说全是废话。你把其中的主词换成其他,例如:把“科学是不容置疑的,因为所有错误的东西都不是科学的”,换成“巫术是不容置疑的,因为所有错误的东西都不是巫术。”这也是逻辑上无懈可击的真理。

基于对谎言悖论的深入思考,波兰逻辑学者阿尔弗雷德·塔斯基(Alfred Tarski19011983)用严谨的逻辑来研究语义,他在1933年发表《形式化语言中的真理概念》提出语义真理论,这个理论被誉为现代逻辑在哲学上的三大成果之一。著名逻辑学家苏珊·哈克认为:“塔斯基的理论大概一直是最有影响的、受到最广泛赞同的真理理论。”

塔斯基认为句子的“真”是个语义的概念。真理论研究怎么定义指称语句是真的这个谓词。谓词(predicate)在数理逻辑中表达一个个体的性质或多个个体的关系,例如:x是红色的,x大于y,等等,它可以表达为谓词逻辑的公式P(x)Q(x, y),看作从个体的论域到逻辑值(TF)的函数。

他认为谓词“是真的”之定义必须要满足实质上恰当与形式上正确的两个条件。【1】“形式上正确(formally correct)”指定义必须是严谨没有歧义的,这要用建立在公理系统的形式语言来描述和逻辑证明的。“实质上恰当(materially adequate)”指它必须符合经验,这便是亚里士多德的解读,将句子的真假和它含义所对应的经验联系起来。因为“真”是非常基本的语义概念,它只能由更基本的,诸如“满足”,“指称”等等更基本的概念来逻辑定义,而这些更基本的语义概念最终只能用一系列符合直觉的“实质上恰当”实例来说明,真理的定义必须能够包容这所有的实例。因此在提出真理的定义前,首先要提出“真”的句子实例必须满足的模式(any adequate definition of truth must satisfy),以便在逻辑上能够证明这定义满足这个模式,然后用公理化方式针对这个模式来定义为真的谓词,他提供了几种简单语言实现这种定义作为例子。【2

这个定义的适当性模式,称为T-schema,它写作:

Schema T: ? T<φ> ? φfor all sentences φ.

这里T是作用在句子名称上的谓词公式符号,指述这个句子是真的。φ是一个陈述句,<φ>是这个句子的名称。T模式解读为“x是真的,当且仅当φ,这里x是句子φ的名称”,但这不是严谨的形式语言定义,只是自然语言对这模式的解读。

这解读就是亚里士多德用自然语言描述的真理概念,符合这模式的实例如:

“雪是白的”是真的,当且仅当雪是白的。

塔斯基强调T模式不是定义,而是实例要符合的模式,“真”之定义应该以满足T模式的所有实例作为语义后承。为什么他不直接给出真理的定义呢?因为若用自然语言给出了判定陈述句为真的定义,那么总会陷入谎言悖论的困境。假设我们在自然语言中用T模式作为真理的定义,即亚里士多德的定义,考虑将这定义应用到下面的例子:

设S为博文中第n行的话。下面是博文中第n行,它是:

博文中第n行的话不是真的。

S是这句话的名称,从T模式的定义有:“S是真的,当且仅当博文中第n行的话不是真的。”依所设的符号定义:S为博文中第n行的话,用S代替上面T模式句子中这“博文中第n行的话”,则有:“S是真的,当且仅当S不是真的。”这就陷入了谎言悖论的困境。

在自然语言系统中,不能避免这类语义悖论。其原因是这类语言系统的语句,可以作形式和语义的两种解读,它可以指向自身,又具有在其自身之中断定句子真值的能力,这叫做“语义上封闭的语言”。这个封闭性造成了自我指涉。

谎言悖论和上面的例子,陷入悖论时都利用了自然语言的歧义,有时作形式,有时作语义的两种解读,以及自指的评价造成的。在无歧义严谨的形式语言中,是否可以避免这类悖论?

(待续)

【参考资料】

【1】 Tarski, A. (1944) "The Semantic Conception of Truth: And the Foundations of Semantics," Philosophy and phenomenological research, vol. 4, no. 3 341-76. http://www.cs.uwyo.edu/~jlc/courses/comp-sem/Semantic%20Conception%20of%20Truth.pdf

【2】SEPTarski's Truth Definitions http://plato.stanford.edu/entries/tarski-truth/

自我指涉(4)——不谈自身无烦恼

无歧义严谨定义的形式语言,现在已经广泛应用在计算机程序语言和数学公理表达中。塔斯基是先驱之一。他严格定义的T模式,让我们可以用数理逻辑的理论,来研究与真理有关的问题。在数理逻辑中,有个著名的“对角线引理”,或称为“不动点定理”,【1】如下:

设S是包含着一阶算术的理论,对任给公式φ(x)存在一个句子ψ,有 S ψφ<ψ>.

这里“包含着一阶算术的理论”指包含着算术公理用一阶逻辑推出的命题集合,现在整个公理化数学系统已建立在这上面。凡能描述算术的形式语言也必须包含它。S 的意思是:理论S中,能够证明右边的式子成立。这里φ<ψ>是φ(<ψ>)的简写,是评判句子ψ具有φ性质的谓词表达式。这个引理的大意是:对于能够谈算术讲逻辑的语言,任给一个用来判定句子的属性φ,总能写出自我指涉的一句话ψ,说自己具有这个属性φ。用自然语言表达ψ就是:“这句子具有属性φ”。不过这里的ψ是用形式语言表达出来,在理论S里证明它逻辑上是这个意思。用它构造个谎言悖论可以证明一个重要的定理。【2

塔斯基定理:任何包含着一阶算术的理论,也包含了T模式,则是不相容的。Any theory extending first-order arithmetic and containing schema T is inconsistent.

有了这个对角线引理,它的证明很简单。如果这个理论也包含T模式,谓词T在这里是个公式,它的否定T也是个公式,根据对角线引理,存在着一个句子ψ,在这个理论里有:ψ T <ψ>。但按T模式,则有ψ T <ψ>,得出T <ψ> ? ?T <ψ>,说明这理论里有矛盾,不是自洽的。

这个定理也称为“Tarski's undefinability theorem”,它指出了语言定义能力的局限性,任何足够丰富包含算术的语言,都不足以无矛盾地解释它所能表达句子的语义,句子的语义必须在更丰富的高阶语言来表达,否则就可能引起悖论。

塔斯基定理几乎与哥德尔定理在同一时间被证明,包含着许多共同的内容。近些年人们认为塔斯基定理值得更多的关注,因为哥德尔定理只是揭露数学系统里的局限性,在哲学层次不清晰,而塔斯基定理则找出问题出在语言固有的局限性,这不仅适用于数学,而且适用于由对角线引理导致自我指涉的任何系统。

为什么要花费时间研究语言的问题呢?因为哲学、科学、包括数学理论的表达和推导都是通过语言来进行的,语言出现的悖论也会在它们的理论中出现,语义悖论的解决方案同样有助于它们问题的解决。

由于这个定理,塔斯基提出要避免语义的悖论,必须把语言的表述功能和对语言的评判功能分开,任何语言都不应该说道自己写的句子,只能用高一级的语言来进行。这时被评判的称为“对象语言(object language)”,评判者称为“元语言(meta language)”,元语言具有对象语言的语法、逻辑关系等表达能力,再加上对对象语言的评判能力。例如,在对象语言可以说“雪是白的”,但不能说“‘雪是白的’是真的”,只能在元语言说这样的话,而(“‘雪是白的’是真的”是真的)只能在更高一级语言中说。这样我们就把语言分了层次,每一个层次的语言都不是语义上封闭的,不能说道自己。不谈自身就什么麻烦都没有了。

在这个规定下,所有的语句都不能指向自己,也不可能通过自我指涉链的传递,指向高阶的评判语句,这就解开了自我指涉,也就没有了这类的悖论。

那么如何定义真理呢?从塔斯基定理知道,在对象语言里不能包含T模式,说句子为真必须在元语言中。指称对象语言中一个句子为真的谓词(式子T)在元语言中表述,在元语言里定义了这个为真的谓词,它必须能够满足T模式所产生的例子,并且被元语言系统逻辑地证明。这可以通过满足所有T模式简单句,和定义它们逻辑连接词形成的复合句来实现。这样形式语言公理化的定义,可以通过一系列繁杂机械性的工作来完成了。这样子,L0语言里的句子,由元语言L1定义的T1谓词来评判它的真假,L1语言由高一级元语言L2里来描述并定义T2谓词,用L0L1L2L3,。。。,来表示层次结构里的语言,每个Ln里定义下面层次语句为真的谓词Tn,和其他层次的不是同一个词,每一个层次的语言都不是语义封闭的,以此来避免悖论。【3】【4

1985Yablo发现类似于谎言悖论,但不是自我指涉的语义悖论。他构造了一个无穷系列的句子链,每个句子都说后面的句子不对。即对于每个自然数i,定义Si =for all j>i, Sj is not true”。我们先用反证法证明没有一个句子是对的。如若不然,则有个iSi是对的。这句子说j>i之后的Sj都不对。特别有Si+1不对。否定了这句,那么至少有个k,k>i+1,句子Sk是对的了,但这与Si的断言相矛盾。这证明了每个句子都不对,包括S0。但如果是这样,则对所有 i>0Si都不对,S0说的便是事实,这又成了矛盾。

这个悖论没有通过一个闭合的链条指向自己,所以不是个自我指涉的悖论,发生悖论的原因是非well-founded的,即它具有无穷的包含关系。要阻止这类悖论,要求某些下降型的层次结构语言是well-founded的。

有了明确的语言层次结构,能够避免自我指涉等悖论的困境,大家高兴了几十年但新的问题又来了。

(待续)

【参考资料】

【1】WikipediaDiagonal lemma http://en.wikipedia.org/wiki/Diagonal_lemma

【2】WikipediaTarski's undefinability theorem http://en.wikipedia.org/wiki/Tarski%27s_undefinability_theorem

【3】 SEPTarski's Truth Definitions http://plato.stanford.edu/entries/tarski-truth/

【4】塔斯基的真理論 http://callmecallme.blogspot.com/2007/02/blog-post.html

自我指涉(5)——真值的间隙

塔斯基的理论成功地应用在表达数学和计算机程序的形式语言中。这些语言的功能比较简单,通过元语言与对象语言可以清晰严谨地分层描述。塔斯基是数理逻辑模型论开创者之一,用严谨的数理逻辑建立起语义真理论。他的真语句集不可定义性定理和判定性问题的研究,在数学、哲学、语言学上意义重大。他对语义悖论的层次结构解决方案,从1933年起主导了这个领域,一直到1975Kripke发表了影响深远的著名论文“Outline of a Theory of Truth”才遇到了真正的挑战【1】。

明确的语言层次结构虽然规避了自我指涉的语义悖论,很成功用在形式语言中,但对于要求有更丰富表达能力的日常语言显然是不自然和不完备的。例如它要求不能在有关联的同一个段落(context)中说“雪是白的”和“‘雪是白的’是真的”,因为它们属于不同层次的语言。在塔斯基理论里,每一个层次语言中都定义了自己“真”的概念,高层语言包含着低层语言所有的元素,它就包含有下面各个层次不同的“真”谓词,当我们说起“真”的时候必须分清它是属于哪一个层次的。判断语句到底属于哪一个层次,这也会成为一个问题。例如,迪恩说:“尼克松说的所有关于水门事件的话都是假的。”尼克松反咬一口:“迪恩说的所有关于水门事件的话都是假的。”因为这两个语句都有评判对方语句的功能,若依评判者而定,它们不能在同一个层次,评判句子要比被评判的句子高一个层次,但是它们间是互相评判的,所以怎么把它们分出层次都会产生矛盾。

生硬的层次结构,违背人们习惯的谓词定义,以及自然语言分层的矛盾,让人们重新审视塔斯基针对“谎言悖论”,设计的解决方案思路。谎言悖论“这句话是假的”,极为干净,形成了悖论的原因很简单,它因自我指涉在逻辑推理后导致矛盾。要解决它,必须在自我指涉否定自己和逻辑规则,这两者中改变一个。塔斯基认为,逻辑是科学的基础,这是不可改变的,所以他选择避免语句评判自己的自我指涉。

但是自我指涉在日常语言和数学中都是经常出现,在绝大多数情况并没有造成问题,并具有难以取代的功能,例如:“这篇博文是用中文写的”,“这里写的都是真话”,以及集合论和哥德尔定理的证明的技巧都是合法、必要和成功的。认为谎言悖论的问题是“不规范”和“没意义”句子的指责是没有道理的,它只是特殊情况时的病态,为了治疗这种病态,要付出改变自然语言习惯为代价,甚至牺牲了语言表达能力的完备性,这个手术太大,不可能被大众接受。自然语言远比形式语言功能强大。人们宁愿容忍其中的矛盾,而且这矛盾在实践中很常是可以被解释清楚的。

作为悖论的解决方案,如果想保留自我指涉,那只能研究怎么改变逻辑规则,来容忍这个矛盾了。

采用辩证法确实是一种解决方案,人们可以承认一个句子既是真的也是假的。这样子所有自我指涉悖论的结果都是合法的。但这否定了逻辑中的矛盾律。否定了这个亚里士多德在他的“形而上学”里,称为“一切原理中最为确定(the most certain of all principles)的矛盾律”,从而无法据此来推理,这对于建立在之上的科学是难以接受的。

如果仅仅在认知语句为真时放弃排中律,在“真”和“假”之外,有个非真非假的“未定”状态,这还是符合人们对语言的学习过程和现实情况的。设想一下牙牙学语的小孩,对“雪是白的”这句话,是无法断定其真假,直到他学了“雪”和“白”与实物的对应,见到了雪,才能断定这句话是真的,在这之前对这句话的判断处在未定状态。有些话,人们永远都无法断定真伪的。这时就要用到三值逻辑,真和假值间符合通常二值的逻辑运算,“未定”与真假值之间的逻辑运算,可以有不同的设计。Kleene的强三值逻辑是其中一种,规定只有“真”和“未定”的与运算的结果为真,其他的“与”运算及“非”运算,有“未定”参与的结果设计仍为“未定”。

按照语义真理论的观点,真理是如何定义指称语句为“真”这个谓词。Kripke的方案模仿了塔斯基的T模式和分层语言结构来定义语句为真的谓词T,只不过这层次不在语法上,而是仅仅用在逐步定义这个“真”的谓词步骤(stage)中,用解释语言L0, L1, L2,…来实现这个构建T语义的过程。所以这方案称为隐层次结构。

中国文化的思想方式基本是接受这个规则。知识的传承通常用口诀和经文的背诵,在与事实对照修正中来领悟。讲究的是读书千遍其义自现,各种不加定义的概念含义和关系在众多事例参照下,从模糊到清晰一层一层地涌现,最后豁然开朗融会贯通,这叫顿悟。而不是像西方科学中的概念,是由逻辑逐个依次严格定义上来的。

在隐层次构建的每一个步骤里,谓词T是部分定义的,有“真”、“假”和“未定”值,依Kleene的强三值逻辑规则进行推理。不同步骤解释语言的唯一区别,在于同一个内涵谓词T的外延不同。在这语言的语句集合中,设有两个不相交的子集UV,依真假分别用来放语句φ,这对应于T<φ>为真和假值的分类。在最初解释语言L0里,所有的语句都在未定状态,集合UV都是空的,对所有语句φT<φ>值都是未定。然后在高一层次语言对低层语句,用三值逻辑的T模式来判定未被放入UV语句的真理值T<φ>如下:

φ is true (false) in Lα T<φ> is true (false) in Lα+1

不难看到,在这个步骤α增加的过程中UV里的语句不断地增加,遗留在外面的越来越少,T<φ>值不是未定的越来越少。这个单调的变化过程终究有时尽,这时T<φ>值是真和假的都已经在UV中,遗留在外的语句,不再随着α增加能在Lα语言里判断出其真假值,也就是T的含义不再随着步骤增加而改变了。这时的步骤记为γ,谓词T就像定义在这语言中有:

φ is true (false) in Lγ T<φ> is true (false) in Lγ.

这个过程一般化称为“固定点定理(Fixed point theorem)”说:完全偏序链上的单调算子至少有一个固定点。它在现代形式真理论中扮演了中心的角色。

谎言的句子因为无法肯定它的真假值,所以不在UV中,叫做在“真值的间隙中(truth-value gap)”。为什么谎言句子和原来一系列语言悖论的句子,现在不再是悖论呢?因为它们在推理中否定了真和假的可能后,在三值逻辑中还允许停留在“未定”值中,这里的规则没有排中律,所以不构成矛盾。

Kripke的论文虽然只是一个大纲,但它是在塔斯基真理论之后最有价值的,合乎直觉和自然语言习惯,能够规避谎言悖论困境的方案。尽管它还有许多疵瑕,还不能彻底摆脱塔斯基的层次结构【3】,但被公认为富有哲思和洞见,及其敏锐精致的理论。

但是,用三值逻辑能够完全摆脱了悖论的困境吗?看下面加强型的谎言悖论:

这句话是假的或者未定的。

从逻辑推断上,无论判断它是真的、假的、还是是未定的都会发生矛盾。这叫做悖论的“报复问题”,当你给出一种解法时,又产生了一个与原来完全类似的新悖论,仍然无解。

自我指涉深入到人类思想的基因中,它的悖论犹如一种无法治愈的疾病,各种的解决方案只能尽量规避或将它驱逐到不怎么常见的地方。下篇将介绍,这相同的疾病也困扰着最为重视严谨性的数学基础,为了解除痛苦,现在也正吃着各种类似的药。

(待续)

【参考资料】

【1】 Kripke, S. (1975): "Outline of a Theory of Truth", The Journal of Philosophy, vol. 72, no. 19: 690-716. http://philo.ruc.edu.cn/logic/reading/Kripke_%20Theory%20of%20Truth.pdf

【2】WikipediaYablo's paradox http://en.wikipedia.org/wiki/Yablo's_paradox

【3】Kripke: 真理论https://phil-commune.net/bbs/thread-635-1-1.html

自我指涉(6)——数学基础的修补

经过几十年的考察,正当集合论被广为接受,成了数学的基础时,1903年罗素(Russell)和策墨罗(Zermelo)几乎同时发现了悖论。罗素悖论是:定义罗素集R为所有不包含自己作为元素的集合:R = { x | x x },然后问R是不是属于这个集合?麻烦的是,如果R R,即R是集合R的元素,依定义有R R;反之如果R R,按集合R的定义,R是集合R的元素,即R R。无论哪一种情况都是矛盾。

为了让这个悖论更通俗易懂,罗素编了个“理发师悖论”:村里的理发师宣布,他给自己不刮胡子的人刮胡子。问他给不给自己刮胡子?R为理发师给刮胡子人的集合,R的成员条件是自己不刮胡子的人,问理发师是否属于这个集合。这就把罗素悖论对应于理发师悖论。

罗素悖论是受1899年康托尔“宇宙集(universal set)”悖论的启发后设计的:设宇宙集U为包含所有集合的集合,问它的势是多少?由康托尔定理知道,集合U的幂集P(U)(即集合中所有子集构成的集合)的势比U的势大,|P(U)|>|U|。但是按定义,集合U包含所有的集合,P(U)的元素都是集合,它当然也包含了集合P(U)的所有元素,所以|U||P(U)|,这产生了矛盾。

康托尔悖论的技术含量不在这逻辑里,他的精华是在康托尔定理的证明中。这定理先假设定理的反命题成立,造成一个自我指涉的悖论来反证。其中的技巧被罗素借用来构造他的悖论。关于罗素悖论和康托尔定理的详细证明请参考看【1】。

集合论的悖论在数学界引起极大的震动,虽然谎言悖论早已知道,人们总是以为是语言歧义引起的,多说几句话就可以澄清了。数学要求极其精确严谨,基础理论中任何的不一致都将导致整个数学系统崩溃。作为数学基础的集合论出现了自相矛盾的现象,这该怎么办?

挑剔疵瑕或编个自圆其说的解释来绕过它?这是糊弄自己。判断是不是悖论,不是按照自己的想象,而是按照大家公认的逻辑和原则。本质的问题没解决,还会以其他的面目出现。

说这两个例子不合法?你必须说出它具体违反了什么规则,才能有效地排除类似的悖论。

禁止自我指涉?生活和数学中有无数的自我指涉,这打击面太宽。科学研究要找出一般的规律和通用的规则,不是仅仅为了解脱眼前的困境来因例设规。基础的修补要保留原来基础上的绝大多数成果,而不是重起炉灶。

康托尔的朴素集合论基于一个非常直观的思想:给定一个属性,等价于定义一个集合包含着具有这种属性的所有个体。这让集合成为非常基本,几乎是自明的概念,从而被广泛接受成为数学的基础。这个思想叫“无限制的抽象原理(unrestricted abstraction)”或者unrestricted comprehension principle,用形式逻辑的公式表示为:

u (u { x | φ(x) } ? φ(u)), for all formulae φ(x).

罗素悖论证明了“朴素集合论不相容定理(Inconsistency of Naive Set Theory)”:

任何理论包含有无限制的抽象原理,会产生自相矛盾。

塔斯基定理和它类比的说法是:形式化表达直观自然的真理,将导致自相矛盾。

不相容定理说明我们必须对集合定义加以限制,才能避免悖论。这两个悖论都因自我指涉,在集合和它元素间的包含关系上出现了矛盾。第一个补救方案由罗素和Whitehead作出,叫做“类型理论(type theory)”。他们认为函数的变量是限定在一定类型的,所以定义集合的公式φ(x)的变量也必须受到类型的限制。于是建造了一个类型的层次结构,每个数学对象都属于一个类型,数学对象的类型从底层一直明确定义上来,互不兼容。这样避免了自我指涉。这相似于塔斯基的语言层次结构。实际上塔斯基是受到类型理论的启发,建立起语言层次结构的。所以用类型理论定义的集合,也有塔斯基方案中过多限制,生硬不好用的缺点。

现代数学中最广为接受的是Zermelo-Fraenkel集合论(ZF)。它是个隐层次结构的解决方案,类似于Kripke的真理论,用构造的方法逐步定义集合,从而在集合间分出层次来。由于多数教科书只谈康托尔的朴素集合(naive set),对大多数只了解朴素集合和基本集合论(Basic Set Theory)的人,在悖论出现后,可能会不知所措。

朴素集合论是直观的,给予一个属性的描述,就能定义一个集合。集合的悖论否定了这种简单想法。公理化的集合论通过严格的方式给集合的构造一个约束,来避免这些悖论。ZF用严谨的形式逻辑语言来书写,又因公理化的定义方式,对此不熟悉的人比较难懂。这里用熟知的集合概念,简略剖析一下ZFC2】的公理和目的,给出一个直观的图像,让大家重拾信心知道趋避。ZF是由下面几个公理组成的。

外延公理(Axiom of extensionality)定义集合相等,是它们有着相同的元素。

正规公理(Axiom of regularity)禁止集合具有循环包含和无限包含链的情况。

空集公理(Axiom of null set)定义了空集的存在。

并集公理(Axiom of union)包含有几个集合中的所有元素,构成一个集合。

幂集公理(Axiom of power set)集合的所有的子集,也构成一个集合。

无穷公理(Axiom of infinity)提供迭代公式来构造一个无穷集合,它对应于自然数集合。

替代公理(Axiom schema of replacement)集合A的映射像F(A)是个集合【3】。这对任何的映射(functional formulaF都有效,所以称为公理的模式。

上面几个公理支撑起ZF集合论。有些ZF的介绍还包含着分类公理和配对公理,但它们都可以从这里推出。对已有朴素集合论知识的人,上面公理的性质都很容易理解。由这些公理导出合法的ZF集合,比朴素集合多的限制只是正规公理和替代公理。正规公理说:非空的集合,必须至少有一个元素它不包含这集合里的其他元素。这样就杜绝了循环包含(如:xy & yz & zx)和无限包含(如:… x3 x2 x1 x0non-well-founded的情况。这意味着集合系统是个well-founded的阶层结构。替代公理用来从已有的集合产生新的集合。

替代公理和空集公理可以导出著名的“分类公理(Axiom schema of separation)”,它原是在Z里设计为限制“无限制的抽象原理”的核心公理。它类似于替代公理,只不过把这个映射变成是对已知集合A中元素的约束φ(x),以此来构造(A的子)集合{ x A | φ(x) } 。从而可用类似朴素集合论的方法来定义集合,只要把它局限在已有的集合里,就不必担心会发生悖论。已知的集合包括数学上常见的各种集合。这时无限制的抽象原理在ZF下改变为局限抽象原理:

u(u { xA | φ(x) } ? φ(u)), for all formulae φ(x) on set A.

有朴素集合论的概念的人,运用分类公理足以定义普通数学应用所需要的集合。只有对数学基础的研究,需要特定公理化集合论特征的集合时才用到替代公理及其他。

替代公理和分类公理必须从已知的集合中生成新的集合。那些初始的集合是从哪里来的?它们是类似于Kripke方案那样逐层构造的。从空集开始迭代地用并集和幂集公理,建立起越来越大的集合系统。空集是最底层,集合的幂集高一个层次,只有高层集合对低一层的集合,存有集合与元素的包含关系。无穷公理说明它们可以高到无穷,并构造了自然数集。并集和替代公理构造的集合填充了每一层,外延公理说明了集合相等的条件。正规公理阻止了低阶集合包含高阶集合的可能,让每个集合呆在这累积层次结构的某一层。这杜绝了罗素集和宇宙集的生成,也就避免了悖论。虽然我们无法确信ZF将来不会再有悖论,但这个隐层次结构已经避免了已知的集合悖论。

ZF公理里加一个选择公理(AC),便是ZFC。这个AC如同平面几何里的第五公设一样,有了它,就可以用来非构造性地证明许多数学定理,使得现有的数学丰富精彩。没有它则按构造主义主张,只承认能被构造出来的事实才存在。这很可靠,但没有想象力的世界很单调。

选择公理(Axiom of choice)说:在集合的一组互不相交的非空子集里,存在着一个方法能够从每一个子集挑出一个元素来。这个选择公理与Zorn引理,Tukey引理和Zermelo定理互相等价,其中最有应用的是Zermelo定理:任何集合都可以良序化。

隐层次结构的另一种补救方案是Quine1937)的新基础(New Foundations)集合论(NF),它认为ZF排除过多不至于产生悖论的集合。【4Quine把无限制的抽象原理改为分层抽象原理(NF comprehension):

u(u { x | φ(x) } ? φ(u)), for all stratified formulae φ(x).

公式φ(x)是分层的(stratified formulae)指存在着一个从公式φ的变量到自然数的映射σ符合这样的关系:对于φ的子公式u v,则有σ(v) = σ(u)+1,对 u = v 则有 σ(v) = σ(u). 显然罗素悖论中公式x x是不满足分层的,这也避免了罗素悖论。

现行的几种集合论补救方案都通过限制某些集合的生成,成功地避免的悖论,付出的代价是集合不再像过去那样无所不包,也不再像过去那样简明直观。朴素的集合论就像物理和化学的原子论一样,单纯质朴。集合的悖论如同打破原子不可分的发现一样,颠覆了这个思想。现在形式公理化的描述,像用复杂的基本粒子理论来构造原来单纯的原子。集合论曾以简单直观被视为数学的基础,现在要了解这个基础超越了大多数人的数学训练。这是科学发展的宿命,研究越深入麻烦也越多。

(待续)

【参考资料】

【1】科学网博文,理解数学——逻辑(2http://blog.sciencenet.cn/blog-826653-709084.html【2】WikipediaZermelo–Fraenkel set theory http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory

【3】Wikipedia Axiom schema of replacement http://en.wikipedia.org/wiki/Axiom_schema_of_replacement#Axiom_schema_of_collection

【4】SEPQuine's New Foundations http://plato.stanford.edu/entries/quine-nf/

自我指涉(7)——语言限制了数学

数理逻辑用严谨的方式研究语法、语义,涉及语言的局限性。先略加解释要用到的概念、术语和符号。

用个体变元、个体常元、函数符号、关系符号(或称谓词符号),以及与∧、或∨、非、蕴涵→等命题连接词,加上“存在”和“一切”两种量词构成了谓词逻辑语言。语言中,用符号表的字符,按照形成规则组成的字符串叫公式。不含有自由变量的公式叫句子sentence)。如果量词“存在”和“一切”只允许对个体使用,不允许对集合或谓词等使用,叫一阶语言1】,它是描写形式公理化系统的标准语言。逻辑语言和这语言中一组句子(称为公理)组成了理论。在一阶语言里如果包含有谓词演算的所有公理、非逻辑公理和谓词演算的所有推理规则,叫一阶理论。如果一阶理论里包含有算术公理,这理论叫一阶算术

在理论S里一个句子ψ为真,指的是语义(semantic),它解释的客观事件是真的。用模型论【2】的术语说:ψ在模型M里是真的,记为M ψ. 哥德尔完备性定理说:一阶理论中的句子ψS的所有模型中都是真的,等价于ψS里成立,记为 S ψ。说句子ψ按照真理T的定义是真的,指在S中证明T<ψ>是真的。这里所说:定义为真的,可以形式逻辑推导出来,被证明,都是同一个意思,记为S φ<ψ>.谓词φ是理论里的一个公式,它用来定义某种属性,包括真理。作为定义要求它对所有的ψ,理论都能证明其真假,也就是可判定的。

一个理论S是相容的(consistent)说;ψψ(表示一对相反的命题)至少有一个不能在S里被证明。完全的(complete)的意思是,ψψ至少有一个能在S里被证明。所以在相容且完全的理论里,能够对任何命题证明其真伪,能够定义任何属性,能够判定任何命题。反过来,这些性质也都要求理论是相容且完全的才行。

ψ谎言悖论的句子,这样的句子无法判断其真伪。在(包含一阶算术的)形式语言里无法定义真理。它表示的命题或反命题,在一阶算术理论里都不能被证明。这说明一阶算术理论不可能是相容且完全的。从这就不难理解塔斯基定理和哥德尔定理的结论。计算机是实现一阶算术理论的逻辑运算工具,所以图灵停机问题也是不可判定的。这些结论的严谨数学证明,在于怎么用形式语言表达出谎言悖论的句子,这是哥德尔的主要贡献。

下面勾画出这个轮廓,更深入地剖析这些局限的本质和这几个定理间的关系。

当自我指涉的悖论撼动数学基础时,康托尔在之前,就曾经用它创造了对角线法的技巧。这个方法通过假定要证明的反命题成立,来构造出自我指涉的悖论。这从此成为一个数学的利器,证明了许多令人惊异的重要定理。受到康托尔对角线法技巧的启发,Carnap (1934)在哥德尔编码的基础上,证明了如下的“对角线引理”【3】:

设S是包含着一阶算术的理论,对任给公式φ(x)存在一个句子ψ,有 S ψφ<ψ>.

这里 S 的意思是:理论S能够证明右边的式子成立。右边式子里的意思是:句子ψ语义的真假与ψ是否具有属性φ是等价的。这里φ<ψ>是φ(<ψ>)的简写,是评判句子ψ具有φ性质的谓词表达式,<ψ>是句子ψ的哥德尔数,看作是对句子的指称。

这个引理说:对于任给一个属性,可以构造出这样一个句子ψ,用自然语言来说是“这句子具有属性φ”。当然这里的ψ是用形式语言表达的,在理论S里证明它是这个意思。前面章节里用它构造个谎言悖论ψ T <ψ> 证明了塔斯基定理。

塔斯基定理:任何包含着一阶算术的理论,也包含了T模式,则是不相容的。(Any theory extendingfirst-order arithmetic and containing schema T is inconsistent.

在一阶算术里构造一个公式φ,φ<ψ>的意思为“命题ψ不能在理论里得到证明”,则可以推出哥德尔定理。我在《哥德尔定理的证明》系列里介绍了这个经典的证明。下面介绍怎么从塔斯基定理,推出哥德尔第一不完全性定理的梗概。以此可以理解:哥德尔定理揭露出来形式公理化数学系统的局限性,其实是由语言的局限所决定的。

哥德尔第一不完全性定理(G?del's first incompleteness theorem):

假如一阶算术理论是ω-相容的(ω-consistent),则它是不完全的。

ω-相容【4】的意思是:对于任何公式φ(x),如果系统里对于每个自然数n,φ(n)都不成立,则不能推出存在着一个xφ(x)成立。用符号记为:φ(n) for all nZ,则x φ(x). 这个ω-相容性比相容性的强,可以推出后者来(J Barkley Rosser1936年证明这定理对较弱的“相容”条件也成立)。哥德尔证明了可以用形式算术语言构造出公式Dem(n, <φ>),有:

Dem(n, <φ>) 当且仅当 n是证明句子φ的形式语言符号串的哥德尔数

如果理论是ω-相容的且完全的,不难从定义中推出,xDem(x, <φ>) 等价于对给定的φ,有个具体的n 使得 Dem(n, <φ>),根据上面元语言的解释即是,对所有的句子(命题)有:

xDem(x, <φ>) φ,forall sentence φ

公式xDem(x, <φ>) 是用形式语言表达了命题φ在理论里可以得到证明的意思,也就是符合“句子φ在这理论里被证明为真”的定义。所以我们可以把它缩写成指称为真的谓词T,即有:

T<φ> φ, forall sentence φ.

这就是T模式。这证明一阶算术如果是ω-相容的和完备的,则包含了T模式。从塔斯基定理得知,它是不相容的。这个矛盾证明了哥德尔定理。上面T模式产生了矛盾的直接解读是:一阶算术理论中的有些真理,不可能在一阶算术理论中得到证明。这个矛盾产生的原因是语言的局限性:在一阶算术里,不能定义形式逻辑的推导(证明)作为判定命题真假的谓词。

停机问题是数理逻辑中可计算性理论的重要问题【5】。图灵的停机问题不可判定性定理(Undecidability of the Halting Problem)说:“不存在着图灵机能够确定停机问题。”用现代的计算机概念来说是:没有一个程序能够通过检验输入的计算机程序,来判断它是否会在有限的时间内完成计算。这个定理原来是通过用图灵机模仿对角线法来证明,下面是程序版的证明,可以让了解C编程的人,对这问题有个直观的理解。

假设上帝程序God_tell通过检查programdata,告诉我们true还是false,对应着program(data)能否在有限时间内完成运算。

bool God_tell (char* program, char* data)

{

if ( program with data will not run forever) //check program to get the answer

return true;

return false;

}

构造一个魔鬼程序Satan_tell和上帝唱反调,会完成的程序让它进入死循环,否则就完成它。

bool Satan_tell (char* program)

{

if ( God_tell (program, program) ) {

//God tell us program(program) will finish and return.

while(1); // loop forever!

return false; // can never get here!

} else

//God tell us program(program) will not stop

return true; //let’s exit

}

现在问Satan_tell (Satan_tell) 会在有限的时间内完成计算吗?相当于问图灵机会停机吗?

这是个自我指涉的问题,它的逻辑类同于Grelling悖论,在那悖论里问:“异质”是异质的吗?Satan_tell就是那个异质形容词,它与形容的对象program的表现相反,所以也陷入Grelling悖论。我们再分析一下它为什么是悖论。Satan_tell (Satan_tell)的结果不外乎两种,一是进入死循环,不能完成,一是完成计算后返回。假如能完成,从上帝程序的设计知道God_tell(Satan_tell, Satan_tell)将返回true,这样在魔鬼程序里便进入死循环不停机,与假设矛盾。假如不能停机,God_tell(Satan_tell, Satan_tell)将返回false,在魔鬼程序里则返回true,却是完成返回。又是一个矛盾。这说明上帝程序God_tell不可能存在,否则就会产生悖论。也就是说不可能有个程序能够判断给定程序的停机问题。

哥德尔不完备性定理、塔斯基不可定义性定理和图灵停机问题不可判定性定理,是上个世纪数理逻辑里最亮丽的风景线,它们紧密相连。分别表达了数学形式证明能力的局限性,形式语言表达能力的局限性和机器计算能力的局限性。它们都是用自我指涉的悖论来证明的。

为什么自我指涉悖论动摇了数学和语言理解的基础,大家因此制定规则来阻止它,我们却又可以用它来证明定理呢?

(待续)

【参考资料】

【1】WikipediaFirst-orderlogic http://en.wikipedia.org/wiki/First-order_logic

【2】科学网博文,理解数学——模型(3http://blog.sciencenet.cn/blog-826653-717208.html

【3】WikipediaDiagonallemma http://en.wikipedia.org/wiki/Diagonal_lemma

【4】Wikipedia,ω-consistenttheory http://en.wikipedia.org/wiki/%CE%A9-consistent_theory

【5】SEPTuring Machines http://plato.stanford.edu/entries/turing-machine/


    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    请遵守用户 评论公约

    类似文章
    喜欢该文的人也喜欢 更多