什么是数理逻辑 · Topos Uranos

摘要

本课界定数理逻辑的对象：它研究的不是个别陈述句的真假，那属于各门科学，而是推理的形式与有效性，即前提与结论之间保证前提之真传递到结论的那种关系。本课定义命题、论证、前提、结论、形式和反例；用结论为假的有效论证和结论为真的无效论证区分有效性与真；说明自然语言既有歧义又能谈论自身，为何不足以严格地研究有效性；并确立对象语言与元语言的区分，这一区分贯穿整个课程。随后，本课连同明确的假设和证明，介绍说谎者悖论、贝里悖论和理发师悖论，以及理发师悖论所预示的罗素悖论，并解释形式语言如何避开它们或把它们变成定理。最后介绍数理逻辑的四大支柱和课程的地图。

学习目标

区分论证的有效性与其前提和结论的真，并通过构造反例驳倒无效的形式。
识别自然语言的歧义，并把歧义陈述句的每一种读法说清楚。
区分对象语言与元语言，区分一个表达式的使用与提及。
分析悖论：分离其假设，推出矛盾，并判定应当放弃哪一个假设。

逻辑研究什么

凡不是通过直接观察获得的知识，都是通过推理获得的：从某些被接受的断言过渡到由它们得出的另一个断言。在几何学中，知道三角形的内角和等于两个直角的人，便断定没有一个三角形有两个钝角；在医学中，知道某种疾病会引起发热、又知道受检者并不发热的人，便排除这种疾病。逻辑是研究这种过渡何时正当的学科，数理逻辑则是用数学方法研究它的逻辑：精确地定义它的对象，即语言、公式和推演，并证明关于它们的定理。

为了精确地说明它研究什么，先要确定术语。命题是可以有意义地说它为真或为假的陈述句：“ $7$ 是素数”是一个真命题；“每个偶数都大于 $5$ ”是一个假命题。反之，疑问句（“现在几点？”）、祈使句（“关上门”）以及含有自由变元的表达式，例如“ $x$ 是偶数”，都不是命题，后者的值取决于 $x$ 指称什么。

论证是一组命题，即前提，连同另一个命题，即结论，结论被当作前提的推论提出。前提可以是任何命题：真的、假的、已知的，或者仅仅是设想；使它们成为前提的，只是它们在论证中所占的位置。我们把论证写成：前提逐行列出，结论前面加上“所以”：

例题一个论证

如果一个数是 $4$ 的倍数，那么它是偶数。数 $28$ 是 $4$ 的倍数。所以， $28$ 是偶数。

它的前提是“如果一个数是 $4$ 的倍数，那么它是偶数”和“ $28$ 是 $4$ 的倍数”；它的结论是“ $28$ 是偶数”。

逻辑不是关于真的理论

既然如此，逻辑的任务就不是查明论证的前提是否为真。 $28$ 是否为 $4$ 的倍数，由算术决定；一个人是否发热，由体温计决定；某场战役是否发生在某一年，由历史决定。界定什么是真，也不是逻辑的事，那是哲学的问题。逻辑承认命题具有真值，不论它是什么，并研究这些真值之间如何相互关联：特别是，一些命题的真何时迫使另一个命题为真。换言之，逻辑不是关于真的理论，而是关于真之传递的理论。

然而，传递真的东西不取决于论证的题材，而取决于论证的结构。把上面的论证与下面这个比较一下：“如果一种动物是哺乳动物，那么它呼吸空气；鲸是哺乳动物；所以，鲸呼吸空气”。两者有同样的形式：“如果某物是 $A$ ，那么它是 $B$ ； $c$ 是 $A$ ；所以， $c$ 是 $B$ ”。论证的形式，就是把其中的非逻辑词项（数、动物、性质）换成字母、保留逻辑词语后剩下的东西，逻辑词语如“非”“且”“或”“如果……那么”“所有”“有些”。给一个形式的字母赋予内容而得到的每个论证，都是该形式的一个实例。

一个形式是有效的，当且仅当它没有一个实例的前提全真而结论为假；一个论证是有效的，当且仅当它的形式有效。前提为真而结论为假的实例称为该形式的反例：由此，一个形式无效，恰好当它有反例。

在本课的证明中，我们使用汉语的一种速记： $V(A)$ 表示“ $A$ 为真”， $F(A)$ 表示“ $A$ 为假”； $\neg$ 表示“非”， $\wedge$ 表示“且”， $\vee$ 表示“或”， $\Rightarrow$ 表示“如果……那么”， $\Leftrightarrow$ 表示“当且仅当”； $\forall$ 读作“对所有”， $\exists$ 读作“存在”。这些符号在这里只是元语言词语的缩写，双线箭头在整个课程中都留作这种用途。下一课将出现单线符号 $\rightarrow$ 和 $\leftrightarrow$ ，连同 $\neg$ 、 $\wedge$ 和 $\vee$ ，作为一种形式语言的缩写，其含义由课程精确规定；箭头笔画的不同将提醒我们是在哪个层次上说话。

命题有效性保证什么

