逻辑

数学是一门诡辩的艺术。而逻辑，是一个哲学概念。逻辑似乎有很多种，人们在“什么样的推导才能保证结论是绝对真理？”这个问题上争论不休。而数学只有一个，那就是千百年流传下来的，最使人信服的诡辩之术的集大成。

当然我们也会心存不安。诡辩这东西，终究让人心里没底。如果有一件事明明是对的而我们没法用诡辩把它推导出来，这不是很失败吗？反之如果每一件事无论对错我们都可以用诡辩把它推导出来，这不是很无赖吗？所以说两头都不讨好。这种时候我们通常需要寻找一个终极关怀。这东西虽说往往会在哲学或者宗教里面找到，但是如果你中毒很深，就会发现除了数学这个世界上已经没有别的东西能让你信服了。所以到头来还是非数学不可，于是我们有了数理逻辑。

数理逻辑

就象所有的数学分支一样，首先你要有一堆符号。这些符号连在一起组成一些式子，你要规定什么是对象式，什么是逻辑式。这样你就有了一个形式体系。对象式相当于这个形式体系里考察的对象，逻辑式相当于形式体系里的命题。

然后你要有一个意义论。也就是说对于形式体系里的对象式，我们如何把它理解成实际意义上的对象；对于逻辑式，如何把它理解成一个命题。把我们的世界转化成一堆杂乱无章的符号实在是太容易了，反过来要从一堆杂乱无章的符号里看出我们的世界，则很难。但在这里一般没有什么问题，因为我们通常按照我们想要表达的意思来规定符号，特别是规定符号的和决定意义论的通常都是一个人。

好了现在你有了一个充满符号的形式体系，你也可以理解这些符号的意义了。接下来你要选出一些逻辑式作为公理，并且规定一些推论的法则，这样才可以在形式体系里做出证明。

现在问题来了：我们在形式体系里可以证明的逻辑式，它所对应的命题是否都是真的？反之如果有一个逻辑式，它对应的命题是真的，我们能否在形式体系里做出一个对此逻辑式的证明？前一个问题称为妥当性，后一个问题称为完备性。

让事情更为复杂的是，仅仅对于非常简单的形式体系（比如命题逻辑和一阶逻辑），我们才有完善的意义论。所谓完善的意义论，意思是说我们总能判断一个逻辑式所对应的命题是真的还是假的。是啊，我们怎么才能知道一件事是真的还是假的呢？上帝大概知道[tex]$\pi$[/tex]的十进小数展开中是否有无数个7，可是我们不知道。或者我们得相信数学推理？认为数学里面证明出来的命题都是真的？可是你难道不是正要把数学转化成一个形式体系，然后讨论它的妥当性和完备性吗？这你要是都这么相信了，还讨论个什么劲？这么复杂的问题还是让哲学家去解决吧。

总之虽然我们并没有完善的意义论，但我们总还知道那么一点。或者说自以为知道那么一点。比如，如果A是真的，B也是真的，那么“A并且B”是真的。再比如，一个命题要么是真的要么是假的。还比如，如果我们不论举出哪个数n，P(n)都是真的，那么“对于任意的x都有P(x)”这个命题应该是真的。诸如此类。

表现

现在假设你的形式体系里包含了自然数。于是我们觉得这样一个体系已经足够大，可以“表现”一些实际上的事物了。也就是说，虽然你最开始已经有了意义论，你能够说出每个对象式对应的是什么样的对象，每个逻辑式对应的是什么样的命题；但是现在我们开始考虑给这些符号赋予另外一种意义，或者说不同层面上的意义，或者说随你怎么称呼。具体说来，如果有一个自然数的函数f(x)和一个形式体系里的对象式f(x)，我们说f(x)是f(x)的表现，当且仅当对于任意自然数a，f(a)=n的时候我们可以在形式体系里证明f(a)=n（a和n是形式体系里表示自然数a和n的对象式）。这个形式体系里的对象式f(x)所表示的意义可能是和f(x)的意义完全不同的；比如说你（用自然语言）定义的f(x)可能是一个非常奇怪的函数，以至于在形式体系里是没办法直接这么定义的；但是你可能想了各种办法在形式体系里定义了一个虽然直接从字面上看起来没有什么关系，但正好满足上面的条件的对象式f(x)。只要是这样，我们就说在形式体系里找到了一个f(x)的表现。同样的，如果有一个关于自然数的关系R(x1,x2,…)和一个形式体系里的逻辑式R(x1,x2,…)，我们说R(x1,x2,…)是R(x1,x2,…)的表现，当且仅当对于任意的自然数a1,a2,…，R(a1,a2,…)成立时我们可以在形式体系里证明R(a1,a2,…)，R(a1,a2,…)不成立时我们可以在形式体系里证明R(a1,a2,…)的否定。

事情于是越发复杂了。不过你很快就会习惯的。真的，如果没有这些绕来绕去的概念，我们还怎么诡辩？

哥德尔数

