第1章预备知识 从引言可以看出本教材会假定读者有一定的数学基础。但是我们也注意到大量对逻 辑感兴趣的读者不一定对纯数学有那么强烈的兴趣。甚至有些读者会觉得太多的数学反 而会与我们的目的南辕北辙,会把辩证的“活”的逻辑搞得太机械以至弄“死”。这种怀 疑是有一定道理的。我们并不声称数学方法或更广义的理性方法是研究逻辑的唯一途径。 但我们要强调,这一点读者在后文也会看到,数理逻辑的一个重要的特点就是它能清楚地 告诉我们各种(包括数学)方法的局限,从而间接提示我们突破局限的方法和需要添加的 工具。 在本章中我们罗列一些预备知识,数学基础好的读者可以略过这一章。 第1节证明的必要性 数学不同于实验性科学,如物理或生命科学。对实验性科学来说,重要的是设计并动 手做实验,收集数据;根据观察到的事实,提岀理论并作岀预测,再用实验数据来检验理 论的正确性。数据(基本)吻合了,理论也就成功了。有极少数的特例问题不大。而数学 则不同。数学的论证必须是“滴水不漏”或是“无可置疑”的。不允许有任何例外。注意 在这一点上数学对论证的要求比思辨性科学(包括哲学)也要高。 我们看几个例子,说明仅仅列举大量事实不能代替数学论证。这也是普通归纳法的缺 陷 例11.我们称一个正整数p为一个素数,如果p≠1并且p只能被1和p整除。观察 31是一个素数,331是一个素数,3331也是一个素数,333和333也都是素数,是 不是所有形如33….3331的整数都是素数? 答案:不能,例如33331不是素数。 例12.费马在1637年注意到:对任何整数n≥3方程m2+y=2n没有x,y和z的正整 数解。经过几代数学家的努力,直到1995年,怀尔斯才证明了这一结论。在怀尔斯之前 人们验证了几乎人类计算极限内的所有整数,涉及的数字达到4,00.000的4,00.00次 方,超过了整个宇宙中所有基本粒子的数目,都没有发现例外。但这些都不能成为数学证
第 1 章 预备知识 从引言可以看出本教材会假定读者有一定的数学基础。但是我们也注意到大量对逻 辑感兴趣的读者不一定对纯数学有那么强烈的兴趣。甚至有些读者会觉得太多的数学反 而会与我们的目的南辕北辙，会把辩证的“活”的逻辑搞得太机械以至弄“死”。这种怀 疑是有一定道理的。我们并不声称数学方法或更广义的理性方法是研究逻辑的唯一途径。 但我们要强调，这一点读者在后文也会看到，数理逻辑的一个重要的特点就是它能清楚地 告诉我们各种（包括数学）方法的局限，从而间接提示我们突破局限的方法和需要添加的 工具。 在本章中我们罗列一些预备知识，数学基础好的读者可以略过这一章。 第 1 节 证明的必要性 数学不同于实验性科学，如物理或生命科学。对实验性科学来说，重要的是设计并动 手做实验，收集数据；根据观察到的事实，提出理论并作出预测，再用实验数据来检验理 论的正确性。数据（基本）吻合了，理论也就成功了。有极少数的特例问题不大。而数学 则不同。数学的论证必须是“滴水不漏”或是“无可置疑”的。不允许有任何例外。注意 在这一点上数学对论证的要求比思辨性科学（包括哲学）也要高。 我们看几个例子，说明仅仅列举大量事实不能代替数学论证。这也是普通归纳法的缺 陷。 例 1.1. 我们称一个正整数 p 为一个素数，如果 p ̸= 1 并且 p 只能被 1 和 p 整除。观察： 31 是一个素数，331 是一个素数，3331 也是一个素数，33331 和 333331 也都是素数，是 不是所有形如 33 · · · 3331 的整数都是素数？ 答案：不能，例如 333333331 不是素数。 例 1.2. 费马在 1637 年注意到：对任何整数 n ≥ 3 方程 x n + y n = z n 没有 x, y 和 z 的正整 数解。经过几代数学家的努力，直到 1995 年，怀尔斯才证明了这一结论。在怀尔斯之前， 人们验证了几乎人类计算极限内的所有整数，涉及的数字达到 4,000,000 的 4,000,000 次 方，超过了整个宇宙中所有基本粒子的数目，都没有发现例外。但这些都不能成为数学证 1
第1节证明的必要性 第1章预备知识 明。我们现在考察一些与之近似的命题:方程x3+y32+23=3没有x,y,z和v的正整 数解。方程x4+y4+z4=v4又如何呢? 答案:方程x4+y4+24=4有解958004+2175194+4145604=4224814。方程x3+ y3+z3=un3是否有正整数解留给读者解答。 注:首先我们没有贬低实验科学中观察及猜想的重要性。好的猜想需要深刻的洞察 力,经常需要神来之笔。其次,从具体例子着手研究也是数学中普遍实行的方法。我们只 不过想强调大量的个例并不构成数学证明。 在数学研究中,反例是非常重要的。错误的猜想经常是被反例推翻的。例如, 例1.1中的3333就是一个反例。这使前面7个例子不重要了,我们也不需要更 多的反例 那数学中怎样证实猜想呢?方法是给出数学证明。大体上说,我们从大家公认的事实 出发。这些公认的事实被称为“公理”。公理是数学证明的起点。接下来我们一步步地列 出一系列的命题,每一步都是根据逻辑规则得出的。这些逻辑规则保证如果你承认上一步 结论的正确性,你就一定承认下一步结论的正确性。在证明中,已经被证明的事实和公理 在任何时候都可以被引用。这一系列命题的终点就是我们要证实的猜想。一旦猜想被证明 了,它就被称为定理。 数学证明的目的是让读者相信其正确性。因此证明通常都是从简单到复杂依照逻辑 规则展开。与之无关的内容一概放弃。从证明中经常看不出数学家的思考过程。这也是数 学证明让初学者感到困惑的地方之一。 下面给出两个经典证明的例子。它们是古希腊数学的两颗明珠,既简单又优雅 例13.证明√2是无理数 证明:假定√2是有理数,即可以写成两个整数a和b之比"。我们可以进一步假定a和b 没有大于1的公因子。 ab 两边平方,再乘b2,得到 由于左边是偶数,右边必定也是,所以a是偶数。令a=2c并代入,得到 同样的理由告诉我们b也是偶数。因而与a和b没有大于1的公因子矛盾。所以不存在这 样的a和b,因而√2是无理数。 例1.4.证明存在无穷多个素数
第 1 节 证明的必要性 第 1 章 预备知识 明。我们现在考察一些与之近似的命题：方程 x 3 + y 3 + z 3 = w 3 没有 x, y, z 和 w 的正整 数解。方程 x 4 + y 4 + z 4 = w 4 又如何呢？ 答案：方程 x 4 + y 4 + z 4 = w 4 有解 958004 + 2175194 + 4145604 = 4224814。方程 x 3 + y 3 + z 3 = w 3 是否有正整数解留给读者解答。 注：首先我们没有贬低实验科学中观察及猜想的重要性。好的猜想需要深刻的洞察 力，经常需要神来之笔。其次，从具体例子着手研究也是数学中普遍实行的方法。我们只 不过想强调大量的个例并不构成数学证明。 在数学研究中，反例是非常重要的。错误的猜想经常是被反例推翻的。例如， 例 1.1 中的 333333331 就是一个反例。这使前面 7 个例子不重要了，我们也不需要更 多的反例。 那数学中怎样证实猜想呢？方法是给出数学证明。大体上说，我们从大家公认的事实 出发。这些公认的事实被称为“公理”。公理是数学证明的起点。接下来我们一步步地列 出一系列的命题，每一步都是根据逻辑规则得出的。这些逻辑规则保证如果你承认上一步 结论的正确性，你就一定承认下一步结论的正确性。在证明中，已经被证明的事实和公理 在任何时候都可以被引用。这一系列命题的终点就是我们要证实的猜想。一旦猜想被证明 了，它就被称为定理。 数学证明的目的是让读者相信其正确性。因此证明通常都是从简单到复杂依照逻辑 规则展开。与之无关的内容一概放弃。从证明中经常看不出数学家的思考过程。这也是数 学证明让初学者感到困惑的地方之一。 下面给出两个经典证明的例子。它们是古希腊数学的两颗明珠，既简单又优雅。 例 1.3. 证明 √ 2 是无理数。 证明: 假定 √ 2 是有理数，即可以写成两个整数 a 和 b 之比 a b。我们可以进一步假定 a 和 b 没有大于 1 的公因子。 √ 2 = a b 。 两边平方，再乘 b 2，得到 2b 2 = a 2。 由于左边是偶数，右边必定也是，所以 a 是偶数。令 a = 2c 并代入，得到 b 2 = 2c 2。 同样的理由告诉我们 b 也是偶数。因而与 a 和 b 没有大于 1 的公因子矛盾。所以不存在这 样的 a 和 b，因而 √ 2 是无理数。 例 1.4. 证明存在无穷多个素数。 2
第1章预备知识 第2节集合 证明:假如只有有穷多个素数,比方说n个。把它们全列出来:p1,p2,…,Pn。考察一个 新的整数 p1p2…Pn+1。 它不能被任何素数整除。这与任何整数都可以被分解成素数乘积这一事实矛盾。因而素数 是无限多的。 以上两个证明也是所谓“反证法”的典型例子。反证法是这类要排除无穷多种情况或 直接涉及无穷的证明的有力工具。 第2节集合 在中学我们学过用A={a0,a1,…,an}表示A是一个集合,a0,a1,…,an是它的元 素。但集合并不总是有有穷多个元素,无穷的集合,例如全体自然数的集合,有时会记 作N={0,1,2,},但这样的写法不能表示不可数的集合,例如全体实数的集合R就 不能以这种方式表示,因此更方便的是用A={x:P(x)}表示一个集合,其中P是 个特定的性质。例如,{x:x是红的}表示所有红色事物组成的集合。一般用x∈A表 示x是A的元素,读作x属于A,一般用xgA表示x不是A的元素。 外延原理关于集合一个最重要的性质是,它是完全由其元素决定的,而与其它的因 素,如我们怎样描述集合里的元素,没有关系。比如,{x∈R:对所有的实数y都满足 x+y=y}和{x∈R:对所有的实数z都满足xxz=x}是同一个集合,因为它们都只 包含实数0这一个元素。所以我们有所谓外延原理:A=B当且仅当A和B有相同的元 素。一方面如果A=B则必然有它们的元素相同,这实际上就是莱布尼兹的不可分辨原 理。另一方面如果集合A的元素都是集合B的元素,反之集合B的元素也都是集合A的 元素,那我们就断定A=B,这是我们证明两个集合相等的基本方法。 集合的交、并、差如果A,B是集合,则将A,B中元素聚集在一起构成新的集合, 称为A与B的并集,记作AUB。所以AUB={x:x∈A或者x∈B}。类似的 同时既属于A又属于B的元素构成A与B的交集,记作A∩B。显然,A∩B= x:x∈A并且x∈B}。最后,A与B的差,A-B指的是属于A但是不属于B的元素, 即A-B={x:x∈A但是xgB} 子集、幂集和空集如果A是一个集合,那么A中的一部分元素可以构成一个新的集合 B,称为A的一个子集,记为BcA。因此,B是A的子集当且仅当所有B的元素都 是A的元素。显然,每个集合都是自己的子集。如果BCA并且B≠A,就称B是A的 真子集。如果需要特别表明,我们会以B≤A表示B是A的真子集
第 1 章 预备知识 第 2 节 集合 证明: 假如只有有穷多个素数，比方说 n 个。把它们全列出来：p1, p2, · · · , pn。考察一个 新的整数 q = p1p2 · · · pn + 1。 它不能被任何素数整除。这与任何整数都可以被分解成素数乘积这一事实矛盾。因而素数 是无限多的。 以上两个证明也是所谓“反证法”的典型例子。反证法是这类要排除无穷多种情况或 直接涉及无穷的证明的有力工具。 第 2 节 集合 在中学我们学过用 A = {a0, a1, · · · , an} 表示 A 是一个集合，a0, a1, . . . , an 是它的元 素。但集合并不总是有有穷多个元素，无穷的集合，例如全体自然数的集合，有时会记 作 N = {0, 1, 2, . . .}，但这样的写法不能表示不可数的集合，例如全体实数的集合 R 就 不能以这种方式表示，因此更方便的是用 A = {x : P(x)} 表示一个集合，其中 P 是一 个特定的性质。例如，{ x : x 是红的} 表示所有红色事物组成的集合。一般用 x ∈ A 表 示 x 是 A 的元素，读作 x 属于 A，一般用 x ̸∈ A 表示 x 不是 A 的元素。 外延原理 关于集合一个最重要的性质是，它是完全由其元素决定的，而与其它的因 素，如我们怎样描述集合里的元素，没有关系。比如，{x ∈ R : 对所有的实数 y 都满足 x + y = y} 和 {x ∈ R : 对所有的实数 z 都满足 x × z = x} 是同一个集合，因为它们都只 包含实数 0 这一个元素。所以我们有所谓外延原理：A = B 当且仅当 A 和 B 有相同的元 素。一方面如果 A = B 则必然有它们的元素相同，这实际上就是莱布尼兹 的不可分辨原 理。另一方面如果集合 A 的元素都是集合 B 的元素，反之集合 B 的元素也都是集合 A 的 元素，那我们就断定 A = B，这是我们证明两个集合相等的基本方法。 集合的交、并、差 如果 A, B 是集合，则将 A, B 中元素聚集在一起构成新的集合， 称为 A 与 B 的并集，记作 A ∪ B。所以 A ∪ B = { x : x ∈ A 或者 x ∈ B } 。类似的， 同时既属于 A 又属于 B 的元素构成 A 与 B 的交集，记作 A ∩ B。显然， A ∩ B = { x : x ∈ A 并且 x ∈ B } 。最后，A 与 B 的差，A−B 指的是属于 A 但是不属于 B 的元素， 即 A − B = { x : x ∈ A 但是 x ̸∈ B } 。 子集、幂集和空集 如果 A 是一个集合，那么 A 中的一部分元素可以构成一个新的集合 B，称为 A 的一个子集，记为 B ⊂ A。因此， B 是 A 的子集当且仅当所有 B 的元素都 是 A 的元素。显然，每个集合都是自己的子集。如果 B ⊂ A 并且 B ̸= A，就称 B 是 A 的 真子集。如果需要特别表明，我们会以 B ( A 表示 B 是 A 的真子集。 3
第2节集合 第1章预备知识 A的所有子集组成的集合称为A的幂集,记作P(A)={x:rcA} 有一个特殊的集合,它不包含任何元素,称为空集,一般记作的。空集是任何集合的 子集,怎样论证这一点对初学者是一个很好的练习。 集合族如果集合的元素本身也是集合,则这样的集合一般称为集合的族。例如 F={F0,F1,…,Fn-1} 表示n个集合的族。对于集合族,我们可以定义其上的一般并 ∪F={x:至少存在一个F∈F,∈F} 如果F≠0,则还可定义它的一般交 ∩F={x:对于每一个F∈F,x∈F} 注意:如果F是空集,则它的一般并仍然是空集,但是此时它的一般交却没有定义。1特 别地 ∪{,B}=AUB,∩{A.,B}=A∩B 为了清楚表示集合族,一般需要一个下标集。虽然理论上任何集合都可以用做下标集,但 最常用的下标集是全体自然数的集合N或者它的子集。对因此上面的集合族也可表示为 F={F2:0≤i<m} 而更一般地, {F1:i∈N} 表示一个无穷的集合族。在这种记法下,集合族F={F,F1,,Fn-1}的一般交和一般 并也表示为 ∪F=∪F,∩F=∩ 类似地, ∪{F:i∈N=∪F,∩{F:i∈N}=∩F 由于F是空集意味着没有F∈F,因此命题“对于每一个F∈F,x∈F”对任何x就总是真的,即所有x都属 于∩F,但这是不允许的,因为包含所有对象的“集合”是一个矛盾的概念
第 2 节 集合 第 1 章 预备知识 A 的所有子集组成的集合称为 A 的幂集，记作 P(A) = {x : x ⊂ A}。 有一个特殊的集合，它不包含任何元素，称为空集，一般记作 ∅。空集是任何集合的 子集，怎样论证这一点对初学者是一个很好的练习。 集合族 如果集合的元素本身也是集合，则这样的集合一般称为集合的族。例如， F = {F0, F1, . . . , Fn−1} 表示 n 个集合的族。对于集合族，我们可以定义其上的一般并： ∪ F = { x : 至少存在一个 F ∈ F, x ∈ F } 。 如果 F ̸= ∅，则还可定义它的一般交 ∩ F = { x : 对于每一个 F ∈ F, x ∈ F } 。 注意：如果 F 是空集，则它的一般并仍然是空集，但是此时它的一般交却没有定义。1 特 别地， ∪ {A, B} = A ∪ B, ∩ {A, B} = A ∩ B。 为了清楚表示集合族，一般需要一个下标集。虽然理论上任何集合都可以用做下标集，但 最常用的下标集是全体自然数的集合 N 或者它的子集。对因此上面的集合族也可表示为： F = {Fi : 0 ≤ i < n}。 而更一般地， F = {Fi : i ∈ N} 表示一个无穷的集合族。在这种记法下，集合族 F = {F0, F1, . . . , Fn−1} 的一般交和一般 并也表示为： ∪ F = n∪−1 i=0 Fi , ∩ F = n∩−1 i=0 Fi。 类似地， ∪ {Fi : i ∈ N} = ∪ i∈N Fi , ∩ {Fi : i ∈ N} = ∩ i∈N Fi。 1由于 F 是空集意味着没有 F ∈ F，因此命题“对于每一个 F ∈ F, x ∈ F”对任何 x 就总是真的，即所有 x 都属 于 ∩ F，但这是不允许的，因为包含所有对象的“集合”是一个矛盾的概念。 4
第1章预备知识 第3节关系 第3节关系 在数学研究中,人们关心的不仅仅是集合,在更多的时候,人们关心的是集合上的结 构。用日常语言来说,一个集合就像一堆砖头,杂乱无章。我们既可以把这堆砖头建成 堵墙,又可以盖一座楼等等。这里的墙或者楼就是所谓的结构。砖头还是砖头,而墙和楼 的不同在于砖与砖之间的关系不同。数学结构也是一样,通常是由一个集合配上若干关系 或者运算所组成的。比如,把自然数集N和自然数上的大小顺序放在一起,我们就有 个自然的“序结构”(N,<),其中 0<1<2<3< 在所有自然数的集合N上我们还可以造其它的序,比如,下面的< 6-4<20-135<7 就给我们另外一个序结构(N,<)。构成这两个结构的集合都是N,但作为结构它们是不同 的,比如第一个结构有最小元,第二个则没有。在我们继续讨论结构之前,先要回顾一下 关系和函数的基本概念。 最简单的关系是二元关系,它可看作一种对应或者广义的映射。每当有第一个元素 时,我们总系之于第二个元素。所以,关系的要素是成对出现的对象,而且这两个对象 是有顺序的,这就需要引入有序对的概念。一般用(a,b)表示由a和b组成的有序对。虽 然{a,b}={b,a},但除非a=b,否则(a,b)≠(b,a)。因此,有序对的“有序性”就是 任何两个有序对(a,b),(a,b),(a,b)=(a,b)当且仅当a=a'且b=b。 令X和Y为集合,则X和Y的卡氏积2定义为 X×Y={(x,y)|x∈X并且y∈Y 如果X=Y,则将X×X简记为X2。 我们称一集合R为集合X,Y之间的一个二元关系,R≤X×Y。这样,二元关 系R的所有元素都是有序对,即,对任意z∈R存在x∈X和y∈Y满足z=(x,y) 般地用R(x,y)表示(x,y)∈R,称和y有关系R。有时习惯地写作xRy。把关系视为 有序对的集合,初学者可能不习惯,因为它并没有直接告诉我们这个关系是什么。我们 之所以这样定义,原因和前面提到的集合的外延原理是一样的:我们并不关心我们怎样 描述R。两个不同的描述,只要它们给出的有序对是一样的,它们就是同一个关系。比如 R1={(x,y)∈N2:y+1=}和R2={(x,y)∈N2:x2=y2+2y+1}是自然数上的同 个关系,尽管我们对它们的描述不同 2卡氏积, Cartesian product,因笛卡尔而得名。笛卡尔, Rene descartes(1596-1650),法国哲学家,数学家
第 1 章 预备知识 第 3 节 关系 第 3 节 关系 在数学研究中，人们关心的不仅仅是集合，在更多的时候，人们关心的是集合上的结 构。用日常语言来说，一个集合就像一堆砖头，杂乱无章。我们既可以把这堆砖头建成一 堵墙，又可以盖一座楼等等。这里的墙或者楼就是所谓的结构。砖头还是砖头，而墙和楼 的不同在于砖与砖之间的关系不同。数学结构也是一样，通常是由一个集合配上若干关系 或者运算所组成的。比如，把自然数集 N 和自然数上的大小顺序放在一起，我们就有一 个自然的“序结构”(N, <)，其中： 0 < 1 < 2 < 3 < · · · 在所有自然数的集合 N 上我们还可以造其它的序，比如，下面的 ≺ · · · ≺ 6 ≺ 4 ≺ 2 ≺ 0 ≺ 1 ≺ 3 ≺ 5 ≺ 7 · · · 就给我们另外一个序结构 (N, ≺)。构成这两个结构的集合都是 N，但作为结构它们是不同 的，比如第一个结构有最小元，第二个则没有。在我们继续讨论结构之前，先要回顾一下 关系和函数的基本概念。 最简单的关系是二元关系，它可看作一种对应或者广义的映射。每当有第一个元素 时，我们总系之于第二个元素。所以，关系的要素是成对出现的对象，而且这两个对象 是有顺序的，这就需要引入有序对的概念。一般用 (a, b) 表示由 a 和 b 组成的有序对。虽 然 {a, b} = {b, a}，但除非 a = b，否则 (a, b) ̸= (b, a)。因此，有序对的“有序性”就是： 任何两个有序对 (a, b),(a ′ , b′ )， (a, b) = (a ′ , b′ ) 当且仅当 a = a ′ 且 b = b ′。 令 X 和 Y 为集合，则 X 和 Y 的卡氏积 2 定义为： X × Y = { (x, y) | x ∈ X 并且 y ∈ Y } 。 如果 X = Y ，则将 X × X 简记为 X2 。 我们称一集合 R 为集合 X, Y 之间的一个二元关系， R ⊆ X × Y 。这样，二元关 系 R 的所有元素都是有序对，即，对任意 z ∈ R 存在 x ∈ X 和 y ∈ Y 满足 z = (x, y) 。一 般地用 R(x, y) 表示 (x, y) ∈ R ，称 x 和 y 有关系 R 。有时习惯地写作 xRy 。把关系视为 有序对的集合，初学者可能不习惯，因为它并没有直接告诉我们这个关系是什么。我们 之所以这样定义，原因和前面提到的集合的外延原理是一样的：我们并不关心我们怎样 描述 R。两个不同的描述，只要它们给出的有序对是一样的，它们就是同一个关系。比如 R1 = {(x, y) ∈ N 2 : y + 1 = x} 和 R2 = {(x, y) ∈ N 2 : x 2 = y 2 + 2y + 1} 是自然数上的同一 个关系，尽管我们对它们的描述不同。 2卡氏积，Cartesian product，因笛卡尔而得名。笛卡尔，René Descartes （1596 - 1650），法国哲学家，数学家。 5