如果一个论证有效且它的前提全都为真，那么它的结论为真。因此，如果一个有效论证的结论为假，那么它的某个前提为假。

证明

$\dato{p}{V(A_1) \wedge \cdots \wedge V(A_n)}$
设有一个有效论证，前提为 $A_1, \ldots, A_n$ ，结论为 $C$ ，并假设所有前提都为真。
$\resaltar{A_1, \ldots, A_n, C}$
每个论证都是它自身形式的一个实例：只需让形式中的字母取它们在论证中所具有的内容。
$\dato{v}{\neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \wedge \resaltar{\neg V(C)} \right)}$
根据有效性的定义，这个形式没有一个实例前提为真而结论为假；特别地，论证本身也不是这样。
$\resaltar{V(C)}$
由于前提为真，被否定的合取中唯一可能不成立的就是结论之假：所以结论为真。
$\neg V(C) \Rightarrow \neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \right)$
反之，如果结论为假，前提就不可能全都为真，因为那样的话结论也会为真。

这个命题说明了有效性保证什么；同样值得清楚地看到它不保证什么。若把论证的有效性、全部前提的真和结论的真组合起来，在八种可能的组合中，只有一种被排除，即有效论证、前提为真而结论为假的组合；其余的组合都会出现。

例题有效，但结论为假

所有素数都是奇数。数 $2$ 是素数。所以， $2$ 是奇数。

它的形式与本课第一个论证相同，所以这个论证是有效的；然而它的结论为假。上面的命题指出了毛病所在：某个前提为假，事实上正是第一个前提，因为 $2$ 是素数而且是偶数。有效的论证不产生真理；它只保存它所接受的真理。

例题无效，但结论为真

如果一个数是 $4$ 的倍数，那么它是偶数。数 $8$ 是偶数。所以， $8$ 是 $4$ 的倍数。

前提和结论都为真，但这个论证是无效的。它的形式“如果某物是 $A$ ，那么它是 $B$ ； $c$ 是 $B$ ；所以， $c$ 是 $A$ ”有一个反例：用数 $6$ 代替 $8$ ，前提仍然为真（“如果一个数是 $4$ 的倍数，那么它是偶数”；“ $6$ 是偶数”），而结论“ $6$ 是 $4$ 的倍数”为假。原来的结论之所以为真，不是来自前提，而是来自算术： $8 = 4 \cdot 2$ 。这种无效形式在日常推理中很常见，称为肯定后件。

由此得到本课将要练习的实用规则：要说明一个论证无效，指出某个前提或结论为假是不够的；要说明它有效，其中一切都为真也是不够的；前者要求给出它的形式的一个反例，后者要求一个对所有实例都成立的推理。

自然语言与形式语言

有效性的定义依赖于两种操作：识别论证的形式，以及判定一个命题是真是假。两者都假定每个语句只有一种读法。自然语言，如汉语、西班牙语或阿拉伯语，是人们不经正规教学就学会、用来交流的语言，它不满足这个条件：它的灵活性使它适合诗歌、交谈和细微的意味，也使它有歧义。

词汇歧义：一个词有几种意义。“他借了我一本书”既可以指他把书借给我，也可以指他向我借了书。
句法歧义：一个语句允许几种结构。“二乘以三加四”可以是 $2 \cdot 3 + 4 = 10$ ，也可以是 $2 \cdot (3 + 4) = 14$ 。
辖域歧义：不清楚一个逻辑词作用于语句的哪一部分。“所有学生没有及格”（不加“都”）既可以理解为没有一个学生及格，也可以理解为并非所有学生都及格；汉语通常用“都不”和“不都”的词序来消除这种歧义。
不精确的联结词：“或”有时允许两种选择同时成立（“要求有学历或工作经验”），有时又排除这一点（“咖啡或茶”）；“如果……那么”有时表示原因，有时表示规则，有时只表示先后。

除了歧义，还有一个更深的特点：自然语言能够谈论自身。它含有“语句”“真的”和“定义”这些词，并且能用它们造出指称自身的语句，例如“这句话有七个字”。这种自指一般是无害的；但我们将会看到，它与真的概念结合起来，就会产生既不能为真也不能为假的语句。

形式语言的设计就是为了消除这两个困难的来源。先确定一个字母表，即一组符号，再确定一些形成规则，它们毫无解释余地地规定哪些符号序列是合式的表达式；随后用同样精确的定义确定每个表达式的意义。这样，一个符号序列是否属于该语言，是一个可以机械地、通过检查规则来解决的问题，而每个表达式只有一种读法。本课程的语言，由关于命题逻辑的语言的那一课构造，它的字母表只有两个符号，圆圈 $\sigO$ 和圆盘 $\sigI$ ，并且只有一条形成规则。

代价是灵活性：形式语言不能用来交谈，而且每种形式语言只能表达它的规则所允许的东西。然而，说表达能力全部被牺牲了，并不正确：一阶逻辑的形式语言足以写出几乎全部数学。被牺牲的是歧义和不受控制的自指；得到的是证明关于语言本身的定理的可能性。

对象语言与元语言

