也谈数理逻辑

Some Thoughts on Mathematical Logic

Posted by Tori on January 13, 2017

考完期末,第一篇想写的就是关于数理逻辑。

数理逻辑就课程内容而言,绝对是一门好课,它生动地展现了人们在严谨逻辑论证的追求上孜孜不倦的探索过程。从这一点上说,数理逻辑和其他数学课似乎没有什么区别,无非都是强调任何一个定理都需要严谨的证明,但是数理逻辑的奥秘在于,它试图将人类主观的推理思维过程客观化,并建立起主观推理与客观证明之间的联系,这一点是很奇妙的。

大概还是应该从为什么要研究数理逻辑开始说起。想必大家都听说过罗素悖论(Russell’s paradox)吧——如果一个村子里只有一个理发师,且这个理发师宣称他只给那些不给自己理发的人理发,那么这个理发师该不该给自己理发?罗素悖论还可以用集合的语言来表述,即:如果集合 A 以那些不以自身为元素的集合为元素,那么 A 是否属于自身?

这般悖论的产生直接导致了第三次数学危机——集合这一现代数学的基本概念直接发生了动摇,而这一数学基础的危机使得数学家们感到惶恐。

数理逻辑的基本目标,就是要研究这样的数学基础问题,而研究数学基础问题的第一步,就在于将自然语言实现严谨的公理化。然而自然语言又实在是太扑朔迷离,难以避免的歧义性甚至对我们关于同一命题的交流都会产生阻碍,因而数学家们转向创造一套形式语言,就像用字母代替数进行运算那样,我们也可以用形式语言来代替自然语言进行推理,进而通过对形式语言的公理化来达到自然语言的公理化目标。

而这公理化目标的具体内容,我想希尔伯特规划应当是描述的最详细不过。希尔伯特规划(Hilbert’s program)希望所有的数学命题都能够用同一种形式语言来表达,而这种形式语言可以利用指定的规则来进行操作(即公理化)。且进一步地,希尔伯特希望这样的形式语言本身具有良好的性质——至少得没有自相矛盾(一致性),能保证推出所有自然语句中的真理(完全性),且最好能通过一种特定的算法来判断任一给定数学命题的真假性(可判定性)。那么这样一来,所有的数学命题都可以被机械地严格判定,整个数学的基础问题理论上就可以称得上是完美解决了。

但不幸的是,1931年哥德尔不完全性定理(Godel’s incompleteness theorem)的发表宣告了希尔伯特规划的破灭。哥德尔利用类似罗素悖论中出现的自指现象(即本身内容涉及到自己),在自然数系统中构造了一个形式语言推导不出的自然真理。严格的表述为,如果一个逻辑系统中蕴含了朴素算术的存在,且这个逻辑系统一致(即不存在矛盾),那么它必然是不完全的(即存在形式语言不能推导出的自然真理)。哥德尔这一定理就直接指明了,只要有自然数的存在,形式语言就不可能完全描述自然语言。这多少还是令人有些沮丧的结果。

那罗素悖论那边又怎么样了呢?集合的概念究竟如何定义?Zermelo 和 Fraenkel 对此提出了著名的 ZF 公理集合论系统,通过在公理中对集合加以限制,将罗素悖论中包含自身的集合A排除在了“集合”这一定义之外,从而从某种意义上解决了罗素悖论。然而并非 ZF 公理系统就完美无缺了——我们尚不知道 ZF 公理系统的一致性。而事实上,ZF 的一致性代表着这套公理对集合概念刻画的精确性,且 ZF 的一致性与算术系统的一致性密切相关。稍微接触过一点 ZF 集合论的同学都会知道,我们可以用 ZF 的集合论系统来定义自然数,因而我们如果得到了 ZF 的一致性,也就自然得到了算术系统的一致性,进而也就确认了算术系统的不完全性。写到这里还是想叹一口气呢。

但以上的这些内容并不是一蹴而就的,数理逻辑课程就要求我们从最简单的命题逻辑出发,一步一步地完善对逻辑系统的认识,去接近上面所描述的这些公理系统,进而拥有对数理逻辑这门学科的宏观视角与整体把握。从命题逻辑,到形式命题逻辑,再由于表达能力不足扩充到一阶逻辑,发展出形式一阶逻辑,再在一阶逻辑的基础上加入不同的公理,如皮亚诺算术公理、集合论公理、群论公理等,扩充得到各式各样的数学系统,我们在这门课中完整地实现了数学系统从底层起一步一步的构建过程。