哥德尔提出了一种方法，把形式体系里的所有对象式、逻辑式和证明都对应了一个不同的自然数。反正到头来这些东西都只不过是一串符号而已，只要适当地编码一下，对应一个自然数总是可能的。这个对应的自然数叫做哥德尔数。对于形式体系里的逻辑式A，把它的哥德尔数记为[A]，形式体系里对应自然数[A]的对象式记为[A]。

对角线论法，自指称命题

定义自然数的函数SUB(x)：如果a是形式体系里某个逻辑式A(y)（y是自由变量）的哥德尔数，那么SUB(a)返回A(a)的哥德尔数；否则返回0。SUB(x)是可以在形式体系里表现的。把这表现记为SUB(x)。

对于形式体系里任意的逻辑式F(x)，F(SUB(x))也是逻辑式；把这逻辑式的哥德尔数记为n，那么SUB(n)就是F(SUB(n))的哥德尔数。所以如果把F(SUB(n))记做A，那么A就是F([A])。
于是对于任意的逻辑式F(x)，我们都有了一个自指称命题：A[tex]$\leftrightarrow$[/tex]F([A])。

说谎者悖论，塔斯基定理

塔斯基定理说，如果我们的形式体系是妥当的、完备的、无矛盾的，那我们就不可能把意义论表现到形式体系里面去（所以我们无法在形式体系里证明它是妥当的、完备的）。也就是说，假设我们这样定义自然数的单项关系T(x)：对于形式体系里的任意逻辑式A，如果A对应的命题是真的，那么T([A])成立；否则不成立。如果这个单项关系T(x)在形式体系里有一个表现T(x)，而形式体系又是妥当的和完备的，那就是说有一个逻辑式T(x)，对于任意的逻辑式A，都可以在形式体系内证明A[tex]$\leftrightarrow$[/tex]T([A])。可是我们可以对“T(x)的否定”应用对角线论法，于是就存在某个逻辑式B，我们可以在形式体系内证明B[tex]$\leftrightarrow$[/tex]“T([B])的否定”。这说明我们的形式体系是矛盾的。

这其实就是所谓的说谎者悖论：“这个命题是假的。”如果我们承认这整个是一个命题，那就会得出矛盾；为了避免矛盾，只有寄希望于我们在形式体系里无法构造出对应于这个的逻辑式，也就是说形式体系里没有这样的命题。可是根据对角线论法，是允许在形式体系里构造自指称命题的（如果形式体系足够大到包含自然数的话），所以我们的退路就只剩下一个：你无法在形式体系里定义真假。

哥德尔不完备性定理

定义这样一个自然数的二项关系：B(x,y)成立当且仅当x是形式体系里某个逻辑式的哥德尔数，而y是这个逻辑式的某个证明的哥德尔数。这个二项关系是可以在形式体系里表现的。把这表现记为B(x,y)。

很自然的我们也可以定义这样一个单项关系：Bew(x)成立当且仅当x是形式体系里某个可被证明的逻辑式的哥德尔数。从意义上来说，Bew(x)相当于“存在y使得B(x,y)成立”。基于这一点我们在形式体系里定义一个对应的逻辑式Bew(x)[tex]$\leftrightarrow\exists$[/tex]yB(x,y)。然而，这样定义的Bew(x)却不是Bew(x)的表现！这正是哥德尔第一不完备性定理的本质上的内容。

事实上，如果逻辑式A可以在形式体系里被证明，那么Bew([A])也可以在形式体系里被证明（这是因为B(x,y)是B(x,y)的表现）。可是如果逻辑式A不能在形式体系里被证明，我们是否能在形式体系里证明Bew([A])的否定呢？如果我们的形式体系是无矛盾的，那么答案就是不一定。因为根据对角线论法，存在一个逻辑式U，我们可以在形式体系里证明U[tex]$\leftrightarrow$[/tex]“Bew([U])的否定”。首先U无法在形式体系里被证明，因为如果U可以被证明的话，那么Bew([U])也可以被证明了，可是U[tex]$\leftrightarrow$[/tex]“Bew([U])的否定”于是形式体系是矛盾的。然后既然U无法在形式体系里被证明而U就是“Bew([U])的否定”，那么当然Bew([U])的否定是无法被证明的。所以Bew(x)并不是Bew(x)的表现。

如果我们对任一自然数n考虑B([U],n)这个命题，它显然是不成立的，因为我们无法在形式体系里证明U。而B(x,y)是B(x,y)的表现，所以我们可以在形式体系里证明B([U],n)的否定。也就是说，我们可以对任一自然数n证明B([U],n)的否定，但是却无法证明“让B([U],n)成立的n是不存在的”，因为后者正是Bew([U])的否定。在这个意义上说，我们的形式体系是不完备的。

哥德尔第一不完备性定理的另一个版本是我们总可以找到一个逻辑式，在形式体系里既不能证明它也不能证明它的否定。在哥德尔的原论文中假定了一个更强的条件“形式体系是[tex]$\omega$[/tex]-无矛盾的”，不过事实上只要假设无矛盾性就可以了。这个既不能证明它也不能证明它的否定的命题和上面的U类似地构造，只不过把Bew(x)的定义稍做改动。