要研究一种语言，就必须谈论它，而要谈论它，就需要另一种语言。对象语言是被研究的语言；元语言是用来研究它的语言。在一本用汉语写的拉丁语语法书中，拉丁语是对象语言，汉语是元语言。在本课程中，对象语言是由圆圈和圆盘构成的形式语言，元语言是汉语，并辅以数学符号和希腊字母 $\varphi$ 、 $\psi$ ，这些字母表示对象语言的任意公式，但本身不属于对象语言。

这一区分之所以是核心的，有一个确切的理由：课程将要证明的关于形式语言的断言（每个公式只有一种读法，一切可推演的都是真的）不是形式语言的公式，而是元语言的语句。因此它们将被称为元定理，以区别于演绎系统在对象语言内部产生的定理。

这一区分的一种基本形式，是把一个表达式的使用与它的提及分开。在“罗马是一座城市”中，这个词被使用，用来谈论那座城市；在“‘罗马’有两个字”中，这个词被提及，引号标明了这一点：这个语句谈的是词，而不是城市。把两者混淆，会产生荒谬的陈述句，例如“罗马有两个字”，或者谬误的论证，例如“罗马是一座城市；‘罗马’是一个两字的词；所以，一座城市是一个两字的词”。

例题三个层次

取拉丁语为对象语言。语句“Roma aeterna est”属于对象语言。语句“‘Roma aeterna est’由三个词组成”属于元语言，即汉语，而且是真的。语句“上一个语句是用汉语写的”谈论的是元语言的一个语句：它属于第三个层次，即元语言的元语言，尽管它是用同一种语言写的。同一种语言完全可以在几个层次上使用；重要的是不要忘记在谈论什么。

语言的悖论

矛盾是一个断言连同它的否定，例如 $V(A) \wedge \neg V(A)$ 。悖论是这样一种推理：它从看似可以接受的假设出发，经过看似有效的步骤，得出矛盾。根据命题“有效性保证什么”，如果这些步骤确实有效，那么某个假设为假：解决一个悖论，就是找出是哪一个。不要把悖论与歧义混为一谈，歧义只是读法的多样；也不要把它与仅仅令人惊讶的事情混为一谈。

说谎者

这类悖论中最古老的一个，通常归于公元前4世纪米利都的欧布利德。在其精确的形式中，它谈的不是说谎，说谎预设了欺骗的意图，而是假：设 $m$ 为语句“语句 $m$ 是假的”。要得出矛盾，两个假设就够了，值得把它们明确写出来。

二值原则 (B)：每个命题或真或假，且不同时既真又假；为假等价于不为真。
真理模式 (T)：一个语句为真，当且仅当它所说的情况成立。例如，“雪是白的”为真，当且仅当雪是白的。

定理说谎者悖论

二值原则和真理模式这两个假设，应用于语句 $m$ ，导致矛盾：没有办法给 $m$ 指派一个同时符合两者的真值。图中，语句 $m$ 指向它自己，箭头走遍两种可能。

证明

$\dato{B}{F(m) \Leftrightarrow \neg V(m)}$
根据二值原则， $m$ 或真或假，且不同时既真又假：为假就是不为真。
$\dato{T}{V(m) \Leftrightarrow \resaltar{F(m)}}$
$m$ 所说的是 $m$ 为假。根据真理模式， $m$ 为真恰好当它所说的情况成立。
$V(m) \Leftrightarrow \resaltar{\neg V(m)}$
把两个等价连接起来， $m$ 的真等价于它自身的否定。
$V(m) \Rightarrow \neg V(m), \quad \resaltar{\neg V(m)}$
如果 $m$ 为真，那么按从左到右读的等价，它就不为真：这个设定自己驳倒自己，所以 $m$ 不为真。
$\resaltar{V(m) \wedge \neg V(m)}$
但这样一来，按从右到左读的等价， $m$ 为真：我们同时得到一个断言和它的否定。

这个定理并不是说逻辑是矛盾的，而是说对于含有语句 $m$ 的语言，这两个假设不能同时成立。因此有三条出路：放弃二值原则，承认没有真值的语句；限制真理模式；或者不让语言构成语句 $m$ 。第三条出路是阿尔弗雷德·塔斯基在1933年提出的：一种语言的谓词“是真的”不属于这种语言本身，而属于它的元语言。在这样的语言中， $m$ 不是合式的语句，悖论根本无法陈述。

贝里悖论

这个悖论由伯特兰·罗素于1906年发表，他把它归于牛津的图书馆员乔治·贝里；它用的不是“真的”这个词，而是“定义”这个词。我们说一个汉语短语定义一个自然数，如果它描述这个数，使人能毫无歧义地确认它：“比十大的最小素数”定义 $11$ 。考虑短语“少于二十字不能定义的最小数”，必须严格照字面来读，并把它想要定义的数称为 $b$ 。在本课程中，自然数是 $1, 2, 3, \ldots$

定理贝里悖论

