集合：构建数学

集合论是现代数学的基础。这句话是说，现代数学的所有成果，其实本质上都是集合论的结果，例如微积分基本定理，就可以用集合论的语言表述和证明。

但是曾经有一个悖论曾困扰众人，让这个基础似乎存在致命缺陷。这个悖论是说，如果一个集合的元素是所有不包含自身的集合全体，那么这个集合是否包含自己？通俗的版本叫理发师悖论：如果一个理发师，只为不给自己理发的人理发，那么这个理发师是否为自己理发？如果不理，那么与自己的原则符合，就该为自己理发；如果理，那么与自己的原则相悖，就不该为自己理。那么在集合论里，这个悖论该如何解决呢？

在现代数学里，数学是公理化的数学。在公理化之下，上面的悖论不成问题。

这是因为，集合的存在性也是需要证明的。不能随便将一堆元素聚集在一起，就说它是一个集合。例如空集存不存在？当然在公理化之下是存在的。再如\{\varnothing\}是不是集合？公理表明这个集合也是存在的。同样\{\{\varnothing\}\}也是集合。这样套有限多次都是集合，但是，套无穷多次就不能是我们一般考虑的集合了，这就像是正无穷我们一般不将其看作是自然数，不然会出现很多新的问题要解决。这种想法对应关键性质是：对任意的x都有x\notin x，不然集合总有自己作为元素，就会变成一个无限嵌套集合，这是不应该的。

接下来就没什么好说了。设S=\{x\mid x\notin x\}是一个集合，那么由上一段的分析所有的集合都在S中，但是开头提到的悖论说明S属于S等价于S不属于S，这说明S不是一个集合。

类比理发师悖论，就是：不存在理发师，只给不为自己理发的人理发。这当然是合理的，我们不能先假定肯定有那么一个理发师，会严格按这个原则理发。

逻辑：不完备定理

数学从公理出发，那么如何选择公理？似乎只能求助于自己的直观。平面几何的平行公设如果不按直觉选择，得到的非欧几何也没什么毛病。如果希望摆脱直觉，完全形式化，那么就是没有什么含义在其中的 文字游戏 了。例如下象棋，炮得架炮架，马不能卡马脚，理解棋子含义能更容易理解、上手象棋，但是去除这些含义，抽象成 炮隔子吃子、马直走一格再按这个方向斜走一格，也是可以下并且下得不错的。

那么，能不能充分地形式化，使得我们能够得到充分客观的、不依赖我们直觉的，并且充分多的 真理？哥德尔不完备定理表明再怎么形式化，形式系统还是有力不能及之处。

哥德尔第一不完备定理：任何自洽的形式系统，只要蕴含皮亚诺公理，就可以构造体系中不能证明、也不能证伪的命题（体系是不完备的）。

我对这个定理在当下的现状是十分失望的。这个定理吸引了数学家、逻辑学家、哲学家，还有大量不可胜数的民科，等等。一般人或者民科，不能理解这个定理的含义，就妄加揣测、夸大其哲学意义，甚至拿着错误的诠释误导他人，祸害不浅。有的人要好些，能看懂科普版证明，但就这么以为已经完全知了了定理的证明，一知半解却全然不知，也是十分遗憾之人。而稍微完整的逻辑学证明，也是难以令人满意，按理说大家的证明思路归根结底都是出自哥德尔的原始论文，那么证明表述出来应该大同小异，但我查阅诸多证明，甚至任两个证明使用的记号几乎都是不一样的。我不愿花费更多时间去特别了解某个特别的证明里其独特的符号体系，因而现在我也不能完全掌握定理的证明。本着 怀疑 的原则，哥德尔的这个定理实际上并未完全使我信服。

定理的证明关键是构造一个 自指 的公式。自指经常会出现很多奇妙现象，比如前面的理发师悖论，集合论中的罗素悖论，图灵机里的停机问题。要构造的公式大致意思就是——本公式不可证。

第一步，将所有公式、公式串，编码为自然数，这些数被称为哥德尔数。

编码的方式有很多，很容易就能做到将每个自然数（以下 数 均指自然数）和公式都唯一编码，而且可以按编码方式唯一地还原回来。至少要证明能够做到：首先每个自然数m都有哥德尔数G(m)；其次，给定一个带自由变量x的公式F(x)的哥德尔数和一个数m，可以将F(x)的哥德尔数看作是x的哥德尔数G(x)的函数，并且命题F(m)的哥德尔数可通过将F(x)的哥德尔数中所有的G(x)替换为G(m)得到——这里面的可操作性可以这么看：公式F(x)的哥德尔数可以将原公式还原，再将数字m代入自由变量进公式F(x)得到F(m)，再对其编码就得到其哥德尔数G(F(m))了。