这个“另一个版本”虽然分外有名，但给我的感觉其实并不如之前的叙述来得震撼。“我们总能提出你无法判定的命题”，这事听起来好象很平常。选择公理是无法判定的。连续统假设也是。解丢番图方程组的一般算法是不存在的。如果不假设选择公理，你无法知道是否任意实数集都是勒贝格可测的。这些都是数理逻辑的伟大定理，在我看来比什么“我们总能提出你无法判定的命题”要伟大多了。（就像埃尔米特证明e是超越数，就比刘维尔给出一个构造超越数的一般方法要伟大多了）

但是如果说有一个命题A(x)，你可以证明A(0),A(1),A(2),…的否定，但是却无法证明“让A(x)成立的自然数x是不存在的”；这着实让人心中不安。请注意出现这种情况并不是因为你的形式体系不够强悍，推论规则太弱了；相反是因为形式体系太强了——强到你可以使用自然数，特别是数学归纳法。也就是说你可以使用归纳法，也甚至可能再加一些更强的推论方式，但还是会有一个命题A(x)，你知道A(0),A(1),A(2),…都不成立，却归纳不出“让A(x)成立的自然数x是不存在的”。

而且，以上的存在证明都是构造性的：也就是说只要你事先规定好了一个形式体系，这个让人不安的A(x)就是可以实实在在地写出来的。但是这怎么可能呢？摆在你面前的是一个实实在在的命题，你知道你可以证明出A(0),A(1),A(2),…的否定，那“让A(x)成立的自然数x是不存在的”这怎么会证不出来呢？难道我们不可以把“你知道”的那一部分内容在形式体系里表达出来吗？也就是说难道我们不可以在形式体系里，仿照上面的步骤，证明出“我们总可以证明A(0),A(1),A(2),…的否定”吗？既然上面我们用的都是很普通的数学推理，这对于任何一个适当的形式体系来讲应该都是可能的——但是除了一点：我们再来看看前面的论证

U无法在形式体系里被证明，因为如果
U可以被证明的话，那么Bew([U])也可以被证明了，
可是U[tex]$\leftrightarrow$[/tex]“Bew([U])的否定”于是形式体系是矛盾的。

确实，基本上所有的部分都可以想办法在形式体系里对应出来：我们已经对“A可以被证明”这话在形式体系里给出了一个对应Bew([A])，虽然这并不是表现，但仍然有某种对应性（比如如果逻辑式A可以在形式体系里被证明，那么Bew([A])也可以在形式体系里被证明）。同样的我们可以对“形式体系是无矛盾的”这话在形式体系里给出一个对应的逻辑式Consist，这样上面的论证都可以在形式体系里面写出来了——但是论证里用到了一个已知条件：我们的形式体系是无矛盾的。有了这个条件才可以应用反证法，证明“U无法被证明”。而如果在形式体系里证明了“U无法被证明”，我们确实是可以证明“对于任意的自然数n，B([U],n)不成立”的，但哥德尔第一不完备性定理说这是不可能的！于是得出结论：我们无法在形式体系里应用“我们的形式体系是无矛盾的”这个条件，即Consist在形式体系里是无法被证明的。这大致上就是很有讽刺意味的哥德尔第二不完备性定理：如果形式体系是无矛盾的，那么它的无矛盾性就是无法在形式体系里被证明的。

于是，一个形式体系的无矛盾性是本质上超越这个形式体系的（无矛盾性和妥当性、完备性不同，是不依赖于意义论，只依赖于形式体系本身的；如此哥德尔第二不完备性定理就比塔斯基定理要深刻的多了）。就像一个集合的幂集合是在本质上比原来的集合要大的。

所以说，即使你在形式体系里加了一条意味着“这个体系是无矛盾的”的一个公理，当你把这公理加进去的时候这个体系已经不是原来的体系了，于是这个新体系的无矛盾性又成了一个未知数。你当然可以再加，于是又是一个新的体系，于是又再加，再加……如此循环往复直到万劫不复。

可是这一切都是对于形式体系而言。我总觉得，为什么我们就不能假定说，我们的这套逻辑，我说的就是这套逻辑，是无矛盾的呢？这样一来当然我们的逻辑体系就是无矛盾的了，哥德尔不完备性定理就见鬼去了——当然这样的话我们的逻辑就不是一个形式体系（就像所有集合的全体不是一个集合），也就是说我们无法把所有公理都形式化地表达出来。可是它不是一个形式体系难道我们就不能理解吗？很好理解嘛，说的就是我们的逻辑体系是无矛盾的啊。而且在我看来事实上我们或多或少一直就是按照这个方针来贯彻的。根本就没有什么事先规定好的公理。你看罗素悖论出来的时候我们不是慌慌张张去修改集合论吗？事情总是见机而行，该变通的时候就变通。数学是一门诡辩的艺术，而诡辩的精髓并不在逻辑——是的，逻辑没什么了不起，数学的神奇之处并不是扎根于这里。