西安电子科技大学出版社：离散数学：第4章 二元关系和函数

第 4章 二元关系和函数第 4章 二元关系和函数
4.1 序偶与笛儿积
4.2 关系及表示
4.3 关系的运算
4.4 关系的性质
4.5 关系的闭包
4.6 等价关系和划分
4.7 序关系
4.8 函数的定义和性质
4.9 函数的复合和反函数
4.10 集合的基数
4.11 例题选解习 题 四第 4章 二元关系和函数
4.1 序偶与笛卡儿积定义 4.1.1(有序对 (或序偶 ),ordered pairs) 由两个元素 x和 y（允许 x=y）按一定次序排列组成的二元组
｛｛ x｝,｛ x,y｝｝称为一个有序对或序偶,记作
〈 x,y〉,其中 x是它的第一元素,y是它的第二元素。
注意,第一,二元素未必不同。
第 4章 二元关系和函数如平面直角坐标系中的任意一点坐标 （ x,y） 均是序偶,而全体这种实数对的集合
{(x,y） |x∈ R∧ y∈ R} 就表示整个平面 。
有序对 〈 x,y〉 具有以下性质：
(1) 当 x≠y 时,〈 x,y〉 ≠〈 y,x〉 。
(2) 〈 x,y〉 =〈 u,v〉 的充要条件是 x=u 且 y=v。
(3) 〈 x,x〉 也是序偶 。
第 4章 二元关系和函数这些性质是二元集 ｛ x,y｝ 所不具备的 。 例如当
x≠y 时有 {x,y}={y,x},原因是有序对中的元素是有序的,而集合中的元素是无序的 。 再例如,｛ x,x｝
={x},原因是集合中的元素是互异的 。
由性质 (２ )可推出 〈 x,y〉 =〈 y,x〉 的充要条件是 x=y。 有序对的概念可以进一步推广到多元有序组 。
第 4章 二元关系和函数定义 4.1.2(n元有序组 ) 若 n∈ N且 n＞ 1,x1,x2,…,
xn 是 n 个元素,则 n 〈 x1,x2,…,xn〉 定义为：
当 n=2时,二元组是有序对 〈 x1,x2〉 ；
当 n≠2时,〈 x1,x2,…,xn〉
=〈〈 x1,x2,…,x n-1 〉,xn〉
本质上,n元有序组依然是序偶。
第 4章 二元关系和函数
n元有序组有如下性质：
〈 x1,x2,…,xi,…,xn〉 =〈 y1,y2,…,yi,…,yn〉 的充要条件是
x1=y1,x2=y2,…,xi=yi,…,xn=yn。
前面提到,一个序偶 〈 x,y〉 的两个元素可来自不同的集合,若第一元素取自集合 A,第二元素取自集合 B,则由 A,B中的元素,可得若干个序偶,这些序偶构成的集合,描绘出集合 A与 B的一种特征,称为笛卡儿乘积 。 其具体定义如下：
第 4章 二元关系和函数定义 4.1.3 设 Α,Β 为集合,用 Α中元素为第一元素，
Β中元素为第二元素构成有序对。
所有这样的有序对组成的集合称为集合 Α和 Β的笛卡儿积 (cartesian product),又称作直积,记作 Α× Β。
Α和 Β 的笛卡儿积的符号化表示为
A× B={〈 x,y〉 |x∈ A∧ y∈ B}
第 4章 二元关系和函数定义 4.1.4 (n阶笛卡儿积 (cartesian product)) 若 n∈ N，
且 n＞ 1,A1,A2,…,An是 n 个集合,它们的 n 阶笛卡儿积记作 A1× A2× … × An,并定义为,
A1× A2× … × An
={〈 x1,x2,…,xn〉 |x1∈ A1∧ x2∈ A2,…,xn∈ An}
当 A1=A2=…= An=A时,A1× A2× … × An简记为 A n。
第 4章 二元关系和函数
【 例 4.1.1】 设 A=｛ 1,2｝,B=｛ a,b,c｝,C=｛ ｝,
R为实数集,则
（ 1） A× B=｛ 〈 1,a〉,〈 1,b〉,
〈 1,c〉,〈 2,a〉,〈 2,b〉,〈 2,c〉 ｝
B× A＝ ｛ 〈 a,1〉,〈 b,1〉,〈 c,1〉,〈 a,2〉,
〈 b,2〉,〈 c,2〉 ｝
× A=

第 4章 二元关系和函数
（ 2） A× B× C=(A× B)× C=｛ 〈 1,a,〉,
〈 1,b,〉,〈 1,c,〉,
〈 2,a,〉,〈 2,b,〉,〈 2,c,〉 ｝
A× (B× C)=｛ 〈 1,〈 a,〉〉,〈 1,〈 b,〉〉,
〈 1,〈 c,〉〉,〈 2,〈 a,〉〉,〈 2,〈 b,〉〉,
〈 2,〈 c,〉〉 ｝
（ 3） A 2={〈 1,1〉,〈 1,2〉,〈 2,1〉,〈 2,2〉 }
(4) B 2={〈 a,a〉,〈 a,b〉,〈 a,c〉,〈 b,a〉,
〈 b,b〉,〈 b,c〉,〈 c,a〉,〈 c,b〉,〈 c,c〉 }



第 4章 二元关系和函数
（ 5） R 2=｛ 〈 x,y〉 |x,y是实数｝,R 2为笛卡儿平面。 显然 R 3为三维笛卡儿空间。
显然 A× B与 B× A所含元素的个数相同 （ A,B是有限集合 ）,但 A× B≠B× A。
定理 4.1.1 若 A,B是有穷集合,则有
|A× B|=|A|·|B| (·为数乘运算 )
该定理由排列组合的知识不难证明 。
第 4章 二元关系和函数定理 4.1.2 对任意有限集合 A1,A2,…,An,有
|A1× A2× … × An|＝ |A1|·… ·| An| (·为数乘运算 )
这是十分直观的,可用归纳法证明之 。
第 4章 二元关系和函数定理 4.1.3 (笛卡儿积与 ∪,∩,～运算的性质 ) 对任意的集合 A,B 和 C,有
（ 1） A× (B∪ C)=(A× B)∪ (A× C)
（ 2） A× (B∩C)=(A× B)∩(A× C)
（ 3） (B∪ C)× A=(B× A)∪ (C× A)
（ 4） (B∩C)× A=(B× A)∩(C× A)
（ 5） A× (B-C)＝ (A× B)-(A× C)
（ 6） (B-C)× A＝ (B× A)-(C× A)
第 4章 二元关系和函数证明 我们仅证明 （ 1） 和 （ 5）,其余完全类似 。
（ 1） 对任意 x,y,有
〈 x,y〉 ∈ A× (B∪ C) x∈ A∧ y∈ (B∪ C)
x∈ A∧ (y∈ B∨ y∈ C)
(x∈ A∧ y∈ B)∨ (x∈ A∧ y∈ C)
〈 x,y〉 ∈ A× B∨ 〈 x,y〉 ∈ A× C
〈 x,y〉 ∈ (A× B)∪ (A× C)
第 4章 二元关系和函数为证 （ 5） 式,设 〈 x,y〉 为 A× (B-C)中任一序偶,
那么 x∈ A,y∈ B,y C,从 〈 x,y〉 ∈ A× B，
〈 x,y〉 A× C,即 〈 x,y〉 ∈ A× B-A× C,A× (B-C)
(A× B)-(A× C) 得证 。 另一方面,设 〈 x,y〉 为
(A× B)-(A× C)中任一序偶,那么 〈 x,y〉 ∈ A× B,〈 x,
y〉 A× C,从而 x∈ A,y∈ B,y C（ 否则由于 x∈ A，
〈 x,y〉 ∈ A× C ）,y∈ B-C,〈 x,y〉
∈ A× (B-C),于是 (A× B)-(A× C) A× (B-C)得证 。
这就完成了 A× (B-C)＝ (A× B)-(A× C)的证明 。

第 4章 二元关系和函数定理 4.1.4( 1) 对任意的集合 A,B 和 C,若 C≠,则
(A B) (A× C B× C) (C× A C× B)
该定理中的条件 C≠ 是必须的,否则不能由
A× C B× C或 C× A C× A推出 A B。
定理 4.1.5( 2) 对任意的集合 A,B,C和 D,有
(A× B C× D) (A C∧ B D)
这两个定理留给读者自己完成证明 。




第 4章 二元关系和函数定理 4.16 对任意非空集合 A,B,有
(A× B) P(P(A∪ B))
证明 设 〈 x,y〉 为 A× B中任一序偶,即 x∈ A，
y∈ B。 现需证
〈 x,y〉 =｛｛ x｝,｛ x,y｝｝ ∈ P(P(A∪ B))
由于 x∈ A,故 ｛ x｝ ∈ P(A∪ B)； 又由于 x∈ A，
y∈ B,故 ｛ x,y｝ ∈ P(A∪ B)。 因此,有
｛｛ x｝,｛ x,y｝｝ P(A∪ B)
即 ｛｛ x｝,｛ x,y｝｝ ∈ P(P(A∪ B))。
事实上,结论对 A,B为空集时也真 。
第 4章 二元关系和函数
4.2 关 系 及 表 示关系是客观世界存在的普遍现象,它描述了事物之间存在的某种联系 。 例如,人类集合中的父子,兄弟,同学,同乡等,两个实数间的大于,小于,等于关系,集合中二直线的平行,垂直等等,集合间的包含,元素与集合的属于 …… 都是关系在各个领域中的具体表现 。 表述两个个体之间的关系,称为二元关系； 表示三个以上个体之间的关系,称为多元关系 。
我们主要讨论二元关系 。
第 4章 二元关系和函数我们常用符号 R表示关系,如个体 a与 b之间存在关系 R,则记作 aRb,或 〈 a,b〉 ∈ R,否则 a b 或 〈 a,b〉
R。 R只是关系的一种表示符号,至于是什么关系，
需要时需附注。 同时关系并不限于同一类事物之间，
也存在于不同物体之间。 如旅客住店,张,王,李、
赵四人,1,2,3号房间,张住 1号,李住 1号,王住
2号,赵住 3号。 若分别以 a,b,c,d 表示四人,R表示住宿关系,则有 R={〈 a,1〉,〈 c,1〉,〈 b,2〉,〈 d,
3〉 }。 因此我们看到住宿关系 R是序偶的集合。
R
第 4章 二元关系和函数定义 4.2.1 任何序偶的集合,确定了一个二元关系，
并称该集合为一个二元关系,记作 R 。 二元关系也简称关系。 对于二元关系 R,如果 〈 x,y〉 ∈ R,也可记作 xRy。
定义并不要求 R中的元素 〈 x,y〉 中的 x,y取自哪个个体域 。 因此,R={〈 2,a〉,〈 u,狗 〉,〈 钱币,
思想 〉 }也是一个二元关系 。 因为它符合关系的定义,
但是无意义,显然对毫无意义的关系的研究也无甚意义 。 若规定关系 R中序偶 〈 x,y〉 的 x∈ A,y∈ B,如上面的住店关系,这样的序偶构成的关系 R,称为从 A到
B的一个二元关系 。 由 A× B的定义知,从 A到 B的任何二元关系,均是 A× B的子集,因此有下面的定义 。
第 4章 二元关系和函数定义 4.2.2 R称为集合 A1,A2,…,An-1 到 An
上的 n元关系（ n array relations）,如果 R是
A1× A2× … × An-1× An的一个子集。 当 A1＝ A2＝ …
＝ An-1＝ An时,也称 R为 A上的 n元关系。 当 n=2时,称
R为 A1到 A2的二元关系。 n元关系也可视为
A1× A2× … × An-1 到 An的二元关系。
由于关系是集合 （ 只是以序偶为元素 ）,因此,
所有规定集合的方式均适用于关系的确定 。
第 4章 二元关系和函数当 A,B均是有限集合时,因为 |A× B|=|A|·|B|,而其子集的个数恰是幂集 P(A× B)的元素个数,
|P(A× B)|=2 |A|·|B|,所以由 A到 B共有 2 |A|·|B| 个不同的二元关系 。
下面介绍一些特殊的二元关系 。 设 R是 A到 B的二元关系：
A× B,A到 B的空关系 。
A× B A× B,称 A× B 为 A到 B的全域关系 。
IA=｛ 〈 x,x〉 |x∈ A｝,称为 A上的恒等关系 。
第 4章 二元关系和函数若 A是实数集合或其子集,R是 A上的二元关系,
可定义下面几种常见的二元关系：
若 R={〈 x,y〉 |x∈ A∧ y∈ B∧ x≤y },则称 R为小于等于关系,常记为 ≤。
若 R={〈 x,y〉 |x∈ A∧ y∈ B∧ x|y },则称 R为整除关系,常记为 |,其中 x|y是 x整除 y。
第 4章 二元关系和函数若 A是任意集合,R是 A上的二元关系,下面的关系也常见：
若 R={〈 x,y〉 |x∈ P(A)∧ y∈ P(B)∧ x y},则称 R
为包含关系,。
若 R={〈 x,y〉 |x∈ P(A)∧ y∈ P(B)∧ x y},则称 R
为真包含关系,。
第 4章 二元关系和函数定义 4.2.3 设 R是 A到 B的二元关系 。
（ 1） 用 xRy表示 〈 x,y〉 ∈ R,意为 x,y有 R关系
（ 为使可读性好,我们将分场合使用这两种表达方式中的某一种 ） 。 x y表示 〈 x,y〉 R。
（ 2） 由 〈 x,y〉 ∈ R的所有 x组成的集合称为关系 R
的定义域 （ domain） 记作 DomR,即
Dom R=｛ x|x∈ A∧ y(y∈ A∧ 〈 x,y〉 ∈ R)｝
R?
第 4章 二元关系和函数
（ 3） 由 〈 x,y〉 ∈ R的所有 y组成的集合称为关系 R
的值域 （ range）,记作 Ran R,即
Ran R＝ {y|y∈ B∧ x(x∈ A∧ 〈 x,y〉 ∈ R)｝
（ 4） R的定义域和值域的并集称为 R的域,记作
Fld R。 形式化表示为：
Fld R=Dom R∪ Ran R
一般地,若 R是 A到 B的二元关系,则有 Dom
R A,Ran R B。

第 4章 二元关系和函数
【 例 4.2.1】 设 A=｛ 1,2,3,4,5,6｝,
B＝ ｛ a,b,c,d｝,则
R＝ ｛ 〈 2,a〉,〈 2,b〉,〈 3,b〉,〈 4 c〉,
〈 6,c〉 ｝
那么如图 4.2.1所示：
Dom R＝ ｛ 2,3,4,6｝,Ran R=｛ a,b,c｝
Fld R={2,3,4,6,a,b,c}
各箭头分别表示 2Ra,2Rb,3Rb,4Rc,6Rc。
第 4章 二元关系和函数图 4.2.1
2
3
4
6
1
5
a
b
c
d
第 4章 二元关系和函数在此引入关系的表示法 。
因为关系是一种特殊的集合,所以关系仍然能使用集合的表示方法 。 如集合的列举法和描述法 。 除此之外,有限集合的二元关系亦可用图形来表示,这就是关系图 。
第 4章 二元关系和函数定义 4.2.4 设集合 A={x1,x2,…,xm}到 B={y1,y2,…,
ym}上的一个二元关系为 R,以集合 A,B中的元素为顶点,在图中用,,"表示顶点 。 若 xiRyj,则可自顶点 xi向顶点 yj引有向边 〈 xi,yj〉,其箭头指向 yj。 用这种方法画出的图称为关系图 （ graph of relation） 。
如图 4.2.1就表示了例 4.2.1中的关系 R。
如关系 R是定义在一个集合 A 上,即 R A× A,只需要画出集合 A中的每个元素即可 。 起点和终点重合的有向边称为环 （ loop） 。
第 4章 二元关系和函数
【 例 4.2.2】 求集合 A=｛ 1,2,3,4 ｝ 上的恒等关系,
空关系,全关系和小于关系的关系图 。
解 恒等关系
IA={〈 1,1〉,〈 2,2〉,〈 3,3〉,〈 4,4〉 }
={ }
全关系 A× A={〈 1,1〉,〈 2,2〉,〈 3,3〉,〈 4,4〉,
〈 1,2〉,〈 2,1〉,〈 3,1〉,〈 4,1〉,〈 1,3〉,〈 2,3〉,
〈 3,2〉,〈 4,2〉,〈 1,4〉,〈 2,4〉,〈 3,4〉,〈 4,3〉,}
第 4章 二元关系和函数小于关系 LA={〈 1,2〉,〈 1,3〉,〈 2,3〉,〈 1,4〉,
〈 2,4〉,〈 3,4〉 }
其关系图分别见图 4.2.2,图 4.2.3,图 4.2.4,图 4.2.5。
第 4章 二元关系和函数图 4.2.2 图 4.2.3
1 2
3 4
1 2
3 4
第 4章 二元关系和函数图 4.2.4 图 4.2.5
1
3 4
2
1 2
3 4
第 4章 二元关系和函数当 A中元素的次序标定后,对于任何关系 R,R的关系图与 R的集合表达式是可以唯一相互确定的 。 我们也可看出关系图直观清晰,是分析关系性质的方便形式,但是对它不便于进行运算 。 关系还有一种便于运算的表示形式,称为关系矩阵 （ matrix of relation） 。
定义 4.2.5 设 R A× B,A=｛ a1,a2,…,am｝,
B=｛ b1,b2,…,bn｝,那么 R的关系矩阵 MR为一 m× n矩阵,它的第 i,j分量 rij 只取值 0或 1,而
1
0ij
r

当且仅当 aiRbj
当且仅当
ija Rb
第 4章 二元关系和函数例如,图 4.2.1所示关系 R的关系矩阵为
0000
1 1 0 0
0 1 0 0
0 0 1 0
0000
0 0 1 0
R
M









第 4章 二元关系和函数例 4.2.2中的图 4.2.2,图 4.2.3,图 4.2.4,图 4.2.5所示关系的关系矩阵分别是
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
1 1 1 1 0 1 1 1
1 1 1 1 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 0 0 0 0
A
A
I
A A I
MM
MM














第 4章 二元关系和函数关系 R的集合表达式与 R的关系矩阵也可以唯一相互确定,因此 R的集合表达式,关系图,关系矩阵三者均可以唯一相互确定,并且它们各有各的特点,可以根据不同的需要选用不同的表达方式 。
第 4章 二元关系和函数
4.3 关 系 的 运 算
A到 B的二元关系 R是 A× B的子集,亦即关系是序偶的集合。 故在同一集合上的关系,可以进行集合的所有运算。 作为集合对关系作并,交,差,补运算是理所当然的,但为了运算结果作为关系的意义更明确,我们也要求运算对象应有相同的域,从而运算结果是同一域间的关系。 同前所述,这一要求也不是本质的。 因此,在讨论关系运算时,我们有时忽略它们的域。
第 4章 二元关系和函数定义 4.3.1 设 R和 S为 A到 B的二元关系,其并,交,
差,补运算定义如下：
R∪ S＝ ｛ 〈 x,y〉 |xRy∨ xSy｝
R∩S＝ ｛ 〈 x,y〉 |xRy∧ xSy｝
R-S＝ ｛ 〈 x,y〉 |xRy∧?xS y｝
～ R＝ A× B-R＝ ｛ 〈 x,y〉 |?xR y｝
第 4章 二元关系和函数
【 例 4.3.1】 设 A={1,2,3,4},若 R={〈 x,y〉 |(x-y)/2
是整数,x,y∈ A},S={〈 x,y〉 |(x-y)/3是正整数,x,
y∈ A},求 R∪ S,R∩S,S-R,～ R,R S。
解
R={〈 1,1〉,〈 1,3〉,〈 2,2〉,〈 2,4〉,〈 3,1〉,
〈 3,3〉,〈 4,2〉,〈 4,4〉 }
S={〈 4,1〉 }R∪ S={〈 1,1〉,〈 1,3〉,〈 2,2〉,
〈 2,4〉,〈 3,1〉,〈 3,3〉,〈 4,2〉,〈 4,4〉,〈 4,1〉 }
第 4章 二元关系和函数
R∩S=
S-R=S={〈 4,1〉 }
～ R=A× A-R={〈 1,2〉,〈 1,4〉,〈 2,1〉,〈 2,3〉,
〈 3,2〉,〈 3,4〉,〈 4,1〉,〈 4,3〉 }
R S =(R∪ S)-(R∩S)=R∪ S
={〈 1,1〉,〈 1,3〉,〈 2,2〉,〈 2,4〉,〈 3,1〉,
〈 3,3〉,〈 4,2〉,〈 4,4〉,〈 4,1〉 }
第 4章 二元关系和函数关系并,交,差,补的矩阵可用如下方法求取：
M R∪ S = M R∨ M S
（ 矩阵对应分量作逻辑析取运算 ）
M R∩S = M R∧ M S
（ 矩阵对应分量作逻辑合取运算 ）
M R-S = M R∩～ S = M R∧ M ～ S
M ～ S =～ ( M S)
（ 矩阵各分量作逻辑非运算 ）
第 4章 二元关系和函数定义 4.3.2 设 R是 A到 B的关系,R的逆关系或逆
（ converse）是 B到 A的关系,记为 R -1,规定为
R -1 =｛ 〈 y,x〉 |xRy｝
由定义很显然,对任意 x∈ A,y∈ B,有
xRy yR -1 x
若 M R为 R的关系矩阵,那么
（ M′表示矩阵 M的转置矩阵 ）
1 RRMM
第 4章 二元关系和函数
【 例 4.3.3】 设 R表示父子关系,即 〈 x,y〉 ∈ R说明
x是 y的父亲,R R就表示祖孙关系 。
【 例 4.3.4】 设 R表示朋友关系,S表示直接后门关系,R S就表示间接后门关系 。
第 4章 二元关系和函数
【 例 4.3.5】 设 A＝ ｛ 0,1,2,3,4,5｝,
B＝ ｛ 2,4,6｝,C＝ ｛ 1,3,5｝,R A× B,S
B× C，
R＝ ｛ 〈 1,2〉,〈 2,4〉,〈 3,4〉,
〈 5,6〉 ｝,S＝ ｛ 〈 2,l〉,〈 2,5〉,〈 6,3〉 ｝
R S。
解
R.S＝ ｛ 〈 l,l〉,〈 1,5〉,〈 5,3〉 ｝ A× C
用图表示 R S,如图 4.3.1所示 。
第 4章 二元关系和函数图 4.3.1
0
1
2
3
4
5
1
3
5
2
4
6
A B CR S
R S
第 4章 二元关系和函数
【 例 4.3.6】 设集合 A＝ ｛ 1,2,3,4,5｝,R,S
均为 A上的二元关系,且
R＝ ｛ 〈 x,y〉 |x+y＝ 4｝ ＝ ｛ 〈 0,4〉,〈 4,0〉,
〈 1,3〉,〈 3,1〉,〈 2,2〉 ｝
S＝ ｛ 〈 x,y〉 |y -x＝ 1｝ ＝ ｛ 〈 0,1〉,〈 1,2〉,
〈 2,3〉,〈 3,4〉 ｝
求 Sο S,SοR,Rο R,Sο S,(Rο S)ο R,Rο (Sο R)。
第 4章 二元关系和函数解 Rο S＝ ｛ 〈 4,l〉,〈 1,4〉,〈 3,2〉,〈 2,3〉 ｝
＝ ｛ 〈 x,z〉 |x+z＝ 5｝
Sο R＝ ｛ 〈 0,3〉,〈 1,2〉,〈 2,1〉,〈 3,0〉 ｝
＝ ｛ 〈 x,z〉 |x+z＝ 3｝
Rο R＝ ｛ 〈 0,0〉,〈 4,4〉,〈 1,1〉,〈 3,3〉,
〈 2,2〉 ｝ ＝ ｛ 〈 x,z〉 |x-z＝ 0｝
第 4章 二元关系和函数
Sο S＝ ｛ 〈 0,2〉,〈 1,3〉,
〈 2,4〉 ｝ ＝ ｛ 〈 x,z〉 |z-x＝ 2｝
(Rο S)ο R ＝ ｛ 〈 4,3〉,〈 1,0〉,
〈 3,2〉,〈 2,1〉 ｝
Rο (Sο R) ＝ ｛ 〈 4,3〉,〈 3,2〉,
〈 2,1〉,〈 1,0〉 ｝
从上例已可看出,一般地 Rο S≠Sο R。
复合运算的性质由下面两个定理介绍 。
第 4章 二元关系和函数定理 4.3.2 设 IA,IB为集合 A,B上的恒等关系,
R A× B,那么
（ 1） IAο R=Rο IB=R
（ 2） Φο R=RοΦ=Φ
第 4章 二元关系和函数证明 （ 1） 为证 IAο R R,〈 x,y〉 ∈ IAο R。
〈 x,y〉 ∈ IAο R u(u∈ A∧ 〈 x,u〉 ∈ IA∧ 〈 u,y〉 ∈ R)
u(u∈ A∧ x=u∧ 〈 u,y〉 ∈ R)
〈 x,y〉 ∈ R
所以 IAο R R得证 。
第 4章 二元关系和函数
（ 2) 显然 Φ Φο R,下证 Φο R Φ。
〈 x,y〉 ∈ Φο R。
〈 x,y〉 ∈ Φο R u(u∈ A∧ 〈 x,u〉 ∈
Φ∧ 〈 u,y〉 ∈ R)
〈 x,u〉 ∈ Φ
说明命题的前件为假,整个蕴含式为真,所以
Φο R Φ。 因此 Φο R=Φ。 同理可证 Rο Φ =Φ。

第 4章 二元关系和函数定理 4.3.3 设 R,S,T均为 A上二元关系,那么
（ 1） Rο (S∪ T)=(Rο S)∪ (Rο T)
（ 2） (S∪ T)ο R=(Sο R)∪ (Tο R)
（ 3） Rο (S∩T) (Rο S)∩(Rο T)
（ 4） (S∩T)ο R (Sο R)∩(Tο R)
（ 5） Rο (Sο T)=(Rο S)ο T
（ 6） (Rο S) -1 =S -1ο R -1
第 4章 二元关系和函数证明 我们仅证明 （ 1）,（ 4）,（ 5）,另外三式的证明留给读者完成 。
（ 1） 对任意 x,y∈ A
〈 x,y〉 ∈ Rο (S∪ T) u (〈 x,u〉 ∈ R∧ 〈 u,y〉 ∈ S∪ T)
u(〈 x,u〉 ∈ R∧ (〈 u,y〉 ∈ S∨ 〈 u,y〉 ∈ T))
u((〈 x,u〉 ∈ R∧ 〈 u,y〉 ∈ S)∨ (〈 x,u〉 ∈ R∧ 〈 u,y〉 ∈ T))

第 4章 二元关系和函数
u(〈 x,u〉 ∈ R∧ 〈 u,y〉 ∈ S)∨ u(〈 x,u〉 ∈ R∧ 〈 u,y〉 ∈ T)
〈 x,y〉 ∈ Rο S∨ 〈 x,y〉 ∈ Rο T
〈 x,y〉 ∈ Rο S∪ Rο T
故 Rο (S∪ T)=(Rο S)∪ (Rο T)。
第 4章 二元关系和函数
（ ４ ） 对任意 x,y∈ A
〈 x,y〉 ∈ (S∩T)ο R u(〈 x,u〉 ∈ (S∩T)∧ 〈 u,y〉 ∈ R)
u(〈 x,u〉 ∈ S∧ 〈 x,u〉 ∈ T∧ 〈 u,y〉 ∈ R)
u(〈 x,u〉 ∈ S∧ 〈 u,y〉 ∈ R∧ 〈 x,u〉 ∈ T∧ 〈 u,y〉 ∈ R)
u(〈 x,u〉 ∈ S∧ 〈 u,y〉 ∈ R)∧ u∈ 〈 x,u〉 ∈ T∧ 〈 u,y〉 ∈ R)
〈 x,y〉 ∈ (Sο R)∧ 〈 x,y〉 ∈ (Tο R)
〈 x,y〉 ∈ (Sο R)∩(Tο R)
故 (S∩T)ο R (Sο R)∩(Tο R)。



