—（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】Wikipedia，Liar paradox http://en.wikipedia.org/wiki/Liar_paradox
【2】Wikipedia，Epimenides 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】Wikipedia，Eubulides http://en.wikipedia.org/wiki/Eubulides
【2】Wikipedia，Grelling–Nelson paradox http://en.wikipedia.org/wiki/Grelling%E2%80%93Nelson_paradox
【3】Wikipedia，Berry paradox http://en.wikipedia.org/wiki/Berry_paradox
【4】Wikipedia，Richard's paradox http://en.wikipedia.org/wiki/Richard's_paradox
自我指涉（3）——什么是真理
上一节的语义悖论反映出自然语言表达的疵瑕和能力的不足。谎言悖论和Grelling's paradox让我们思考语义的基本概念：什么样的句子是“真”的。后两例，Berry’s paradox和Richard's paradox反映了语言表达“可定义”的能力问题。它们归结为：怎么定义句子为真的。
在哲学家和逻辑学者眼中，真理是用语言表达的观念。除去把真理当着形容词的神圣光环后，当我们问到真理时，它指怎么定义语言的陈述是真的。
对这个问题，亚里士多德的回答是：真理描述了实在的世界。他在“形而上学”里的名言是：“说是者为非，或说非者为是，则为假；说是者为是，非者为非，则为真。”这个经典的答案被生活和科学界广泛地接受，成为了常识。
两千年后理性主义兴起，斯宾诺莎、莱布尼茨、黑格尔和布拉德雷等认为，真理是与整个知识体系系统无矛盾的命题和理论。这受到用演绎推理的科学家们欢迎。但如此，真理的正确性只是相对于系统的假设而言，能对任何系统都保持绝对正确的真理只剩下重言式的命题。莱布尼茨认为有两种真理：“推理的真理和事实的真理，推理的真理是必然的，而事实的真理是偶然的。事实的真理依赖于经验，而推理的真理，即逻辑真理，来自天赋的内在原则。”二十世纪初，维特根斯坦更明确地提出逻辑真理就是重言式，重言式既不能为经验所证实，同样也不能为经验所否定。它与现实经验没有任何联系的。
重言式是无论怎么解释其命题变项，逻辑上永远为真的命题公式，它在形式逻辑中扮演重要的角色。将重言式的命题变项代入具体值的句子，比如说：“小张很受女孩喜欢，因为他有女孩缘。”“要发生的终究是要发生。”“科学是不容置疑的，因为所有错误的东西都不是科学的。”这些论断在逻辑上是自给的，怎么也不能说错，日常人们也好这么说。但是所有的重言式的例子都不需要依赖于现实，没有你想了解的真相，也就是说全是废话。你把其中的主词换成其他，例如：把“科学是不容置疑的，因为所有错误的东西都不是科学的”，换成“巫术是不容置疑的，因为所有错误的东西都不是巫术。”这也是逻辑上无懈可击的真理。
基于对谎言悖论的深入思考，波兰逻辑学者阿尔弗雷德·塔斯基（Alfred Tarski，1901—1983）用严谨的逻辑来研究语义，他在1933年发表《形式化语言中的真理概念》提出语义真理论，这个理论被誉为现代逻辑在哲学上的三大成果之一。著名逻辑学家苏珊·哈克认为：“塔斯基的理论大概一直是最有影响的、受到最广泛赞同的真理理论。”
塔斯基认为句子的“真”是个语义的概念。真理论研究怎么定义指称语句是真的这个谓词。谓词（predicate）在数理逻辑中表达一个个体的性质或多个个体的关系，例如：x是红色的，x大于y，等等，它可以表达为谓词逻辑的公式P(x)和Q(x, y)，看作从个体的论域到逻辑值（T，F）的函数。
他认为谓词“是真的”之定义必须要满足实质上恰当与形式上正确的两个条件。【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】SEP，Tarski's Truth Definitions http://plato.stanford.edu/entries/tarski-truth/
无歧义严谨定义的形式语言，现在已经广泛应用在计算机程序语言和数学公理表达中。塔斯基是先驱之一。他严格定义的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谓词，用L0，L1，L2，L3，。。。，来表示层次结构里的语言，每个Ln里定义下面层次语句为真的谓词Tn，和其他层次的不是同一个词，每一个层次的语言都不是语义封闭的，以此来避免悖论。【3】【4】
在1985年Yablo发现类似于谎言悖论，但不是自我指涉的语义悖论。他构造了一个无穷系列的句子链，每个句子都说后面的句子不对。即对于每个自然数i，定义Si =“for all j>i, Sj is not true”。我们先用反证法证明没有一个句子是对的。如若不然，则有个i，Si是对的。这句子说j>i之后的Sj都不对。特别有Si+1不对。否定了这句，那么至少有个k，k>i+1，句子Sk是对的了，但这与Si的断言相矛盾。这证明了每个句子都不对，包括S0。但如果是这样，则对所有 i>0，Si都不对，S0说的便是事实，这又成了矛盾。
这个悖论没有通过一个闭合的链条指向自己，所以不是个自我指涉的悖论，发生悖论的原因是非well-founded的，即它具有无穷的包含关系。要阻止这类悖论，要求某些下降型的层次结构语言是well-founded的。
有了明确的语言层次结构，能够避免自我指涉等悖论的困境，大家高兴了几十年，但新的问题又来了。
（待续）
【参考资料】
【1】Wikipedia，Diagonal lemma http://en.wikipedia.org/wiki/Diagonal_lemma
【2】Wikipedia，Tarski's undefinability theorem http://en.wikipedia.org/wiki/Tarski%27s_undefinability_theorem
【3】 SEP，Tarski's Truth Definitions http://plato.stanford.edu/entries/tarski-truth/
【4】塔斯基的真理論 http://callmecallme.blogspot.com/2007/02/blog-post.html
塔斯基的理论成功地应用在表达数学和计算机程序的形式语言中。这些语言的功能比较简单，通过元语言与对象语言可以清晰严谨地分层描述。塔斯基是数理逻辑模型论开创者之一，用严谨的数理逻辑建立起语义真理论。他的真语句集不可定义性定理和判定性问题的研究，在数学、哲学、语言学上意义重大。他对语义悖论的层次结构解决方案，从1933年起主导了这个领域，一直到1975年Kripke发表了影响深远的著名论文“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的外延不同。在这语言的语句集合中，设有两个不相交的子集U和V，依真假分别用来放语句φ，这对应于T<φ>为真和假值的分类。在最初解释语言L0里，所有的语句都在未定状态，集合U和V都是空的，对所有语句φ，T<φ>值都是未定。然后在高一层次语言对低层语句，用三值逻辑的T模式来判定未被放入U和V语句的真理值T<φ>如下：
φ is true (false) in Lα T<φ> is true (false) in Lα+1
不难看到，在这个步骤α增加的过程中U和V里的语句不断地增加，遗留在外面的越来越少，T<φ>值不是未定的越来越少。这个单调的变化过程终究有时尽，这时T<φ>值是真和假的都已经在U和V中，遗留在外的语句，不再随着α增加能在Lα语言里判断出其真假值，也就是T的含义不再随着步骤增加而改变了。这时的步骤记为γ，谓词T就像定义在这语言中有：
φ is true (false) in Lγ T<φ> is true (false) in Lγ.
这个过程一般化称为“固定点定理（Fixed point theorem）”说：完全偏序链上的单调算子至少有一个固定点。它在现代形式真理论中扮演了中心的角色。
谎言的句子因为无法肯定它的真假值，所以不在U与V中，叫做在“真值的间隙中（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】Wikipedia，Yablo's paradox http://en.wikipedia.org/wiki/Yablo's_paradox
【3】Kripke: 真理论https://phil-commune.net/bbs/thread-635-1-1.html
经过几十年的考察，正当集合论被广为接受，成了数学的基础时，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用严谨的形式逻辑语言来书写，又因公理化的定义方式，对此不熟悉的人比较难懂。这里用熟知的集合概念，简略剖析一下ZFC【2】的公理和目的，给出一个直观的图像，让大家重拾信心知道趋避。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 formula）F都有效，所以称为公理的模式。
上面几个公理支撑起ZF集合论。有些ZF的介绍还包含着分类公理和配对公理，但它们都可以从这里推出。对已有朴素集合论知识的人，上面公理的性质都很容易理解。由这些公理导出合法的ZF集合，比朴素集合多的限制只是正规公理和替代公理。正规公理说：非空的集合，必须至少有一个元素它不包含这集合里的其他元素。这样就杜绝了循环包含（如：x∈y & y∈z & z∈x）和无限包含（如：… x3 ∈ x2 ∈ x1 ∈ x0）non-well-founded的情况。这意味着集合系统是个well-founded的阶层结构。替代公理用来从已有的集合产生新的集合。
替代公理和空集公理可以导出著名的“分类公理（Axiom schema of separation）”，它原是在Z里设计为限制“无限制的抽象原理”的核心公理。它类似于替代公理，只不过把这个映射变成是对已知集合A中元素的约束φ(x)，以此来构造（A的子）集合{ x ∈A | φ(x) } 。从而可用类似朴素集合论的方法来定义集合，只要把它局限在已有的集合里，就不必担心会发生悖论。已知的集合包括数学上常见的各种集合。这时无限制的抽象原理在ZF下改变为局限抽象原理：
u(u ∈ { x∈A | φ(x) } ? φ(u)), for all formulae φ(x) on set A.
有朴素集合论的概念的人，运用分类公理足以定义普通数学应用所需要的集合。只有对数学基础的研究，需要特定公理化集合论特征的集合时才用到替代公理及其他。
替代公理和分类公理必须从已知的集合中生成新的集合。那些初始的集合是从哪里来的？它们是类似于Kripke方案那样逐层构造的。从空集开始迭代地用并集和幂集公理，建立起越来越大的集合系统。空集是最底层，集合的幂集高一个层次，只有高层集合对低一层的集合，存有集合与元素的包含关系。无穷公理说明它们可以高到无穷，并构造了自然数集。并集和替代公理构造的集合填充了每一层，外延公理说明了集合相等的条件。正规公理阻止了低阶集合包含高阶集合的可能，让每个集合呆在这累积层次结构的某一层。这杜绝了罗素集和宇宙集的生成，也就避免了悖论。虽然我们无法确信ZF将来不会再有悖论，但这个隐层次结构已经避免了已知的集合悖论。
在ZF公理里加一个选择公理（AC），便是ZFC。这个AC如同平面几何里的第五公设一样，有了它，就可以用来非构造性地证明许多数学定理，使得现有的数学丰富精彩。没有它则按构造主义主张，只承认能被构造出来的事实才存在。这很可靠，但没有想象力的世界很单调。
选择公理（Axiom of choice）说：在集合的一组互不相交的非空子集里，存在着一个方法能够从每一个子集挑出一个元素来。这个选择公理与Zorn引理，Tukey引理和Zermelo定理互相等价，其中最有应用的是Zermelo定理：任何集合都可以良序化。
隐层次结构的另一种补救方案是Quine（1937）的新基础（New Foundations）集合论（NF），它认为ZF排除过多不至于产生悖论的集合。【4】Quine把无限制的抽象原理改为分层抽象原理（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】科学网博文，理解数学——逻辑（2）http://blog.sciencenet.cn/blog-826653-709084.html【2】Wikipedia，Zermelo–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】SEP，Quine's New Foundations http://plato.stanford.edu/entries/quine-nf/
数理逻辑用严谨的方式研究语法、语义，涉及语言的局限性。先略加解释要用到的概念、术语和符号。
用个体变元、个体常元、函数符号、关系符号（或称谓词符号），以及与∧、或∨、非、蕴涵→等命题连接词，加上“存在”和“一切”两种量词构成了谓词逻辑语言。语言中，用符号表的字符，按照形成规则组成的字符串叫公式。不含有自由变量的公式叫句子（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 n∈Z，则x φ(x). 这个ω-相容性比相容性的强，可以推出后者来（J Barkley Rosser在1936年证明这定理对较弱的“相容”条件也成立）。哥德尔证明了可以用形式算术语言构造出公式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通过检查program和data，告诉我们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】Wikipedia，First-orderlogic http://en.wikipedia.org/wiki/First-order_logic
【2】科学网博文，理解数学——模型（3）http://blog.sciencenet.cn/blog-826653-717208.html
【3】Wikipedia，Diagonallemma http://en.wikipedia.org/wiki/Diagonal_lemma
【4】Wikipedia，ω-consistenttheory http://en.wikipedia.org/wiki/%CE%A9-consistent_theory
【5】SEP，Turing Machines http://plato.stanford.edu/entries/turing-machine/
联系客服