第二步，可证性关系。

推理关系可以用哥德尔数间的二元关系来表示。如果通过推理规则D_1可以使我们从公式S_1,S_2推出公式S，那么其对应的关系R_1就是 nR_1m（其中n是公式串S_1,S_2的哥德尔数，m是加上公式S的公式串的哥德尔数）成立。设系统有推导规则D_1,D_2,\dots及对应的二元关系R_1,R_2,\dots，第二部分的证明的关键就是 可证性关系。

每一个可证的命题，它或者是公理，或者是定理。定理就是从公理经过推理规则的有限次推导后得到的命题。公式S的证明就是一连串的有特定的二元关系的数学命题，每个公式是公理或是与前一个公式有着对应推理规则的关系，推理到最后一个公式自然就是S，因而，证明可被编码为哥德尔数，并进一步定义关系Proof(x,y)，当且仅当x是公式S的一个证明的公式串的哥德尔数、y是S的哥德尔数时，关系成立。

Proof(x,y)是两个数之间的算术关系（例如，y整除x），对二元关系R和数m,n，命题mRn或\neg mRn是可证的（且其中仅有一个可证），这是因为两个数之间是可以通过 判断 来得知是否成立这一关系。具体需要归纳法，所有这些可能的关系被逐一构建；这里面的技术细节是非常长的；对形式系统在这里需要关键的假设，没有的话是构建不出这一关系的。Proof(x,y)可以有一个哥德尔数。

第三步，自指的公式。

定义一个关系q(n,G(F))，关系成立的意思是——n不是F(G(F))的证明的哥德尔数。q(n,G(F))可证，如果n编码的公式串不是命题F(G(F))的证明；\neg q(n,G(F))可证，如果是其证明。同样，二者可证且仅可证其一。如果成立：\forall x,q(x,G(F))，那么就是说命题F(G(F))没有证明。

定义公式P(x)=\forall x,q(x,y)，那么，P是有一个哥德尔数G(P)的。

最后，考虑命题P(G(P))=\forall x,q(x,G(P))，对应着 P(G(P))没有证明，而这个命题本身就是P(G(P))，这就出现了我们希望的自指现象。这个命题及否定都是不可证的。如果可证，意思就是存在x使其对应的公式是P(G(P))的证明，但是命题本身的意思是任意x，都不是证明；这是个矛盾，矛盾说明 P(G(P))不可证。（现在对任意的x，假定\neg q(x,G(P))可证，那么这表明x对应的公式是P(G(P))的证明，但已经知道它不可证，矛盾说明x不可能使\neg q(x,G(P))可证，但关系q及其否定有且仅有一个可证，故q(x,G(P))可证，于是得到\forall n,q(n,G(P))。）如果否定可证，即\neg P(G(P))=\exists x,\neg q(x,G(P))可证，那么同时成立着：\forall n,q(n,G(P))可证以及\exists x,\neg q(x,G(P))可证，这是个矛盾。故\neg P(G(P))也不可证。

注意：构造出的公式上面只是说在形式上，不可证且否定不可证，没有说其 真假。什么叫 真命题？什么又叫 假命题？一般来说，如果能从公理证出来，那么它就是真命题，如果能证明否定，那它就是假命题。定理说明存在 不知真假 的公式，但如果回顾这个公式的意思——本公式没有证明，我们会发现这确实又是对的，它确实不可证。因而我们会说：我们构造出了一个公理不能判定真假的真命题。在里面似乎有所矛盾，真假是依据证明确定，那怎么就说是真命题了呢？

其实这说的 真命题，是说语义上的真命题，而证明确定的，是形式系统中形式上的真假。这里面的一个关键之处就是哥德尔把含义为真和真值为真给区别开来了，从而避免了悖论的产生。在形式系统里，这些命题公式是没有含义的，真假就是形式证明确定的真值；但我们理解的时候，给它赋予了含义，没有把它单纯地当作一个形式系统，赋予了它在形式之外更强的结构。这个赋予含义的结构，就是我们的经验结构。拿前面的象棋类比来说，就是在棋子中赋予了棋子的含义，比如仕在九宫之中斜走，意为护卫将帅的近侍，相则不能过河；但是下揭棋则没有九宫、河内的限制了，因为去除了含义，只保留了原来的走法。我们从经验上赋予了形式系统更强的结构——标准自然数结构，于是有了原命题含义真这一论断。

这说明大家还是习惯从经验上的结构考虑的，形式化毕竟还是略为抽象。最后留一个小问题：是不是数学本质上只能建立在经验的基础上呢？