在集合论和语言研究中发现了自我指涉悖论时，数学家们如临大敌，制定规则来阻止它。为什么却可以在定理证明中使用它？

先考察对比罗素悖论和康托尔定理。康托尔用自我指涉的悖论证明了集合论基石性的定理。罗素模仿康托尔定理证明的技巧，用几乎相同的逻辑，构造出罗素悖论，动摇了数学的基础。关于罗素悖论和康托尔定理的具体证明可参考【1】。

在罗素悖论里，定义罗素集R为所有不包含自己作为元素的集合：R = { x | x ∉ X }，当问起R是不是属于这个集合时，产生了悖论。推理如下：如果R ∈ R，即R是集合R的元素，依定义有R ∉R；反之如果R ∉ R，按集合R的定义，R是它的元素，即R ∈ R。无论哪一种情况都是矛盾。这里的逻辑无懈可击，唯一薄弱环节是可否有这集合。这集合是按“无限制的抽象原理”来构造的。即给定一个属性，则可以定义一个集合包含着具有这种属性的所有个体。这是朴素集合论默许的。悖论发生且无可解脱时，只能质疑这个原理靠不住。而后的各种公理化集合论的修正方案都是通过限制集合的构造，来避免产生罗素和其他悖论。

康托尔定理说：集合的势小于它幂集的势。他用了反证法。假如幂集P(S)的势不大于集合S的势，则存在着从S到P(S)的一个满映射f，P(S)的每一个元素，即S中的子集都有一个S中的元素通过f和它对应。将所有f映射象不包括自己的元素，来构造S的一个子集C = { x ∈ S | x ∉ f(x) }。因为C是S的子集，则有一个S中的元素a，f(a)=C。然后问，a是不是属于C？走罗素悖论相同的逻辑辩驳，就可以发现这是个悖论。在这个悖论中，辩驳的逻辑同样无懈可击。这里子集C的定义，按照现代罗素类型理论、ZF集合论等公理化理论都是合法的。映射f是由势的定义而来的。造成矛盾局面唯一可指责的，就只有是最初的假设。悖论否定了这假设，则证明了定理。

这两个例子用了同样的自我指涉悖论，为了走出逻辑困境，在这逻辑链中，各自否定了最薄弱的环节。为什么我们不禁止一切自我指涉呢？自我指涉是悖论中产生逻辑矛盾的模式。它在大多数情况下并无不妥，几千年来深入到自然语言和数学中，扮演着重要的角色，已经不可能排除它了。后面我们将看到自我指涉在算术里是不可避免的。在百多年前数学危机的大争论中，大多数数学家不愿放弃排中律带来的丰硕成果，只能否定了更严谨直观和保守的有限主义。人类道德标准，国家法律都是理想与现实妥协的结果，数学的规则原理也是如此。

因此把要证明定理的反命题，作为假设构造出一个悖论，当其他环节都无懈可击时，假设就是最薄弱的一环，否定它就证明了定理。如果是从理论系统里不加假设地推出悖论来，当其他环节都无懈可击时，人们就该反思，是否可以改变某个不言而喻的信念，来消除这个悖论。公理化集合论和塔斯基分层结构，在自己的论域里舍弃了语言的任意描述，来回避它。有些书刊误认为自我指涉是不允许的，这是简单化的错误理解。

1994年，Perlis等用元语言描写了满足自我指涉悖论的“围笼模式（Inclosure Schema）”【2】：

对于谓词P和Q（用来描述某种性质的函数）和局部函数δ（从定义域中选出部分元素来）满足下列条件的语句都构成自我指涉的悖论：

1.  w ={x | P(x)} 存在且 Q(w) 成立；

2.  如果y 是 w 的子集而且Q(y) 也成立，有δ(y) ∉ y，和δ(y) ∈ w.

满足这些条件就会形成悖论，这并不难证明。y是w的子集就有δ(w) ∉ w，和δ(w) ∈ w推出了矛盾。

绝大多数自我指涉的悖论都符合这个模式，但这仅仅说明这样的逻辑结构会产生悖论。在这里P，Q，δ的设计是构成自我指涉的逻辑链条的环节，只有指出在哪一个环节出错了，违反了什么原则，才是真正找到错误的原因，才能破解悖论。

Richard悖论【3】是直接模仿康托尔的对角线法证明。下面我们分析，为什么康托尔可以用来证明实数不可数定理，Richard却出错了？

Richard悖论说：考虑用有限个字的短语描述来定义一个实数，例如“根号2”，“正弦45度”，“个位是3，十位是1的两位数”等等。将所有这类的描述按照字典的顺序，排列成一个表，称为Richard表。然后利用这个表来定义一个实数。

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

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

1891年康托尔证明实数不可数是这样的，他写的更细致些。

假如实数是可数的，在（0，1）区间任何一个实数r对应着一个自然数n，记为r_n，按这顺序排成一个序列，表中第n个实数就可以表示为r_n=0.a_n1a_n2a_n3…，这里a_nk是序列中实数r_n的第k位小数的数字。现在定义一个新的实数b=0.b₁b₂b₃…，它是这样构造的，从第一位小数k=1开始，对照着这个表逐个给b_k赋值，如果a_kk=2，则b_k=1，否则令b_k=2。因为b的每一位小数都和顺序表中任何一个实数的那位小数都不一样，这个b是不可能在这表中。但顺序表假定是列出了所有（0，1）区间的实数。这个矛盾证明了实数是不可数的。