如果汉语的字是有限的，并且关系“短语定义该数”是完全确定的，就会得出矛盾：数 $b$ 存在，而且同时既能又不能用少于二十个字定义。图中，短的短语被送到它们所定义的数，这些数为数不多；第一个空着的数就是 $b$ 。

证明

$\dato{N}{N \leq k + k^2 + \cdots + k^{19}}$
设 $k$ 为字典所收的字数。一个字的短语至多有 $k$ 个；两个字的，至多有 $k^2$ 个；依此类推，直到十九个字的短语。因此，少于二十个字的短语只有有限个，记其个数为 $N$ 。
$\dato{D}{D = \{ d_1, \ldots, d_r \}, \quad r \leq N}$
每个短语至多定义一个数。设 $D$ 为某个少于二十个字的短语所定义的自然数的集合：它至多有 $N$ 个元素。
$(\exists n \leq N + 1)\,(n \notin D), \quad \resaltar{b \notin D}$
在 $N + 1$ 个数 $1, 2, \ldots, N + 1$ 之中，有一个不在 $D$ 中。按顺序逐个检查，第一个不在 $D$ 中的数，就是少于二十个字不能定义的最小自然数：它前面的数都在 $D$ 中。
$13 < 20, \quad \resaltar{b \in D}$
但是短语“少于二十字不能定义的最小数”只有十三个字，而它恰好定义了 $b$ 。
$\resaltar{b \in D \wedge b \notin D}$
我们同时得到一个断言和它的否定。

通常的讲法只指出这个短语不到二十个字，从而省略了论证的一半：数 $b$ 是存在的，这需要字的有限性，以及选取第一个缺失的数。失败的是第二个假设：“定义”不是汉语中的一个精确关系，因为定义 $b$ 的短语本身就用了“定义”这个词，而它的意义取决于哪些短语算作定义。在一种形式语言 $L$ 中，可以精确规定“在 $L$ 中可定义”是什么意思，但这个概念只能在元语言中表达；定义 $b$ 的短语不属于 $L$ ，矛盾就消失了： $b$ 在 $L$ 中不能用很少的符号定义，尽管它在元语言中是可定义的。

理发师与罗素集合

理发师悖论通常是这样讲的：一个村子里有一位理发师，他是村里的男人，他给村里所有不给自己刮脸的男人刮脸，而且只给这些人刮脸。这位理发师给不给自己刮脸？“只给这些人”这几个字至关重要：一个给所有不给自己刮脸的人刮脸、却没有这一限制的理发师，也可以给自己刮脸，毫无矛盾。这个悖论是一个具有对角线形式的一般引理的特例，值得一劳永逸地证明它。

引理对角线引理

设 $D$ 是一个对象的汇集， $R$ 是它们之间的一个关系，使得对任意一对对象 $x$ 、 $y$ ，只要二者属于 $D$ ，断言 $R(x, y)$ 就或真或假。那么没有任何对象 $b$ 既属于 $D$ ，又满足：对每个 $x$ ，只要它属于 $D$ ， $R(b, x)$ 成立当且仅当 $R(x, x)$ 不成立。图中，每一行是一个对象 $x$ ，每一列是一个对象 $y$ ，当 $R(x, y)$ 成立时格子被涂满；我们为 $b$ 寻找的那一行应当把对角线反过来，因此它与每一行在该行的对角线格子上都不同。

证明

$\dato{b}{(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)}$
假设存在这样的 $b$ ，它属于 $D$ 。
$R(b, \resaltar{b}) \Leftrightarrow \neg R(\resaltar{b}, \resaltar{b})$
这个条件对一切 $x$ 成立，其范围是 $D$ ，而 $b$ 是其中之一：可以取 $x = b$ 。
$R(b, b) \Rightarrow \resaltar{\neg R(b, b)}$
如果 $R(b, b)$ 成立，那么由等价它不成立：矛盾。
$\neg R(b, b) \Rightarrow \resaltar{R(b, b)}$
如果 $R(b, b)$ 不成立，那么由等价它成立：同样矛盾。
$\neg (\exists b \in D)\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
两种情形必有一种发生，所以这个设定站不住：不存在这样的 $b$ 。

推论理发师不存在

没有一个村子里有这样一个村里的男人，他给村里所有不给自己刮脸的男人刮脸，而且只给这些人刮脸。

证明

