离散数学基础-课件汇 第1-4章 集合 -初等数论基础

离散数学基础1目录CONTENTS第一部分

集合论第二部分

初等数论

第三部分

图论第四部分

组合数学

第五部分

代数结构

第六部分

数理逻辑

第七部分

形式语言与自动机

2集合论01.集合02.二元关系

03.函数

Partone第一部分301集合的基本概念集合的运算及性质有限集的计数

集合41.1集合的基本概念

5常见的表示集合的方法(1/2)

6常见的表示集合的方法(2/2)

7集合间的关系(1/3)

8定义1.1.1集合间的关系(2/3)例如，{x∈2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

9定义1.1.2定义1.1.3集合间的关系(3/3)例如，{x∈x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

10定义1.1.4定义1.1.5多重集例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

111.2集合的运算及性质正如算术运算处理数字，集合运算也遵循一系列规则，它们以集合作为操作对象，通过既定的运算规则，生成一个新的集合作为结果.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

12定义1.2.1集合的运算例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

13解例1.2.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.集合的运算

14集合的运算例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

15集合运算的性质集合的并、交、差和补运算满足很多恒等式，概括如下.

16定理1.2.1定理1.2.1的证明根据定义1.1.2，要证明两个集合相等，只需要证明这两个集合互相包含.在此我们选证分配律中的第一个等式和德摩根律中的第二个等式，其他留给读者完成.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

17证明定理1.2.1的证明例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

18证明集族例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

19广义并与广义交

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

20定义1.2.2定义1.2.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.广义并与广义交例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

21注1.2.1例1.2.2广义并与广义交例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

22笛卡尔积

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

23定义1.2.4笛卡尔积例如，{x∈2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

24例1.2.3笛卡尔积例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

25定义1.2.5笛卡尔积例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

我们重回例1.2.3.

26例1.2.4例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.1.3有限集的计数

27使用维恩图计数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

图1.3.1

宠物调查维恩图

28例1.3.1使用维恩图计数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

29例1.3.2使用维恩图计数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

图1.3.2

运动调查维恩图30例1.3.2解使用维恩图计数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

31例1.3.2解（续）包含排斥原理例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.事实上，等式（1.3.1）和（1.3.2）对任意有限集都是成立的，我们甚至可以将其推广到更一般的情形——包含排斥原理（也称容斥原理）.

定理1.3.1（包含排斥原理）例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

32证明包含排斥原理例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

定理1.3.1证明（续）

33包含排斥原理例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.定理1.3.1证明（续）将式（1.3.4）和（1.3.6）代入（1.3.5），得故式（1.3.3）成立，因此完成了定理的证明.

34包含排斥原理例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

35解例1.3.3包含排斥原理例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

36推论1.3.102关系的定义及运算关系的性质等价关系与划分偏序关系

二元关系372.1二元关系的定义及运算

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

38定义2.1.1二元关系

39二元关系例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

40例2.1.1常见关系例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

41例2.1.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.关系的表示——关系矩阵

42关系的表示——关系矩阵例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

43例2.1.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.关系的表示——关系矩阵

44关系的表示——关系矩阵

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

45例2.1.4关系的运算

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

46例2.1.5关系的运算——求逆例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

47定义2.1.2例2.1.6关系的运算——复合例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

48定义2.1.3例2.1.7关系的运算——复合例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

49例2.1.7（续）逆关系和复合运算的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

在关系复合运算的基础上，可以如下归纳定义关系的幂运算.定理2.1.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

50定义2.1.4例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.关系的幂运算

51关系的幂运算例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

52例2.1.8解例2.1.8关系的幂运算例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

53例2.1.8解（续）关系的幂运算合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

54例2.1.8解（续）2.2关系的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

本节介绍关系常见的5种性质：自反性、反自反性、对称性、反对称性和传递性.

55定义2.2.1关系的性质—自反性和反自反性例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

56解例2.2.1关系的性质—对称性和反对称性例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

57定义2.2.2关系的性质—自反性和反自反性例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

58解例2.2.2关系的性质—传递性

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

59定义2.2.3解例2.2.3关系的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.定理2.2.1

60关系的性质定理2.2.1证明例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

61关系的性质定理2.2.1证明(续)例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

62关系的性质表2.2.1

关系性质的特征表示形式性质自反性反自反性对称性反对称性传递性集合表达式关系矩阵矩阵是对称矩阵关系图每个顶点都有自环每个顶点都没有自环如果两个顶点之间有边，那么一定是一对方向相反的边（无单边）如果两个顶点之间有边，那么一定只有一条有向边（无双向边）632.3等价关系与划分证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

64定义2.3.1定义2.3.2等价关系与划分例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

65例2.3.1等价类的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.定理2.3.1证明

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

定理2.3.166等价类的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

定理2.3.1证明（续）例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

67商集例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

68定义2.3.3划分例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

69定义2.3.4划分例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

70解

例2.3.2划分不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

71解例2.3.3划分例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

图2.3.1

三元集的所有划分

72例2.3.3（续）关系闭包例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

73定义2.3.5例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.关系闭包

74闭包的构造例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

75证明命题2.3.1闭包的构造

76例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

证明命题2.3.2闭包的构造

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

77定理2.3.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

证明闭包的构造例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

78定理2.3.2证明（续）闭包的构造例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

79注2.3.22.4偏序关系例如，{x∈2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

80定义2.4.1偏序关系例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

81例2.4.1哈斯图利用偏序关系的自反性、反对称性和传递性，可以简化一个偏序关系的关系图，得到偏序集的哈斯图.为了说明哈斯图的画法，需要定义偏序集中元素的覆盖关系.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

82定义2.4.2哈斯图{x∈R

2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性不难证明，空集是唯一的，所以前文用∅表示空集是合理的.两个哈斯图如图2.4.1所示.

83解例2.4.2哈斯图反过来，给定一个哈斯图，我们也能立即得到对应的偏序集.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

84解例2.4.3偏序集的特殊元素例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

85定义2.4.3偏序集的特殊元素例如，{x∈R|x2=1}={1,−1}；N=Z

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

86解例2.4.4偏序集的界例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

87定义2.4.4偏序集的界基于最小上界和最大下界，我们可以定义一类特殊的偏序集——格.格在程序验证、数据库和编译器设计等领域都有着广泛的应用.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

88定义2.4.5例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例2.4.5拓扑排序在日常生活中，任务之间往往存在依赖关系，某些任务可能依赖于其他任务的完成，因此我们经常用偏序关系来约束这些任务的完成顺序.然而，尽管这些约束条件对任务施加了偏序关系，任务实际上必须按照某种顺序完成.我们面临的挑战是将偏序关系扩展为全序关系——也就是说，构建一个保持偏序关系所有约束条件，同时使以前无法比较的元素变成可比较的全序关系.为此，先引入相容性的概念.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

一般地，对于给定的偏序，可能存在多个与之相容的全序，这意味着拓扑排序并不是唯一的.为了介绍拓扑排序算法，我们需要下面的引理和定理.89拓扑排序例如，{x∈R|x，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

90证明引理2.4.1拓扑排序证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

91证明定理2.4.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.拓扑排序算法2.4.1给出了基于定理2.4.1及其证明的拓扑排序算法的伪码.

92拓扑排序例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

93解例2.4.6拓扑排序例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

图2.4.3

任务顺序关系图图2.4.4

任务偏序的哈斯图94例2.4.7例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

解03函数的基本概念函数的复合与逆函数无限集的计数

函数953.1函数的基本概念函数是二元关系的一种特殊形式，通常被理解为一种输入与输出的对应关系：每一个输入都唯一对应一个输出.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

96定义3.1.1函数的基本概念例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

97解例3.1.1常见的函数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

98定义3.1.2

常见的函数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

99定义3.1.2(续)常见的函数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

100定义3.1.2(续)定义3.1.3常见的函数的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

101命题3.1.1

递归定义函数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

除了常见的解析表达式、图像法、列表法等表示函数的方式外，在计算机科学中经常会遇到递归定义函数的情形.事实上，当函数的定义域是通过1.1节的归纳定义法给出时，递归往往提供了一种便捷的确定函数取值的方法，此时，函数的定义自然地与定义域的归纳性质相吻合.102例3.1.2递归定义函数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

103例3.1.2（续）函数的像和原像例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

104定义3.1.4函数的像和原像例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

105定义3.1.5函数的像和原像例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

106注3.1.2函数的像和原像例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

107例3.1.3函数的像和原像

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

108解例3.1.43.2函数的复合与逆函数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.函数是一种特殊的二元关系，函数的复合和逆函数分别对应关系的复合和逆关系.

图3.2.1

函数合成交换图109定义3.2.1函数的复合例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

110例3.2.1函数的复合例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

下面是函数复合的两个基本性质，其中第一个性质表明函数复合满足结合律，第二个性质说明了恒等函数在复合中的特殊作用.图3.2.2和图3.2.3分别图示了这两个性质.图3.2.2

函数复合满足结合律图3.2.3

恒等函数与一般函数的复合111命题3.2.1函数的复合例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

112证明命题3.2.2函数的复合

113函数的复合例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

函数作为特殊的关系，通过关系的求逆运算，可以得到一个逆关系，但一般情况下这个逆关系不一定是函数.

图3.2.4

可逆函数114定义3.2.2函数的复合例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

115注3.2.1函数可逆的充要条件例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

116证明命题3.2.3函数可逆的充要条件

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

117解例3.2.2函数可逆的充要条件例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

118定理3.2.13.3无限集的计数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

在1.3节，我们描述性地介绍了有限集和无限集，并引入了表示有限集中元素数量的概念——基数（势），本节我们将基于双射，进一步形式化这些概念，比较两个无限集所含元素个数的“多少”.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

119定义3.3.1例3.3.1无限集的计数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

120例3.3.1（续）等势的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

121注3.3.1命题3.3.1等势的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

122定义3.3.2可数集例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

在可计算性理论和程序语言理论中经常要考虑函数是否可计算、程序是否终止的问题，就会用到“可数”的概念.下面给出可数集的定义.

123定义3.3.3可数集例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

124证明例3.3.2可数集集是合理的.

图3.3.1

正有理数排序

125例3.3.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

证明可数集集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

126证明例3.3.4可数集例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

127例3.3.4证明（续）可数集例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

128证明命题3.3.2可数集例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

129命题3.3.2证明（续）可数集例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

130证明注3.3.2命题3.3.3基数对于一般的无限集，只能通过基数衡量两个集合的相对大小.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

下面给出基数研究中的一个关键定理，该定理归功于施罗德和伯恩斯坦（F.Bernstein，1878–1956）.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

定理3.3.1(施罗德-伯恩斯坦定理)131定义3.3.4基数例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

132证明例3.3.5注3.3.3康托尔定理例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

定理3.3.2（康托尔定理）

133证明康托尔定理例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

134康托尔定理证明（续）康托尔定理例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

135证明推论3.3.1初等数论04.初等数论基础Parttwo第二部分13604整除性素数同余在信息科学中的应用

初等数论基础1374.1整除性例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈Rx2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

138定义4.1.1整除的基本性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

定理4.1.1（带余除法）139命题4.1.1整除的基本性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

140证明定理4.1.1证明整除的基本性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

141定义4.1.2定义4.1.3注4.1.1整除的基本性质例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

基于引理4.1.1，我们可得到下面的欧几里得算法.该算法也称作辗转相除法.

142证明引理4.1.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

143证明定理4.1.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

144例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

145解例4.1.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

146证明定理4.1.3（贝祖等式）例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

147推论4.1.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.欧几里得算法

148解例4.1.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最大公因数的基本性质

149证明证明命题4.1.2推论4.1.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最大公因数的基本性质

150证明命题4.1.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最大公因数的基本性质

151证明命题4.1.4例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最大公因数的基本性质

152证明命题4.1.5最小公倍数

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

153定义4.1.4例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最小公倍数

154证明证明命题4.1.6引理4.1.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最小公倍数与最大公因数之间的关系

155证明命题4.1.7例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.最小公倍数与最大公因数之间的关系

156证明命题4.1.8例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.4.2素数

157定义4.2.1证明命题4.2.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数

158命题4.2.1证明（续）定理4.2.1（算术基本定理）例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.算术基本定理

159证明例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

算术基本定理

160注4.2.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.算术基本定理

进而，可将标准分解式用于刻画最大公因数和最小公倍数.下面的结论直接由定义即得.

161命题4.2.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素性测试

162证明引理4.2.1例如，{x∈R2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素性测试

163推论4.2.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.埃拉托色尼筛法

164例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.埃拉托色尼筛法

表4.2.1埃拉托色尼筛法165例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数的个数及分布存在无限多个素数.

166证明定理4.2.2定理4.2.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数的个数及分布

下面结果告诉我们，两个相邻素数之间可能间隔任意多个合数，这表明素数的分布是极不规则的.

167证明命题4.2.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数的个数及分布

168定理4.2.4(素数定理)例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数的个数及分布

169例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.素数的个数及分布

170例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.4.3同余

171定义4.3.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.同余

172命题4.3.1注4.3.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.同余

173命题4.3.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.同余

174解例4.3.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z