Richard构造这个实数的方法与康托尔的证明里完全一样，他们都是用这实数所属的表来构造一个实数，然后因这构造的方法证明了这实数不属于这张表。这是自我指涉！就像Grelling悖论里定义“异质”这个词的含义，然后问：“‘异质’是异质的吗？”这样做是合法的吗？当然，没有一条数学的规则禁止这一点。在这对角线法构造里，将这些实数列表根据的是可数的定义，构造新的实数是逐位直接赋值的，没有任何含糊之处，推出这个新的实数不在表中逻辑也很干净。构造这实数时并没有假定这实数是在表中，但是这个表设为包含了（0，1）区间的所有实数，所以这个表必须包含这个新构造的实数，这就发生矛盾了。在康托尔的定理证明里，唯一的薄弱环节是实数可数的假设，否定了它就证明了定理。

那Richard悖论问题出在哪里？1963年Tucker认为这同实数不可数证明一样，Richard表是不可数的。其实这没那么简单。因为这个表是由有限个字的短语构成，所有可能的字符是有限的，所有有限个字的短语是个可数集，所以这个解释不成立。1966年I. J. Good在牛津大学Mind期刊上【4】，解释Richard悖论的错在构造这个实数时，它走过Richard表中每一个短语来确定对应的实数，不可能通过有限步来实现，所以也不可能通过有限个字来正确地描述。这里的理由与Church和Turing认为判定性问题是无解的逻辑一样。【5】

为什么在数学里不能避免自我指涉？这是自然数的本质决定的。自然数是一个序数，这可以作为一个ID，任何的公式都可以通过编码得到一个自然数，唯一代表着自己。它也可以通过解码这个ID得到它所代表的公式。当把公式自身的编码所得的自然数ID，作为具体数值代入这个以自然数为变量的公式时，合适的公式就可以通过这个ID谈论自己，这就构成了自我指涉。只需要在理论中包含有算术的公理，就可以做到哥德尔编码和解码。所以在一阶算术的理论，对于任何一个属性都可以构造出一个自我指涉的句子，说明自己具有这种属性。这个“对角线引理”的证明细节看【6】。

为什么集合论和形式语言要规避自我指涉？因为朴素集合的定义和自然语言真之定义，产生了自我指涉的悖论。我们虽然不能阻止在数学和自然语言中使用它，但却可以通过限制集合和形式语言的定义在某些范围内规避它，以保持理论的相容性。

悖论破坏了原来简洁和谐系统朦胧的美，代之以各种繁杂的修补方案，公理化集合论就有很多种【7】。基于不同的方案，虽然维护现实系统的稳定和成果是一致的，但对于某些问题的答案可能不同。例如谎言悖论语句，它在塔斯基方案里是违反了语法，在Kripke方案里是合法的有“未定”值，在自然语言里构成悖论，却找不到它违反了什么规则。

科学是一个不断发展完善的过程。课堂里学习的知识，都是成为主流的思想和规则，它们是经过千百年的争执，最后胜出的观点。许多问题在这思想和规则下都有了明确的标准答案。人们只需要跟从主流思想，遵守规则，就能做出学术界认可的研究成果。离经叛道就像造反一样，你必须有足够实力和理由颠覆世界征服人心，否则就是找死。自我指涉悖论引起的危机和修补不到百年。时间还未抚平这些的波折，也许还没有找到更为完美的方案。这个系列文章，带你窥视自我指涉悖论带来曾经的混乱，和修补规则制定的过程。希望你学习到这些知识时，不仅知道“是什么”，还能知道“为什么”。

知识和思考不是一回事，知识是内功和资产，思考是能力和野心，书本知识让你站在前人的肩上，深思会打开你的眼界，能想象才能够飞翔。

（完）

【参考资料】

1. 科学网博文，自我指涉（2）——语义悖论http://blog.sciencenet.cn/blog-826653-741618.html

2. SEP，Self-Referencehttp://plato.stanford.edu/entries/self-reference/

3. Wikipedia，Richard'sparadox http://en.wikipedia.org/wiki/Richard's_paradox

4. Good, I. J. (1966). "ANote on Richard's Paradox". Mind 75 (299): 431 http://mind.oxfordjournals.org/content/LXXV/299/431.extract

5. Wikipedia，Entscheidungsproblemhttp://en.wikipedia.org/wiki/Entscheidungsproblem

6. Proof Wiki，DiagonalLemma http://www.proofwiki.org/wiki/Diagonal_Lemma

7. SEP,Alternative Axiomatic Set Theory http://plato.stanford.edu/entries/settheory-alternative/

【后记 】 贴于评论6，点击1605，2013-12-9

评论中有人提问一阶理论的完备性问题，许多文章和我前面的回复都说的比较含糊，容易被误解，借此澄清一下。

哥德尔的完备性定理和不完备性定理，虽然英文用的是completeness theorem 和incompleteness theorem，其实谈的并不是完全相反的性质。完备性定理说的是形式推理和直觉真理间的关系（一阶理论中任何语句能够被形式证明，等价于它在所有模型中都成立），其中的“完备”指“普遍有效的公式”可以被形式证明。不完备性定理说的是推理能力的局限性（在一阶算术中，存在着不能被形式证其真或证其非的语句），其中的“不完备”是对正反命题至少其一能够被形式证明能力的否定。这两者有联系但不是直接相反，所以有时把后者译为“不完全”以示区别。

哥德尔完备性定理并不是说一阶理论都是相容且完全的，只是有这种可能性。较简单的理论，如包含代数中的群论一阶理论是相容且完全的，包含算术的一阶理论则不是相容且完全的。

无论哥德尔的完备性定理和不完备性定理都用了反证法。