$(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
设 $D$ 为村里男人的汇集， $R(x, y)$ 为关系“ $x$ 给 $y$ 刮脸”。理发师 $b$ 是村里的男人，所以他在 $D$ 中；他是所描述的那种理发师，意思是：他给村里的每个男人刮脸，恰好当这个男人不给自己刮脸。
$\resaltar{\neg (\exists b \in D)}\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
根据对角线引理，村里没有一个男人满足这个条件：所描述的理发师不存在。这个故事不是悖论，而是对其主人公不可能存在的证明。

理发师的结论是无害的：从来没有人断言这样的理发师存在。它在集合论中的版本就不同了。1902年，罗素写信给戈特洛布·弗雷格，指出弗雷格那个想把算术建立在逻辑之上的系统承认如下的概括原则：对每一个性质，都有一个集合，它的元素恰好是具有该性质的对象。把这个原则应用于不属于自身这一性质，它就断言存在集合

Z = \{ x : x \notin x \}

推论罗素悖论

不加限制的概括原则是矛盾的。

证明

$\dato{Z}{(\forall x \in D)\,\left( x \in Z \Leftrightarrow x \notin x \right)}$
设 $D$ 为所有集合的汇集， $R(x, y)$ 为关系“ $y$ 属于 $x$ ”。概括原则应用于性质 $x \notin x$ ，断言存在一个集合 $Z$ ，它的元素是不属于自身的集合。
$(\forall x \in D)\,\left( \resaltar{R(Z, x)} \Leftrightarrow \resaltar{\neg R(x, x)} \right)$
在所选的关系下， $Z$ 的条件恰好是对角线引理的条件，只是 $Z$ 处在 $b$ 的位置： $x \in Z$ 就是 $R(Z, x)$ ， $x \notin x$ 就是 $\neg R(x, x)$ 。
$\resaltar{Z \in Z \Leftrightarrow Z \notin Z}$
集合 $Z$ 是一个集合，所以它在 $D$ 中；根据对角线引理，这样的 $Z$ 不存在，取 $x = Z$ 就得到那个不可能的等价。但是原则断言它存在。因此，这个原则蕴涵矛盾。

与理发师不同，这里 $Z$ 的存在不是一个故事里的设定，而是理论的一条原则。罗素悖论不是靠宣布 $Z$ 不存在来解决，而是靠改造理论：策梅洛1908年的公理化集合论只允许用一个性质构成某个已给集合的子集，在这一限制下推不出矛盾。

什么不是悖论

人们有时把这样一个观察称为“空集悖论”：空集存在，尽管它没有元素，仿佛一个存在的对象必须由存在的对象构成。这里没有任何矛盾：集合不是像墙由砖砌成那样由它的元素构成的，而是由它的元素确定的，一个集合的元素的汇集可以一个元素也没有，就像一个空盒子仍然是盒子。一个事实令人惊讶，并不使它成为悖论；悖论要求推出矛盾，而这里推不出任何矛盾。

形式语言如何对待它们

由上所述可知，形式语言避开悖论并不是靠魔法，而是靠两种确切的方式。第一种是：它可以缺少产生悖论的手段。本课程构造的命题逻辑的语言，既没有指称自身的语句，也没有真谓词：在其中写不出说谎者语句，而且它的语义在变元的每一个赋值下，都给每个公式指派唯一的真值。第二种是：在更丰富的语言中，悖论变成了定理：严格地进行说谎者的推理，可以证明一种表达能力足够强的语言的真在这种语言本身中不可定义（塔斯基）；理发师和罗素的推理证明某些汇集不是集合；而与贝里悖论相近的论证处于库尔特·哥德尔1931年不完备性定理的核心。于是，在自然语言中是困惑的东西，在形式语言中成了信息。

数理逻辑的四大支柱

数理逻辑诞生于19世纪末和20世纪初，出自弗雷格、皮亚诺、罗素和大卫·希尔伯特之手，是对一个确切问题的回答：数学建立在什么基础之上，这些基础是否没有矛盾。今天人们把它分为四大分支，它们彼此不断交织。

证明论：把形式证明当作数学对象来研究，即当作遵循明确规则的有限公式序列；它问一个系统中能证明什么、一个系统是否一致，以及证明之间如何相互变换。本课程的“演绎”单元是对它的初次接触。
模型论：研究形式语言与解释它的结构，即它的模型，之间的关系；它问哪些结构满足一个公式集，以及结构的哪些性质能在给定的语言中表达。“语义”单元及其真值赋值，是它最初等的形态。
集合论：用精确的公理研究集合，例如策梅洛和弗兰克尔的公理，几乎全部数学都能在其中写出；它在很大程度上产生于避免罗素悖论的需要。
可计算性理论：研究哪些问题能用机械程序解决，哪些不能。命题逻辑是可判定的，课程将会看到：存在一个程序，能在有限步内判定一个公式是否为重言式；谓词逻辑则不然。

没有一个支柱能够在不触及其他支柱的情况下得到深入研究：完备性是本课程的核心结果，它既是证明论的定理，又是模型论的定理，而由它得到的可判定性属于可计算性理论。

课程的地图

本课程针对最简单的逻辑语言，即命题逻辑的语言，走完一种逻辑理论的全过程，分为四个单元。

语言：语法。构造对象语言，包括它由两个符号组成的字母表和它的形成规则；证明每个公式只有一种读法；学习用归纳法证明；把自然语言的陈述句和论证翻译成形式语言，并指出翻译保留了什么、失去了什么。
演绎：确定一个由公理和推理规则组成的系统，并定义公式 $\varphi$ 从公式集 $\Gamma$ 推演出来是什么意思，记作 $\Gamma \vdash \varphi$ 。这是有效性的语法一面：按照规则操作符号，不考虑它们的意义。
语义：在每个赋值下给每个公式指派一个真值，并定义 $\varphi$ 是 $\Gamma$ 的后承是什么意思，记作 $\Gamma \models \varphi$ ：凡使 $\Gamma$ 的公式为真的赋值都使 $\varphi$ 为真。这是有效性的语义一面，即本课的定义被精确化之后的样子。
元理论：证明两面是一致的。可靠性说一切可推演的都是后承，完备性说一切后承都是可推演的。随后研究紧致性，以及一种判定公式集是否可满足的机械方法，即归结。

既然如此，本课程就是以推理本身为对象的数学理论的第一个完整例子；而它关于形式语言的所有断言，正如我们在本课中看到的，都将是以数学的严格性证明的元语言语句。

例题

下面的问题按难度递增，练习本课的各种区分：驳倒一个所有语句都为真的论证，分开一个歧义陈述句的几种读法，给对象语言和元语言的表达式分类，以及分析两个看似悖论的推理，判定它们是否真是悖论。

例题 1一切为真，却仍然无效

证明下面的论证是无效的，尽管它的前提和结论都为真：“所有 $6$ 的倍数都是偶数；数 $12$ 是偶数；所以， $12$ 是 $6$ 的倍数”。

解答

$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(12), \quad S(12)$
把“ $x$ 是 $6$ 的倍数”简记为 $S(x)$ ，把“ $x$ 是偶数”简记为 $P(x)$ 。前提和结论都为真，因为 $12 = 6 \cdot 2$ 。
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{c}), \quad S(\resaltar{c})$
把名称 $12$ 换成字母 $c$ ，就得到形式：两个前提和一个结论。
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{4})$
寻找一个前提为真的实例：第一个前提不依赖于 $c$ ，第二个前提要求一个偶数。取 $c = 4$ 。
$\neg S(\resaltar{4})$
这个实例的结论为假，因为 $4$ 不是 $6$ 的倍数。
$\resaltar{12 = 6 \cdot 2}$
这个形式有反例：它是无效的，论证也是无效的。论证的结论之所以为真，来自算术，而不是来自前提。