本来想关于数理逻辑本身写一篇长文的,以表达这门课程对我思想影响的深远,但我期末考完觉得还是更想吐槽一下关于该课程的考试形式。下面是2016年数理逻辑的期末考试试题

logic-final-2016

只要上过该课程的都知道这些内容都是课件上有的逻辑演算和定理证明,所以题目也没什么可说的。但我觉得这样的数理逻辑考试完全泯灭了数理逻辑这门学科本身的开放性和灵活性。要是我来出题,我至少会出一道5分的思考题(李伟固附体)。下面是我这学期思考的一些关于数理逻辑的问题,有一些是可以给出严谨论证的,而更多的则是开放的哲♂学问题。

Problem List:

  • 悖论是否一定需要涉及自指?若是,谈谈你的观点,若否,请举出一个例子并作简要解释。
  • 为什么在命题逻辑的基础上我们需要一阶逻辑?在这种原因的驱使下,两套逻辑系统出现了怎样的差别和分歧?
  • 若在命题逻辑系统 L 中引入一已知的矛盾式 F,试说明 Peirce 定律 \(((A\to B)\to A)\to A\) 可以代替 L 中的公理 (L3),并由此说明 L 只需要一个连接符来表达,即隐含。
  • 你认为一阶逻辑中可数无穷多个一阶公式能否满足表达所有自然语言语句的需要?
  • 你认为公理系统 L 和 K 中的几条公理是如何总结出来的?这几条公理的合理性在什么地方?
  • 一阶逻辑演算系统 K 中的公理 (K6) 似乎显得很诡异,使用频率也很低,是否和欧几里得第五公设一样存在可修改的可能性?
  • 你认为一阶语言的表达能力是否已经足够?若是,谈谈理由,若否,提出一些你认为可以进一步扩展一阶语言表达能力的手段。
  • 如何将下面这个推理用形式语言表达?推理:因为 2 < 3,所以 3 > 2。
  • 在一阶逻辑中,一阶公式 \(A\) 逻辑有效当且仅当 \((\forall x_i)A\) 逻辑有效,这是否意味着自由变元和约束变元之间不存在任何差别?结合 Tarski 的语义学谈谈你的理解。
  • 试对“任何一阶公式都与其斯科伦式矛盾等价”这一事实给予一个直观的解释。
  • 证明对一个一致的一阶系统 S,其任意两个模型都是初等等价的,即它们在任一给定公式上的真值均相同,但两个模型本身可能并不同构。
  • 如何解释斯科伦悖论,即 ZF 公理集合论系统如果是一致的,则必存在可数模型(Lowenheim-Skolem 定理),而这与 ZF 蕴含了不可数集的存在相矛盾?
  • 如何看待形式算术系统 N 中的公理 (N7) 与一般数学归纳法之间的区别和联系?
  • 试从哥德尔不完全性定理出发,说明形式算术系统 N 存在非标准模型(标准模型即指自然数集)。
  • 能否得到一个形式算术系统 N 的一致完全扩充?若能,给出一种构造方法,若不能,谈谈理由。
  • 试在不完全性定理的 Henkin 证法中,通过修改关系 W 和相应的一阶公式,在将 N 满足的条件从 \(\omega\)-一致弱化为一致的情况下,证明相应的定理结论(假定你给出的关系都是递归关系)。
  • 简述利用哥德尔不完全性定理证明第二不完全性定理的思路,即证明形式算术系统 N 不能在其内部证明自身的一致性。
  • 你认为 Hilbert 规划的失败是否是必然的?应当如何看待形式语言和自然语言之间的关系?
  • ……

数理逻辑还有很多深入的发展方向。在数学方面,有证明论、递归论、模型论、公理集合论等,对理论计算机中的可计算性理论、可判定性理论等也有重大的影响。在哲学方面,有意义理论、本体论、模态逻辑、归纳逻辑等。但不管怎样,数理逻辑这门学科永远不是死板的,而是在数学与哲学交界处的一门学科,是希望实现数学与哲学在认识论意义上统一的一门学科。我的感慨结束了,谢谢大家读到最后一行。