第 4章 二元关系和函数定义 4.3.4 设 R是 A上的关系,n个 R的复合称为 R的
n次幂。 由于关系复合运算有结合律,因此用“幂”
表示集合上关系对自身的复合是适当的，
R n= Rο … ο R,规定 R 0＝ IA（ R为 A上二元关系）。
R n满足下列性质。
定理 4.3.4 设 R为 A上二元关系,m,n为自然数,那么
(1) R n+1 =R nο R=Rο R n=R mο R n-m+1
(2) R mο R n＝ R m+n
(3) (R m) n＝ R mn
(4) (R -1 ) n=(R n) -1
第 4章 二元关系和函数
【 例 4.3.7】 设 A={0,1,2,3,4},R={〈 0,0〉,〈 0,1〉,
〈 1,3〉,〈 2,4〉,〈 3,1〉,〈 4,4〉 }
解 R 2={〈 0,0〉,〈 0,1〉,〈 0,3〉,〈 1,1〉,
〈 2,4〉,〈 3,3〉,〈 4,4〉 }
R 3={〈 0,0〉,〈 0,1〉,〈 0,3〉,〈 1,3〉,
〈 2,4〉,〈 3,1〉,〈 4,4〉 }
第 4章 二元关系和函数
R 4={〈 0,0〉,〈 0,1〉,〈 0,3〉,〈 1,1〉,
〈 2,4〉,〈 3,3〉,〈 4,4〉 }=R 2
R,R 2,R 3,R 4的关系图如图 4.3.2所示 。
R,R 2,R 3,R 4所对应的关系矩阵为第 4章 二元关系和函数
2
3 2 4 3
1 1 0 0 0 1 1 0 1 0
0 0 0 1 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 1
0 1 0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0 1
1 1 0 1 0 1 1 0 1 0
0 0 0 1 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 1
0 1 0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0 1
M M M M
M M M M M M
















第 4章 二元关系和函数图 4.3.2
0
1
3
4
2
R
0
1
3
4
2
R
2
0
1
3
4
2
R
3
0
1
3 4
2
R
4
第 4章 二元关系和函数定理 4.3.5 设集合 A的基数为 n,R是 A上二元关系,
那么存在自然数 i,j使得证明 我们知道,当 |A|=n时,A上不同二元关系共个,令,因此,在 R 0,R 1,R2,…,
R K
这 K+l个关系中,至少有两个是相同的 （ 鸽巢原理 ）,即有 i,j(0≤i＜ j≤ ),使 R i＝ R j 。
ijRR?
22n 22nK?
22n
第 4章 二元关系和函数定义 4.3.5 设 R为 A到 B的二元关系,A在 R下的像 R
［ A］ 为集合
R［ A］ ={y|( x)(x∈ A∧ 〈 x,y〉 ∈ R)}
集合在关系下的像的性质：
定理 4.3.6 R是 X到 Y的关系和集合 A,B,则
（ 1） R［ A∪ B］ =R［ A］ ∪ R［ B］
（ 2） R［ ∪ A ］ =∪ {R［ B］ |B∈ A}
（ 3） R［ A∩B］ R［ A］ ∩R［ B］
（ 4） R［ ∩A ］ ∩{R［ B］ |B∈ A} (A≠Φ)
（ 5） R［ A］ -R［ B］ R［ A-B］
第 4章 二元关系和函数
4.4 关 系 的 性 质本节总假定关系是某一非空集合上的二元关系,
这一假定不失一般性 。 因为任一 A到 B的关系 R,即
R A× B,A× B (A∪ B)× (A∪ B),所以关系 R总可看成是 A∪ B上的关系,它与原关系 R具有完全相同的序偶,对它的讨论代替对 R的讨论无损于问题的本质 。

第 4章 二元关系和函数定义 4.4.1 设 R是 A上的二元关系,即 R A× A。
（ 1） 称 R是自反的 （ reflexive）,如果对任意 x∈ A，
均有 xRx。 即 R在 A x(x∈ A→xRx)。
（ 2） 称 R是反自反的 （ irreflexive）,如果对任意
x∈ A,xRx均不成立 。 即 R在 A 上是反自反的当且仅当
x(x∈ A→ xRx)。

第 4章 二元关系和函数
（ 3） 称 R是对称的（ Symmetric）,如果对任意
x∈ A,y∈ A,xRy蕴涵 yRx。 即 R在 A 上是对称的当且仅
x y(x∈ A∧ y∈ A∧ xRy→yRx)。
（ 4） 称 R是反对称的（ antisymmetric）,如果对任意 x∈ A,y∈ A,xRy且 yRx蕴涵 x＝ y。
即 R在 A
x y(x∈ A∧ y∈ A∧ xRy∧ yRx→x=y)。 反对称性的另一种等价的定义为,R在 A
x y(x∈ A∧ y∈ A∧ xRy∧ x≠y→〈 y,x〉 R)。