例题 2一个辖域歧义

设 $L$ 为数的列表 $4$ 、 $6$ 、 $7$ 。证明语句“ $L$ 中所有的数不是素数”有两种读法，并且对这个列表，一种读法为真，另一种为假。

解答

$\dato{a}{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)}$
把“ $x$ 是素数”简记为 $Q(x)$ 。第一种读法：否定作用于每一个数，语句说的是没有一个是素数。
$\dato{n}{\neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)}$
第二种读法：否定作用于整个断言，语句说的是并非所有的数都是素数。
$Q(7), \quad \neg\left( \neg Q(4) \wedge \neg Q(6) \wedge \resaltar{\neg Q(7)} \right)$
由于 $7$ 是素数，第一种读法的最后一项为假，整个合取也随之为假：第一种读法为假。
$\neg Q(4), \quad \neg\left( \resaltar{Q(4)} \wedge Q(6) \wedge Q(7) \right)$
由于 $4$ 不是素数，第二种读法中的合取为假，它的否定为真：第二种读法为真。
$\resaltar{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)} \Rightarrow \neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)$
两种读法并不等价：第一种蕴涵第二种，反之则不然，这个列表就说明了这一点。在数学中，第二种写作“ $L$ 中的数并非都是素数”，第一种写作“ $L$ 中没有一个数是素数”。

例题 3对象语言与元语言

取符号 $\sigO$ 和 $\sigI$ 组成的序列为对象语言，取汉语为元语言，并用希腊字母表示任意序列。给下列每个表达式分类，并在有意义时判定它是否为真：(a) $\sigO\sigO\sigI$ ；(b) “ $\sigO\sigO\sigI$ 有三个符号”；(c) “对每个序列 $\varphi$ ，序列 $\sigI\varphi$ 以一个圆盘开头”；(d) “ $\sigO\sigO\sigI$ 是真的”。

解答

$\resaltar{\sigO\sigO\sigI}$
表达式 (a) 属于对象语言：它是一个符号序列，不是汉语的语句，无所谓真假；人们谈论它，但它本身什么也不断言。
$\sigO \; \sigO \; \sigI \quad (3)$
表达式 (b) 是元语言的语句，它提及序列 (a) 并数它的符号：它是真的。
$\resaltar{\sigI}\varphi$
表达式 (c) 是元语言的语句。字母 $\varphi$ 不是对象语言的符号，而是遍历对象语言序列的元语言变元；这个语句是真的，因为按构造， $\sigI\varphi$ 以圆盘开头。
$v_2 = \sigO\sigO\sigI$
表达式 (d) 属于元语言，但还没有真值：序列 $\sigO\sigO\sigI$ 将是课程语言的一个变元，而变元本身无所谓真假，只有当一个赋值在“语义”单元中给它一个值时才有真假。下一课将把它称为 $v_2$ 。

例题 4埃庇米尼得斯不是说谎者

一块黑板上写着语句 $e$ ，也许还有别的语句：“写在这块黑板上的每个语句都是假的”。承认二值原则和真理模式，证明 $e$ 为假，并且黑板上另有某个真语句；再推出：当且仅当黑板上没有别的真语句时才有悖论， $e$ 是黑板上唯一的语句时就是如此。

