01 / 导读
导读
引用
Leary, C. C., & Kristiansen, L. (2015). A Friendly Introduction to Mathematical Logic (2nd ed.). Milne Library, SUNY Geneseo. 开放教材（CC BY-NC-SA）。
章节概要
全书共八章，另有一个简短的附录、部分练习的解答（约75页）和参考文献，总计约365页。前面几章中大多数小节以练习结尾，每章最后有一节"Summing Up, Looking Ahead"，说明论证接下来走向何处。第2版在Leary 2000年的第1版基础上扩充，新增了一章可计算性理论以及练习解答。
第1章：结构与语言
建立一阶逻辑的词汇。先把一阶语言定义为符号的集合，然后归纳地定义项和公式，并推广归纳法，使其能证明关于项和公式的命题。数论语言（含0、后继、加法、乘法、幂运算和序关系）成为贯穿全书的例子。随后定义结构、变元指派和结构中的真，处理代入以及变元在量词之下被捕获的问题，最后讲逻辑蕴涵和有效性。
第2章：演绎
从"什么是证明"这一问题出发，定义形式演绎。给出逻辑公理（等词公理和量词公理）和推理规则（命题后承与量词规则），证明可靠性定理和该系统的一些性质，包括等号是等价关系以及演绎定理的一种形式。最后讲非逻辑公理，以向量空间和算术的一个较弱公理系统N为例。
第3章：完全性与紧致性
用亨金的方法证明完全性定理：把一致的语句集扩张为极大一致集，并由项构造模型。紧致性随之而来，并被用来构造算术的非标准模型，说明没有任何一阶语句集能唯一刻画自然数。本章以子结构、初等子结构以及向下和向上的吕文海姆–斯科伦定理结束。
第4章：从两个角度看不完全性
解释为什么在完全性一章之后接着讲不完全性，定义完全的公理集，并确立目标：找到一个无法被证明的真语句。章中引入由有界和无界量词衡量的公式复杂度，给出以把演绎编码为数为基础的路线，预告另一条经过可计算函数的路线，并展示如何把数的有限序列编码成一个数。本章以回顾公理系统N及其强度结束。此后读者可以继续读第5、6章，也可以直接跳到第7章。
第5章：句法不完全性：准备工作
基于公式的路线的技术核心。引入可表示的集合与函数，把它们与计算机程序及等价的计算模型（递归函数、图灵机、λ演算）作非形式的联系，然后建立哥德尔编码的机制。逐步证明项、公式、公理和演绎的编码都可以在N中表示，最终得到一个公式，它成立当且仅当某个数是某个公式的一个演绎的编码。
第6章：不完全性定理
证明自指引理，并用它构造一个断言自身不可证的语句。据Peter Smith的书评，本章接着给出第一不完全性定理的语义形式和句法形式、算术的不可判定性、塔斯基定理、罗瑟的改进，以及布洛斯基于贝里悖论的不完全性证明，并在假设可导性条件的前提下证明第二不完全性定理。
第7章：可计算性理论
第2版新增的一章，约70页。从简短的历史一节出发，进入μ-递归函数、s-m-n定理和克林范式定理，随后证明集合K不可计算。这被用来证明判定问题（Entscheidungsproblem）不可判定、给出不完全性的第二个证明以及希尔伯特第十问题（见Smith的书评）。
第8章与书末部分
第8章"Summing Up, Looking Ahead"把各条线索收拢，并指出进一步阅读的方向。附录"Just Enough Set Theory to Be Dangerous"之后是部分练习的解答和参考文献。
核心概念
第1–2章：语言、结构、演绎
- 一阶语言与结构：一边是由符号和公式构成的句法，另一边是解释它们的数学模型。
- 逻辑蕴涵与有效性：一个公式从另一些公式推出，是指在满足后者的每个结构和指派下它都为真。
- 演绎：公式的有限序列，每一项或是公理，或由前面的项按规则得出，是证明的形式化。
- 可靠性：能被演绎出来的，在所有模型中都为真。
第3章：完全性与紧致性
- 完全性定理：从一个公理集逻辑地推出的，都可以从它演绎出来。
- 紧致性定理：一个语句集有模型，当且仅当它的每个有限子集都有模型。
- 非标准模型：与自然数初等等价、但不与之同构的结构。
- 吕文海姆–斯科伦定理：存在其他基数的初等子结构和初等扩张。
第4–6章：不完全性
- 完全的公理集：能证明或否证其语言中每个语句的公理集。
- 可表示的集合或函数：被理论中的公式所定义，并且理论能证明其正确性的集合或函数。
- 哥德尔编码：给符号、公式和演绎分配自然数，使关于证明的陈述变成关于数的陈述。
- 自指引理：对任一公式，都存在一个语句，断言该公式对它自身成立。
- 第一、第二不完全性定理：算术不存在可判定、一致且完全的公理化，足够强的公理系统也不能证明自身的一致性。
第7–8章：可计算性
- 可计算（μ-递归）函数：由基本函数经复合、原始递归和极小化构造出的函数。
- 范式定理：每个可计算函数都可以用一个固定的可计算谓词和一次无界搜索来写出。
- 判定问题（Entscheidungsproblem）：判定一阶逻辑有效性的问题，其答案是否定的。
评析
优点
- 亲切、节奏适中的叙述。 Peter Smith在Logic Matters上的书评喜欢其轻松而有吸引力的语气，认为讲解的水平很适合入门课程，并称其清晰度堪称典范。作者用来提示记号陷阱和交代动机的"Chaff"旁注（例如把数字0与数0区分开来）是各章的一大特色。
- 通向同一目标的两条路。 作者在第4章之后把通往不完全性定理的道路分成两条：经过第5、6章的基于公式的路线，以及经过第7章的基于计算的路线。课程可以任选其一，读者也可以看到两种方法。
- 练习与解答。 前六章中大多数小节以练习结尾，第2版又增加了约75页解答。开放教材倡议（Open Textbook Initiative）列出本书有许多练习的解答，Smith则说这使它更适合自学。
- 对可表示性的细致演示。 Smith称第5章直接写出定义公式的处理，是现有的完整演示中最易于使用的之一，并指出第2版缓和了对角化引理证明给人的突兀感。
- 免费而紧凑。 正文以知识共享许可开放，作者的目标是在一个学期内讲到不完全性定理。
局限
- 希尔伯特式系统。 演绎系统是规则很少的公理化系统。Smith提醒说，没有见过一阶逻辑形式系统的读者起初可能觉得它很密集，习惯于树形或自然演绎的学生也许希望有人解释这一选择。
- 第5章很费力。 作者自己也把这一章描述为密集而技术性的，是接连不断的定义。需要为它预留时间。
- 范围较窄。 本书涵盖到吕文海姆–斯科伦定理为止的一阶逻辑、不完全性定理和一部分可计算性；更深入的模型论和公理集合论不在其内，集合论只出现在一个简短的附录中。
- 默认已懂命题逻辑。 命题逻辑只在推理规则一章中作简要复习，没有学过的读者需要先找别的资料。
- 第二不完全性定理依赖假设的条件。 据Smith所说，可导性条件是被假设而非被证明的。
在课程中的定位
在本站的逻辑与集合论书籍中，Leary和Kristiansen是面向哥德尔定理的数理逻辑第一门课的教材。它接在讲证明写作的书之后：Hammack的免费教材 Book of Proof 和Velleman的 How to Prove It 以非形式的方式讲逻辑、集合和证明方法，这正是本书加以形式化的背景。Liebeck、Eccles和Allenby关于证明、集合与数系的较广泛的书，则是更早阶段的另一些选择。
最接近的比较对象是Enderton的 A Mathematical Introduction to Logic，它严格地处理命题逻辑和一阶逻辑、形式理论与模型论，并与可计算性相联系。Leary和Kristiansen则是目标更集中的免费选择，直奔不完全性定理，在模型论上花的篇幅较少。无论读哪一本，都为学习模型论、集合论或可计算性的专门教材做好了准备。
如何使用本书
本书写给高年级本科生，序言介绍了通往不完全性的两条路线；据Smith所说，对于不排斥抽象论证的哲学专业学生，它也是可读的。本站列出的先修条件是有证明型数学的经验。
建议的计划如下：
- 核心： 第1–4章。第1–3章是一阶逻辑直到完全性和紧致性的自足入门；请慢慢读第1、2章的定义，因为后面的证明依赖其确切形式。Smith指出，已经熟悉结构和演绎的读者可以单独阅读第3章。
- 选择通向不完全性的路线： 第4章之后，选第5、6章（公式与哥德尔编码）或第7章（可计算性）。第二遍阅读时再读另一条。
- 可选： 第8章和附录篇幅不长，主要起导向作用。
- 练习： 做那些要求给出明确演绎和结构的题目，并用解答核对。