第 4章 二元关系和函数
（ 5） 称 R是传递的（ transitive）,如果对任意
x∈ A,y∈ A,z∈ A,xRy且 yRz蕴涵 xRz 。 即 R在 A 上是
x y z(x∈ A∧ y∈ A∧ z∈ A∧ xRy∧ yRz→xRz)。
第 4章 二元关系和函数
【 例 4.4.1】 设 A=｛ a,b,c｝,以下各关系
Ri（ i＝ 1,2,…,8） 均为 A上二元关系 。
（ 1） R1＝ ｛ 〈 a,a〉,〈 a,c〉,〈 b,b〉,
〈 c,c〉 ｝ 是自反的,而 R2＝ ｛ 〈 a,c〉,〈 c，
a〉 ｝ 不是自反的,是反自反的 。 存在既不自反也不反自反的二元关系,例如 R3＝ ｛ 〈 a,a〉 ｝ 。 显然 A
上的 Φ关系是反自反的,不是自反的 。 可是值得注意的是,当 A＝ Φ时 （ 这时 A上只有一个关系 Φ）,A上空关系既是自反的,又是反自反的,因为 A＝ Φ使两者定义的前提总为假 。
第 4章 二元关系和函数
（ 2） R 4＝ ｛ 〈 a,b〉,〈 b,a〉 ｝ 是对称的；
R5＝ ｛ 〈 a,c〉,〈 c,a〉,〈 a,b〉,〈 a,a〉 ｝
不是对称的； R6＝ ｛ 〈 a,b〉,〈 a,c〉 ｝ 是反对称的 。 其实 R5既不是对称的,也不是反对称的 。 特别有意思的是,存在既对称又反对称的二元关系,例如
A上的恒等关系 IA。
（ 3） R7＝ ｛ 〈 a,b〉,〈 b,c〉,〈 a,c〉,
〈 c,c〉 ｝ 是传递的,但 R7-｛ 〈 a,c〉 ｝ 便不是传递的了 。 应当注意,A上的空关系 Φ，
R8＝ ｛ 〈 a,b〉 ｝ 等是传递的,因为传递性定义的前提对它们而言均为假 。
第 4章 二元关系和函数
（ 4） 任何非空集合上的空关系都是反自反,对称,
反对称,传递的； 其上的相等关系是自反,对称,
反对称,传递的； 其上的全关系是自反,对称,传递的 。
(5) 三角形的相似关系,全等关系是自反,对称,
传递的 。
（ 6） 正整数集合上的整除关系是自反,反对称,
传递的； 但整数集合上的整除关系只有传递性 。 判断一个关系是否具有上述某种的性质,除直接用定义,
还有下面的充要条件 。
第 4章 二元关系和函数定理 4.4.1 设 R为集合 A上二元关系,即 R A× A,则
（ 1） R是自反的当且仅当 IA R。
（ 2） R是反自反的当且仅当 IA∩R=Φ。
（ 3） R是对称的当且仅当 R=R -1 。
（ 4） R是反对称的当且仅当 R∩R -1 IA。
（ 5） R是传递的当且仅当 Rο R R。
第 4章 二元关系和函数证明 （ 1） 先证必要性,因为 R是自反的,设对任意的
〈 x,y〉 ∈ IA x ∈ A∧ y∈ A∧ x=y 〈 x,y〉 ∈ R。
再证充分性,任取 x∈ A,有 〈 x,x〉 ∈ IA,因为 IA
( R,所以 〈 x,x〉 ∈ R,因此 R是自反的 。

第 4章 二元关系和函数
（ 2） 先证必要性,用反证法 。
假设 R∩IA≠Φ,必存在 〈 x,y〉 ∈ R∩IA 〈 x,y〉 ∈ IA,
由于 IA是 A上的恒等关系,从而有 x=y,所以
〈 x,x〉 ∈ R,这与 R 在 A上是反自反的相矛盾 。
再证充分性,任取 x∈ A,则有 x∈ A 〈 x,x〉 ∈ IA
〈 x,x〉 R(由于 IA∩R=Φ),从而证明了 R在 A上是反自反的 。
第 4章 二元关系和函数
（ 3） 先证必要性,设 R对称,那么对任意 x,y∈ A,有
〈 x,y〉 ∈ R 〈 y,x〉 ∈ R （ 因为 R在 A上对称 ）
〈 x,y 〉 ∈ R -1
故 R=R -1 。
再证充分性,任取 〈 x,y〉 ∈ R,由 R=R -1,有
〈 x,y〉 ∈ R 〈 x,y〉 ∈ R -1
〈 y,x〉 ∈ R
所以 R在 A上是对称的 。
第 4章 二元关系和函数
（ 4） 先证必要性,设 R反对称,那么对任意 x,
y∈ A,有
〈 x,y〉 ∈ R∩R -1 〈 x,y〉 ∈ R∧ 〈 x,y〉 ∈ R -1
〈 x,y〉 ∈ R∧ 〈 y,x〉 ∈ R
x=y （ R反对称 ）
〈 x,y〉 ∈ IA
因此 R∩R -1 IA。
第 4章 二元关系和函数再证充分性,设 R∩R -1 IA。 为证 R反对称,
又设 〈 x,y〉 ∈ R∧ 〈 y,x 〉 ∈ R,由 R∩R -1 IA,有
〈 x,y〉 ∈ R∧ 〈 y,x〉 ∈ R 〈 x,y〉 ∈ R∧ 〈 x,y〉 ∈ R -1
〈 x,y〉 ∈ R∩R -1
〈 x,y〉 ∈ IA
因而 x=y。 所以 R在 A上是反对称的,得证 。
第 4章 二元关系和函数
（ 5） 先证必要性,设 R传递,那么对任意 x,y∈ A,有
〈 x,y〉 ∈ Rο R u(u∈ A∧ 〈 x,u〉 ∈ R∧ 〈 u,y 〉 ∈ R)
u(u∈ A∧ 〈 x,y〉 ∈ R) （ R是传递的 ）
〈 x,y〉 ∈ R
故 Rο R R。


第 4章 二元关系和函数再证充分性,设 Rο R R。 为证 R传递,设有
〈 x,y〉 ∈ R,〈 y,z〉 ∈ R。
〈 x,y〉 ∈ R∧ 〈 y,z〉 ∈ R 〈 x,z〉 ∈ Rο R
〈 x,z〉 ∈ R (Rο R R)
所以 R在 A上是传递的,得证 。
关系的基本性质与关系图,关系矩阵有怎样的联系呢？ 表 4.4.1详解之 。
第 4章 二元关系和函数表 4.4.1
第 4章 二元关系和函数
【 例 4.4.2】 设 Ri是 A={1,2,3}上的二元关系（如图
4.4.1所示）,判断它们各具有什么性质？ 并说明理由。
解 根据关系图的特征,我们可判断下列各关系具有的性质。 R1具有反自反性,对称性,反对称性、
传递性。 因为每一结点处均无环,既无双边又无单边，
既无双边又无三角形。
第 4章 二元关系和函数
R2具有自反性,对称性,反对称性,传递性 。
因为每一结点处有一环,既无双边又无单边,既无双边又无三角形 。
R3具有自反性,对称性,传递性 。 因为每一结点处有一环,有边就有双边,有双边又有双环,有三角形就是向量三角形 。
R4具有反对称性,传递性 。 因为无双边,无三角形 。
R5具有对称性 。 因为无单边 。
第 4章 二元关系和函数
R6具有反自反性,反对称性 。 因为每一结点处均无环 。
R7具有自反性,对称性,反对称性,传递性 。 因为每一结点处有一环,有三角形,且是向量三角形 。
R8具有反自反性,传递性 。 因为每一结点处均无环,有三角形,且是向量三角形 。
R9均不具备 。
第 4章 二元关系和函数图 4.4.1
1
2 3
1
2 3
1
2 3
1
2 3
R
1
R
2
R
3
R
4
1
2 3 2 3
1
2 3
R
7
R
5
R
6
1
2 3
R
8
1
2 3
R
9
1
第 4章 二元关系和函数关系是序偶的集合,可作交,并,差,逆,复合运算 。 如果已知某些关系具有某一性质,经过关系运算后的结果是否仍具有这一性质,是一个令人关注的问题 。 如果是,我们称该性质对这一运算封闭 。 现在我们来讨论五大特性对基本运算的封闭性 。
第 4章 二元关系和函数定理 4.4.2 设 R1,R2是 A上的自反关系,则 R -11、
R1∩R2,R1∪ R2,R1ο R2也是 A上的自反关系 。 证明留给读者 。
定理 4.4.3 设 R1,R2是 A上的对称关系,则 R -11,
R1∩R2,R1∪ R2,R1-R2也是 A上的对称关系 。
第 4章 二元关系和函数证明 仅证对称性对并运算封闭 。
设 R1,R2对称,要证 R1∪ R2对称 。 任取 〈 x,y〉
∈ R1∪ R2,那么 〈 x,y〉 ∈ R1或 〈 x,y〉 ∈ R2。 由 R1，
R2对称知 〈 y,x〉 ∈ R1或 〈 y,x〉 ∈ R2,因而 〈 y,x〉
∈ R1∪ R2。 R1∪ R2对称性得证 。
第 4章 二元关系和函数定理 4.4.4 设 R1,R2是 A上的传递关系,则
R -11,R1∩R2是 A上的传递关系。 但 R1∪ R2不一定是传递的。
证明 (1) 证传递性对求逆运算封闭 。
设 R1传递,要证 R -11传递,设有 〈 x,y〉 ∈ R -11,
〈 y,z〉 ∈ R -11,那么 〈 y,x 〉 ∈ R1,〈 z,y〉 ∈ R1。 由
R1具有传递性可得 〈 z,x〉 ∈ R1,即 〈 x,z〉 ∈ R -11 。
R -11在 A上是传递的,得证。
第 4章 二元关系和函数
(2) 证传递性对交运算封闭 。
设 R1,R2传递,要证 R1∩R2传递 。 设有 〈 x,y〉
∈ R1∩R2,〈 y,z〉 ∈ R1∩R2,那么 〈 x,y〉 ∈ R1,〈 x,y〉
∈ R2,〈 y,z〉 ∈ R1,〈 y,z〉 ∈ R2。 由 R1,R2具有传递性,可得 〈 x,z〉 ∈ R1,〈 x,z〉 ∈ R2,从而 〈 x,z〉
∈ R1∩R2。 故 R1∩R2在 A上是传递的,得证 。
第 4章 二元关系和函数定理 4.4.5 设 R1,R2是 A上的反对称关系,则
R-11,R1∩R2,R1-R2是 A上的反对称关系 。 但 R1∪ R2不一定是反对称的 。
证明 仅证反对称性对差运算封闭 。
设 R1,R2反对称,要证 R1-R2反对称 。
设 〈 x,y〉 ∈ (R1-R2)且 〈 y,x〉 ∈ (R1-R2),因而 〈 x,y〉
∈ R1,〈 y,x〉 ∈ R1,从而由 R1的反对称性得 x=y。 这就完成了 R1-R2反对称的证明 。
第 4章 二元关系和函数定理 4.4.6 设 R1,R2是 A上的反自反关系,则
R -11,R1∩R2,R1∪ R2,R1-R2是 A上的反自反关系 。
证明留给读者 。
我们举例说明反自反性,对称性,反对称性,传递性对合成运算均不封闭。
第 4章 二元关系和函数
【 例 4.4.3】 A={a,b,c},讨论在下列各种情况下 Rο S具有的性质 。
(1) R={〈 a,b〉 },S={〈 b,a〉 },R,S是反自反的 。
(2) R={〈 a,b〉,〈 b,a〉 },S={〈 b,c〉,〈 c,b〉 },
R,S是对称的 。
(3) R={〈 a,b〉,〈 b,c〉 },S={〈 b,b〉,〈 c,a〉 },
R,S是反对称的 。
(4） R={〈 a,b〉,〈 b,c〉,〈 a,c〉 },S={〈 b,a〉,
〈 b,c〉,〈 c,a〉 },R,S是传递的 。
第 4章 二元关系和函数解
（ 1） Rο S={〈 a,a〉 },所以 Rο S不是反自反的 。
（ 2） Rο S={〈 a,c〉 },所以 Rο S不是对称的 。
（ 3） Rο S={〈 a,b〉,〈 b,a〉 },所以 Rο S是对称的 。
（ 4） Rο S={〈 a,a〉,〈 a,c〉,〈 b,a〉 },因为 〈 b,a〉
∈ Rο S,〈 a,c〉 ∈ Rο S,
但 〈 b,c〉 Rο S,所以 Rο S不是传递的 。
第 4章 二元关系和函数
4.5 关 系 的 闭 包闭包运算是关系运算中一种比较重要的特殊运算,
是对原关系的一种扩充 。 在实际应用中,有时会遇到这样的问题,给定了的某一关系并不具有某种性质,
要使其具有这一性质,就需要对原关系进行扩充,而所进行的扩充又是 "最小 "的 。 这种关系的扩充就是对原关系的这一性质的闭包运算 。
第 4章 二元关系和函数
【 定义 4.5.1】 设 R是非空集合 A 上的关系,如果 A
上有另一个关系 R′满足：
（ 1） R′是自反的 （ 对称的或传递的 ） ；
（ 2） R R′；
（ 3） 对 A上任何自反的 （ 对称的或传递的 ） 关系 R″,
若 R R″,均有 R′ R″,则称 R′为 R的自反 （ 对称或传递 ） 闭包 。

第 4章 二元关系和函数一般将 R的自反闭包记作 r(R),对称闭包记作 s(R)，
传递闭包记作 t(R)。 它们分别是具有自反性或对称性传递性的 R的 "最小 "超集合 。 称 r,s,t为闭包运算,
它们作用于关系 R后,分别产生包含 R的,最小的具有自反性,对称性,传递性的二元关系 。 这三个闭包运算也可由下述定理来构造 。
第 4章 二元关系和函数定理 4.5.1 设 R是集合 A上的二元关系,那么
（ 1） r(R)=IA∪ R
（ 2） s(R)=R∪ R -1
（ 3）
1
() i
i
t R R
第 4章 二元关系和函数证明
（ 1） IA∪ R自反且 R IA∪ R是显然的 。 为证 IA∪ R为自反闭包,还需证它的 "最小性 "。 为此,令 R′自反,
且 R R′,欲证 IA∪ R R′。 由于 R′自反,据定理 4.4.1,IA R′,连同 R R′，
即得 IA∪ R R′。
（ 2） 本式证明留给读者 。
（ 3）

1
i
i
RR
是显然的。
第 4章 二元关系和函数
【 例 4.5.1】 设 A＝ {1,2,3},R1={〈 1,2〉,〈 2,1〉,
〈 1,3〉,〈 1,1〉 },R2={〈 1,2〉,〈 2,1〉 },
R3={〈 1,2〉 },求它们的闭包 。
解 r(R1)=IA∪ R
={〈 1,1〉,〈 2,2〉,〈 3,3〉,〈 1,2〉,
〈 2,1〉,〈 1,3〉 }
s(R1)=R∪ R -1
={〈 1,2〉,〈 2,1〉,〈 1,3〉,〈 3,1〉,〈 1,1〉 }
第 4章 二元关系和函数
t(R1)={〈 1,2〉,〈 2,1〉,〈 1,1〉,〈 2,2〉,〈 1,3〉,〈 2,3〉 }
r(R2)=IA∪ R={〈 1,1〉,〈 2,2〉,〈 3,3〉,〈 1,2〉,〈 2,1〉 }
s(R2)=R∪ R -1 ={〈 1,2〉,〈 2,1〉 }=R2
t(R2)={〈 1,2〉,〈 2,1〉,〈 1,1〉,〈 2,2〉 }
r(R3)=IA∪ R={〈 1,2〉,〈 1,1〉,〈 2,2〉,〈 3,3〉 }
s(R3)=R∪ R -1 ={〈 1,2〉,〈 2,1〉 }
t(R3)={〈 1,2〉 }=R3
第 4章 二元关系和函数
【 例 4.5.2】 设 R是集合 A={a,b,c,d}上的二元关系,
R={〈 a,b〉,〈 b,a〉,〈 b,c〉,〈 c,d〉 }。 求 R的闭包：
r（ R）,s（ R）,t（ R）,并画出对应的关系图 。
解 r(R)={〈 a,b〉,〈 b,a〉,〈 b,c〉,〈 c,d〉,〈 a,a〉,〈 b,b〉,
〈 c,c〉,〈 d,d〉 }
s(R)={〈 a,b〉,〈 b,a〉,〈 b,c〉,〈 c,d〉,〈 c,b〉,〈 d,c〉 }
t(R)={〈 a,b〉,〈 b,a〉,〈 b,c〉,〈 c,d〉,〈 a,a〉,〈 a,c〉,
〈 b,b〉,〈 b,d〉,〈 a,d〉 }
其对应的关系图分别如图 4.5.1(a),(b),(c)所示 。
第 4章 二元关系和函数图 4.5.1
a b c d
( a )
a b c d a b c d
( b )
( c )
第 4章 二元关系和函数从以上讨论可以看出,传递闭包的求取是很复杂的 。 但是,当集合 A为有限集时,A上二元关系的传递闭包的求取便可大大简化 。
推论 A为非空有限集合,|A|=n。 R是 A上的关系,
则存在正整数 k≤n,使得
t(R)=R +=R∪ R 2∪ … ∪ R k
第 4章 二元关系和函数下列算法是求取 R +的有效算法 。
Warshall(沃夏尔 ) 算法,设 R为有限集 A上的二元关系,|A|=n,M为 R的关系矩阵,可如下求取 R +的关系矩阵 W。
（ 1） 置 W为 M。
（ 2） 置 i=1。
（ 3） 对所有 j,1≤j≤n,做第 4章 二元关系和函数
① 如果 W［ j,i］ =1,则对每一 k=1,2,…,n,置
W［ j,k］ 为 W［ j,k］ ∨ W［ i,k］,即当第 j行,第 i列为 1时,对第 j行每个分量重新置值,取其当前值与第 i
行的同列分量之析取 。
② 否则对下一 j值进行 ① 。
（ 4） 置 i为 i+1。
（ 5） 若 i≤n,回到步骤 （ 3）,否则停止 。
第 4章 二元关系和函数
【 例 4.5.3】 设 A={1,2,3,4,},R={〈 1,1〉,〈 1,2〉,
〈 2,3〉,〈 3,4〉,〈 4,2〉 },则
R 2={〈 1,1〉,〈 1,2〉,〈 1,3〉,〈 2,4〉,
〈 3,2〉,〈 4,3〉 }
R 3={〈 1,1〉,〈 1,2〉,〈 1,3〉,〈 1,4〉,
〈 2,2〉,〈 3,3〉,〈 4,4〉 }
R 4={〈 1,1〉,〈 1,2〉,〈 1,3〉,〈 1,4〉,
〈 2,3〉,〈 3,4〉,〈 4,2〉 }
第 4章 二元关系和函数因此 R +=R∪ R 2∪ R 3∪ R 4={〈 1,1〉,〈 1,2〉,〈 1,
3〉,〈 1,4〉,〈 2,2〉,〈 2,3〉,〈 2,4〉,〈 3,2〉,〈 3,
3,〉,〈 3,4〉,〈 4,2〉,〈 4,3〉,〈 4,4〉 }
现用 Warshall算法求取 R +。
显然，
1 1 0 0
0 0 1 0
0 0 0 1
0 1 0 0
M






第 4章 二元关系和函数以下使用 Warshall算法求取 W。
（ 1） W以 M为初值 。
（ 2） 当 i＝ 1时,由于 W中只有 W［ 1,1］ ＝ l,故需将第一行各元素与其本身作逻辑和,并把结果送第一行 。 即重新置值为 W［ 1,k］ ∨ W［ 1,k］ = W［ 1,
k］,但 W 事实上无改变 。
（ 3） 当 i=2时,由于 W ［ 1,2］ ＝ W ［ 4,2］ ＝ 1，
故需将第一行和第四行各分量重新置值为 W ［ 1,k］
∨ W［ 2,k］ 和 W ［ 4,k］ ∨ W ［ 2,k］ 。 于是有：
第 4章 二元关系和函数
1 1 1 0
0 0 1 0
0 0 0 1
0 1 1 0
W






第 4章 二元关系和函数
（ 4） 当 i=3时,由于 W ［ 1,3］
＝ W ［ 2,3］ ＝ W ［ 4,3］ =1,故需将第一,二,
四行各分量重新置值,分别为 W ［ 1,k］ ∨ W ［ 3,k］
＝ W ［ 1,k］,W ［ 2,k］ ∨ W ［ 3,k］ =W ［ 2，
k］,W ［ 4,k］ ∨ W ［ 3,k］ = W ［ 3,k］ 。 于是有：
1 1 1 1
0 0 1 1
0 0 0 1
0 1 1 1
W






第 4章 二元关系和函数
（ 5） 当 i＝ 4时,由于 W ［ 1,4］ ＝ W ［ 2,4］ =
W ［ 3,4］ = W ［ 4,4］ =1,故需将第一,二,三,
四行各分量重新置值,分别为 W ［ 1,k］ ∨ W ［ 4,k］
＝ W ［ 1,k］,W ［ 2,k］ ∨ W ［ 4,k］ = W ［ 2，
k］,W ［ 3,k］ ∨ W［ 4,k］ = W ［ 3,k］,W
［ 4,k］ ∨ W［ 4,k］ = W ［ 4,k］ 。 最终 W 为
1 1 1 1
0 1 1 1
0 1 1 1
0 1 1 1
W






第 4章 二元关系和函数故 R +＝ {〈 1,1〉,〈 1,2〉,〈 1,3〉,〈 1,4〉,〈 2,
2〉,〈 2,3〉,〈 2,4〉,〈 3,2〉,〈 3,3,〉,〈 3,4〉,〈 4,
2〉,〈 4,3〉,〈 4,4〉 }。
第 4章 二元关系和函数下面几个定理给出了闭包的主要性质 。
定理 4.5.2 设 R是集合 A上任一关系,那么
（ 1） R自反当且仅当 R=r(R)。
（ 2） R对称当且仅当 R=s(R)。
（ 3） R传递当且仅当 R=t(R)。
第 4章 二元关系和函数证明 （ 1）,（ 3） 的证明留给读者,现证 （ 2） 。
（ 2） 的充分性由 s(R)定义立得 。
为证必要性,设 R对称,那么 R＝ R-1 （据定理
4.4.1）。 另一方面,s(R)=R∪ R-1 =R∪ R=R,故
s(R)=R。
定理 4.5.3 对非空集合 A上的关系 R1,R2若 R1 R2，
则
（ 1） r(R1) r(R2)
（ 2） s(R1) s(R2)
（ 3） t(R1) t(R2)
第 4章 二元关系和函数证明 （ 1） 和 （ 2） 的证明留作练习,下面仅证明 （ 3） 。
因为 t(R2)传递,且 t(R2) R2,但 R1 R2，
故 t(R2) R1。
因 t(R1)是包含 R1的最小传递关系,所以 t(R1) t(R2)。

第 4章 二元关系和函数定理 4.5.4 对非空集合 A上的关系 R1,R2,则
（ 1） r(R1)∪ r(R2)=r(R1∪ R2)
（ 2） s(R1)∪ s(R2)=s(R1∪ R2)
（ 3） t(R1)∪ t(R2) t(R1∪ R2)?
第 4章 二元关系和函数证明 (1） 和 （ 2） 的证明留作练习,下面仅证明 （ 3） 。
因为 R1∪ R2 R1,由定理 4.5.3知
t(R1∪ R2) t(R1)
同理 t(R1∪ R2) t(R2)
所以 t(R1∪ R2) t(R1)∪ t(R2)
第 4章 二元关系和函数定理 4.5.5 设 R是集合 A上任意二元关系,则
（ 1） 如果 R是自反的,那么 s(R)和 t(R)都是自反的 。
（ 2） 如果 R是对称的,那么 r(R)和 t(R)都是对称的 。
（ 3） 如果 R是传递的,那么 r(R)是传递的 。
第 4章 二元关系和函数证明
（ 1） 是显然的 。
（ 2） 由于
r(R) -1 =(IA∪ R) -1 =I -1A∪ R -1 =IA∪ R=r(R),故 r(R)
是对称的。
另外,由于对任意自然数 n，
(R n) -1 =(R -1 ) n（ 据定理 4.3.4）,又由于 R对称,
故 (R n) -1 =R n。 因此,对任意 〈 x,y〉 ∈ t(R),总有 i
使 〈 x,y〉 ∈ R i,从而 〈 y,x〉 ∈ (R i) -1 =R i,即 〈 y,
x〉 ∈ t(R)。 故 t(R)对称 。
第 4章 二元关系和函数
（ 3） 本式证明留给读者。 请注意,R传递并不保证 s(R)传递。 例如,R={〈 a,b〉 }是传递的,但是
s(R)={〈 a,b〉,〈 b,a〉 }却不是传递的。
第 4章 二元关系和函数定理 4.5.6 设 R为集合 A上的任一二元关系,那么
（ 1） rs(R)＝ sr(R)
（ 2） rt(R)＝ tr(R)
（ 3） st(R) ts(R)
证明
（ 1） sr(R) =s(IA∪ R)=IA∪ R∪ (IA∪ R) -1
=IA∪ R∪ R -1 =IA∪ s(R)=rs(R)
第 4章 二元关系和函数
（ 2） 易证
1
() niAA
i
I R I R
对一切正整数 n均成立 （ 见本章习题 24）,于是
1
1 1 1 1
1
( ) ( ) ( )
( ) ( )
( ) ( )
i
AA
i
jj
AA
i j i j
i
A
i
A
tr R t I R I R
I R I R
IR
I t R rt R




第 4章 二元关系和函数
（ 3） 由定理 4.5.3可知,任一闭包运算 Δ和任意二元关系 R1,R2,如果 R1 R2,那么 Δ(R1) Δ(R2)； 又据闭包定义,对任意二元关系 R有 R s(R),故 t(R)
ts(R),st(R) sts(R) 。 由于 ts(R) 是对称的 （ 据定理
4.5.5）,由定理 4.5.2知 sts(R)＝ ts(R)。 于是可得到
st(R) ts(R)
第 4章 二元关系和函数
【 例 4.5.4】 设 R是集合 X上的二元关系,X={a,b,c}，
R={〈 a,b〉,〈 b,c〉 }。 求 st(R)和 ts(R),并画出关系图 。
解 t（ R） ={〈 a,b〉,〈 b,c〉,〈 a,c〉 }
st(R)={〈 a,b〉,〈 b,c〉,〈 a,c〉,〈 b,a〉,
〈 c,b〉,〈 c,a〉 }
s(R)={〈 a,b〉,〈 b,c〉,〈 b,a〉,〈 c,b〉 }
ts(R)={〈 a,b〉,〈 b,c〉,〈 b,a〉,〈 c,b〉,〈 a,c〉,
〈 a,a〉,〈 b,b〉,〈 c,a〉,〈 c,c〉 }
st(R)和 ts(R)的关系图分别如图 4.5.2(a),(b)所示。
第 4章 二元关系和函数图 4.5.2
a
b c
( b )
a
b c
( a )
第 4章 二元关系和函数
4.6 等价关系和划分本节的目的就是要研究可用以对集合中元素进行分类的一种重要二元关系 --等价关系 。
定义 4.6.1 设 R是非空集合 A上的二元关系,如果 R
是自反的,对称的和传递的,则称 R 为 A 上的等价关系（ equivalent relation）。
第 4章 二元关系和函数
【 例 4.6.1】
（ 1) 人类集合中的 "同龄 ","同乡 "关系都是等价关系 。
（ 2） 三角形集合的相似关系,全等关系都是等价关系 。
（ 3） 住校学生的 "同寝室关系 "是等价关系 。
（ 4） 命题公式间的逻辑等价关系是等价关系 。
（ 5） 对任意集合 A,A上的恒等关系 IA和全域关系 A× A
是等价关系。
第 4章 二元关系和函数
【 例 4.6.2】 设 A={1,2,3,4} 且 R={〈 1,1〉,
〈 1,2〉,〈 2,1〉,〈 2,2〉,〈 3,4〉,〈 4,3〉,〈 3,3〉,
〈 4,4〉 }。 我们易证 R是一个等价关系 。
【 例 4.6.3】 整数集合 I中的二元关系
R={〈 x,y〉 |m|(x-y),m∈ I+},其中 "|"表示整除关系,证明 R是等价关系 。
第 4章 二元关系和函数证明
（ 1） x∈ I,因为 x-x=0,所以 m|(x-x),因此 〈 x,x〉
∈ R,R是自反的 。
（ 2） x,y∈ I,设 〈 x,y〉 ∈ R,则 m|(x-y),即
xy kI
m

y x x y kI
mm

故 〈 y,x〉 ∈ R,所以 R是对称的。
第 4章 二元关系和函数
（ 3） x,y,z∈ I,设 〈 x,y〉 ∈ R且 〈 y,z〉 ∈ R,则
xy kI
m
yx lI
m

因而
x z x y y z k l I
mm

故 〈 x,z〉 ∈ R,所以 R是传递的。
因此,R是一个等价关系。
第 4章 二元关系和函数定义 4.6.2 设 R为集合 A上的等价关系 。 对每一
a∈ A,令 A中所有与 a 等价的元素构成的集合记为
［ a］ R,即形式化为
［ a］ R=｛ x|x∈ A∧ xRa｝
称 ［ a］ R为 a的关于 R所生成的等价类 （ equivalent
class）,简称 a的等价类,简单地记为 ［ a］,a称为
［ a］ R的代表元素 。
第 4章 二元关系和函数
【 例 4.6.4】 设 R是 X={0,1,2,3,4}上的二元等价关系,R={〈 x,y〉 |x,y(X且 (x-y)/2是整数 }。
(1) 给出关系矩阵；
(2) 画出关系图；
(3) 求出等价类 。
第 4章 二元关系和函数解 （ 1） R的关系矩阵为 1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
R
M








（ 2） R的关系图如图 4.6.1所示 。
（ 3） ［ 0］ R=［ 2］ R=［ 4］ R={0,2,4}
［ 1］ R=［ 3］ R={1,3}
第 4章 二元关系和函数
【 例 4.6.５ 若在例 4.6.2中取 m=4,即设 R为整数集上的 ≡4关系,它有四个不同的等价类；
［ 0］ =｛ …,-12,-8,-4,0,4,8,12,…｝ =｛ x|4整除 x｝
［ 1］ =｛ …,-11,-7,-3,1,5,9,13,…｝ =｛ x|4除 x余 1｝
［ 2］ =｛ …,-10,-6,-2,2,6,10,14,…｝ =｛ x|4除 x余 2｝
［ 3］ =｛ …,-9,-5,-1,3,7,11,15,…｝ =｛ x|4除 x余 3｝
下面几个定理介绍等价类的性质 。
第 4章 二元关系和函数定理 4.6.1 设 R是非空集合 A上的等价关系 。
（ 1） 对任意的 a∈ A,［ a］ R≠Φ,且 ［ a］ R A,
［ a］ R是 A的非空子集 。
（ 2） ∪ {［ a］ |a∈ A}=A(∪ S表示集合 S中的元素做并运算所构成的集合 )。
证明 （ 1） 对任意的 a∈ A,因为 R自反,aRa所以恒有 a∈ ［ a］ R。
第 4章 二元关系和函数
(2) 先证 ∪ {［ a］ |a∈ A} A。 任取 x,有
x∈∪ {［ a］ |a∈ A} y(y∈ A∧ x∈ ［ y］ )
x∈ A (因为 ［ y］ A)
从而有 ∪ {［ a］ (a∈ A} A。
再证 A ∪ {［ a］ |a∈ A}。 任取 x,有
x∈ A x∈ ［ x］ ∧ x∈ A
x∈∪ {［ a］ (a∈ A}
所以 A ∪ {［ a］ (a∈ A}成立 。
因此 ∪ {［ a］ |a∈ A}=A。

第 4章 二元关系和函数定理 4.6.2 设 R是集合 A上的等价关系,那么,对任意 a,b∈ A,有 aRb 当且仅当 ［ a］ R=［ b］ R
证明 设 aRb。 为证 ［ a］ R ［ b］ R,又设
x∈ ［ a］ R,那么 xRa。 又据 aRb及 R的传递性,有
xRb,从而 x∈ ［ b］ R。 ［ a］ R∈ ［ b］ R得证 。
同理可证 ［ b］ ［ a］ 。 于是 ［ b］ =［ a］ 得证 。
反之,设 ［ a］ R=［ b］ R。 由于 a∈ ［ a］ R,故
a∈ ［ b］ R,因而 aRb。
第 4章 二元关系和函数定理 4.6.3 设 R是集合 A上的等价关系,那么,对任意 a,b∈ A,或者［ a］ R=［ b］ R或者
［ a］ R∩［ b］ R=Φ。
证明 设 ［ a］ R∩［ b］ R≠Φ,那么有
x∈ ［ a］ R∩［ b］ R,从而有 xRa,xRb。 据 R的对称性又有 aRx,xRb。 再用 R的传递性,得 aRb。 由定理
4.6.2 知 ［ a］ R=［ b］ R。
第 4章 二元关系和函数由定理 4.6.2,定理 4.6.3知,对任何集合 A上的等价关系 R，
有对任何 a,b∈ A，
aRb［ a］ R=［ b］ R［ a］ R∩［ b］ R≠Φ关于等价类有下面十分显然的事实：
（ 1） 对任何集合 A,IA有 ( A (个不同的等价类,每个等价类都是单元素集 。
（ 2） 对任何集合 A,A(A只有一个等价类 为 A
（ 即每个元素的等价类全为 A） 。
（ 3） 同一等价类可以有不同的表示元素,或者说,
不同的元素,可能有相同的等价类 。
第 4章 二元关系和函数定义 4.6.3 当非空集合 A的子集族 π（ π P(A)） 满足下列条件时称为 A的一个划分 （ partitions）,
（ 1） 对任意 B∈ π,B≠Φ。
（ 2） 对任意 B∈ π,B A。
（ 3） ∪ π＝ A。
（ 4） 对任意 B,B′∈ π,B≠B′时,B∩B′=Φ。
则称 π中元素为划分的划分块 。
第 4章 二元关系和函数
【 例 4.6.6】 设 A＝ {0,1,2,3,4 },则
π1={{1,3},{0,2,4}}
π2={{0,1,3},{2,4}}
π3={{3},{0,l,2,4}}
π4={{0,l,2,3,4}}
均为 A的划分,且 π1中的元素恰是例 4.6.3的等价类 。
第 4章 二元关系和函数定理 4.6.4 设 R为集合 A上的等价关系,那么 R对应的 A划分是 {［ x］ R|x(A}。
该定理的证明留作练习 。
定理 4.6.5 设 π是集合 A的一个划分,则如下定义的关系 R为 A上的等价关系：
R=｛ 〈 x,y〉 | (B(B∈ π∧ x∈ B∧ y∈ B)｝
称 R为 π对应的等价关系 。
证明是极为容易的,请读者自己完成 。
第 4章 二元关系和函数定理 4.6.6 设 π是集合 A的划分,R是 A上的等价关系,
那么,对应 π的等价关系为 R,当且仅当 R对应的划分为 π。
证明 A=Φ时,只有 Φ划分和等价关系 Φ,结论显然成立 。 下文设 A≠Φ。
先证必要性 。 设对应 π的等价关系为 R,R对应的划分为 π′,欲证 π=π′。 为此对任一元素 a∈ A,设 B，
B′分别是 π,π′中含 a的单元 。 那么,对 A中任一元素 b，
有第 4章 二元关系和函数
b∈ B aRb （ R是对应的等价关系 ）
b∈ ［ a］ R
b∈ B′ （ π′是 R对应的划分 ）
这就是说 B=B′。 由于 a是 A中任意元素,故可断定 π=π′。
第 4章 二元关系和函数再证充分性 。 设 R对应的划分为 π,π对应的等价关系为 R′,欲证 R=R′。 为此考虑对 A中任意元素 a,b，
有
aRb b∈ ［ a］ R
B(B∈ π∧ ［ a］ R=B∧ b∈ B)
(π为 R对应的划分 )
B(B∈ π∧ a∈ B∧ b∈ B)
aR′b
（ R′为 π对应的等价关系 ）
故 R=R′。
第 4章 二元关系和函数
【 例 4.6.7】 设 A 是一个集合且 |A|=4,则 A 上共有多少种不同的等价关系？
解 本题利用划分与等价关系的一一对应,用划分求等价关系,具体求解见表 4.6.1。
第 4章 二元关系和函数表 1.6.1
第 4章 二元关系和函数定义 4.6.4 设 R为集合 A上的等价关系,那么称 A的划分 {［ a］ R|a∈ A}为 A关于 R的商集（ quotient sets），
记为 A/R。
例 4.6.8 设关系 R是例 4.6.2中定义的,计算 A/R。
解 从该例子中,我们有
［ 1］ R={1,2}=［ 2］ R,同时 ［ 3］ R={3,4}=［ 4］ R。 所以 A/R={{1,2},{3,4}}。
第 4章 二元关系和函数
【 例 4.6.9】 在例 4.6.3中的等价关系中,取 m=2。
求 A/R。
解
［ 0］ ={…,-6,-4,-2,0,2,4,6,8,…},即由偶整数组成,因为它们整除 2的余数是 0。
［ 1］ ={…,-5,-3,-1,1,3,5,7,…},即由奇整数组成,因为它们整除 2的余数是 1。 因此 A/R是由偶整数集合和奇整数集合组成的集合 。
第 4章 二元关系和函数由上两个例子我们有对有穷集合 A如何求 A/R的步骤：
(1) 从集合 A中任意选一个元素 a,并计算 a所在的等价类 ［ a］ 。
(2) 如果 ［ a］ ≠A,选另一个元素 b,b∈ A且 b
［ a］,计算 ［ b］ 。
(3) 如果 A不与上面计算的所有等价类的并相等,
则在 A中选不在这些等价类中的元素 x且计算 ［ x］ 。
(4) 重复 (3)直到集合 A与所有等价类的并相等,则结束 。
第 4章 二元关系和函数定义 4.6.5 设 π1,π2为集合的两个划分 。 称 π1细分
π2,如果 π1的每一划分块都包含于 π2的某个划分块 。
π1细分 π2表示为 π1≤π2。 π1≤π2且 π1≠π2,则表示为 π1
＜ π2,读作 π1真细分于 π2。
第 4章 二元关系和函数
【 例 4.6.10】 当 A=｛ a,b,c,d｝ 时,
π1=｛｛ a,b｝,
｛ c｝,｛ d｝｝ 细分 π2=｛｛ a,b,c｝,｛ d｝｝,
π3=｛｛ a｝,｛ b｝,｛ c｝,｛ d｝｝ 细分所有划分 。 而所有划分均细分 π4=｛｛ a,b,c,d｝｝ 。 并且,π1真细分 π2,π3真细分 π1。
第 4章 二元关系和函数定理 4.6.7 设 R1,R2为集合 A上的等价关系,
π1,π2分别是 R1,R2所对应的划分,那么
R1 R2 当且仅当 π1≤π2
证明 当 A=Φ时命题显然真 。 以下设 A≠Φ。
先证必要性。 设 R1 R2,B1为 π1中任一划分块，
令 B1=［ a］ R1,a∈ A。 考虑［ a］ R2 =B2∈ π2。 对任一 b∈ B1,即 b∈ ［ a］ R1,有 bR1a,从而有 bR2a（因
R1 R2）,故 b∈ ［ a］ R2 =B2。 这就是说 B1 B2,因而 π1≤π2。
第 4章 二元关系和函数再证充分性。 设 π1≤π2,对任意 x,y,若 xR1y,那么有 π1中划分块 B1＝［ x］ R,使 x,y∈ B1。 由于 π1≤π2，
故有 π2中划分块 B2,使 B1 B2,从而 x,y∈ B2,即 x，
y属同一个 R2等价类,因此 xR2y。 至此我们证得 R1 R2。
本定理表明,越 "小 "(含有较少序偶 )的等价关系对应越细的划分,反之亦然。 很明白,最小的等价关系是相等关系,它对应于最细的划分（每一划分块恰含一个元素）,最大的等价关系是全关系,它对应于最粗的划分（只有一个划分块）。
第 4章 二元关系和函数
4.7 序 关 系序关系是关系的一大类型,它们的共同点是都具有传递的,因此可根据这一特性比较集合中各元素的先后顺序 。 事物之间的次序常常是事物群体的重要特征,决定事物之间次序的还是事物间的关系 。 本节的目的则是要研究可用以对集合中元素进行排序的关系 --
序关系 。 其中很重要的一类关系称作偏序关系 。 偏序的作用是用来排序 （ 称偏序是因为 A上的所有元素不一定都能按此关系排序,所以又称为半序,部分序 ） 。
第 4章 二元关系和函数定义 4.7.1 设 R是非空集合 A上的二元关系,如果 R
是自反,反对称,传递的,称 R为 A上的偏序关系
（ partial ordered relations）,。 如果集合 A上有偏序关系 R,则称 A为偏序集 （ ordered sets）,用序偶 〈 A,R〉 表示之 。 若 〈 x,y〉 ∈,常记作 x y,读作 "x小于或等于 y",说明 x在偏序上排在 y的前面或者相同 。 为简明起见,
系,从而 〈 A,〉 表示一般的偏序集 。
第 4章 二元关系和函数
【 例 4.7.1】
（ 1） 设 A是集合 S的子集为元素所构成的集合,包含关系 " "是 A 上的一个偏序关系,因此 〈 A,〉 是一个偏序集 。
（ 2） 实数集 R上的 "≤"即小于等于关系为一偏序关系,〈 R,≤〉 表示偏序集 。 实数集 R上的 "≥"即大于关系也是偏序关系,〈 R,≥〉 也表示一个偏序集 。 7≥6，
可以写作 7 6,理解为在大于等于偏序关系中,7排在 6的前面,或说 7比 6大 。
第 4章 二元关系和函数定义 4.7.2 设 R为非空集合 A上的偏序关系,
（ 1） x,y∈ A,若 x y或 y x,则称 x与 y可比 。
（ 2） x,y∈ A,若 x y且 x≠y,则称 x y,读作 x小于 y。 这里所说的小于是指在偏序中 x排在 y的前边 。
由上面的定义可知,A中任取两个元素 x和 y,可能有下述几种情况发生：
x y（或 y x）,x=y,x与 y不是可比的。
第 4章 二元关系和函数例如,实数集合上的小于等于关系是偏序关系且任意两个数均是可比的 。 而正整数上的整除关系也是偏序关系,但不是任意两个数都可比,如 2与 3不可比,
因为 2不能整 除 3。
我们可对偏序关系的关系图作简化 。 由于偏序关系自反,各结点处均有环,约定全部略去 。
第 4章 二元关系和函数由于偏序关系反对称且传递,关系图中任何两个不同结点之间不可能有相互到达的边或通路,因此可约定边的向上方向为箭头方向,省略全部箭头 。 最后由于偏序关系具有传递性,我们还可将由传递关系可推定的边也省去 。 经过这种简化的具有偏序关系的关系图称为哈斯 （ Hasse） 图 。 哈斯图既表示一个偏序关系,又表示一个偏序集 。
第 4章 二元关系和函数
【 例 4.7.2】 表示集合 {a,b}的幂集 P(｛ a,b｝ )上的子集包含关系的关系图,可如图 4.7.1作简化 。
为了说明哈斯图的画法,首先定义“覆盖”的性质。
定义 4.7.3 设偏序集 〈 A,,如果 x,y∈ A,x y,
x≠y,且不存在元素 z∈ A,使得 x z 且 z y,则称 y覆盖 x。 A上的覆盖关系 cov A定义为
cov A={〈 x,y〉 |x∈ A∧ y∈ A∧ y盖住 x}
第 4章 二元关系和函数图 4.7.1
{ a }
{ b }
{ a,b }
{ a } { b }
{ a,b }
( a ) ( b )
第 4章 二元关系和函数
【 例 4.7.3】 设 A是正整数 m=12的因子的集合,并设为整除的关系,求 cov A。
解
cov A={〈 1,2〉,〈 1,3〉,〈 2,4〉,〈 2,6〉,〈 3,6〉,
〈 4,12〉,〈 6,12〉 }
第 4章 二元关系和函数
【 例 4.7.4】 例 4.7.2中,cov P({a,b})={ 〈 (,{a}〉,
〈 (,{b}〉,〈 {a},{a,b}〉,〈 {b},{a,b}〉 }。
定的偏序集 〈 A,〉,它的覆盖关系是唯一的,所以可用覆盖的性质画出偏序集合图,又称为哈斯图,其作图法为：
(1) 以 "ο "表示元素 ;
(2) 若 x y,则 y画在 x的上层 ;
(3) 若 y覆盖 x,则连线 ;
(4) 不可比的元素,可画在同一层 。
第 4章 二元关系和函数
【 例 4.7.5】 画出下面几个偏序集的哈斯图：
（ 1） 〈 S8,|〉,其中 S8表示 8的所有因子作元素构成的集合 。
（ 2） 〈 ｛ 2,3,6,12,24,36｝,|〉,其中 "|"是集合上的数之间的整除关系 。
（ 3） 〈 S 30,|〉,其中 S 30 表示 30 的所有因子作元素构成的集合。
第 4章 二元关系和函数解 先分别求出其覆盖 。
（ 1） S8={1,2,4,8}
cov{S8}={〈 1,2〉,〈 2,4〉,〈 4,8〉 }
（ 2） cov{2,3,6,12,24,36}
= {〈 2,6〉,〈 3,6〉,〈 6,12〉,〈 12,24〉,〈 12,36〉 }
第 4章 二元关系和函数
（ 3） S 30 ={1,2,3,5,6,10,15,30}
cov S 30 ={〈 1,2〉,〈 1,3〉,〈 1,5〉 〈 2,6〉,
〈 2,10〉 〈 3,6〉,〈 3,15〉,〈 5,10〉,
〈 5,15〉,〈 6,30〉,〈 10,30〉,〈 15,30〉 }
画出其哈斯图,如图 4.7.2所示,（ a）,（ b）,
（ c） 分别表示上述各偏序集 。
第 4章 二元关系和函数
（ 3） S 30 ={1,2,3,5,6,10,15,30}
cov S 30 ={〈 1,2〉,〈 1,3〉,〈 1,5〉 〈 2,6〉,
〈 2,10〉 〈 3,6〉,〈 3,15〉,〈 5,10〉,〈 5,15〉,
〈 6,30〉,〈 10,30〉,〈 15,30〉 }
画出其哈斯图,如图 4.7.2所示,（ a）,（ b）、
（ c）分别表示上述各偏序集。
第 4章 二元关系和函数图 4.7.2
8
4
2
1
24 36
12
6
2 3
30
10
3
1
2
6
5
15
( a ) ( b ) ( c )
第 4章 二元关系和函数
【 例 4.7.6】 由图 4.7.3所示的哈斯图,写出对应的偏序关系,关系矩阵 。
解 A={a,b,c,d,e}
={〈 a,a〉,〈 b,b〉,〈 c,c〉,
〈 d,d〉,〈 e,e〉,〈 c,a〉,〈 c,b〉,〈 d,e〉,
〈 d,a〉,〈 d,b〉 }
第 4章 二元关系和函数图 4.7.3
a b
c e
d
第 4章 二元关系和函数关系矩阵
1 0 0 0 0
0 1 0 0 0
1 1 1 0 0
1 1 1 1 0
0 0 0 0 1
M








偏序集中链和反链的概念是十分重要的。
第 4章 二元关系和函数定义 4.7.4 设偏序集 〈 A,〉,B A。
(1) 如果对任意的 x,y∈ B,x和 y 都是可比的,则称 B为 A上的链 （ chain）,B中元素个数称为链的长度 。
(2) 如果对任意的 x,y∈ B,x和 y 都不是可比的,
则称 B 为 A上的反链 （ antichain）,B中元素个数称为反链的长度 。
我们约定,若 A的子集只有单个元素,则这个子集既是链又是反链。
第 4章 二元关系和函数
【 例 4.7.7】 图 4.7.4中的哈斯图表示一偏序集,举例说明链及反链 。
长度为 5的链有 {a,c,e,h,m },{a,b,e,i,n}等 。
长度为 4的链有 {b,d,g,m},{c,e,h,k},{c,d,f,j}等 。
长度为 3的链有 {b,e,i},{f,d,c},{n,i,e}等 。
长度为 2的链有 {d,f},{m,h}等 。
长度为 1的链有 {m},{n}等 。
长度为 4的反链只有 {b,c,d,e}和 {n,m,k,i}。
长度为 3的反链有 {j,k,i},{f,g,e},{d,h,i}等 。
长度为 2的反链有 {d,e},{b,c},{g,h},{f,e}等 。
长度为 1的反链有 {a},{e}等 。
第 4章 二元关系和函数图 4.7.4
c
a
b
d
f
j
g
k m n
h i
e
第 4章 二元关系和函数定义 4.7.5 设偏序集 〈 A,〉,如果 A是一个链,
A上的全序关系,或称线序关系 。
并称 〈 A,〉 为全序集 (totally ordered)。 全序集
〈 A,〉 意味着对任意 x,y∈ A,或者有 x y或者有 y x
成立 。
例如,实数集合上的小于等于关系是偏序关系且任意两个数均是可比的,所以也是全序关系 。 利用偏序关系可对有序集合中元素进行比较或排序 。 在哈斯图中,各元素都处在不同的层次上,有的元素的位置特殊,它们是偏序集合中的特殊元素,了解这些元素有助于我们对偏序集合进行深入分析 。
第 4章 二元关系和函数定义 4.7.6 设 〈 A,〉 为偏序集,B A。
（ 1） 如果 b∈ B且对每一 x∈ B,b x,称 b为 B的最小元 （ least element） 。 即 b为 B的最小元
b∈ B∧ x(x∈ B→b x)

第 4章 二元关系和函数
（ 2）如果 b∈ B，并且对每一 x∈ B,x b，称 b为 B
greatest element ）。即 b为 B的最大元
b∈ B∧ x( x∈ B→x b)
（ 3）如果 b∈ B，并且没有 x∈ B,x≠b，使得 x b，
称 b为 B minimal element ）。即
b为 B b∈ B∧ x(x∈ B∧ x≠b∧ x b)
第 4章 二元关系和函数
（ 4）如果 b∈ B，并且没有 x∈ B,x≠b，使得 b x，
称 b为 B maximalelement ）。即
b为 B b∈ B∧ ﹁ x(x∈ B∧ x≠b∧ b x)?
第 4章 二元关系和函数从以上定义可以看出，最小元与极小元是不一样的。最小元是 B中最小的元素，它与 B中其它元素都可比；而极小元不一定与 B中元素都可比，只要没有比它更小的元素，它就是极小元，同理最大元是 B中最大的元素，它与 B中其它元素都可比；而极大元不一定与 B
中元素都可比，只要没有比它更大的元素，它就是极大元。
第 4章 二元关系和函数
【 例 4.7.8】 偏序集 〈 {1,2,3,4,5,6,7,8},，由图
4.7.5所示哈斯图给出。
（ 1） B={1,2,3,5}
B的最大元为 5。
B的极大元为 5。
B的最小元为 1。
B的极小元也为 1。
第 4章 二元关系和函数图 4.7.5
8
7
5
3
1
2
4
6
第 4章 二元关系和函数
（ 2） B={2,3,4,5,6,7}
B无最大元和最小元。
B的极大元是 6,7，极小元是 2,3。
（ 3） B={4,5,8}
B的最大元是 8，无最小元。
B的极大元为 8，极小元为 4,5。
（ 4） B={4,5}
B无最大元，也无最小元。
B的极大元是 4,5，极小元也是 4,5。
第 4章 二元关系和函数从例 4.7.8中可知，最大元、最小元未必存在，若存在则必唯一。极大元、极小元虽存在，但却不唯一，
它们之间不可比，并处在子集哈斯图的同一层次上，
极大元在最高层，极小元在最低层。关于这些，有下面的定理。
第 4章 二元关系和函数定理 4.7.1 设 〈 A,为偏序集,B A。
（ 1）若 b为 B的最大（最小）元，则 b为 B的极大
（极小）元。
（ 2）若 B有最大（最小）元，则 B的最大（最小）
元唯一。
（ 3）若 B为有限集，则 B的极大元、极小元恒存在。
第 4章 二元关系和函数当 n=1时,B中仅有一个元素，它既是极大元，也是极小元。当 n=2时，设 B={b1,b2}。那么,b1 b2时 b1
为极小元,b2为极大元； b2 b1时 b2为极小元,b1为极大元； ﹁ b1 b2且 ﹁ b2 b1时,b1,b2同为极大元，也同为极小元。
第 4章 二元关系和函数设 n=k时命题为真。若 n=k+1,B={b1,b2,…,bk,bk+1}。
据归纳假设,{b1,b2,…,bk}有极大元 bi，极小元 bj。考虑
{bi,bk+1}，若 bi bk+1,bk+1 显然是 B的极大元；若
bk+1 bi，或两者不可比较，则 bi是 B的极大元。同理可证,bj或 bk+1 是 B的极小元。
归纳完成，（ 3）得证。
第 4章 二元关系和函数
【 例 4.7.9】 在例 4.7.5中的（ 3）题中设子集
B={15,5,6}，则子集 B的极大元,15,6；极小元,5,6；
最大元：无；最小元：无。
在例 4.7.6中,A的极大元是 a,b； A的极小元是
d,e;A无最大元；也无最小元。
定理 4.7.2(偏序集的分解定理 ) 设 〈 A,为一有限的偏序集，且 A中最长链的长度为 n，则将 A中元素分成不相交的反链，反链个数至少是 n。即 A有一划分，使划分有 n个划分块，且每个划分块为一反链。
第 4章 二元关系和函数证明 对 n进行归纳。
当 n=1时,A
因此 A本身既为一链，又为一反链，因此划分 {A}即满足要求。
设 n=k时命题成立。现令 n=k+1。
第 4章 二元关系和函数设 M为 A中所有极大元素的集合。由于 A为有限集，
因此 M必为一非空的反链（极大元之间是不可比较的）。考虑有序集 〈 A-M 〉,它不可能有长度为 n
的链（否则 A中链的长度将超过 n，关于这一点请读者思考），因而 〈 A-M 〉 中最长链的长度应当为 n-
1=k。据归纳假设,A-M有 k个划分块的划分，且每个划分块为一反链。这 k个反链连同反链 M，恰构成 A的 k+1
个划分块组成的划分。所以归纳完成。
第 4章 二元关系和函数定理 4.7.3 设 〈 A,为一偏序集,|A|=mn+1，那么,A中或者存在一条长度为 m+1的反链，或者存在一条长度为 n+1的链。
证明 若 A中链的长度不超过 n，那么据定理 4.7.2,A
中必有长度为 m+1个划分块的反链，否则 |A|≤mn。
第 4章 二元关系和函数定义 4.7.7 设 〈 A,为偏序集,B A。
（ 1）如果 a∈ A，且对每一 x∈ B,x a，称 a为 B的
upperbound ）。即
a为 B a∈ A∧ x(x∈ B→x a)
（ 2）如果 a∈ A，且对每一 x∈ B,a x,a称为 B的
lowerbound ），即
a为 B a∈ A∧ x(x∈ B→a x)
（ 3）如果 C是 B的所有上界的集合，即 C={y|y是 B
的上界 }，则 C的最小元 a称为 B的最小上界或上确界
leastupperbound ）。
第 4章 二元关系和函数
（ 4）如果 a是 B的所有下界的集合，即 C={y|y是 B的上界 }，则 C的最大元 a称为 B
greatestlowerbound ）。
从以上定义可知,B的最小元一定是 B的下界，同时也是 B的最大下界。同样地,B的最大元一定是 B的上界，同时也是 B的最小上界。但反过来不一定正确，
B的下界不一定是 B的最小元，因为它可能不是 B中的元素。同样地,B的上界也不一定是 B
第 4章 二元关系和函数
【 例 4.7.10】 设偏序集 〈 A,如图 4.7.4所示，考虑集合 B={h,i}，它有上界 j,k，但无最小上界；它有下界 f,g等，但没有最大下界。当 B={b,c,d,e}时，它有上界 h,i等，无最小上界；它没有下界和最大下界。
再设偏序集 〈 A,如图 4.7.5所示。
（ 1）当 B={2,3,4,5,7}时,B有上界 7,8,下界 1；最小上界 7，最大下界 1。
第 4章 二元关系和函数
（ 2）当 B={2,5,4,6}时,B有上界 8，下界 2,1；最小上界 8，最大下界 2。
第 4章 二元关系和函数定理 4.7.4 设 〈 A,为偏序集,B A。
（ 1）若 b为 B之最大元（最小元），则 b必为 B最小上界（最大下界）。
（ 2）若 b为 B之上（下）界，且 b∈ B，则 b必为 B的最大（最小）元。
（ 3）如果 B有最大下界（最小上界），则最大下界（最小上界）唯一。
证明略。
第 4章 二元关系和函数定义 4.7.8 设 〈 A,为偏序集，如果 A的任何非空子集都有最小元,well founded
relation ）,称 〈 A,为良序集 ( well ordered set )。
第 4章 二元关系和函数
【 例 4.7.11】 设 I n={1,2,…}及 N={1,2,3,…},对于小于等于关系来说是良序集合，即 〈 I n,是良序集合。
定理 4.7.5 一个良序集一定是全序集。
证明 设 〈 A,为良序集合，则对任意两个元素
x,y∈ A可构成子集 {x,y},必存在最小元素，这个最小元素不是 x就是 y,因此一定有 x y或 y x。所以 〈 A,
为全序集合。
第 4章 二元关系和函数定理 4.7.6 一个有限的全序集一定是良序集。
证明 设 A={a1,a2,…,an},令 〈 A,是全序集合。
用反证法，假定 〈 A,不是良序集合，则必存在一个非空子集 B A,在 B中不存在最小元素，由于 B是一个有限集合，故一定可以找出两个元素 x与 y是无关
〈 A,是全序集,x,y∈ A,所以 x,y必有关系，得出矛盾，故 〈 A,必是良序集合。
第 4章 二元关系和函数上述结论对于无限的全序集合不一定成立。
例如，大于 0小于 1的全部实数，按大小次序关系是一个全序集合，但不是良序集合，因为集合本身就不存在最小元素。
定理 4.7.8（良序定理） 任意的集合都是可以良序化的。
第 4章 二元关系和函数
4.8 函数的定义和性质函数概念是最基本的数学概念之一，也是最重要的数学工具。初中数学中函数定义为 "对自变量每一确定值都有一确定的值与之对应 "的因变量；高中数学中函数又被定义为两集合元素之间的映射。
第 4章 二元关系和函数现在，我们要把后一个定义作进一步的深化，用一个特殊关系来具体规定这一映射，称这个特殊关系为函数，因为关系是一个集合，从而又将函数作为集合来研究。离散结构之间的函数关系在计算机科学研究中也已显示出极其重要的意义。我们在讨论函数的一般特征时，总把注意力集中在离散结构之间的函数关系上，但这并不意味着这些讨论不适用于其它函数关系。
第 4章 二元关系和函数定义 4.8.1 设 X,Y为集合，如果 f为 X到 Y的关系
（ f X× Y），且对每一 x∈ X，都有唯一的 y∈ Y，使
〈 x,y〉 ∈ f，称 f为 X到 Y functions ），记为 f,X→Y X=X1× X2× …× Xn 时，称 f为 n元函
mapping ）。
第 4章 二元关系和函数换言之，函数是特殊的关系，它满足
（ 1）函数的定义域是 X，而不能是 X的某个真子集。
（ 2）若 〈 x,y〉 ∈ f,〈 x,y′〉 ∈ f，则 y＝ y′（单值性）。
由于函数的第二个特性，人们常把 〈 x,y〉 (f或 xfy
这两种关系表示形式，在 f为函数时改为 y=f(x)。这时称
x为自变元,y为函数在 x处的值；也称 y为 x的像点,x为
y的源点。一个源点只能有唯一的像点，但不同的源点允许有共同的像点。注意，函数的上述表示形式不适用于一般关系。（因为一般关系不具有单值性。）
第 4章 二元关系和函数
【 例 4.8.1】 设 A={a,b},B={1,2,3}，判断下列集合是否是 A到 B的函数。
F1={〈 a,1〉,〈 b,2〉 },F2={〈 a,1〉,〈 b,1〉 }，
F3={〈 a,1〉,〈 a,2〉 },F4={〈 a,3〉 }
解
F1,F2是函数,F3,F4不是函数，但若不强调是 A到 B
的函数，则 F4是函数，其定义域为 {a}。
第 4章 二元关系和函数
【 例 4.8.2】 下列关系中哪些能构成函数？
（ 1） {〈 x,y〉 |x,y∈ N,x+y〈 10}
（ 2） {〈 x,y〉 |x,y∈ N,x+y=10}
（ 3） {〈 x,y〉 |x,y∈ R,|x|=y}
（ 4） {〈 x,y〉 |x,y∈ R,x=|y|}
（ 5） {〈 x,y〉 |x,y∈ N,|x|=|y|}
第 4章 二元关系和函数解 只有（ 3）能构成函数。
由于函数归结为关系，因而函数的表示及运算可归结为集合的表示及运算，函数的相等的概念、包含概念，也便归结为关系相等的概念及包含概念。
第 4章 二元关系和函数定义 4.8.2 设 f:A→B,g:C→D，如果 A=C,B＝ D，
且对每一 x∈ A，有 f(x) g(x) f等于 g,记为
f=g。如果 A C,B＝ D，且对每一 x∈ A，
有 f(x) g(x) f包含于 g，记为 f g。
事实上，当不强调函数是定义在哪个集合上的时候，由于函数是序偶的集合（特殊的关系），所以 f=g
的充分必要条件是 f g且 g f。

第 4章 二元关系和函数
【 例 4.8.3】 设 A={a,b},B={1,2,3}。由 A→B能生成多少个不同的函数？由 B→A能生成多少个不同的函数？
解 设 fi:A→B(i=1,2,…,9),gi:B→A(i=1,2,…,8)
第 4章 二元关系和函数
f1={〈 a,1〉,〈 b,1〉 } g1={〈 1,a〉,〈 2,a〉,〈 3,a〉 }
f2={〈 a,1〉,〈 b,2〉 } g2={〈 1,a〉,〈 2,a〉,〈 3,b〉 }
f3={〈 a,1〉,〈 b,3〉 } g3={〈 1,a〉,〈 2,b〉,〈 3,a〉 }
f4={〈 a,2〉,〈 b,1〉 } g4={〈 1,a〉,〈 2,b〉,〈 3,b〉 }
f5={〈 a,2〉,〈 b,2〉 } g5={〈 1,b〉,〈 2,a〉,〈 3,a〉 }
f6={〈 a,2〉,〈 b,3〉 } g6={〈 1,a〉,〈 2,a〉,〈 3,b〉 }
f7={〈 a,3〉,〈 b,1〉 } g7={〈 1,b〉,〈 2,a〉,〈 3,b〉 }
f8={〈 a,3〉,〈 b,2〉 } g8={〈 1,b〉,〈 2,b〉,〈 3,b〉 }
f9={〈 a,3〉,〈 b,3〉 }
第 4章 二元关系和函数定理 4.8.1 设 |A|=m,|B|=n，那么 {f|f:A→B}的基数为 nm，即共有 nm个 A到 B的函数。
证明 设 A={a1,a2,…,am},B={b1,b2,…,bn}，那么每一个
f:A→B由一张如下的表来规定,
a a1 a2 … am
f(a) bi1 bi2 … bin
第 4章 二元关系和函数其中 b i1,b i2,…,b im 为取自 b1,b2,…,bn的允许元素重复的排列，这种排列总数为 n m个。因此，上述形式的表恰有 n m张，恰对应全部 n m个 A到 B的函数。
由于上述缘故，当 A,B是有穷集合时，我们以 B A记所有 A到 B的全体函数的集合：
B A={f|f:A→B}
则 |B A|=|B| |A| 。
特别地 A A表示 A上函数的全体。目前在计算机科学中，也用 A→B替代 B A。
第 4章 二元关系和函数例 4.8.2中,B A={f1,f2,…,f9},|B A|=9，
A B={g1,g2,…,g8},|A B|=8。
该定理当 X或 Y中至少有一个集合是空集时，可分成下面两种情况：
(1)当 X X到 Y的空关系为一函数，称为空函数，即 Y X= ={ }。
(2)当 X≠ 且 Y= 时,X到 Y的空关系不是一个函数，即 Y X= X= 。
关于函数有下列术语和记号。


X
第 4章 二元关系和函数定义 4.8.3 设 f:X→Y,A X，称 f(A)为 A
image ），定义为
f(A)={y| x(x∈ A∧ y=f(x))}
显然，此时 f为 P(X)到 P(Y)的函数，且
f( )=,f(X)= Ran (f)，此时 f(X)称为函数的像,f({x})={f(x)}(x∈ A)。
在这里请注意区别函数值和像两个不同的概念。
函数值 f(x)∈ Y,而像 f(A) Y。关于像有下列性质。

第 4章 二元关系和函数定理 4.8.2 设 f:X→Y，对任意 A X,B X，有
（ 1） f(A∪ B)=f(A)∪ f(B)
（ 2） f(A∩B) f(A)∩f(B)
（ 3） f(A)-f(B) f(A-B)

第 4章 二元关系和函数证明 （ 1）对任一 y∈ Y
y∈ f(A∪ B) x(x∈ A∪ B∧ y=f(x))
x((x∈ A∧ y=f(x))∨ (x∈ B∧ y=f(x)))
x(x∈ A∧ y=f(x))∨ x(x∈ B∧ y=f(x))
y∈ f(A)∨ y∈ f(B)
y∈ f(A)∪ f(B)
因此 f(A∪ B)=f(A)∪ f(B)。
（ 2）、（ 3）的证明请读者完成。注意，（ 2）、
（ 3）中的包含符号不能用等号代替。我们举例说明。



第 4章 二元关系和函数
【 例 4.8.4】 设 X={a,b,c,d},Y={1,2,3,4,5},f:X→Y,
如图 4.8.1所示。那么，
f ({a})={2},
f ({b})={2},
f ({a})∩f({b})={2}
f ({a})-f({b})=
f ({a}∩{b})=f( )=
f ({a}-{b})=f({a})={2}
f ({a}∩{b}) f({a})∩f({b})
f ({a})-f({b}) f({a}-{b})

第 4章 二元关系和函数图 4.8.1
1a
b
c
d
2
3
4
5
第 4章 二元关系和函数定义 4.8.4 给定函数 f:X→Y，
(1)如果函数 f的值域 Ran f=Y，则称 f:X→Y为满射函数（ surjection ）,满射函数也称映上的函数。
(2)对于任意 x1,x2∈ X,若 x1≠x2 f(x1)≠f(x2),或者
f(x1)=f(x2) x1=x2,则称 f为单射函数（ injection ）,单射函数也称一对一的函数。
第 4章 二元关系和函数
(3) f:X→Y。如果它既是映满的映射，又是一对一的映射，则称 f为双射函数（ bijection ）,双射函数也称一一对应。
由定义不难看出，如果 f:X→Y是满射的，则对于任意的 y∈ Y,都存在 x∈ X,使得 y=f(x);
如果 f:X→Y是单射的，则对于任意的 y∈ Ran f,都存在唯一的 x∈ X,使得 y=f(x)。
图 4.8.2说明了这三类函数之间的关系。注意，既非单射又非满射的函数是大量存在的。
第 4章 二元关系和函数图 4.8.2
既非单射又非满射单射 双射 满射
Y
X
第 4章 二元关系和函数
【 例 4.8.5】 对于给定的 f和集合 A，请判断 f的性质；
并求 A在 f下的像 f(A)。
(1) f:R→R,f(x)=x,A={8}
(2) f:N→N× N,f(x)=〈 x,x+1〉,A={2,5}
(3) f:Z→N,f(x)=|x|,A={-1,2}
(4)f:S→R，
S=［ 0,+∞),A=［ 0,7)
1()
1fx x
第 4章 二元关系和函数解
（ 1） f是双射,f (A)=f({8})={8}
(2) f是单射,f (A)=f({2,5})={〈 2,3〉,〈 5,6〉 }
(3) f是满射,f (A)=f({-1,2})={1,2}
(4) f是单射,f (A)=f(［ 0,7))=（ 1/8,1］
第 4章 二元关系和函数定理 4.8.3 设 A,B是有穷集合,|A|=|B|，则 f:A→B是单射的充分必要条件是 f是满射。
证明 先证必要性。设 f是单射，则 |A|=|f(A)|=|B|。因为
f(A) B，而 B是有穷集合，所以 f(A)=B，故 f是满射。
再证充分性。设 f是满射，则 f(A)=B。于是
|A|=|f(A)|=|B|。又因为 A是有穷集合，所以 f是单射。
第 4章 二元关系和函数
（ 1）设 f:X→Y,如果存在 c∈ Y，使得对所有的 x∈ X
都有 f(x)=c，则称 f:X→Y是常函数。
（ 2）任意集合 A上的恒等关系 IA为一函数，常称为恒等函数，因为对任意 x∈ A都有 IA(x)=x。
(3)设 〈 X,,〈 Y,为偏序集,f:X→Y,如果对任意的 x1,x2∈ X,x1 x2,就有 f(x1) f(x2),则称 f为单调递增的；如果对任意的 x1,x2∈ X,x1 x2,就有 f(x1) f(x2),
则称 f为严格单调递增的。类似地，也可以定义单调递减的和严格单调递减的第 4章 二元关系和函数
(4)设 A为集合，对于任意的 A′ A,A′的特征函数 χ
A′,A→{0,1}定义为
1
0A
aA
a A A




(5)设 R是 A上的等价关系，令
g:A→A/R
第 4章 二元关系和函数
a∈ A,g(a)=［ a］,其中［ a］是由 a生成的等价类，
则称 g是从 A到商集 A/R的自然映射。
我们都很熟悉实数集合 R 上的函数 f:R→R,f(x)=x+1,
它是单调递增的和严格单调递增的，但它只是上面定义中的单调函数的特例。而在上面的定义中，单调函数可以定义于一般的偏序集合上。
第 4章 二元关系和函数
【 例 4.8.6】 给定偏序集 〈 P({a,b}),R,
〈 {0,1},≤〉,其中 R 为集合的包含关系,≤为一般的小于或等于关系。令
f:P({a,b})→{0,1},f( )=f({a})=f({b})=0,f({a,b})=1,则 f是单调递增的，但不是严格单调递增的。
关于集合的特征函数：设 A为集合，不难证明,A
的每一个子集 A′都对应于一个特征函数，不同的子集则对应于不同的特征函数。而自然映射 g给定集合 A和 A
上的等价关系 R，就可以确定一个自然映射 g:A→A/R。
第 4章 二元关系和函数
【 例 4.8.7】 设 A={1,2,3,4},
R={〈 1,2〉,〈 2,1〉 }∪ IA,求自然映射,g1:A→A/IA，
g2:A→A/R。
解 g1(1)=g1(2)=g1(3)=g1(4)=A
g2(1)=g2(2)={1,2},g2(3)={3},g2(4)={4}
注意到,A/IA={{1,2,3,4}}={A}，
A/R={{1,2},{3},{4}}，所以自然映射都是满射且只有等价关系取 IA时是双射。
第 4章 二元关系和函数定义 4.8.6 设 A为有限集,p,A→A为一单射函数，
那么称 p为 A上的置换（ permutations ）。当 |A|=n时，
称 p为 n次置换。置换常用一种特别的形式来表示。设
A={a1,a2,…,an},那么
12
12
n
i i i n
a a a
p
a a a


表示一个 A上的 n次置换,它满足
p(aj)=a ij
A上的恒等函数显然为一置换，称为幺置换，用 i表示之。
第 4章 二元关系和函数
4.9 函数的复合和反函数定理 4.9.1 设 f:X→Y,g:Y→Z，，那么合成关系 f g
为 X到 Z的函数。
证明 首先证明 Dom (f g)=X。对任一 x∈ X，有
y∈ Y，使 〈 x,y〉 (f；对这一 y，有 z∈ Z，使得
〈 y,z〉 ∈ g，因此 〈 x,z〉 ∈ f g。故 x∈ Dom (f g)。
Dom (f g)=X得证。
第 4章 二元关系和函数再证 f g的单值性。设对任意 x∈ X有 z1,z2，使
〈 x,z1〉 ∈ f g,〈 x,z2〉 ∈ f g。那么有 y1,y2，使
〈 x,y1〉 ∈ f,〈 y1,z1〉 (g,〈 x,y2〉 ∈ f,〈 y2,z〉 ∈ g。由于
f为函数，知 y1=y2；又因 g为函数，得知 z1=z2。 f g为 X到
Z的函数得证。
我们注意到,〈 x,z〉 ∈ f g是指有 y使
〈 x,y〉 ∈ f,〈 y,z〉 ∈ g，即 y=f(x),z=g(y)=g(f(x))，因而
f g(x)=g(f(x))
第 4章 二元关系和函数这就是说，当 f,g为函数时，它们的合成作用于自变量的次序刚好与合成的原始记号的顺序相反。
我们约定，函数合成时，只有当两个函数中一个的定义域与另一个的值域相同时，它们的合成才有意义。
第 4章 二元关系和函数
【 例 4.9.1】 设
A={x1,x2,x3,x4}B={y1,y2,y3,y4,y5},C={z1,z2,z3}。
f:A→B,f={〈 x1,y2〉,〈 x2,y1〉,〈 x3,y3〉,〈 x4,y5〉 }
g:B→C,g={〈 y1,z1〉,〈 y2,z2〉,〈 y3,z3〉,
.〈 y4,z3〉,〈 y5,z2〉 }
求 f 。 g。
解 f。 g={〈 x1,z2〉,〈 x2,z1〉,〈 x3,z3〉,〈 x4,z2〉 }
用关系图图示 f。 g，其中 →表示 f。 g,见图 4.9.1。
第 4章 二元关系和函数图 4.9.1
x
1
x
2
x
3
x
4
y
4
y
5
y
3
y
2
y
1
A B C
f g
z
1
z
2
z
3
f g
第 4章 二元关系和函数
【 例 4.9.2】 设 f,g均为实函数,f(x)=2x+1,g(x)=x 2+1,求
f。 g,g。 f,f。 f,g。 g。
解 f。 g(x)=g(f(x))=(2x+1) 2+1=4x 2+4x+2
g。 f(x)=f(g(x))=2(x 2+1)+1=2x 2+3
f。 f(x)=f(f(x))=2(2x+1)+1=4x+3
g。 g(x)=g(g(x))=(x 2+1) 2+1=x 4+2x 2+2
所以 f。 g={〈 x,4x 2+4x+2〉 }
g。 f={〈 x,2x 2+3〉 }
f。 f={〈 x,4x+3〉 }
g。 g={〈 x,x 4+2x 2+2〉 }
第 4章 二元关系和函数推论 函数的复合运算满足结合律，即
f。 (g。 h)=(f。 g)。 h。
证明 因对任意 x∈ Dom (f)，有
f。 (g。 h)(x) =(g。 h)(f(x))
=h (g(f(x))
=h((f。 g)(x))
=(f。 g)。 h(x) 得证第 4章 二元关系和函数由于函数的合成满足结合律,n个函数 f的合成可记为 f n，常称为 f的 n次迭代。显然
0
1
()
( ) ( ( ))nn
f x x
f x f f x?


第 4章 二元关系和函数
【 例 4.9.3】
（ 1）设 f为 N上的后继函数，即 f(x)=x+1，那么
f yy(x)=x+y。这表明，当把复合运算强化地运用于变元
（合成次数），它就成为一种有力的构造新函数的手段。
（ 2）设 f:X→X,X={a,b,c}。若
f(a)=b,f(b)=b,f(c)=c，那么 f 2=f。这时称 f是等幂的。
函数复合的下列性质也是明显的。
第 4章 二元关系和函数定理 4.9.2 设 f:X→Y,则
f。 Iy=Ix。 f=f
关于单射的、满射的和双射的函数有下列性质。
定理 4.9.3 设函数 f,X→Y,g,Y→Z，那么
（ 1）如果 f和 g是单射的，则 f。 g也是单射的。
（ 2）如果 f和 g是满射的，则 f。 g也是满射的。
（ 3）如果 f和 g是双射的，则 f。 g也是双射的。
第 4章 二元关系和函数证明
（ 1）设 x1,x2∈ X,x1≠x2，由于 f为单射，故有 y1≠y2∈ Y,
且 y1=f(x1)≠y2=f(x2)；又因为 g也是单射，所以有 z 1≠z 2∈ Z,
且 z1=g(y1)≠z2=g(y2) g(f(x1))≠g(f(x2))，即
f。 g(x1)≠f。 g(x2)。 f。 g是单射得证。
（ 2）为证 f。 g为满射，设 z 为 Z中任一元素。由于 g
为满射，因而至少有一 y∈ Y使 g(y)=z 。对于这一 y，由于
f为满射，又必有 x∈ X使 y=f(x)。于是我们找到 x，使
g(f(x))=z,即 f。 g(x)=z 。 f。 g是满射得证。
（ 3）由（ 1）、（ 2）立得。
第 4章 二元关系和函数图 4.9.2
( a ) ( b )
f gf g
f g f g
第 4章 二元关系和函数定理 4.9.4 设 f,X→Y,g,Y→Z，那么
（ 1）如果 f。 g是单射，则 f是单射函数。
（ 2）如果 f。 g是满射，则 g是满射函数。
（ 3）如果 f。 g是双射，则 f是单射函数,g是满射函数。
第 4章 二元关系和函数证明
（ 1）设 f。 g是单射，而 f并非单射。那么有 x1，
x2∈ X,x1≠x2，使 f(x1)=f(x2)，
f。 g(x1)=g(f(x1))=g(f(x2))=f。 g(x2) 与 g。 f为单射矛盾。因此 f为单射。
（ 2）、（ 3）的证明留给读者。
由于习惯上把置换的复合写得与一般函数复合次序相同，因而置换的复合的书写与关系复合的书写次序一致。显然，对任一集合 A上的任一置换 p，有
p。 i = i。 p=p
第 4章 二元关系和函数
【 例 4.9.4】 设 A={1,2,3,4},P1,P2为 X上置换，12
1 2 2
2 1 2
1 2 3 4 1 2 3 4
2 4 1 3 3 4 2 1
1 2 3 4 1 2 3 4 1 2 3 4
2 4 1 3 3 4 2 1 4 1 3 2
1 2 3 4 1 2 3 4 1 2 3 4
3 4 2 1 2 4 1 3 1 3 4 2
PP
P P P
P P P












P1。 P2(2)=P2(P1(2))=P2(4)=1
P2。 P1(2)=P1(P2(2))=P1(4)=3
第 4章 二元关系和函数定理 4.9.5 若 f,X→Y为一双射，那么其逆关系 f -1
为 Y到 X的函数，称为 f的反函数（ inversefunctions ），
f -1,Y→X也为一双射。
证明 我们只证 f -1 为一函数，而把 f -1 为单射和满射的证明留给读者。
第 4章 二元关系和函数由于 f为满射，因此对每一 y∈ Y，有 x∈ X，使
f(x)=y，从而 〈 y,x〉 ∈ f -1,这表明 Dom (f -1 )＝ Y。为证 f -1 的单值性，设 y∈ Y，且 〈 y,x1〉 ∈ f -1,〈 y,x2〉
∈ f -1,从而 f(x1)=y=f(x2)。据 f的单射性，有 x1=x2。
f -1 的单值性证毕。故 f -1 为 Y到 X的一个函数。
当 f为一双射函数时,f -1 为 f的反函数，称 f是可逆的。
关于反函数，有下列性质是明显的。
第 4章 二元关系和函数定理 4.9.6 若 f,X→Y是可逆的，那么
（ 1） (f -1 ) -1 =f
（ 2） f。 f -1 =IX,f -1 。 f=IY
证明
（ 1）由定理 4.9.5知 f -1 为一双射，因而 f -1 也是可逆的。故 (f-1 ) -1 =(f -1 ) -1 =f。
（ 1）设 x为 X中任一元素,f(x)=y，那么 x=f -1 (y)。由于 f。 f -1 (x)＝ f -1 (f(x))=f -1 (y)=x，故 f。 f -1 =IX。同理可证 f -1 。 f=IY。
第 4章 二元关系和函数定理 4.9.7 设 f,X→Y,g,Y→Z都是可逆的，那么 f。
g也是可逆的，且
(f。 g) -1 =g -1 。 f -1
证明留作练习。
第 4章 二元关系和函数
【 例 4.9.5】 设 f,g∈ n,N 为自然数集。且
1 0,1,2,3
/2
( ) 0 4 ( )
3
5
xx
x
f x x g x
xx





x为偶数
x为奇数
(1)求 f。 g，并讨论它的性质（是否是单射或满射）。
(2)设 A={0,1,2}，求 f。 g（ A）。
第 4章 二元关系和函数解
04
11
( 1 ) ( ) ( ( ) ) 2 3
30
/ 2 5
x
x
f g x g f x x
x
xx




2,或 x≥5且为奇数且为偶数因为对任何一个 y∈ N，均有 x∈ N使得 f。 g（ x） =y，
所以 f。 g是满射。
（ 2） f。 g（ A） ={1,3}
第 4章 二元关系和函数定理 4.9.8 设 f,R→R,f（ x） =x 2-2； g,R→R，
g（ x） =x+4。
(1)求 g。 f,f。 g
(2)问 g。 f和 f。 g是否为单射、满射、双射？
（ 3）求出 f,g,g。 f和 f。 g中的可逆函数的逆（反）
函数。
第 4章 二元关系和函数解
（ 1） g。 f={〈 x,x2+8x+14〉 |x(R} f。
g={〈 x,x 2+2〉 |x∈ R}
（ 2） g。 f和 f。 g均是非单非满函数。
（ 3）因为 g是双射，所以可逆，反函数为：
g -1 （ x） =x-4。
第 4章 二元关系和函数
4.10 集合的基数在第三章中，我们把基数简单地看作集合元素的个数，这对于有限集来说是没有问题的，但对于无限集而言,"元素的个数 "这个概念是没有意义的。那么两个集合的 "大小 "相同的确切含义是什么呢？用基数相同的概念可以精确地刻画集合的 "大小 "。
第 4章 二元关系和函数下文我们先讨论自然数集合、有限集、无限集的定义，然后再指出形式地描述元素 "多少 "概念的最好工具是函数，并给出常见无限集的基数规定及基数的基本性质。第三章中我们只是直观地描述有限集与无限集的意义，现在要给出它们的严格定义。定义 4.10.1
设 S为任意集合,S∪ {S}称为 S的后继集合，记为 S +。
第 4章 二元关系和函数定义 4.10.1 设 S为任意集合,S∪ {S}称为 S的后继集合，记为 S +。易证对于任意集合 S都有 S∈ S +和 S S +
成立。
例如，令 S=,反复利用定义 4.10.1可以构造出集合序列：
∪ { } ={ }，
{ }∪ {{ }}={,{ }}
{,{ }}∪ {{,{ }}} ={,{ },{,{ }}}…



第 4章 二元关系和函数将上面的各集合依次命名为 0,1,2,…，就可构造出自然数。下面用记号 ",="给这些集合命名，于是，
0,=
1,=0 +={ }={0}
2,=1 +={,{ }}={0,1}
3,=2 +={,{ },{,{ }}}={0,1,2}
……
一般地，若已给出 n,则 n+1:=n +={0,1,2,…}，因此得到自然数集 N ={0,1,2,3,…}。

第 4章 二元关系和函数
G.Peano 将自然数所组成的集合的基本特性描述为下列公理：设 N 表自然数集合，则
（ 1 0,0∈ N；
（ 2）若 n∈ N,则 n +∈ N；
（ 3）若子集 S N且 0∈ S,又若 n∈ S，则 n +∈ S,则 S= N 。
该定理中（ 3）说明了 N 是满足条件（ 1），（ 2）
的最小集合，（ 3）也称为极小性质。
第 4章 二元关系和函数定义 4.10.2 如果存在集合 {0,1,2,…,n-1}（自然数 n）到 A，或 A到集合 {0,1,2,…,n-1}的双射，
则集合 A称为有限集，否则称为无限集。
定理 4.10.1 自然数集 N为 无限集。
证明 只需证明 N 不是有限集。为证明这一点，反设 为有限集，即存在 f是 {0,1,2,…,n-l}到 N 的双射。现令 L∈ N,L＝ 1+ max {f(0),f(1),…,f(n-1)}。显然，
对每一 i=0,1,2,…,n-1，恒有 f(i)＜ L，这就是说 f不是满射,与前面矛盾。因此 N 不是有限集,是无限集。
第 4章 二元关系和函数定理 4.10.2 有限集的任何子集均为有限集。
证明 设 S为有限集，因而有双射 f，自然数 n，
f,{0,l,2,…,n-l}→S
因此 S={f(0),f(1),f(2),…,f(n-1)}。若 S1为 S的任一子集，则 S1={f(a0),f(a1),f(a2),…,f(a k-1 )},k≤n。
a0,a1,a2,…,a k-1 为 {0,1,2,…,n-l}中的不同成员。
第 4章 二元关系和函数将序列 a0,a1,a2,…,a k-1 看作 {0,1,2,…,k-l}到
{a0,a1,a2,…,a k-1 }(=S2)的双射,记为 g，那么
g。 f↑S2:{0,1,2,…,k-l}→S1
为一双射，其中 f↑S2表示双射 f将集合 S2作为定义域。
因此 A为有限集。
第 4章 二元关系和函数定理 4.10.4 无限集必与它的一个真子集存在双射函数。
证明 设 S为任一无限集，显然 S≠,可取元素
a0∈ S。考虑 S1=S-{a0},S1仍为非空无限集，又在 S1中可取元素 a1∈ S1。考虑 S2=S1-{a1},S2依然为非空无限集，
同样有 a2∈ S2……如此等等。
令 B={a0,a1,a2,…}，显然 B S，且对任一自然数 n，
总有 an∈ B,S有可数无限子集 B={a0,a1,a2,…}。令
S0=S-{a0} S。定义函数 f,S→S0为
1
()
( 0,1,2 )ii
x x B
fx
a x a B i?



容易看出 f为一双射。
第 4章 二元关系和函数推论 凡不能与自身的任意真子集之间存在双射函数的集合为有限集合。这里给出了有限集合和无限集合的另一个定义，它与定义 4.10.2是等价的。即凡能与自身的某一真子集之间存在双射函数的集合为无限集合，否则为有限集合。对无限集还可作进一步的分类。
第 4章 二元关系和函数定义 4.10.3 如果存在从 N到 S的双射（或 S到 N的双射），则称集合 S为可数无限集
（ countableinfinitesets ）。其它无限集称为不可数无限集。有限集和可数无限集统称为可数集
（ countablesets ）。因此，不可数集即不可数无限集。
显然，自然数集合 N为可数集,N的任何子集均为可数集。自然数集 N 可以排成一个无穷序列的形式：
第 4章 二元关系和函数
0,1,2,3,…
因此，任何可数集 S中的元素也可以排成一个无穷序列的形式：
a0,a1,a2,a3,a4,…
反之，对于任何集合 S，如果它的元素可以排成上述无穷序列的形式，则 S一定是可数集。因为 S中元素 ai
与 i之间可以建立一一对应的关系，所以一个集合是可数集的充要条件是它的元素可以排成一个无穷序列的形式。
第 4章 二元关系和函数
【 例 4.10.1】
非负偶数集以及正奇数集均为可数集，因为
f(x)=2x,f(x)=2x+1分别为 N到非负偶数集以及正奇数集的双射。
定理 4.10.5 整数集为可数无限集。
证明 建立函数 f,Z →N（ Z 为整数集）。
2
( ) 0
2 ( ) 1
x
fx
x


当 x＞ 0
当 x=0
当 x＜ 0
第 4章 二元关系和函数定理 4.10.6 任何无限集必含有一个可数子集。
该定理的证明类似于定理 4.10.4，从无限集中可以依次取出一列元素构成一个可数集。
定理 4.10.7 可数集的任何无限子集必为可数集。
证明 设 S是可数集,S中的元素可以排成：
a0,a1,a2,a3,a4,…，设 B是 S的任一无限子集，它的元素也是 S的元素，并且一定可以排成,a0k,a 1k,a 2k,a 3k,
a 4k,…,所以 B是可数集。
第 4章 二元关系和函数定理 4.10.8 可数集中加入有限个元素（或删除有限个元素）仍为可数集。
证明 设 S={a0,a1,a2,a3,a4,…}是可数集，不妨在 S中加入有限个元素 b0,b1,b2,b3,…,bm,且它们均与 S的元素不相同，得到新的集合 B,它的元素也可排成无穷序列：
b0,b1,b2,b3,…,bm,a0,a1,a2,a3,a4,… 所以
B={b0,b1,b2,b3,…,bm,a0,a1,a2,a3,a4,…}是可数集。
第 4章 二元关系和函数定理 4.10.9 两个可数集的并集是可数集。
证明 设 S1={a0,a1,a2,a3,a4,…},S2={b0,b1,b2,b3,b4,…}均为可数集。不仿设 S1与 S2不相交。 S1∪ S2的元素可以排成无穷序列，即 a0,b0,a1,b1,a2,b2,a3,b3,a4,…，所以
S1∪ S2={a0,b0,a1,b1,a2,b2,a3,b3,a4,…}是可数集。
推论 有限个可数集的并集是可数集。
定理 4.10.10 可数个可数集的并集是可数集。
第 4章 二元关系和函数图 4.10.1
a
00
a
01
a
10
a
11
a
20
a
21
a
30
a
31
a
02
a
12
a
22
a
32
a
03
a
13
a
23
a
33
…
…
…
…
…………
第 4章 二元关系和函数证明 不失一般性，设这可数个可数集均非空，且它们都是两两不相交的。
S0={a 00,a 01,a 02,…}
S1={a 10,a 11,a 12,…}
S2={a 20,a 21,a 22,…}
…
第 4章 二元关系和函数当 Si为有限集 {a i0,a i1,a i2,…,a ik }时，令
a ik =a i(k+1) =a i(k+2) =…，从而
,S中元素排列次序如图 4.10.1中的箭头所示。
从左上角开始排，每一斜线上的每个元素的两个足标之和都相同，依次为 0,1,2,3,4,5,…，各斜线上的元素的个数依次为 1,2,3,4,…，因此这一排列可以写为,a 00,a 01,a 10,a 02,a 11,a 20,a 03,
a 12,a 21,a 30,… 因而 S是可数集。
0 1 2
0
,i
i
S S S S S S

第 4章 二元关系和函数
【 例 4.10.2】 利用对角线方法证明 N× N是可数集。
证明 N× N 中的元素可以排成如图 4.10.2所示的形式。
类似定理 4.10.7，按对角线方法可以将这样的排列写为,(0,0)(0,1)(1,0)(0,2)(1,1)(2,0)(0,3)(1,2)(2,1)(3,0)… 所以 N× N 是可数集。
第 4章 二元关系和函数图 4.10.2
( 0,0 )
…………
( 1,0 )
( 2,0 )
( 3,0 )
( 0,1 )
( 1,1 )
( 2,1 )
( 3,1 )
( 0,2 )
( 1,2 )
( 2,2 )
( 3,2 )
( 0,3 )
( 1,3 )
( 2,3 )
( 3,3 ) …
…
…
…
第 4章 二元关系和函数
【 例 4.10.3】 有理数集是可数集。
证明 先证正有理数集 Q +是可数的。上例已证得
N× N是可数集，从 N× N 中删除所有使 i和 j不是互质的有序对（ i,j），并删除所有有序对 (i,0),得到集合为 S,S
N× N 。因为 S中包含 (1,1)(2,1)(3,1)…，显然 S是可数集。定义函数 f:S→ Q+,f((i,j))=i / j,显然 f是双射，所以
Q+ 是可数集。
设负有理数集 Q -，同理也可证是可数集。而
Q=Q+∪ Q-∪ {0} 显然也是可数集。
第 4章 二元关系和函数定理 4.10.11 实数集的子集［ 0,1］区间是不可数集。
证明 用反证法证明。设［ 0,1］为可数集
{a0,a1,a2,a3,a4,…}。由于［ 0,1］中实数均可表示为十进制无限小数（对于有限小数均可以写成以,9”为循环节的无限循环小数形式（数 0例外,0表示为 0.000…，
1表示为 0,999…,0.87=0.86999…），因此［ 0,1］中实数可如下列出：
第 4章 二元关系和函数
a0 0.x00 x 01 x 02 x 03 …
a1 0.x 10 x 11 x 12 x 13 …
a2 0.x 20 x 21 x 22 x 23 …
…
an 0.x n0 x n1 x n2 x n3 …
…
第 4章 二元关系和函数这里 x nj (n,j=0,l,2,…)为第 n个小数的第 j个数字。现作一个十进制小数 y=0.y0y1y2…，其中
11
21
ii
i
ii
x
y
x



第 4章 二元关系和函数显然 y满足,yi≠0,yi≠9,i=0,1,2,3,…,y∈ (0,1)，且对于任一 n，因为 yi≠x ii,所以 y与 {a0,a1,a2,a3,a4,…}中的任一个数都不相同，即 y {a0,a1,a2,a3,a4,…}=［ 0,1］,于是产生矛盾。这表明，［ 0,1］是不可数集。
第 4章 二元关系和函数定义 4.10.4 如果有双射 f:{0,1,2,…,n-1}→S,或双射 f：
A→{0,1,2,…,n-1}，则称集合 S的基数（ cardinalnumber ）
为 n(n为自然数 )，记为 |S|=n。
显然，集合 S为有限集，当且仅当它以自然数为其基数，即存在自然数 n使 |S|=n。可以说 n是集合 A的元素个数。
定义 4.10.5 如果有双射 f,N →S，或双射 f,S→N，
N 为自然数集,称集合 S的基数为 и0，记为 |S|=и0,读作阿列夫零。
第 4章 二元关系和函数因此，自然数集及一切可数无限集的基数均为。
定义 4.10.6 如果有双射 f：［ 0,l］ →S，或双射 f：
S→［ 0,1］，则称集合 S的基数为 c，也记为 И，读作阿列夫。记为 |S|=c。具有基数 c的集合常称为连续统
（ continuum ）。
第 4章 二元关系和函数定义 4.10.7 设 A,B为任意集合。
（ 1）如果有双射 f,A→B或双射 f,B→A，则称 A，
B基数相等，记为 |A|=|B|。
（ 2）如果有单射 f,A→B或满射 f,B→A，则称 A的基数小于等于 B的基数，记为 |A|≤|B|。
（ 3）如果 |A|≤|B|,且 |A|≠|B|，则称 A的基数小于 B的基数，记为 |A|＜ |B|。
第 4章 二元关系和函数定理 4.10.12 对任意集合 A,B,C，有
（ 1） |A|≤|A|。
（ 2）若 |A|≤|B|,|B|≤|C|，则 |A|≤|C|。
请读者自行证明本定理。
定理 4.10.13 对任意集合 A,B，或者 |A|＜ |B|，或者
|A|=|B|，或者 |B|＜ |A|，且任意两者都不能兼而有之。
本定理常称为基数三歧性定理，它的证明依赖于选择公理，我们略去这一证明，有兴趣的读者可参阅相关文献。
第 4章 二元关系和函数定理 4.10.14 对任意集合 A,B，如果 |A|≤|B|,|B|≤|A|，
那么 |A|=|B|。
证明 设 |A|≠|B|,那么根据基数三歧性定理，或者
|A|＜ |B|，或者 |B|＜ |A|,且不能兼而有之。
若 |A|＜ |B|,则 |B|＜ |A|不成立,且 |A|≠|B|,于是与 |A|≤|B|矛盾。若 |B|＜ |A|,则 |A|＜ |B|不成立,且 |A|≠|B|,于是又与
|B|≤|A|矛盾。
|A|=|B|得证。
第 4章 二元关系和函数
【 例 4.10.5】 P( N)（ N 为自然数集）的基数是 c。
证明 为此要建立单射函数 f,P (N) →［ 0,1］，
单射函数 g：［ 0,1］ →P( N) 以便证明，
|P (N) |≤c,c≤|P (N) |。
定义 f:P (N) →［ 0,1］如下：对每一 A N
f(A)=0.x0x1x2x3…（十进制小数）
其中
1
0
i
iA
x
iA



第 4章 二元关系和函数例如 f( )＝ 0.000…,f(N)=0.111…，
f({0,2})＝ 0.10100…，显然 f为单射。
定义 g：［ 0,1］ →P(N)如下：对每一［ 0,1］中数的二进制表示（如果这种表示不唯一，则取定其中之一） 0.x0x1x2x3…（ xi为 0或 1）：
g(0.x0x1x2x3)={i(xi＝ 1} 易知,g也是单射。故原命题得证。
第 4章 二元关系和函数定理 4.10.15（康托定理） 设 M为任意集合，记 M的幂集为 S，则 |M|＜ |S|。
证明 对任意集合 M,当 M= 时,显然 |M|=0,S=2
M={ },|S|=1,故定理得证。
当 M≠ 时,对任意 a∈ M,有 {a}∈ 2 M=S,因为如下定义的函数 f,M→S，明显为一单射：对每一 a∈ M，
f(a)={a},所以 |M|≤|S|。现证 |M|≠|S|(用反证法 )。
第 4章 二元关系和函数设 |M|=|S|，故有双射 g,M→S，使得对每一 a∈ M，
有唯一的 g(a)∈ S，即 g(a) M。定义集合
B＝ {a|a∈ M∧ a g(a)}
当然 B∈ S。由于 g为双射，对 B∈ S,有唯一的 y∈ M，
使得 g(y)=B。考虑 y∈ B与否，得知
y∈ B y∈ {a|a∈ M∧ a g(a)}
y g(y)
y B
这是一个矛盾，因此 g不存在。 |M|≠|S|,因此,|M|＜ |S|。
这个定理表明没有最大的基数，也没有最大的集合。
第 4章 二元关系和函数
4.11 例 题 选 解
【 例 4.11.1】 证明：非空的对称、传递关系不可能是反自反关系。
证明 设 R是集合 A上的对称、传递关系，若 R非空，
x,y∈ A，有 〈 x,y〉 ∈ R。由于 R对称，因此 〈 y,x〉
∈ R，又由于 R是传递的，因此 〈 x,x〉 ∈ R。因此非空的对称、传递关系不可能是反自反关系。
第 4章 二元关系和函数
【 例 4.11.2】 设 R,S均是 A上的等价关系，证明,R。
S于 A上等价 iff S。 R=R。 S。
证明 " "（先证必要性）
〈 x,z 〉
〈 x,z 〉 ∈ S。 R y（ 〈 x,y〉 ∈ S∧ 〈 y,z 〉 ∈ R）
y（ 〈 z,y〉 ∈ R∧ 〈 y,x〉 ∈ S） (由于 R,S均是对称的 )
z,x〉 ∈ R。 S
x,z 〉 ∈ R。 S (由于 R。 S于 A上是对称的 )
故 S。 R=R。 S。

第 4章 二元关系和函数
" "（再证充分性）
(1) x∈ A，由于 R,S均是自反的，因此 〈 x,x〉 ∈ R且
〈 x,x〉 ∈ S，所以 〈 x,x〉 ∈ R。 S，即 R。 S是自反的。
(2) x,y〉
〈 x,y〉 ∈ R。 S t（ 〈 x,t〉 ∈ R∧ 〈 t,y〉 ∈ S）
t（ 〈 t,x〉 ∈ R∧ 〈 y,t〉 ∈ S） (由于 R,S均是对称的 )
y,x〉 ∈ S。 R
y,x〉 ∈ R。 S (由于 S。 R=R。 S)
即 R。 S是对称的。


第 4章 二元关系和函数
(3) x,y〉 〈 y,z 〉
〈 x,y〉 ∈ R。 S∧ 〈 y,z 〉 ∈ R。 S
x,y〉 ∈ R。 S∧ 〈 y,z 〉 ∈ S。 R (由于 S。 R=R。 S)
x,z 〉 ∈ R。 S。 S。 R
x,z 〉 ∈ R。 (S。 S)。 R (关系的复合满足结合律 )
x,z 〉 ∈ R。 S。 R （由于 S传递，因此 S。 S S）
〈 x,z 〉 ∈ R。 R。 S （由于 S。 R=R。 S)
x,z 〉 ∈ R。 S （由于 R传递，因此 R。 R R
即 R。 S是传递的。

第 4章 二元关系和函数
【 例 4.11.3】 设 R,S均是 A上的等价关系，证明,R∪ S于
A上等价 iff R。 S R∪ S且 S。 R R∪ S。
证明 " "（先证必要性）
〈 x,y〉 ∈ R。 S t（ 〈 x,t〉 ∈ R∧ 〈 t,y〉 ∈ S）
t（ 〈 x,t〉 ∈ R∪ S∧ 〈 t,y〉 ∈ R∪ S）
〈 x,y〉 ∈ R∪ S (由于 R∪ S传递 )
即 R。 S R∪ S。
同理可证,S。 R R∪ S。
" "（再证充分性）

第 4章 二元关系和函数
(1) x∈ A，由于 R,S均是自反的，因此 〈 x,x〉 ∈ R且
〈 x,x〉 ∈ S，所以 〈 x,x〉 ∈ R∪ S，即 R∪ S是自反的。
(2) x,y〉
〈 x,y〉 ∈ R∪ S x,y〉 ∈ R∨ 〈 x,y〉 ∈ S
〈 y,x〉 ∈ R∨ 〈 y,x〉 ∈ S） (由于 R,S均是对称的 )
〈 y,x〉 ∈ R∪ S
即 R∪ S是对称的。
第 4章 二元关系和函数
【 例 4.11.4】 设 R,S均是非空集合 A上的偏序关系，证明,R∩S也是 A上的偏序关系。
证明 (1) x∈ A，由于 R,S均是自反的，因此有 〈 x,x〉
∈ R且 〈 x,x〉 ∈ S，即 〈 x,x〉 ∈ R∩S，故 R∩S自反。
(2) x,y〉 ∧ x≠y
〈 x,y〉 ∈ R∩S x,y〉 ∈ R∧ 〈 x,y〉 ∈ S
〈 y,x R∧ 〈 y,x S
（由于 R,S均是反对称的）
〈 y,x R∩S
故 R∩S反对称。

第 4章 二元关系和函数
(3) x,y〉 〈 y,z 〉
〈 x,y〉 ∈ (R∩S)∧ 〈 y,z 〉 ∈ (R∩S)
(〈 x,y〉 ∈ R∧ 〈 x,y〉 ∈ S)∧ (〈 y,z 〉 ∈ R∧ 〈 y,z 〉 ∈ S)
(〈 x,y〉 ∈ R∧ 〈 y,z 〉 ∈ R)∧ (〈 x,y〉 ∈ S∧ 〈 y,z 〉 ∈ S)
x,z 〉 ∈ R∧ 〈 x,z 〉 ∈ S （由于 R,S均是传递的）
〈 x,z 〉 ∈ R∩S
故 R∩S传递。
因此,R∩S也是偏序关系。

第 4章 二元关系和函数
【 例 4.11.5】 A={a,b}上有多少不同的偏序关系？
解 因为偏序关系与哈斯图一一对应，所以只要画出所有不同的哈斯图，就可求出其不同的偏序关系，
详见图 4.11.1。
所以该集合上共有 3个不同的偏序关系。
【 例 4.11.6】 给出 A={a,b,c}上既是等价关系又是偏序关系的 R。
解 R=IA
第 4章 二元关系和函数图 4.11.1
a
( b )
b
b
( c )
a
( a )
a b
第 4章 二元关系和函数
【 例 4.11.7】 设 A={1,2,3,4,5,6,9,24,54},R是 A上的整除关系。
(1)画出偏序关系 R的 Hasse 图。
(2)求 A关于 R的极大元、极小元。
(3)设 B={2,3}，求 B的上界和上确界。
(4)找出 〈 A,R〉 中的长度为 4的反链。
解
（ 1）关系 R的 Hasse 图见图 4.11.2。
（ 2） A关于 R的极大元,54,24,5；极小元,1,5。
（ 3） B的上界,6,54,24；下界,1。
（ 4）长度为 4的反链,{4,5,6,9}。
第 4章 二元关系和函数图 4.11.2
54 24
9 6 4
3 2
1
第 4章 二元关系和函数
【 例 4.11.10】 设 f,A→B是函数，并定义一个函数 g：
B→P（ A）。对于任意的 b∈ B，有
g（ b） ={x|（ x∈ A） ∧ （ f（ x） =b） }
请证明：若 f是 A到 B的满射，则 g是 B到 P（ A）的单射。
证明 对任意 b1,b2∈ B（ b1≠b2），由于 f是满射，
因此 a1,a2∈ A，使得 f（ a1） =b1,f（ a2） =b2。又由于
b1∈ b2且 f是函数，因此 a1≠a2。又
g（ b1） ={x|（ x∈ A） ∧ (f（ x） =b1） }
g（ b2） ={x|（ x∈ A） ∧ （ f（ x） =b2） }
第 4章 二元关系和函数因此有 a1∈ g（ b1）,a2(g（ b2），但 a1 g（ b2），
a2 g（ b1），所以 g（ b1） ≠g（ b2），故 g为单射。
第 4章 二元关系和函数
【 例 4.11.11】 设 X≠,R为 X X上的关系，定义为
〈 f,g〉 ∈ R Ran f= Ran g
证明,R是 X X上的等价关系，且存在双射 φ：
X X/R→P（ X） -{ }.
证明 （ 1 f∈ X X，由于 Ran f= Ran f，因此 〈 f,f〉
∈ R，即 R是自反的。
② 〈 f,g〉〈 f,g〉 ∈ R Ran f= Ran g
Ran g= Ran f
〈 g,f〉 ∈ R
即 R是对称的。
第 4章 二元关系和函数
〈 f,g〉,〈 g,h 〉
〈 f,g〉 ∈ R∧ 〈 g,h 〉 ∈ R ( Ran f=
Rang)∧ (Rang=Ranh )
Ran f= Ran h
〈 f,h 〉 ∈ R
即 R是传递的。
综上,R是 X X上的等价关系。
第 4章 二元关系和函数
（ 2）定义 φ,X X/R→P（ X） -{ }
［ f］ R∈ X X/R,φ（［ f］ R） = Ran f，
于是
φ（［ f］ R） =φ（［ g］ R） Ran f= Ran g
〈 f,g〉 ∈ R ［ f］ R=［ g］ R
因而 φ是单射。
第 4章 二元关系和函数
A∈ P（ X） -{ },A X,A≠,取定元素
a∈ A，定义 f,X→X为

()
x x A
fx
a x A



则 φ（［ f］ R） = Ran f=A，因而 φ是满射。
综上所述，存在双射 φ,X X/R→P（ X） -{ }。
第 4章 二元关系和函数
【 例 4.11.12】 设 f,A→B,g,B→C是两个函数，证明：
（ 1）若 f。 g是满射且 g是单射，则 f是满射。
（ 2）若 f。 g是单射且 g是满射，则 f是单射。
（注：这里函数的复合为右复合。）
第 4章 二元关系和函数证明
（ 1 b∈ B，因为 g是函数，所以存在 c∈ C，使得 g（ b） =c。由 f。 g是满射，对该元素 c，存在 a∈ A，
使得 f。 g（ a） =c，即 g（ f（ a）） =c。由 g（ b） =c，所以 g（ f（ a）） =g（ b） =c。由 g是单射，所以有
f（ a） =b b∈ B a∈ A，使得 f（ a） =b。因此 f
是满射。

第 4章 二元关系和函数
（ 2）对任意 b1,b2∈ B（ b1≠b2），由于 f是单射，
a1,a2∈ A，使得 f（ a1） =b1,f（ a2） =b2。由于
b1≠b2且 f是函数，所以 a1≠a2。再由 f。 g是单射，可得
f。 g（ a1） ≠f。 g（ a2），即
g（ f（ a1）） ≠g（ f（ a2）），所以 g（ b1） ≠g（ b2）。
因此 g是单射。
第 4章 二元关系和函数
【 例 4.11.13】 设 f,A→B是函数，并定义一个函数
g,B→P（ A）。对于任意的 b∈ B，有
g（ b） ={x|（ x∈ A） ∧ （ f（ x） =b） }
证明若 f是 A到 B的满射，则 g是 B到 P（ A）的单射。
证明 如果 f是 A到 B的满射，则对每个 b∈ B,至少存在一个 a∈ A,使 f(a)=b,故 g的定义域为 B。
第 4章 二元关系和函数若有 b1,b2∈ B,且 b1≠b2,
g(b1)={x|（ x∈ A） ∧ （ f（ x） =b1） }
g（ b2） ={y|（ y∈ A） ∧ （ f（ y） =b2） }
因为 b1≠b2,f(x)≠f(y),而 f是函数，故 x≠y,所以
g(b1)≠g(b2)。
因此 g是 B到 P（ A）的单射。
第 4章 二元关系和函数习 题 四
1,已知 A={ },求 P(A)× A。
2,设 A={1,2,3},R为实数集,请在笛卡儿平面上表示出 A× R和 R× A。
3,以下各式是否对任意集合 A,B,C,D均成立？
试对成立的给出证明,对不成立的给出适当的反例 。
第 4章 二元关系和函数
（ 1） (A-B)× C=(A× C)-(B× C)
（ 2） (A∩B)× (C∩D)=(A× B)∩(C× D)
（ 3） (A-B)× (C-D)＝ (A× C)-(B× D)
（ 4） (A∪ B)× (C∪ D)=(A× C)∪ (B× D)
第 4章 二元关系和函数
4,设 A,B,C,D为任意集合,
（ 1） 若 A C,B D,那么 A× B C× D。
（ 2） 若 C,A× C B× C,则 A B。
（ 3） (A× B)-(C× D)＝ ((A-C)× B)∪ (A× (B-D))。
5,证明定理 4.1.3中的 （ 2）,（ 3）,（ 4）,（ 6） 。
6,证明定理 4.1.4和定理 4.1.5。


第 4章 二元关系和函数
7,给定集合 A={1,2,3},R,S均是 A上的关系,
R={〈 1,2〉,〈 2,1〉 }∪ IA,S={〈 1,1〉,〈 2,3〉 }
（ 1） 画出 R,S
（ 2） 说明 R,S
（ 3） 求 R S。
第 4章 二元关系和函数
8,设 A＝ {0,1,2,3,4,5},B={1,2,3},用列举法描述下列关系,
（ 1） R1={〈 x,y〉 |x(A∩B∧ y∈ A∩B}
（ 2） R2={〈 x,y〉 |x(A∧ y∈ B∧ x=y2}
（ 3） R3={〈 x,y〉 |x(A∧ y∈ A∧ x+y=5}
（ 4） R4={〈 x,y〉 |x(A∧ y∈ A∧ k(x=k·y∧ k∈ N∧ k＜ 2)}
（ 5） R5={〈 x,y〉 |x(A∧ y∈ A∧ (x=0∨ 2x＜ 3)}
第 4章 二元关系和函数
9,设 R,S为集合 A上任意关系,
（ 1） Dom(R∪ S)=Dom(R)∪ Dom(S)
（ 2） Ran(R∩S) Ran(R)∩Ran (S)
10,设 A=｛ 1,2,3,4,5｝,A上关系
R=｛ 〈 1,2〉,〈 3,4〉,〈 2,2〉 ｝,
S=｛ 〈 4,2〉,〈 2,5〉,〈 3,1〉,〈 1,3〉 ｝ 。
试求 R S的关系矩阵 。
11,设 A=｛ 1,2,3,4｝,A上关系
R＝ ｛ 〈 1,4〉,〈 3,1〉,〈 3,2〉,〈 4,3〉 ｝ 。
求 R的各次幂的关系矩阵 。
第 4章 二元关系和函数
12,证明定理 4.3.1中的 （ 1）,（ 4）,（ 5） 及 （ 6）
13,设 A＝ {a,b,c,d},A上二元关系 R1,R2
R1={〈 b,b〉,〈 b,c〉,〈 c,a〉 }
R2={〈 b,a〉,〈 c,a〉,〈 c,d〉,〈 d,c〉 }
计算 R1 R2,R2 R1,R2 1,R2 2。
第 4章 二元关系和函数
14,设 A={0,1,2,3},R和 S均是 A上的二元关系,
R={〈 x,y〉 |（ y=x+1） ∨ （ y=x/2） }
S={〈 x,y〉 |（ x=y+2） }
（ 1） 用列元素法表示 R,S
（ 2） 说明 R,S
（ 3） 求 R S。
15,证明定理 4.3.3中的 （ 2）,（ 3）,（ 6） 。
第 4章 二元关系和函数
16,设 R1,R2,R3,R4,R5都是整数集上的关系,
xR1y |x-y|=1
xR2y x·y＜ 0
xR3y x|y(x整除 y)
xR4y x+y=5
xR5y x=y n(n是整数 )
T(True)和 F(False) 填写表 4.1。
第 4章 二元关系和函数表 4.1
第 4章 二元关系和函数
17,证明定理 4.4.2和定理 4.4.6。
18．设 A={0,1,2,3},R A× A且
R={〈 x,y〉 |x=y∨ x(y∈ A}
(1)画出 R
(2)写出关系矩阵 MR
(3)R具有什么性质？
19,设 A为一集合,|A|=n,
（ 1） A上有多少种不同的自反的 （ 反自反的 ） 二元关系
（ 2） A上有多少种不同的对称的二元关系？
（ 3） A上有多少种不同的反对称的二元关系？
第 4章 二元关系和函数
20,设 R为 A上的自反关系,证明,R是传递的 iff R R=R。
并举例说明其逆不真 。
21
（ 1）如果 R对称且传递，那么 R必自反，因为由 R对称可知 xRy蕴涵 yRx，而由 R传递及 xRy,yRx，可知 xRx
（ 2）如果 R反自反且传递，那么 R必定是反对称的,因为若
R对称可知 xRy蕴涵 yRx，而由 R传递及 xRy,yRx，可导出 xRx,从第 4章 二元关系和函数
22,证明：当关系 R传递且自反时,R2＝ R。
23,设 R,S,T均是集合 A上的二元关系,证明：
若 R S,则 T R T S。
24,设 R为集合 A上任一关系,求证对一切正整数 n
有

1
()
n
ni
AA
i
I R I R
第 4章 二元关系和函数
25．设 R是集合 A上的二元关系,R在 A上是反传递的定义为：若 〈 x,y〉 ∈ R,〈 y,z〉 ∈ R,则 〈 x,z R
x y z(xRy∧ yRz→﹁ xRz)。证明,R是反传递的，当且仅当（ R R） ∩R=

第 4章 二元关系和函数
26,证明定理 4.5.1中的 （ 2） 。
27,证明定理 4.5.2中的 （ 1）,（ 3） 。
28,证明定理 4.5.3中的 （ 1）,（ 2） 。
29,证明定理 4.5.4 中的 （ 1 ）,（ 2 ） 及对 （ 3 ）
t(R1∪ R2)=t(R1)∪ t(R2)举出反例 。
30,证明定理 4.5.5中的 （ 3） 。
第 4章 二元关系和函数
31．设 R是 X={1,2,3,4,5}上的二元关系，
R={〈 1,2〉,〈 2,1〉,〈 1,5〉,〈 5,1〉,〈 2,5〉,〈 5,2〉,
〈 3,4〉,〈 4,3〉 }∪ I A。请给出关系矩阵并画出关系图；
若 R
32,若 {{a,c,e},{b,d,f}}是集合 A={a,b,c,d,e,f}的一个划分,求其等价关系 R。
33,若 {{1,3,5},{2,4}}是集合 A={1,2,3,4,5}
的一个划分,求其等价关系 R。
第 4章 二元关系和函数
34,设 S={1,2,3,4,5}且 A=S× S,在 A上定义关系 R:
〈 a,b〉 R〈 a′,b′〉 当且仅当 ab′=a′b。
（ 1） 证明 R是一个等价关系 。
（ 2） 计算 A/R。
35,设 R是集合 A上的二元关系,R在 A上是循环的充分必要条件是：若 aRb并且 bRc,则 cRa。 证明,R为等价关系当且仅当 R是自反的和循环的 。
第 4章 二元关系和函数
36,设 R,S为 A上的两个等价关系,且 R S。 定义 A/R上的关系 R/S
〈 ［ x］,［ y］ 〉 ∈ R/S当且仅当 〈 x,y〉 ∈ S
证明,R/S为 A/R上的等价关系 。
第 4章 二元关系和函数
37,设 {A 1,Ａ 2,…,A m}为集合 A的划分,证明：
对任意集合 B,{A1∩B,A 2∩B,…,Am∩B}-{ }必为集合 A∩B的划分 。
38,设 R1表示整数集上模 m1相等关系,R2表示模
m2相等关系,π1,π2分别是 R1,R2对应的划分 。 证明：
π 1细分于 π2当且仅当 m1是 m 2的倍数 。
第 4章 二元关系和函数
39,确定下面集合 A上的关系 R是不是偏序关系 。
（ 1） A=Z,aRb a=2b
（ 2） A=Z,aRb b2|a
（ 3） A=Z,aRb 存在 k使 a=bk
（ 4） A=Z,aRb a≤b
第 4章 二元关系和函数
40．设 A={a,b,c,d,e},A上的偏序关系
R={〈 c,a〉,〈 c,d〉 }∪ I A
(1)画出 R
(2)(1)画出 R A关于 R的极大元和极小元。
41,偏序集 〈 A,≤〉 的哈斯图如图 4.1所示 。
（ 1） 用列举元素法求 R
（ 2） 求 A关于 R
（ 3） 求子集 {c,d,e}
（ 4）求子集 {a,b,c}的下界和下确界。
第 4章 二元关系和函数图 4.1
a
b
f
c
e
d
第 4章 二元关系和函数图 4.2
e d
c
a
b
第 4章 二元关系和函数
42,图 4.2为一偏序集 〈 A,R〉 的哈斯图 。
（ 1） 下列命题哪些为真？
aRb,dRa,cRd,cRb,bRe,aRa,eRa
（ 2） 画出 R
（ 3） 指出 A的最大,最小元 （ 如果有的话 ）,极大,
（ 4） 求出子集 B1={c,d,e},B2={b,c,d},B 3={b,c,d,e}的上界,下界,上确界,下确界 （ 如果有的话 ） 。
第 4章 二元关系和函数
43,设 R是集合 A={a,b,c,d}上的偏序关系,关系矩阵为
1 0 1 1
0 1 1 1
0 0 1 0
0 0 0 1






第 4章 二元关系和函数
（ 1） 写出 R
（ 2） 画出 R
（ 3） 求子集 B={a,b}关于 R的上界和上确界 。
44,对下列每一条件构造满足该条件的有限集和无限集各一个 。
（ 1） 非空有序集,其中有子集没有最大元素 。
（ 2） 非空有序集,其中有子集有下确界,但它没有最小元素 。
（ 3） 非空有序集,其中有一子集存在上界,但它没有上确界 。
第 4章 二元关系和函数
45,图 4.3给出了集合 S={a,b,c,d}上的四个关系图 。
请指出哪些是偏序关系图,哪些是全序关系图,哪些是良序关系图,并对偏序关系图画出对应的哈斯图 。
第 4章 二元关系和函数图 4.3
a
c d
b a
c d
b a
c d
b
( a )
a
c d
b
( b ) ( c ) ( d )
第 4章 二元关系和函数
46,下列集合中哪些是偏序集合,哪些是全序集合,哪些是良序集合？
（ 1） 〈 P(N),〉
（ 2） 〈 P(N),〉
（ 3） 〈 P{a},〉
（ 4） 〈 P( ),〉

第 4章 二元关系和函数
47,设 R是集合 S上的关系,S′ S,定义 S′上的关系 R′为,R′＝ R∩(S′× S′） 。
（ 1） 如果 R传递,则 R′传递 。
（ 2） 如果 R为偏序关系,则 R′也是偏序关系 。
（ 3） 如果 〈 S,R〉 为全序集,则 〈 S′,R′〉 也是全序集 。
（ 4） 如果 〈 S,R〉 为良序集,则 〈 S′,R′〉 也是良序集 。
第 4章 二元关系和函数
48．设 〈 A,≤〉 为一有限全序集,|A|≥2,R是 A× A
上的关系，根据 R下列各定义，确定 〈 A× A,R〉 是否为偏序集、全序集或良序集。设 x,y,u,v为 A中任意元
（ 1） 〈 x,y〉 R〈 u,v x≤u∧ y≤v
（ 2） 〈 x,y〉 R〈 u,v〉 x≤u∧ x≠u∨ (x=u∧ y≤v)
（ 3） 〈 x,y〉 R〈 u,v〉 x≤u
（ 4） 〈 x,y〉 R〈 u,v〉 x≤u∧ x≠u
第 4章 二元关系和函数
49,指出下列各关系是否为 A到 B
（ 1） A＝ B＝ N,R={〈 x,y〉 |x∈ A∧ y∈ B∧ x+y＜ 100}
（ 2） A=B=R（ 实数集 ）,
S={〈 x,y〉 |x∈ A∧ y∈ B∧ y=x 2}
（ 3） A＝ {1,2,3,4},B＝ A× A,R={〈 1,〈 2,3〉〉,
〈 2,〈 3,4〉〉,〈 3,〈 1,4〉〉,〈 4,〈 2,3〉〉 }
（ 4） A={1,2,3,4},B=A× A,S={〈 1,〈 2,3〉〉,
〈 2,〈 3,4〉〉,〈 3,〈 2,3〉〉 }
第 4章 二元关系和函数
50,设 f,X→Y,g,X→Y，
（ 1） f∩g为 X到 Y的函数当且仅当 f=g。
（ 2） f∪ g为 X到 Y的函数当且仅当 f=g。
51,设 f和 g为函数,且有 f g和 Dom(g) Dom(f)。 证明 f=g。
52,证明定理 4.8.2中的 （ 2）,（ 3） 。
53,设 f:X→Y,A B X,求证 f(A) f(B)。
54,令 f={〈,{,{ }}〉,〈 { },〉 }为一函数 。 计算
f( ),f({ }),f({,{ }})。




第 4章 二元关系和函数
55,设 X,Y均是有穷集合 。 |X|=n,|Y|=m,分别找出从
X到 Y存在单射,满射,双射的必要条件 。 试计算集合
X到集合 Y有多少个不同的单射函数和多少个不同的满射函数及多少个不同的双射函数 。
第 4章 二元关系和函数
55,设 X,Y均是有穷集合 。 |X|=n,|Y|=m,分别找出从 X
到 Y存在单射,满射,双射的必要条件 。 试计算集合 X
到集合 Y有多少个不同的单射函数和多少个不同的满射函数及多少个不同的双射函数 。
56．
f(x)=2x2+1,g(x)=-x+7,N(x)=2x,k(x)= sin x
求 gｏ f,fｏ g,fｏ f,gｏ g,fｏ N,fｏ k,kｏ N。
第 4章 二元关系和函数
57,设 X={1,2,3},请找出 X X中满足下列各式的所有函数 。
（ 1） f2(x)=f(x)（ f等幂 ）
（ 2） f2(x)=x（ f2为恒等函数 ）
（ 3） f3(x)=x（ f3为恒等函数 ）
第 4章 二元关系和函数
58,设 A≠,A,B,C为集合 。
（ 1） 求 A,,
（ 2） 若 A B,则 AC BC。
59,设 N为 X上的函数,证明下列条件中 （ 1） 与 （ 2） 等价,（ 3） 与 （ 4） 等价 。
（ 1） N为一单射 。
（ 2） 对任意 X上的函数 f,g,fｏ N＝ gｏ N蕴涵 f=g。
（ 3） N为一满射 。
（ 4）对任意 X上的函数 f,g,Nｏ f＝ Nｏ g蕴涵 f＝ g
A

第 4章 二元关系和函数
60,设 A={l,2,3},作出全部 A上的置换,并以三个函数值组成的字的字典序排列这些置换 。 试计算
p 2ｏ p 3,p 3ｏ p 3,p 3ｏ p 2,并求 x,使得
p 3ｏ p x=p xｏ p 3=i。
第 4章 二元关系和函数
61,下列函数为实数集上的函数,如果它们可逆,
请求出它们的反函数 。
（ 1） y=3x+1
（ 2） y=x2-1
（ 3） y=x2-2x
（ 4） y= tg x+1
62．
（ 1） 4∪ 7,3∩5
（ 2） 6-5,4 2
（ 3） 2× 5
第 4章 二元关系和函数
66,证明,{1,3,5,…,2n+1,…}是可数集 。
67,设 A,B为可数集,证明,A× B为可数集 。
68,设 f,A→B为一满射 。
（ 1） A为无限集时,B是否一定为无限集？
（ 2） A为可数集时,B是否一定为可数集？
69,设 f,A→B为一单射 。
（ 1） A为无限集时,B是否一定为无限集？
（ 2） A为可数集时,B是否一定为可数集？
70,证明定理 4.10.12。
71.若 |A|=|B|,|C|=|D|,则 |A× C|=|B× D|。