解答

$\dato{T}{V(e) \Leftrightarrow (\forall x \in O)\,F(x)}$
设 $O$ 为黑板上语句的集合； $e$ 是其中之一。根据真理模式， $e$ 为真当且仅当 $O$ 中所有语句都为假。
$V(e) \Rightarrow \resaltar{F(e)} \Rightarrow \neg V(e)$
如果 $e$ 为真，那么 $O$ 中所有语句都为假，而 $e$ 在 $O$ 中： $e$ 就为假，根据二值原则它就不为真。这个设定自己驳倒自己。
$\resaltar{F(e)}$
所以 $e$ 不为真；根据二值原则，它为假。
$(\exists x \in O)\,\left( x \neq e \wedge V(x) \right)$
根据真理模式， $e$ 为假意味着 $O$ 中的语句并非都为假：有某个语句为真，而且它不是为假的 $e$ 。
$\neg (\exists x \in O)\,\left( x \neq e \wedge V(x) \right) \Rightarrow \resaltar{V(e) \wedge \neg V(e)}$
如果黑板上另有一个真语句，一切都是一致的： $e$ 只是为假而已。反之，如果别的语句都不真，那么没有任何 $x$ 既不同于 $e$ 、又在 $O$ 中、又为真，就会得到矛盾，就像说谎者那样；特别是，当 $e$ 是黑板上唯一的语句时就是如此。因此，悖论是否出现，取决于一个经验事实：黑板上写着什么。

例题 5他谓的

一个形容词如果适用于它自身，就是自谓的（“短”这个词是短的；“中文的”这个词是中文的），否则就是他谓的（“长”这个词不长；“英文的”这个词不是英文的）。证明：如果“他谓的”是一个形容词，并且关系“适用于”对所有形容词都是完全确定的，就会得出矛盾；并判定应当放弃哪一个假设。

解答

$\dato{R}{R(x, x)}$
设 $D$ 为汉语形容词的汇集， $R(x, y)$ 为关系“形容词 $x$ 适用于词 $y$ ”。形容词 $x$ 是自谓的，如果 $R(x, x)$ ；是他谓的，如果 $\neg R(x, x)$ 。
$\dato{h}{(\forall x \in D)\,\left( R(h, x) \Leftrightarrow \neg R(x, x) \right)}$
设 $h$ 为形容词“他谓的”。根据它的定义，它适用于一个形容词，恰好当这个形容词不适用于自身。
$R(\resaltar{h}, \resaltar{h}) \Leftrightarrow \neg R(\resaltar{h}, \resaltar{h})$
如果 $h$ 是一个形容词，它就在 $D$ 中，而它的条件正是对角线引理的条件。取 $x = h$ ，就得到那个不可能的等价。
$h \in D \Rightarrow \resaltar{h \notin D}$
根据对角线引理， $D$ 中没有一个对象满足 $h$ 的条件。如果 $h$ 在 $D$ 中，就有矛盾。
$\resaltar{h \notin D}$
失败的是第二个假设：对于像“他谓的”这样本身又借助这同一个关系来定义的形容词，“适用于”不是一个精确的关系。在形式语言中，关系 $R$ 会在元语言中定义，形容词 $h$ 不会属于对象语言，于是条件 $h \in D$ 为假，也就没有矛盾。

练习题

前两道题练习有效性和歧义；第三道练习使用与提及；最后两道要求分析一个新的悖论，并在语言学之外应用对角线引理。每道题都有提示，最好在自己尝试之后再打开。

练习题 1两个相似的形式

考虑下面两个形式：(a) “如果 $p$ ，那么 $q$ ；非 $q$ ；所以，非 $p$ ”；(b) “如果 $p$ ，那么 $q$ ；非 $p$ ；所以，非 $q$ ”。判定哪一个有效，哪一个无效；对无效的那个，用关于数的陈述句构造一个反例；对有效的那个，解释为什么它的任何实例都不可能是反例。

提示

对于形式 (b)，找一个关于数的性质之间的真蕴涵，例如“如果 $n$ 是 $4$ 的倍数，那么它是偶数”，再找一个没有第一个性质却有第二个性质的数。对于形式 (a)，假设前提为真，并问问自己：如果 $p$ 为真，会发生什么。

答案

形式 (a) 称为否定后件式（modus tollens），它是有效的：如果前提为真，而 $p$ 为真，那么 $q$ 也为真，与第二个前提相违。形式 (b) 即否定前件，是无效的：“如果 $6$ 是 $4$ 的倍数，那么 $6$ 是偶数； $6$ 不是 $4$ 的倍数；所以， $6$ 不是偶数”前提为真而结论为假。

练习题 2护照、身份证和签证

一则告示写道：“入境需要护照或身份证和签证”。用字母 $p$ （护照）、 $d$ （身份证）和 $v$ （签证）写出它的两种读法，并描述一位旅客，按一种读法可以入境，按另一种读法却不行。

提示

