复旦大学：《数理逻辑》课程教学资源（讲义）第1章预备知识.pdf_大学文库

第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

第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

第1章预备知识第4节函数根据定义每一个函数都是一个关系,所以我们前面定义的关系的定义域、值域、象、逆等等概念在这里仍然适用。并且,与关系类似,函数可以推广到n元的情形。一般来说,如果函数的定义域是一个n元有序组的集合,则称为n元函数。注意到n元函数是个n+1元关系。例如f:An→A是A上的n元函数,这样的函数经常称为A上n元运算。自然数上的加法是一个二元运算的例子。由于我们可以将n元序组看作一个对象, 因此以下对函数的讨论可以限制在一元函数的情形定理12.如果∫和g是函数,则它们的复合go∫也是函数。它的定义域为dom(gof)= ∫- dong。并且,对所有r∈dom(gof),(gof)(x)=g(f(x) 证明:(首先注意我们在定义∫是函数时,只需要f是有序对(比如A×B)的子集并满足“输出唯一性”;我们并没有明确给出∫的定义域。在本题中如果我们限制好了∫:A→B且g:B→C,那整个问题就简单多了。我们把本题当作有序对的练习好了。) 设(x,a1),(x,2)∈(g°∫),根据定义,存在v,y,(x,)∈f,(,x1)∈g且(x,y2)∈ f,(v2,2)∈g。由f是函数,可得y=v,再由g是函数,x1=z2所以gof是函数至于第二个命题,根据定义域的定义,我们有x∈dom(go∫)当且仅当存在z使得(x,2)∈gof;再根据复合的定义,我们有r∈dom(gof)当且仅当存在z和y使得(x,y)∈f且(y,x)∈g。因此,一方面,如果x∈dom(gf)则x∈dom(f)且f(x)∈ dom(g),也就有x∈dom(f)且x∈f-ldom(g。另一方面,如果x∈dom(f)且x∈ f-ldom(g)],我们有(x,y)∈f且y∈dom(g),也就有z和y使得(x,y)∈f且(v,2)∈ 所以x∈do 最后,设r∈dom(go∫),且(go∫)(x)=z。根据复合的定义,存在y,f(x)= y且g(y)=z,因此g(f(x)=9(y)=z=(gof)(x) 函数f:X→Y称为一一的或单射,如果对所有的x1,x2∈X都有x1≠x2蕴涵f(x1)≠f(x2),函数f:X→Y称为满射,如果ran(f)=Y;既是单射又是满射的函数称为双射,或称∫为X和Y之间的一个一一对应。如果f:X→Y是函数,A是X的子集,则∫到A上的限制,记作f「A,是由A到Y的函数,并且对于每一x∈A,都有fA(x)=f(x)。如果g是f的一个限制, 则称f是g的一个扩展函数的概念在数学中是非常基本的,成为数学语言的一部分,也就是说,人们经常会利用函数来描述一些其它的概念。逻辑中也是一样。下面举几个例子 (1)在中学我们学过等差数列和等比数列等概念。它们都是序列的例子。所谓序列 ao,a1,a2,,直观上说就是一个无穷的数串,并且我们能够分辨哪一个是它的第项,哪个是第二项等等。序列的严格定义通常是用函数来完成的。例如,一个实数序列就是一个从N到R的一个函数f,它的第n项就是f(n)

第 1 章预备知识第 4 节函数根据定义每一个函数都是一个关系，所以我们前面定义的关系的定义域、值域、象、逆等等概念在这里仍然适用。并且，与关系类似，函数可以推广到 n 元的情形。一般来说，如果函数的定义域是一个 n 元有序组的集合，则称为 n 元函数。注意到 n 元函数是一个 n + 1 元关系。例如 f : An → A 是 A 上的 n 元函数，这样的函数经常称为 A 上 n 元运算。自然数上的加法是一个二元运算的例子。由于我们可以将 n 元序组看作一个对象，因此以下对函数的讨论可以限制在一元函数的情形。定理 1.2. 如果 f 和 g 是函数，则它们的复合 g ◦ f 也是函数。它的定义域为 dom(g ◦ f) = f −1 [domg]。并且，对所有 x ∈ dom(g ◦ f) ，(g ◦ f)(x) = g(f(x)) 。证明: （首先注意我们在定义 f 是函数时，只需要 f 是有序对（比如 A × B）的子集，并满足“输出唯一性”；我们并没有明确给出 f 的定义域。在本题中如果我们限制好了 f : A → B 且 g : B → C，那整个问题就简单多了。我们把本题当作有序对的练习好了。）设 (x, z1),(x, z2) ∈ (g◦f)，根据定义，存在 y1, y2，(x, y1) ∈ f，(y1, z1) ∈ g 且 (x, y2) ∈ f，(y2, z2) ∈ g。由 f 是函数，可得 y1 = y2，再由 g 是函数， z1 = z2。所以 g ◦ f 是函数。至于第二个命题，根据定义域的定义，我们有 x ∈ dom(g ◦ f) 当且仅当存在 z 使得 (x, z) ∈ g ◦ f；再根据复合的定义，我们有 x ∈ dom(g ◦ f) 当且仅当存在 z 和 y 使得 (x, y) ∈ f 且 (y, z) ∈ g。因此，一方面，如果 x ∈ dom(g ◦ f) 则 x ∈ dom(f) 且 f(x) ∈ dom(g)，也就有 x ∈ dom(f) 且 x ∈ f −1 [dom(g)]。另一方面，如果 x ∈ dom(f) 且 x ∈ f −1 [dom(g)]，我们有 ∃y(x, y) ∈ f 且 y ∈ dom(g)，也就有 z 和 y 使得 (x, y) ∈ f 且 (y, z) ∈ g，所以 x ∈ dom(g ◦ f)。最后，设 x ∈ dom(g ◦ f) ，且 (g ◦ f)(x) = z。根据复合的定义，存在 y，f(x) = y 且 g(y) = z，因此 g(f(x)) = g(y) = z = (g ◦ f)(x)。函数 f : X → Y 称为一一的或单射，如果对所有的 x1, x2 ∈ X 都有 x1 ̸= x2 蕴涵 f(x1) ̸= f(x2)，函数 f : X → Y 称为满射，如果 ran(f) = Y ；既是单射又是满射的函数称为双射，或称 f 为 X 和 Y 之间的一个一一对应。如果 f : X → Y 是函数， A 是 X 的子集，则 f 到 A 上的限制，记作 f A，是由 A 到 Y 的函数，并且对于每一 x ∈ A，都有 f A(x) = f(x)。如果 g 是 f 的一个限制，则称 f 是 g 的一个扩展。函数的概念在数学中是非常基本的，成为数学语言的一部分，也就是说，人们经常会利用函数来描述一些其它的概念。逻辑中也是一样。下面举几个例子。 (1) 在中学我们学过等差数列和等比数列等概念。它们都是序列的例子。所谓序列 a0, a1, a2, . . .，直观上说就是一个无穷的数串，并且我们能够分辨哪一个是它的第一项，哪个是第二项等等。序列的严格定义通常是用函数来完成的。例如，一个实数序列就是一个从 N 到 R 的一个函数 f，它的第 n 项就是 f(n)。 9

第 5 节等价关系与划分第 1 章预备知识 (2) 集合论中基数的比较也是利用函数来描述的。我们称两个集合 A 和 B 具有相同的基数，如果存在一个双射 f : A → B。直观上说，A 和 B 具有相同的基数就是说 A 和 B 具有同样多的元素。至于为什么这样定义，我们在集合论的课程中会仔细讲。在习题中，我们会看到一些例子，说明有些集合会和它的某个真子集具有相同的基数。 (3) 在后文中，我们经常会给一些逻辑符号指派意义，这也是利用函数来描述的。例如， S 是一个抽象符号的集合，而 A 是一个已知概念的集合，一个函数 f : S → A 可以被视为给 S 中的符号指派它们的意义，或者说 f 是一个解释。第 5 节等价关系与划分如果有一类物体，尽管它们各不相同，但就我们关心的性质来说，它们的表现是一样的，则我们很自然地把它们等同起来，不加区分。比如，自然数 7 和 4 不相等，但如果我们只关心模 3 的算术的话，7 和 4 的性质完全一样，因为 7 ≡ 4 (mod 3)。因此我们完全可以把 7 和 4 当成一个数来处理。上面的想法自然引导我们考察等价关系和等价类。定义 1.1. 令 R ⊂ X2 为二元关系，则我们称 (1) R 是自反的如果对所有的 x ∈ X，R(x, x)； (2) R 是对称的如果对所有的 x, y ∈ X，如果 R(x, y) 则 R(y, x)； (3) R 是传递的如果对所有的 x, y, z ∈ X，如果 R(x, y)，且 R(y, z)，则 R(x, z)； (4) R 是一个等价关系如果 R 是自反、对称、传递的。习惯上用 ∼ 表示等价关系；如果 ∼ 为 X 上的一个等价关系，并且 x ∼ y，则我们称 x 与 y 等价。例 1.8. (1) 如果 P 代表所有人的集合，如下定义 P 上的二元关系： D = { (x, y) | x 是 y 的后代} ; (1.1) B = { (x, y) | 至少有一个 x 的祖先也是 y 的祖先} ; (1.2) S = { (x, y) | x 的父母是 y 的父母} 。 (1.3) D 不是自反的，也不是对称的，但是传递的； B 是自反的，对称的，却不是传递的；最后， S 是等价关系。 10

复旦大学：《数理逻辑》课程教学资源（讲义）第1章 预备知识

复旦大学：《数理逻辑》课程教学资源（讲义）第1章预备知识