问题在于签证只是与身份证搭配，还是与两种证件中的任何一种搭配。试试只有一种证件的旅客。

答案

两种读法是 $p \vee (d \wedge v)$ 和 $(p \vee d) \wedge v$ 。一位有护照而没有签证的旅客，按第一种读法可以入境，按第二种读法不能。

练习题 3引号

判定下列每个语句谈的是城市还是词，以及它是真还是假：(a) “罗马有两个字”；(b) “‘罗马’有两个字”；(c) “‘罗马’是意大利的首都”；(d) “语句‘罗马是意大利的首都’含有词‘罗马’”。

提示

引号把一个表达式变成这个表达式的名称。在每种情况下问问自己：语句的主语指称什么对象，一座城市、一个词还是一个语句。

答案

(a) 谈的是城市，为假，因为城市没有字。(b) 谈的是词，为真。(c) 谈的是词，为假，因为一个词不是首都。(d) 谈的是一个语句和一个词，为真。

练习题 4一张卡片的两面

一张卡片的一面写着语句 $A$ ：“语句 $B$ 是真的”；另一面写着语句 $B$ ：“语句 $A$ 是假的”。承认二值原则和真理模式，证明没有办法给 $A$ 和 $B$ 指派真值。如果 $B$ 改为说“语句 $A$ 是真的”，会怎样？

提示

为每个语句写出真理模式，把等价连接起来，直到得到一个把 $V(A)$ 与它自身联系起来的等价。在变体中，做同样的事，并检查哪些指派满足它。

答案

在第一种情形下得到 $V(A) \Leftrightarrow \neg V(A)$ ，与说谎者一样，尽管没有一个语句谈论自身。在变体中， $V(A) \Leftrightarrow V(B)$ 允许两种指派，两者都真或两者都假：没有矛盾，但也没有任何东西能在两者之间作出决定。

详细解答

解答

$\dato{A}{V(A) \Leftrightarrow V(B)}$
根据真理模式， $A$ 为真恰好当 $B$ 为真。
$\dato{B}{V(B) \Leftrightarrow F(A) \Leftrightarrow \neg V(A)}$
根据真理模式， $B$ 为真恰好当 $A$ 为假；根据二值原则，为假就是不为真。
$V(A) \Leftrightarrow \resaltar{\neg V(A)}$
把两个等价连接起来， $A$ 的真等价于它自身的否定，于是像说谎者那样推理：如果 $A$ 为真，它就不为真；如果它不为真，它就为真。
$V(A) \Leftrightarrow V(B) \Leftrightarrow V(A)$
在变体中， $B$ 的真理模式给出 $V(B) \Leftrightarrow V(A)$ ，它与第一个等价合起来，只要求两者具有相同的值：有两种一致的指派，没有矛盾。

练习题 5康托尔的对角线

设 $s_1, s_2, s_3, \ldots$ 是由零和一组成的无穷序列的任意一个列表，并用 $s_x(y)$ 记第 $y$ 项（所属序列为 $s_x$ ）。用对角线引理证明：序列 $d$ ，即由 $d(y) = 1$ （当 $s_y(y) = 0$ 时）和 $d(y) = 0$ （当 $s_y(y) = 1$ 时）定义的序列，不在列表中。并推出：没有一个编号列表包含所有由零和一组成的序列。

提示

取自然数为汇集 $D$ ，取关系 $R(x, y)$ 为断言 $s_x(y) = 1$ 。一个数 $b$ ，若使 $s_b = d$ ，会满足什么条件？

答案

如果 $d = s_b$ ，那么数 $b$ 会满足 $R(b, y) \Leftrightarrow \neg R(y, y)$ ，对所有 $y$ 都如此，而这是对角线引理所禁止的。因此 $d$ 与每个 $s_b$ 至少在第 $b$ 项上不同，没有一个列表包含所有序列。

详细解答

解答

$\dato{R}{R(x, y) \Leftrightarrow s_x(y) = 1}$
设 $D$ 为自然数的集合， $R(x, y)$ 为断言：第 $y$ 项，即 $s_x$ 的这一项，等于 $1$ 。
$\dato{d}{d(y) = 1 \Leftrightarrow \neg\left( s_y(y) = 1 \right)}$
根据定义， $d(y)$ 等于 $1$ ，恰好当 $s_y(y)$ 不等于 $1$ 。
$(\forall y \in D)\,\left( R(\resaltar{b}, y) \Leftrightarrow \neg R(y, y) \right)$
假设 $d$ 出现在列表的第 $b$ 个位置上，即 $d = s_b$ 。那么对所有 $y$ ， $R(b, y)$ 等价于 $d(y) = 1$ ，而后者等价于 $\neg R(y, y)$ 。
$d(b) \neq s_b(b)$
根据对角线引理，没有一个 $b$ 满足这个条件：序列 $d$ 不在列表中。具体地说，它与 $s_b$ 在第 $b$ 项上不同。
$(\forall b \in \mathbb{N})\,(d \neq s_b)$
由于列表是任意的，没有一个编号列表包含所有由零和一组成的序列：每个列表至少缺少它自己的对角线序列。