第三章 二元关系
§ １二元关系
[定义 ]相关,按照某种规则,确定二个对象或多个对象之间有关系,称这二个对象或多个对象是相关的 。
注意,相关性与指定的规则有关 。
(1)扑克牌中的方块ｋ与梅花ｋ
同花关系：不相关同点关系：相关
(2)父子二人同辈关系：不相关注：
二元关系：二个对象之间相关的关系多元关系：多个对象之间的关系多元关系常化成二元关系来研究无序的二元关系：方块ｋ与梅花ｋ，谁在前，谁在后都还是同点的有序的二元关系：父子关系，不能交换父与子的次序又如,
（ 1） ａ＋ｂ＝偶数,ａ与ｂ是无序的用 ［ ａ,ｂ ］ 表示无序对
（ 2） ａ? ｂ,ａ与ｂ是有序的二元关系,叫作ａ相关于ｂ,记成 ａｒｂ,用 （ ａ,ｂ ） 表示有序对
（ 3） 无序的二元关系可用有序的二元关系表示即 （ ａ,ｂ ） 与 （ ｂ,ａ ） 都属于这种二元关系定义 2,二元关系 ----按照某种规定,定义了一个有序对 （ ａ,ｂ ） 的集合Ｒ,其中ａ ∈ Ａ,ｂ ∈
Ｂ,称Ｒ为Ａ到Ｂ的一个二元关系 。
注意,二元关系是指满足某规律的有序对的全体 。
Ｒ＝ ｛（ ａ,ｂ ） ｜ａ ∈ Ａ,ｂ ∈ Ｂ,ａｒｂ ｝
其中ａｒｂ读作ａ相关于ｂ 。
定义 3,当Ａ＝Ｂ时，Ｒ是Ａ到Ａ的二元关系,
称为Ａ上的二元关系。
例：Ｒ＝ ｛（ ａ,ｂ ） ｜ ａ /ｂ,ａ,ｂ ∈ Ｎ ｝
是自然数集Ｎ上的二元关系定义,二元关系的表示：因为二元关系本身也是集合,也可用穷举法,描述法来表示,还可用表格,
图示,矩阵法表示 。
例如：
Ａ＝ ｛ 张三,李四,王五,赵六 ｝
Ｂ＝ ｛ １００米,跳高,铅球,足球,跨栏 ｝
Ｒ＝ ｛（ 张三,铅球 ）,（ 张三,足球 ）,
（ 李四,１００米 ）,（ 李四,跳高 ）,
（ 王五,跨栏 ）,（ 赵六,１００米 ）｝
是运动会的报名表 。
100 米 跳高 铅球 足球 跨栏张三 √ √
李四 √ √
王五 √
赵六 √
Ａ＝ ｛ ａ,ｂ,ｃ,ｄ ｝
Ｂ＝ ｛ １,２,３,４,５ ｝
表格表示法：用表格表示一目了然
a
b
c
d
1
2
3
4
5
图示法：关系图，直观相关矩阵法表示：
把Ａ,Ｂ集合内元素排好序
Ｒ＝ )(
00001
10000
00011
01100
ij
a
d
c
b
a
１ ２ ３ ４
由于直交积Ａ × Ｂ＝ ｛（ ａ,ｂ ） ｜ａ ∈ Ａ,ｂ ∈
Ｂ ｝,二元关系Ｒ＝ ｛（ ａ,ｂ ） ｜ａ ∈ Ａ,ｂ ∈ Ｂ,
ａｒｂ ｝,可见二元关系是直交积Ａ × Ｂ的子集 。 若Ｒ
＝Ａ × Ｂ,则相关矩阵元素全为１,
Ｒ＝
111
111
111
注：
（ 1） 若Ｒ＝Ａ × B,称此二元关系为普遍关系
（ 2） 设Ａ＝ ｛ ａ 1,ａ 2,…,ａ n｝
Ｒ＝ ｛（ ａ i,ａ j） ｜ａ i,ａ j∈ Ａ ｝
若Ｒ＝ ｛（ ａ i,ａ i） ｜ａ i∈ Ａ ｝
称Ｒ为恒等关系,用Ｉ A表示,是单位矩阵
A =
1000
0100
0010
0001
把二元关系看成函数关系
Ｒ＝ ｛（ ａ,ｂ ） ｜ａｒｂ,ａ ∈ Ａ,ｂ ∈ Ｂ ｝
Ａ称为Ｒ的定义域,记Ａ＝ｄｏｍＲ
Ｂ称为Ｒ的值域,记Ｂ＝Ｒａｎｇｅ Ｒ
当定义域与值域交换得
Ｒ C＝ ｛（ ｂ,ａ ） ｜ （ ａ,ｂ ） ∈ Ｒ,ａ ∈ Ａ,
ｂ ∈ Ｂ ｝,称为Ｒ的逆关系 。
§ ２ 二元关系的运算二元关系是集合,集合存在并,
交,差,非和对称差的运算 。
故二元关系也存在这样的运算 。
设Ｒ 1和Ｒ 2是Ａ到Ｂ的二元关系,则
（ 1） Ｒ 1∪ Ｒ 2＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ 1
或 （ ａ,ｂ ） ∈ Ｒ 2｝
（ 2） Ｒ 1∩ Ｒ 2＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ 1
且 （ ａ,ｂ ） ∈ Ｒ 2｝
（ 3） Ｒ 1-Ｒ 2＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ 1
但 （ ａ,ｂ ）? Ｒ 2｝
（ 4 ） 1R ＝ ｛ ( a,b) ｜ ( a,b) ∈ A*B,但 （ａ，ｂ）? Ｒ 1 ｝
（ 5） Ｒ 1?Ｒ 2＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ 1∪ Ｒ 2
但 （ ａ,ｂ ）?Ｒ 1∩Ｒ 2｝
例１：Ａ＝ ｛ １,２,３,４ ｝, Ｒ＝ ｛ （ａ，ｂ）｜ａ，ｂ∈Ａ,2
ba?
Ｓ＝ ｛ （ａ，ｂ）｜ａ，ｂ∈Ａ，
3
ba?
∈Ｉ,a － b ＞０｝
求：Ｒ∪Ｓ，Ｒ∩Ｓ，
R
，Ｒ－Ｓ，Ｓ－Ｒ，Ｓ
Ｒ＝ ｛（ １,１ ）,（ ２,２ ）,（ ３,３ ）,
（ ４,４ ）,（ １,３ ）,（ ３,１ ）,
（ ２,４ ）,（ ４,２ ）｝
Ｓ＝ ｛（ ４,１ ）｝
Ｒ ∪ Ｓ＝ ｛（ １,１ ）,（ ２,２ ）,（ ３,３ ）,
（ ４,４ ）,（ １,３ ）,（ ３,１ ）,（ ２,４ ）,
（ ４,２ ）,（ ４,１ ）｝
注：
二元关系的矩阵运算：
相关矩阵可表示二元关系,可用矩阵的逻辑运算来研究二元关系的运算 。
R ＝ ｛ （１，２）,（２，１）,（１，４）,（４，１），
（２，３）,（３，２）,（３，４）,（４，３）｝
Ｒ－Ｓ＝Ｒ，Ｓ－Ｒ＝Ｓ，Ｓ?
R∩Ｓ＝ Φ
设,Ａ＝｛ａ 1，ａ 2,…，ａ n
Ｂ＝｛ｂ 1，ｂ 2,…，ｂ m
Ｒ 1＝（ｃ ij）
Ｒ 2＝（ｄ ij）
其中,
逻辑加 (∨),０ ∨ ０＝０,０ ∨ １＝１,
１ ∨ ０＝１,１ ∨
逻辑乘 (∧),０ ∧ ０＝０,０ ∧ １＝０,
１ ∧ ０＝０,１ ∧ １＝１
则,Ｒ
1
∪Ｒ
2
＝ （ c
ij
∨ｄ
ij
Ｒ
1
∩Ｒ
2
＝ （ｃ
ij
∧ｄ
ij
）
Ｒ
1
－Ｒ
2
＝ （ｃ
ij
∧ ijd
1R ＝ （ ij
C
）
逻辑非 （－）,0 ＝１， 1 ＝０
Ｒ＝
1010
0101
1010
0101
， Ｓ＝
0001
0000
0000
0000
则用矩阵的逻辑运算,
Ｒ∪Ｓ＝
1011
0101
1010
0101
=S? R
Ｒ∩Ｓ ＝
0000
0000
0000
0000
＝
0101
1010
0101
1010
R,
Ｒ－Ｓ＝Ｒ，
２,
[定义 ]：
设Ｒ 1为Ａ到Ｂ的二元关系,Ｒ 2为Ｂ到Ｃ的二元关系,
Ｒ 1＝ ｛（ ａ,ｂ ） ｜ａｒ 1ｂ,ａ ∈ Ａ,ｂ ∈ Ｂ ｝
Ｒ 2＝ ｛（ ｂ,ｃ ） ｜ｂｒ 2ｃ,ｂ ∈ Ｂ,ｃ ∈ Ｃ ｝
则Ｒ 1·Ｒ 2是由Ａ到Ｃ的二元关系,称为Ｒ 1,Ｒ 2的复合关系
Ｒ 3＝ ｛（ ａ,ｃ ） ｜ （ ａ,ｂ ） ∈ Ｒ 1，
且 （ ｂ,ｃ ） ∈ Ｒ 2 ｝
记 Ｒ 3＝Ｒ 1·Ｒ 2。
例２：
Ｒ是父子关系,则Ｒ ２ ＝Ｒ ·Ｒ是祖孙关系 。
例３：
Ａ＝ ｛
4321
aaaa
李兰，陈平，王兵，张华
Ｂ＝ ｛
4321
bbbb
遥感，自动化，硬件，软件
C ＝ {
4321
cccc
离散数学，操作系统，电子线路，工程制图 ｝
则：Ｒ 1＝ ｛（ ａ 1,ｂ 1）,（ ａ 1,ｂ 3）,
（ ａ 2,ｂ 2）,（ ａ 2,ｂ 4）,
（ ａ 3,ｂ 3）,（ ａ 3,ｂ 4）,
（ ａ 4,ｂ 1）,（ ａ 4,ｂ 4） ｝
是选双学位专业的 二元关系 。
Ｒ 2＝ ｛（ ｂ 1,ｃ 3）,（ ｂ 1,ｃ 4）,（ ｂ 2,ｃ 2）,
（ ｂ 2,ｃ 3）,（ ｂ 2,ｃ 4）,（ ｂ 3,ｃ 1）,
（ ｂ 3,ｃ 2）,（ ｂ 4,ｃ 2）,（ ｂ 4,ｃ 4）｝
是各专业本学期必修课的二元关系 。
Ｒ 3＝Ｒ 1·Ｒ 2＝ ｛（ ａ 1,ｃ 1）,（ ａ 1,ｃ 2）,
（ ａ 1,ｃ 3）,（ ａ 1,ｃ 4）,
（ ａ 2,ｃ 2）,（ ａ 2,ｃ 3）,
（ ａ 2,ｃ 4）,（ ａ 3,ｃ 1）,
（ ａ 3,ｃ 2）,（ ａ 3,ｃ 4）,
（ ａ 4,ｃ 2）,（ ａ 4,ｃ 3）,
（ ａ 4,ｃ 4）｝
是选双学位学生本学期必修课的二元关系
Ａ＝ )(
ij
a
nm?
，
Ｂ＝ )( jkb
Ln?
，
则,Ｃ＝Ａ·Ｂ＝ )(
ik
c
Lm?
ｃ ik ＝ jkij
n
j
baV?
1
普通的矩阵乘法：
而二元关系的复合的矩阵布尔型乘法：
而 ｃ
ik
＝?
n
j
jkij ba
1
对例 3
Ｒ
1
＝
1001
1100
1010
0101
,Ｒ
2
=
1010
0011
1110
1100
Ｒ
3
＝Ｒ
1
·Ｒ
2
＝
1110
1011
1110
1111
在行处标上姓名,列处标上课程,就知谁该必修哪些课了 。
若Ｒ是Ａ上二元关系,
Ｒ＝ ｛（ ａ,ｂ ） ｜ａｒｂ,ａ ∈ Ａ,ｂ ∈ Ａ ｝
若设,
Ｒ 1＝Ｒ
(1)Ｒ 2＝Ｒ ·Ｒ＝Ｒ 2＝ ｛（ ａ,ｃ ） ｜ （ ａ,ｂ ）,
（ ｂ,ｃ ） ∈ Ｒ ｝
(2)设Ｒ n＝Ｒ ·Ｒ …Ｒ＝Ｒ n已定义,
Ｒ n+1＝Ｒ n·Ｒ＝Ｒ n·Ｒ＝Ｒ n+1
= {（ ａ,ｃ ） ｜ （ ａ,ｂ ） ∈ Ｒ ｎ,
（ ｂ,ｃ ） ∈ Ｒ ｝
例４：
Ｒ＝ ｛（ ０,０ ）,（ ０,３ ）,
（ ２,３ ）,（ ３,２ ）,
（ ２,１ ）,（ ２,０ ） ｝
是有限集 ｛ ０,１,２,３ ｝ 上的二元关系
Ｒ的关系图：
Ｒ 2＝ ｛（ ０,０ ）,（ ０,２ ）,（ ０,３ ）,
（ ２,０ ）,（ ２,２ ）,（ ２,３ ）,
(３,０ ）,（ ３,１ ）,（ ３,３ ） ｝
Ｒ 2的关系图中不存在 （３，２），
（２，１），故Ｒ?Ｒ 2
Ｒ n的关系图的构造：
可由Ｒ的关系图来构造，从Ｒ的每个结点 ai出发，数 n条边。凡通过数 n条边能到达的结点 aj，则有（ ai,aj） ∈ Ｒ n。关系图中从ａ i出发到ａ j的边是存在的。
这样处理容易出错，用相关矩阵的布尔型乘法来做，简单，又不容易错，还适宜于计算机处理。
Ｒ 2 ＝Ｒ·Ｒ＝
1011
1101
0000
1101
0100
1011
0000
1001
0100
1011
0000
1001
0100
1011
0000
1001
R
二元关系的逆关系：运算设Ｒ,Ｓ是Ａ到Ｂ的二元关系,Ｔ是Ｂ到Ｃ的二元关系,Ｐ是Ｃ到Ｄ的二元关系 。 则：
(1) （Ｒ∪Ｓ）
c
＝Ｒ
c
∪Ｓ
c
(2) （Ｒ∩Ｓ）
c
＝Ｒ
c
∩Ｓ
c
(3) )( R
C
＝
)(
c
R
(4) （Ｒ－Ｓ）
C
＝Ｒ
C
－Ｓ
C
(5) （Ａ×Ｂ）
C
(6) R ＝
(7) （Ｓ·Ｔ）
C
＝Ｔ
C
·Ｓ
C
( 8 ) （Ｒ·Ｔ）·Ｐ＝Ｒ·
( 9 )
且 （Ｒ∩Ｓ）·Ｔ?
( 1 0 ) Ｒ
Ｓ? Ｒ
C?
Ｓ
C
证明其中,
(1)任意 （ ｘ,ｙ ） ∈ （ Ｒ ∪ Ｓ ） C
（ ｙ,ｘ ） ∈ （ Ｒ ∪ Ｓ ）
（ ｙ,ｘ ） ∈ Ｒ 或 （ ｙ,ｘ ） ∈
（ ｘ,ｙ ） ∈ Ｒ C 或 （ ｘ,ｙ ） ∈ Ｓ C
（ ｘ,ｙ ） ∈ Ｒ C ∪ Ｓ C
( 4 ) （Ｒ－Ｓ）
C ＝ （Ｒ∩ S ） C
)ii
R
C S? C )iii
R
C? S C
= R
c - s c
(7) （ Ｓ ·Ｔ ） C＝Ｔ C·Ｓ C
证：
对?（ ｘ,ｙ ） ∈ （ Ｓ ·Ｔ ） C,有
（ ｙ,ｘ ） ∈ Ｓ ·
ｚ ∈ Ｂ,使 （ ｙ,ｚ ） ∈ Ｓ,
（ ｚ,ｘ ） ∈
即,（ ｚ,ｙ ） ∈ Ｓ C，
（ ｘ,ｚ ） ∈ Ｔ C
（ ｘ,ｙ ） ∈ Ｔ C·Ｓ C
证明：等式不成立若?ａ ∈ Ａ,ｂ 1,ｂ 2∈ Ｂ,ｃ ∈ Ｃ,且
（ ａ,ｂ 1） ∈ Ｒ,（ ａ,ｂ 2） ∈ Ｓ,
（ ａ,ｂ 1）?Ｓ,（ ａ,ｂ 2）?Ｒ,
（ ｂ 1,ｃ ） ∈ Ｔ,（ ｂ 2,ｃ ） ∈ Ｔ,
显然 （ ａ ｃ ） ∈ Ｒ ·Ｔ ∩ Ｓ ·Ｔ
但 （ ａ,ｃ ）? （ Ｒ ∩ Ｓ ） ·Ｔ
(10) 证：
（ x,y) ∈ Rc? (y,x) ∈ R
(y,x) ∈ s? (x,y) ∈ Sc注：
Ｒ ·Ｔ ∩ Ｓ ·Ｔ?（Ｒ ∩ Ｓ） ·Ｔ不一定成立，
由于 （Ｒ ∩ Ｓ） ·Ｔ?Ｒ ·Ｔ ∩ Ｓ ·Ｔ
若上式成立，
则（Ｒ ∩ Ｓ） ·Ｔ =Ｒ ·Ｔ ∩ Ｓ ·Ｔ
§ ３
设Ｒ是Ａ上的二元关系,Ｒ =(rij)n*n
(1)自反性,
对?ａ ∈ Ａ，（ａ，ａ） ∈ Ｒ，则 Ｒ称为自反的二元关系。
显然,rii＝ 1（ ｉ＝１,２,…,n)
反自反性,
对?ａ ∈ Ａ,（ ａ,ａ ）?Ｒ,则Ｒ称为反自反的二元关系 。
即 rii＝０ （ ｉ＝１,２,…,n)
注,
自反和反自反性互斥,但不互补 。
如,rij中既有 0又有 1,则 R既不是自反的也不是反自反的 。
(2）
若ａ ≠ ｂ,a（ ａ,ｂ ） ∈ Ｒ,必有 （ ｂ,ａ ）
∈ Ｒ,称Ｒ为对称的二元关系即Ｒ的相关矩阵为对称阵,ａ ij＝ａ ji
反对称性：
若ａ ≠ ｂ,（ ａ,ｂ ） ∈ Ｒ,
则 （ ｂ,ａ ）?Ｒ,称Ｒ为反对称的二元关系 。
注,
（ 1
rij∧ rji ＝０（ｉ ≠
（ 2）若 rij＝１，则 rji=０，但 rij＝０时，
不要求 rji＝１，即 rij＝ rji＝０是允许的。
(3) 对称性与反对称性既不互斥，又不互补例：
恒等关系,既是对称的，又是反对称的；
而相关矩阵是
1001
0100
0100
1001
的二元关系，
是既不对称，又不是反对称的。
３）传递性,
若 （ａ，ｂ）,（ｂ，ｃ）∈Ｒ，
则 （ a,ｃ）∈Ｒ，称Ｒ为传递的二元关系。
即,（ rr
jkij
）∨ r
ik
注,rij,rjk中有一个不是１,
则 =1,rik就可以任意 。
即若 (ａ,ｂ ),(ｃ,ｄ )中有 1 个不属于 R，
则讨论 （ a,c)是否属于 R,无意义 。
即没有传递的条件,也不需传递的结果 。 如,
Ａ＝ ｛ a,b,c,d｝,Ｒ＝ ｛（ ａ,ｂ ）,（ ｃ,ｄ ）｝
rr jkij ^
二元关系的性质对应于关系图,有：
（ 1） 自反性：每个顶点都有自回路,
（ 2） 反 自反性：每个顶点都没有自回路；
（ 3） 对称性：任二个顶点间或没有边,或有二条相对而指的有向边；
（ 4） 反对称性：任二个顶点至多只有一条有向边；
（ 5） 传递性：若ｘ到ｙ有边,ｙ到ｚ有边,
则ｘ到ｚ必有边 。
注,由对称性与传递性可推出自反性 。
理由,若 （ ａ,ｂ ） ∈ Ｒ,由对称性,
有 （ ｂ,ａ ） ∈ Ｒ,由传递性有 （ ａ,ａ ） ∈ Ｒ 。
如：
R的相关矩阵是 全 0矩阵,是对称的,
传递的,反自反的,但不是自反的 。
错误原因：不是?ａ,
ｂ,使 （ ａ,ｂ ） ∈ Ｒ 。
例１：Ｒ 1＝ ｛（ ａ,ｂ ） ｜ａ ≤ｂ,ａ,ｂ ∈ Ｎ ｝
自反的,rii=1;
不对称的,(1,2) ∈ R1,而 (2,1)? R1
反对称的,传递的 。
注：将 ≤改为＜,则无自反性,且是反自反的 。
例２：Ｒ 2＝ ｛（ ａ,ｂ ） ｜ａ｜ｂ,ａ,ｂ ∈ Ｎ ｝
自反的,不对称的,反对称的,传递的 。
例３：Ｒ 3＝ ｛（ Ｓ 1,Ｓ 2） ｜Ｓ 1?Ｓ 2,Ｓ 1，
Ｓ 2∈ Ｐ （ Ｓ ）｝ 其中Ｐ （ Ｓ ） 是Ｓ的幂集 。
自反的,不对称的,反对称的,传递的 。
注：若?改为?,则无自反性 。
例４：
Ｒ 4＝ ｛（ ａ,ｂ ） ｜ａ＋ｂ＝偶数,
ａ,ｂ ∈ Ｎ ｝
自反的,对称的,传递的,
因：ａ＋ｂ＝偶,ｂ＋ｃ＝偶,
则：０＜ａ＋ｃ＝ （ ａ＋ｂ ） ＋ （ ｂ＋
ｃ ） －２ｂ＝偶数与偶数之差＝偶数 。
例５：
Ｒ 5＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ＝１
（ 互素 ）,ａ,ｂ ∈ Ｎ ｝
对称的,但不是自反的,也无传递性 。
[定理 1],设Ｒ是Ａ上的二元关系,则Ｒ ∪ Ｉ A一定是自反的,而且是包含Ｒ,具有自反性的最小关系 。
（ 其中Ｉ A是Ａ上恒等关系 ） 。
[定义 1]：称Ｒ ∪ Ｉ A是Ｒ的自反闭包,记为 r(R） 。
证明,对?ｘ ∈ Ａ,（ ｘ,ｘ ） ∈ Ｉ A?Ｒ ∪ Ｉ A，
且Ｒ?Ｒ ∪ Ｉ A。
若Ｒ ’ 为包含Ｒ且具有自反性,则Ｉ A?
Ｒ ’,Ｒ?Ｒ ’,Ｉ A∪ Ｒ?Ｒ ’ 。 即Ｉ A∪ Ｒ为最小 。
[推论 1],当且仅当Ｒ是自反闭包,Ｒ具有自反性 。
证明：
（ 1） Ｒ是自反闭包,R=Ｉ A∪ Ｒ?Ｉ A?Ｒ ;
（ 2） Ｒ具有自反性,Ｉ A?Ｒ,Ｒ ∪ Ｉ A＝Ｒ；
[定理 2]：设Ｒ是Ａ上的二元关系,则Ｒ ∪ Ｒ c是对称的,包含Ｒ的最小关系,
（ 其中Ｒ C是Ｒ的逆关系 ） 。
[定义 2],称Ｒ ∪ Ｒ C是Ｒ的对称闭包,记为 s(R)。
证明,若 （ ａ,ｂ ） ∈ Ｒ ∪ Ｒ C,则
（ ａ,ｂ ） ∈ Ｒ 或 （ ａ,ｂ ） ∈ Ｒ C，
（ ｂ,ａ ） ∈ Ｒ C 或 （ ｂ,ａ ） ∈ Ｒ
故 （ ｂ,ａ ） ∈ Ｒ ∪ Ｒ C（ 对称性 ）,
若Ｒ ’ 为包含Ｒ,对称的二元关系,
则对?（ ａ,ｂ ） ∈ Ｒ ∪ Ｒ C，
若 （ ａ,ｂ ） ∈ Ｒ?（ ａ,ｂ ） ∈ Ｒ ’ ；
若 （ ａ,ｂ ） ∈ Ｒ C?（ ｂ,ａ ） ∈ Ｒ,
（ ｂ,ａ ） ∈ Ｒ ’
又Ｒ ’ 具有对称性,（ ａ,ｂ ） ∈ Ｒ ’,
故Ｒ ∪ Ｒ C?Ｒ ’ 。
[推论 2]：当且仅当Ｒ是对称闭包时,Ｒ具有对称性 。
证明,（ 1） Ｒ具有对称性,
若 （ ａ,ｂ ） ∈ Ｒ,则 （ ｂ,ａ ） ∈ Ｒ,
又 （ ｂ,ａ ） ∈ Ｒ c
即?（ ｂ,ａ ） ∈ Ｒ c,（ ａ,ｂ ） ∈ Ｒ
（ ｂ,ａ ） ∈ Ｒ
Ｒ C? Ｒ?Ｒ ∪ Ｒ C＝Ｒ；
(2） Ｒ是对称闭包时,Ｒ＝Ｒ ∪ Ｒ C?Ｒ具有对称性 。
[定义 3],传递扩张设Ｒ＝ ｛（ ａ,ｂ ） ｜ａｒｂ,ａ,ｂ ∈ Ａ ｝,
则称Ｒ 1＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ,或?Ｃ
∈ Ａ,使 （ ａ,ｃ ）,（ ｃ,ｂ ） ∈ Ｒ ｝ 为Ｒ的传递扩张 。
(1)Ｒ?Ｒ 1
(2)Ｒ 1不一定是传递的,如：
Ｒ＝ ｛（ ａ,ｂ ）,（ ｂ,ｃ ）,（ ｃ,ｄ ）｝
Ｒ 1＝ ｛（ ａ,ｂ ）,（ ｂ,ｃ ）,（ ｃ,ｄ ）,
（ ａ,ｃ ）,（ ｂ,ｄ ）｝
由 （ ａ,ｃ ）,（ ｃ,ｄ ）,（ ａ,ｂ ）,
（ ｂ,ｄ ） 又产生了新的传递条件,而 （ ａ,ｄ ）
Ｒ 1,Ｒ 1不是传递的 。
(3) 当且仅当Ｒ是传递的,Ｒ＝Ｒ 1。
证明：,?”,Ｒ是传递的,（ ＲＲ 1）
对?（ ａ,ｂ ） ∈ Ｒ 1,有
（ ａ,ｂ ） ∈ Ｒ 或? c∈ Ａ,
使 （ ａ,ｃ ）,（ ｃ,ｂ ） ∈ Ｒ,
由Ｒ的传递性,（ ａ,ｂ ） ∈ Ｒ,
故Ｒ 1Ｒ,得Ｒ＝Ｒ 1。
,?”,Ｒ＝Ｒ 1
若 （ ａ,ｃ ） ∈ Ｒ,（ ｃ,ｂ ） ∈ Ｒ,
则 （ ａ,ｂ ） ∈ Ｒ 1＝Ｒ,Ｒ是传递的 。
注,（ 1） 若Ｒ 1不是传递的,可扩张到Ｒ 2，
Ｒ 3,…Ｒ k ；
（ 2） 若Ｒ k是传递的,则Ｒ k+1＝Ｒ k。
[定义 3]：
设Ｒ 0＝Ｒ,Ｒ k+1是Ｒ k的传递扩张 （ ｋ＝０,１,
２,…）,则称Ｒ *＝Ｒ 0∪ Ｒ 1∪ Ｒ 2∪ …∪ Ｒ k∪ …为Ｒ
的传递闭包,也记作 t(R)。
[定理 3] 传递闭包Ｒ *＝Ｒ ∪ Ｒ 2∪ …∪ Ｒ k∪ …
证明,Ｒ 2＝Ｒ ·Ｒ＝｛（ａ，ｂ）｜
（ａ，ｃ），（ｃ，ｂ） ∈
Ｒ 1＝｛（ａ，ｂ）｜（ａ，ｂ） ∈ Ｒ
或（ａ，ｃ）,（ｃ，ｂ） ∈ Ｒ｝
＝Ｒ ∪ Ｒ 2
Ｒ 2＝｛（ａ，ｂ）｜（ａ，ｂ） ∈ Ｒ 1，
或 （ａ，ｃ），（ｃ，ｂ） ∈ Ｒ 1｝
（ 1） 若 （ ａ,ｃ ）,（ ｃ,ｂ ） ∈ Ｒ,
则 （ ａ,ｂ ） ∈ Ｒ ·Ｒ,
（ 2） 若其一,如 (ａ,ｃ ） ∈ Ｒ
另一,如 (c,ｂ ） ∈ Ｒ ·Ｒ
则 （ ａ,ｂ ） ∈ Ｒ ·Ｒ ·Ｒ ∈ Ｒ 3，
（ 3） 若 （ ａ,ｃ ）,（ ｃ,ｂ ） ∈ Ｒ ·Ｒ
则 （ ａ,ｂ ） ∈ Ｒ ·Ｒ ·Ｒ ·Ｒ ∈ Ｒ 4 ＝Ｒ 22，
即Ｒ 2＝Ｒ ∪ Ｒ 2∪ Ｒ 3∪ Ｒ 4
假设Ｒ k＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ,或 …，
或 （ ａ,ｂ ） ∈ Ｒ 2k ｝
则 Ｒ k+1＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ k，
或 （ ａ,ｃ ）,（ ｃ ｂ ） ∈ Ｒ k｝
当 （ ａ,ｃ ） ∈ Ｒ i,（ ｃ,ｂ ） ∈ Ｒ j，
（ ｉ,ｊ＝１,２,…,2k）
（ ｉ＋ｊ＝２,３,…,２ k+1）
有Ｒ k+1＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ,或 … 或
（ ａ,ｂ ） ∈ Ｒ 2k+1 ｝ ＝Ｒ ∪ Ｒ 1 ∪ Ｒ 2∪ Ｒ 3∪ …∪ Ｒ 2k+1
故，Ｒ的闭包
*
R ＝Ｒ∪Ｒ
1
∪Ｒ
2
∪?∪Ｒ
k
∪?
＝?
0k
k
R
＝Ｒ∪Ｒ
2
∪Ｒ
3
∪?∪
k
R
2
∪?
＝?
1k
k
R
[定理 4],传递闭包 Ｒ *一定是传递的 。
证明：设 （ ａ,ｂ ） （ ｂ,ｃ ） ∈ Ｒ *,则
ｉ,ｊ,使 （ ａ,ｂ ） ∈ Ｒ i，
（ ｃ,ｂ ） ∈ Ｒ j，
故 （ ａ,b） ∈ Ｒ (i+j)?Ｒ *
传递扩张的实际意义：
举 例,
Ｒ＝ ｛（ ａ,ｂ ） ｜ａ与ｂ是父子关系 ｝
Ｒ ·Ｒ＝ ｛（ ａ,ｂ ） ｜ａ与ｂ是祖孙关系 ｝
Ｒ １ ＝ ｛（ ａ,ｂ ） ｜ａ与ｂ是三代以内男性直系亲属 ｝
…
证明：
对?（ ｘ,ｙ ） ∈ Ｒ *,?ｋ,使 （ ｘ,ｙ ）
∈ Ｒ k,表明在Ａ中存在不同元素ａ 1,ａ 2,…，
ａ k-1,使 （ ｘ,ａ 1）,（ ａ 1,ａ 2）,（ ａ 2，
ａ 3）,…,（ ａ k-1,ｙ ） ∈ Ｒ 。
若ｋ＞ｎ,由鸽洞原理,则ａ 1,ａ 2,…，
ａ k-1,ｙ中至少有两个相同,不妨设ａ i＝ｙ,
（ ｉ? ｋ－１ ） 。
[定理 5]：
设｜Ａ｜＝ｎ,Ｒ是Ａ上二元关系,
则存在正整数ｋ,ｋ? ｎ,使 Ｒ * ＝Ｒ
∪ Ｒ 2∪ …∪ Ｒ k。
于是（ｘ，ａ 1）,…（ａ i，ａ i-1 ） ∈ Ｒ,
（ａ i-1,ｙ） ∈ Ｒ，
故（ｘ，ｙ） ∈ Ｒ i，
即 若ｋ＞ｎ，必存在比ｋ的正整数ｉ，
使（ｘ，ｙ） ∈ Ｒ i。
注：
定理说明,可用Ｒ ∪ Ｒ 2∪ …∪ Ｒ n来求 Ｒ * 。
例６,
设Ａ＝ ｛ １,２,３ ｝,
Ｒ＝ ｛（ １,１ ）,（ １,２ ）,(２,３ ）｝
求 Ｒ * 。
解,Ｒ＝
000
100
011
,Ｒ
2
＝
000
000
111
＝Ｒ
3
故
R
＝Ｒ∪Ｒ
2
∪Ｒ
3
＝
000
100
111
R
＝ ｛ （１，１）,（１，２）,（１，３）,（２，３）｝
设Ｒ是ｎ个元素集合上的二元关系
(1)
(2)ｉ ← １；
(3)ｆｏｒ ｊ＝１ ｔｏ ｎ
iｆ ａ j,i＝１ ｔｈｅｎ
ｆｏｒ ｋ＝１ ｔｏ ｎ ｄｏ
ａ j,k← ａ j,k∨ ａ i,k
(4)ｉ =ｉ＋１；
(5) iｆ ｉ ≤ｎ,ｔｈｅｎ go (3)
ｅｌｓｅ ｓｔｏｐ
注,当｜Ａ｜＝ｎ较大时,用定理 5计算 Ｒ *
工作量非常大 。
注,（ 1） 结果 (aij)nxn是Ｒ *的相关矩阵 。
（ 2） 算法的复杂度为ｎ 3。
例 6：重新计算Ｒ *
例７：Ａ＝ ｛ ａ,ｂ,ｃ,ｄ ｝
Ｒ＝ ｛（ ａ,ｂ ）,（ ｂ,ｃ ）,
（ ｃ,ｄ ） ｝
计算Ｒ *。
0000
1000
0100
0010
R
(1)i=1 由于 aj1=0(j=1,2,3,4) 不改动
(2)i=2 j=1,aji=1? a13=1
(3)i=3
0000
1000
0100
0110
j=1,a13=1? a14=1
j=2,a23=1? a24=1
即
Ｒ * ＝｛（ａ，ｂ），（ａ，ｃ），
（ａ，ｄ），（ｂ，ｃ），
（ｂ，ｄ），（ｃ，ｄ）｝
§ ４ 等价关系
４,１ 等价关系
[定义 1] 等价关系,
Ａ上的二元关系Ｒ,如果Ｒ是
(1） 自反的
(2） 对称的
(3) 传递的称Ｒ为等价关系 。
（ ａ,ｂ ） ∈ Ｒ,称ａ与ｂ等价,记作ａ～ｂ 。
[定义 4.2] 等价类,把Ａ中的等价元素归为一类,
称为等价类 。
注：
等价关系Ｒ把Ａ的元素分为若干类,各类之间没有公共元素 。 确定的Ｒ是对集合Ａ进行的分划 。
[定义 4.3]集合的分划：把集合Ａ分为若干子集
Ａ 1,Ａ 2,…,满足：
（ 1） 当ｉ ≠ ｊ时Ａ i∩ Ａ j＝?
（ 2）?ａ ∈ Ａ,?ｉ,
使ａ ∈ Ａ i（ ｉ＝１,２,…）
则集合 Pr（ Ａ ） ＝ ｛ Ａ 1,Ａ 2,…,Ａ n,…｝ 称为
Ａ的一个分划 。
注：
（１）
P （Ａ）? ｐ （Ａ） （Ａ的幂集）
（２）当且仅当Ａ＝? 时,?P （Ａ）＝ｐ （Ａ）＝ ｛? ｝
（３）Ａ非空时?P （Ａ）? ｐ （Ａ）
[定理 1]：
Ａ在等价关系Ｒ下的等价类正是Ａ的一种分划,Ａ的任一种分划,也必有Ａ上的一个等价关系Ｒ与之对应 。
证明：
Ｒ是等价关系,?ａ ∈ Ａ,由Ｒ的自反性,
（ ａ,ａ ） ∈ Ｒ,即ａ与ａ属于同一等价类,
也即?ｉ,ａ ∈ Ａ i
若ｉ ≠ｊ,Ａ i≠Ａ j,而Ａ i∩Ａ j ≠?,则?ｃ
∈ Ａ i∩Ａ j,ｃ ∈ Ａ i,且ｃ ∈ Ａ j,
对?ａ ∈ Ａ i,ａ～ｃ,ｃ ∈ Ａ j
对?ｂ ∈ Ａ j,ｂ～ｃ,即ｃ～ｂ (对称性 )
由Ｒ传递性,ａ～ｂ
由ａ,ｂ的任意性,故Ａ i＝Ａ j
若Ａ已进行了分划,则构造二元关系Ｒ 。
(1)?ａ ∈ Ａ,使 （ ａ,ａ ） ∈ Ｒ,
(2)分别对每一等价类内所有两个不同元素ａ,
ｂ,（ ａ,ｂ ） ∈ Ｒ,使 （ ｂ,ａ ） ∈ Ｒ,
显然,Ｒ是自反的,对称的,而且也是传递的,因为若 （ ａ,ｂ ） ∈ Ｒ,（ ｂ,ｃ ）
∈ Ｒ,则ａ,ｂ,ｃ均在同一等价类内,
故 （ ａ,ｃ ） ∈ Ｒ 。
与Ａ i和Ａ j 为不同的等价类矛盾 。
故Ａ i∩Ａ j ≠?
所以,Ｒ完成了等价类的分划例１：
Ａ＝ ｛ ５２张扑克 ｝
Ｒ 1＝ ｛（ ａ,ｂ ） ｜ａ与ｂ同花,ａ,ｂ是扑克 ｝
Ｒ 2＝ ｛（ ａ,ｂ ） ｜ａ与ｂ同点,ａ,ｂ是扑克 ｝
则,Ｒ 1把Ａ分为四类同花类,
Ｒ 2把Ａ分为１３类同点类 。
例２：
Ａ＝ ｛ ０,１,２,３,４,５ ｝
Ｒ＝ ｛（ ０,０ ）,（ １,１ ）,（ ２,
２ ）,（ ３,３ ）,（ １,２ ）,（ １,３ ）,
（ ２,１ ）,（ ２,３ ）,（ ３,１ ）,（ ３,
２ ）,（ ４,４ ）,（ ４,５ ）,（ ５,４ ）,
（ ５,５ ）｝
Ｒ 是等价关系,但不直观,用关系图表示 。
三个不连通的图二元关系 R是自反的,对称的,传递的,
且 把 Ａ 分 成 了 三 个 等 价 类,（ Ａ ） ＝
｛｛ ０ ｝,｛ １,２,３ ｝,｛ ４,５ ｝｝
[定义 ]：商集的元素个数 （ 即Ａ在Ｒ下的等价类个数 ） 称为Ｒ的秩,
[定义 ] 商集：等价关系 R将 A分成若干等价类,每个类选个代表组成新的集合称为 A关于 R的商集,表示为 A/R。
例：在上例中
A/R＝ ｛［ ０ ］,［ １ ］,［ ４ ］｝
例３：
Ｒ＝ ｛（ ａ,ｂ ） ｜ａ ≡ ｂ （ ｍｏｄ３ ）,
ａ,ｂ ∈ Ｉ ｝ 是整数集合Ｉ上模３同余的二元关系,
证明 R是等价关系 。
证明：由于３｜ （ ａ－ｂ ） ａ ≡ ｂ （ ｍｏｄ３ ）
(1) ３｜ （ ａ－ａ ）,
(2)若３｜ （ ａ－ｂ ）,则３｜ （ ｂ－ａ ）
(3)若３｜ （ ａ－ｂ ）,３｜ （ ｂ－ｃ ）,则
ａ－ｃ＝ （ ａ－ｂ ） ＋ （ ｂ－ｃ ）
３｜ （ ａ－ｃ ）
满足传递性,
商集：Ｉ／Ｒ＝ ｛［ ０ ］,［ １ ］,［ ２ ］｝
其中 ［ ０ ］ ＝ ｛ …,－６,－３,０,３,６,…｝
［ １ ］ ＝ ｛ …,－５,－２,１,４,７,…｝
［ ２ ］ ＝ ｛ …,－４,－１,２,５,８,…｝
例４：
Ｎ的一个分划为：若１０ i-1? ａ＜１０ i，
则ａ ∈ Ａ i,对应的等价关系
Ｒ＝ ｛（ ａ,ｂ ） ｜ａ与ｂ有相同位数,
ａ,ｂ ∈ Ｎ ｝ 相同位的数归为一类,此Ｒ把
Ｎ分划为可列个等价类 。
[定义 ]相 容关系：
Ａ上的二元关系Ｒ,若是自反的,
对称的,称Ｒ为相容关系 。
等价关系必然是相容关系 。
[定理 2]：
若Ｒ 1,Ｒ 2是Ａ上的等价关系,则Ｒ 1∩ Ｒ 2也是等价关系 。
证明：Ｒ 1∩ Ｒ 2＝Ｒ 3,Ｒ 3传递 。
(1）?ａ ∈ Ａ,由Ｒ 1,Ｒ 2自反
（ ａ,ａ ） ∈ Ｒ 1,（ ａ,ａ ） ∈ Ｒ 2,于是
（ ａ,ａ ） ∈ Ｒ 1∩ Ｒ 2＝Ｒ 3,Ｒ 3自反
(2)若 （ ａ,ｂ ） ∈ Ｒ 3,则 （ ａ,ｂ ） ∈ Ｒ 1
且 （ ａ,ｂ ） ∈ Ｒ 2,由Ｒ 1,Ｒ 2对称
（ ｂ,ａ ） ∈ Ｒ 1,（ ｂ,ａ ） ∈ Ｒ 2
于是 （ ｂ,ａ ） ∈ Ｒ 1∩ Ｒ 2＝Ｒ 3,Ｒ 3对称
４,２ 等价关系的运算
222
111
),(),(,),(
),(),(,),(
RcaRcbRba
RcaRcbRba
(3)若 （ ａ,ｂ ） ∈ Ｒ 3,（ ｂ,ｃ ） ∈ Ｒ 3
于是 （ ａ,ｃ ） ∈ Ｒ 1∩ Ｒ 2＝Ｒ 3,Ｒ 3传递 。
归纳以上三点,Ｒ 3＝Ｒ 1∩Ｒ 2也是等价的二元关系 。
[定理 3],若Ｒ 1,Ｒ 2是Ａ上等价关系,则Ｒ 1∪ Ｒ 2
是相容关系 。
注：Ｒ 1∪ Ｒ 2 不一定 是等价关系 。
证明：
设Ｒ 4＝Ｒ 1∪ Ｒ 2
(1)?ａ ∈ Ａ,（ ａ,ａ ） ∈ Ｒ 1,（ ａ,
ａ ） ∈ Ｒ 2,于是 （ ａ,ａ ） ∈ Ｒ 1∪ Ｒ 2＝Ｒ 4。
(2） 若 （ ａ,ｂ ） ∈ Ｒ 4,（ ａ,ｂ ） ∈
Ｒ 1或 （ ａ,ｂ ） ∈ Ｒ 2由Ｒ 1,Ｒ 2对称性,（ ｂ,
ａ ） ∈ Ｒ 1或 （ ｂ,ａ ） ∈ Ｒ 2，
于是 （ ｂ,ａ ） ∈ Ｒ 1∪ Ｒ 2＝Ｒ 4
注：Ｒ 4＝Ｒ 1∪ Ｒ 2是相容的,即
Ｒ 1∪ Ｒ 2不一定是等价关系若 （ ａ,ｂ ） ∈ Ｒ 4,（ ｂ,ｃ ） ∈ Ｒ 4
（ ａ,ｂ ） 与 （ ｂ,ｃ ） 可能分别属于
Ｒ 1与Ｒ 2,无法保证Ｒ 1∪ Ｒ 2的传递性 。
例５：
Ａ＝ ｛ ａ,ｂ,ｃ ｝
Ｒ 1＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,
（ ｃ,ｃ ）,（ ａ,ｂ ）,（ ｂ,ａ ）｝
Ｒ 2＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,
（ ｃ,ｃ ）,（ ｂ,ｃ ）,（ ｃ,ｂ ）｝
Ｒ 4＝Ｒ 1∪ Ｒ 2＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,
（ ｃ,ｃ ）,（ ａ,ｂ ）,（ ｂ,ａ ）,
（ ｂ,ｃ ）,（ ｃ,ｂ ）｝
显然,（ ａ,ｂ ）,（ ｂ,c） ∈ Ｒ 1∪ Ｒ 2
但 （ ａ,c）?Ｒ 1∪ Ｒ 2（ 不具有传递性 ）,
但 （ Ｒ 1∪ Ｒ 2） *一定是传递的 。
[定理 4],若Ｒ 1,Ｒ 2是Ａ上等价关系,
则 （ Ｒ 1∪ Ｒ 2） *也是Ａ上等价关系 。
证明：
(1)?ａ ∈ Ａ,（ ａ,ａ ） ∈ （ Ｒ 1∪ Ｒ 2）
（ Ｒ 1∪ Ｒ 2） *
(2)（ Ｒ 1∪ Ｒ 2） 是对称的,只需证明对称的二元关系的传递扩张还是对称的 。
设Ｒ是Ａ上对称的二元关系,Ｒ 1是Ｒ的传递扩张,若 （ ａ,ｂ ） ∈ Ｒ 1,则 （ ａ,ｂ ） ∈ Ｒ
或 （ ａ,ｂ ） ∈ Ｒ ·Ｒ,
a,若 （ ａ,ｂ ） ∈ Ｒ,（ ｂ,ａ ） ∈ Ｒ,
故 (ｂ,ａ )∈ Ｒ 1;
由 （ Ｒ 1∪ Ｒ 2） 对称?（ Ｒ 1∪ Ｒ 2） 1也对称,…，
对任一ｋ,（ Ｒ 1∪ Ｒ 2） k也对称 。
若 （ ａ,ｂ ） ∈ （ Ｒ 1∪ Ｒ 2） *,则?ｋ,
使 （ ａ,ｂ ） ∈ （ Ｒ 1∪ Ｒ 2） k，
故 （ ｂ,ａ ） ∈ （ Ｒ 1∪ Ｒ 2） k? （ Ｒ 1∪ Ｒ 2） *，
于是 （ Ｒ 1∪ Ｒ 2） *是对称的 。
（ 3） 任一传递闭包都具有传递性 。
即证 。
b,若（ａ，ｂ） ∈ Ｒ ·Ｒ，则ｃ，使
（ａ，ｃ），（ｃ，ｂ） ∈ Ｒ
（ｂ，ｃ），（ｃ，ａ） ∈ Ｒ
（ｂ，ａ） ∈ Ｒ ·Ｒ
（ｂ，ａ） ∈ Ｒ 1
等价关系对应于集合的一种分划 。
设Ｒ 1,Ｒ 2是Ａ上等价关系,对应的分划为
π1,π2，
π1·π2对应于Ｒ 1∩Ｒ 2,称为 二个分划的积,
使分划分更细；
π1＋ π2对应于 （ Ｒ 1∪ Ｒ 2） *,称为两个 分划的和,使分划比 π1,π2要粗 。
例６：
Ａ＝ ｛ ａ,ｂ,ｃ,ｄ,ｅ,ｆ,ｇ,ｈ,
ｉ,ｊ,ｋ ｝
４,３ 等价关系的运算与分划的关系
Ｒ 1? π 1 ＝ ｛
4
3
2
1
,,,
AAAA
jkhie fga b c d ｝
Ｒ
2
π
2
＝ ｛
43
21
,,,
BBBB
ge fi kdia b c h ｝
Ｒ 1＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,（ ｃ,ｃ ）,（ ｄ,
ｄ ）,（ ｅ,ｅ ）,（ ｆ,ｆ ）,（ ｇ,ｇ ）,（ ｈ,
ｈ ）,（ ｉ,ｉ ）,（ ｊ,ｊ ）,（ ｋ,ｋ ）,（ ａ,
ｂ ）,（ ａ,ｃ ）,（ ａ,ｄ ）,（ ｂ,ｃ ）,（ ｂ,
ｄ ）,（ ｃ,ｄ ）,（ ｂ,ａ ）,（ ｃ,ａ ）,（ ｄ,
ａ ）,（ ｃ,ｂ ）,（ ｄ,ｂ ）,（ ｄ,ｃ ）,（ ｅ,
ｆ ）,（ ｅ,ｇ ）,（ ｆ,ｇ ）,（ ｆ,ｅ ）,（ ｇ,
ｅ ）,（ ｇ,ｆ ）,（ ｈ,ｉ ）,（ ｉ,ｈ ）,（ ｊ,
ｋ ）,（ ｋ,ｊ ）｝
Ｒ 2＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,（ ｃ,ｃ ）,
（ ｄ,ｄ ）,（ ｅ,ｅ ）,（ ｆ,ｆ ）,
（ ｇ,ｇ ）,（ ｈ,ｈ ）,（ ｉ,ｉ ）,
（ ｊ,ｊ ）,（ ｋ,ｋ ）,（ ａ,ｂ ）,
（ ａ,ｃ ）,（ ａ,ｈ ）,（ ｂ,ｃ ）,
（ ｂ,ｈ ）,（ ｃ,ｈ ）,（ ｂ,ａ ）,
（ ｃ,ａ ）,（ ｈ,ａ ）,（ ｃ,ｂ ）,
（ ｈ,ｂ ）,（ ｈ,ｃ ）,（ ｄ,ｉ ）,
（ ｉ,ｄ ）,（ ｅ,ｆ ）,(ｅ,ｊ ）,
（ ｅ,ｋ ）,( f,j ),（ ｆ,ｋ ）,
（ ｊ,ｋ ）,（ ｆ,ｅ ）,（ ｊ,ｅ ）,
（ ｋ,ｅ ）,（ ｊ,ｆ ）,（ ｋ,ｆ ）,
（ ｋ,ｊ ）｝
Ｒ 1∩ Ｒ 2＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,
（ ｃ,ｃ ）,（ ｄ,ｄ ）,（ ｅ,ｅ ）,
（ ｆ,ｆ ）,（ ｇ,ｇ ）,（ ｈ,ｈ ）,
（ ｉ,ｉ ）,（ ｊ,ｊ ）,（ ｋ,ｋ ）,
（ ａ,ｂ ）,（ ａ,ｃ ）,（ ｂ,ｃ ）,
（ ｅ,ｆ ）,（ ｊ,ｋ ）,（ ｂ,ａ ）,
（ ｃ,ａ ）,（ ｃ,ｂ ）,（ ｆ,ｅ ）,
（ ｋ,ｊ ）
Ｒ 1∪ Ｒ 2＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,（ ｃ,ｃ ）,
（ ｄ,ｄ ）,（ ｅ,ｅ ）,（ ｆ,ｆ ）,（ ｇ,ｇ ）,
（ ｈ,ｈ ）,（ ｉ,ｉ ）,（ ｊ,ｊ ）,（ ｋ,ｋ ）,
（ ａ,ｂ ）,（ ａ,ｃ ）,（ ａ,ｄ ）,（ ｂ,ｃ ）,
（ ｂ,ｄ ）,（ ｃ,ｄ ）,（ ｂ,ａ ）,（ ｃ,ａ ）,
（ ｄ,ａ ）,（ ｃ,ｂ ）,（ ｄ,ｂ ）,（ ｄ,ｃ ）,
（ ａ,ｈ ）,（ ｂ,ｈ ）,（ ｃ,ｈ ）,（ ｈ,ａ ）,
（ ｈ,ｂ ）,（ ｈ,ｃ ）,（ ｅ,ｆ ）,（ ｅ,ｇ ）,
（ ｆ,ｇ ）,（ ｆ,ｅ ）,（ ｇ,ｅ ）,（ ｇ,ｆ ）,
（ ｈ,ｉ ）,（ ｉ,ｈ ）,（ ｊ,ｋ ）,（ ｋ,ｊ ）,
（ ｄ,ｉ ）,（ ｉ,ｄ ）,（ ｅ,ｊ ）,（ ｅ,ｋ ）,
（ ｆ,ｊ ）,（ ｆ,ｋ ）,（ ｊ,ｅ ）,（ ｋ,ｅ ）,
（ ｊ,ｆ ）,（ ｋ,ｆ ）｝
但Ｒ 1∪ Ｒ 2不是传递的,如,（ ｃ,ｈ ）,
（ ｈ,ｉ ） ∈ Ｒ 1∪ Ｒ 2,而 （ ｃ,ｉ ）?Ｒ 1∪ Ｒ 2。
把Ｒ 1∪ Ｒ 2扩张到传递性满足,就是 （ Ｒ 1∪ Ｒ 2） *。
Ｒ
1
∩Ｒ
2
π
1
· π
2
＝ ｛
34
2313
4422
2111
,,,,,,
BA
BABA
BABA
BABA
jkihgefda b c
｝
凡是在 π
1
,π
2
中有一个要求把它们拆开的
（Ｒ
1
∪Ｒ
2
）
*?
｛
4342
2131
,
BBAA
BBAA
e fg jka b c d i h
｝
例７,
Ａ＝ ｛ ５２张扑克牌 ｝
Ｒ 1＝ ｛（ ａ,ｂ ） ｜ａ与ｂ同花,
ａ,ｂ是扑克 ｝
π 1
Ｒ 2＝ ｛（ ａ,ｂ ） ｜ａ与ｂ同点,
ａ,ｂ是扑克 ｝
π 2
Ｒ 1∩ Ｒ 2? π 1·π 2把扑克分成５２张单张
（ Ｒ 1∪ Ｒ 2） *? π 1＋ π 2把５２张扑
[定义 ]平凡分划,
集合 A的最粗或最细的分划,称为 平凡分划 。
注,
（ 1） 等价关系,用穷举法很难判别
（ 2） 用关系图比较直观,明确
（ 3） 用集合的分划来研究等价关系
§ ５ 半序关系
[定义 ],半序关系 （ 偏序关系 ）
Ｒ是Ａ上的二元关系,如果Ｒ满足：
(1) 自反的
(2） 反对称的
(3) 传递的则称Ｒ是Ａ上半序关系 。
例：
Ａ＝ ｛ １,２,３,４,５,６,７,８,９ ｝
Ｂ＝ ｛ ａ,ｂ,ｃ ｝
Ｒ 1＝ ｛（ ａ,ｂ ） ｜ ａ? ｂ,ａ,ｂ ∈ Ａ ｝
Ｒ 2＝ ｛（ ａ,ｂ ） ｜ ａ |ｂ,ａ,ｂ ∈ Ａ ｝
Ｒ 3＝ ｛（ ｓ 1,ｓ 2） ｜ｓ 1?ｓ 2，
ｓ 1,ｓ 2∈ ｐ （ Ｂ ）｝
记号：
Ｒ ={（ ａ,ｂ ） |ａ ≤Ｒ b,ａ,ｂ ∈ Ａ ｝ 其中 ≤Ｒ 可为?,|,?
注：
（ 1） 用矩阵表示半序关系,不能明显看到二元关系的特征 。
（ 2） 用简化的关系图表示较适合 。
(1)自反性：每个顶点都有自回路,省去 。
(2)反对称性：两个顶点间只可能有一个箭头从左 → 右,或从下 → 上的方向从小到大安置顶点,可省略箭头 。
(3)传递性：由于有 （ ａ,ｂ ）,（ ｂ,ｃ ） ∈ R
则 （ ａ,ｃ ） ∈ R
故只画 （ ａ,ｂ ）,（ ｂ,ｃ ） 对应的边省略边 （ ａ,ｃ ） 。
[定义 ],Ｈａｓｓｅ图设 ≤是Ａ上的一个半序关系,如果
ａ ≤ｂ,则将ａ画在ｂ下面,且不?ｃ,
使ａ ≤ｃ,ｃ ≤ｂ,则ａ,ｂ间用直线连接 。 并符合简化的关系图的绘制,
称这样得到关系图为Ｈａｓｓｅ图 。
例中半序关系的Ｈａｓｓｅ图如下：
1
2
3
4
5
6
7
8
9
R1
[定义 ] 全序,
Ａ上半序关系Ｒ,如果?ａ,ｂ ∈ Ａ,都有
ａ ≤ｂ,或ｂ ≤ａ,则称Ｒ为Ａ上的全序关系 。
注：
（ 1） 全序的含义：Ａ中每两个元素均能比大小,即任何两个元素都相关 。
（ 2） 半序则是部分有序 。
（ 3） Ｒ 1是全序,Ｒ 2,Ｒ 3都是半序如：Ｒ 2中,｛ １,２,６ ｝,｛ １,２,
４,８ ｝,｛ １,３,９ ｝ 都排成了序,但２
与３,５与７,７与９ …,在整除的意义上来说无法排出大小来 。
[定义 ]半序集：
集合Ａ及Ａ上的一个半序关系Ｒ组成的二元组 （ Ａ,Ｒ ）,称为半序集,记为
（ Ａ,? Ｒ ） 或 （ Ａ,≤） 。
注：
（ 1） 同一集合上的两个不同的半序关系,
所构成两个半序集,如：
Ｒ 1和Ｒ 2都定义在Ａ＝ ｛ １,２,３,４,
５,６,７,８,９ ｝ 上,但 （ Ａ,Ｒ 1） 与
（ Ａ,Ｒ 2） 显然不是一样的半序集 。
[定义 ]全序集：
半序集 （ Ａ,? Ｒ ） 中的半序关系? Ｒ 是Ａ上的全序,则此 （ Ａ,? Ｒ ）
称为全序集 。
（ Ａ,Ｒ 1） 是全序集 。 显然,全序集是半序集的特例 。 又如,（ － ∞,＋ ∞）
实数全体,在 ≤下是全序集；平面上点集,
也可以规定一种? Ｒ,模长大的大,模长相等的情况下,以幅角的大小来比大小,
因此,平面上点集也是全序集 。 （ Ｎ,≤）
当然也是全序集 。
注,
实数全体,平面点集是无法用Ｈａｓ
ｓｅ图表示的 。 一般来说,对有限集用Ｈ
ａｓｓｅ图比较好,对可列集只能示意一下,对不可列无限集是没法表示的,因为任二个数之间一定还有别的数 。
[定义 ]链：
设 （ Ａ,≤Ｒ ） 是半序集,,若
（ Ｂ,≤Ｒ ） 是全序集,则称Ｂ为 （ Ａ,≤
Ｒ ） 中的链 （ Ｃｈａｉｎ ） 。
当Ｂ是有限集时,Ｂ的基数｜Ｂ｜称为链长 。
例：
在上例 Ｈａｓｓｅ图 （ Ａ,Ｒ 2） 中,
取Ｂ 1＝ ｛ １,２,４,８ ｝,Ｒ 2＝ |（ 整除 ）,则
（ Ｂ 1,Ｒ 2） 是全序关系,Ｂ 1是半序集 （ Ａ,|） 中链长为４的链 。
Ｂ 2＝ ｛ １,２,６ ｝,Ｂ 3＝ ｛ １,
３,９ ｝,Ｂ 4＝ ｛ １,５ ｝,Ｂ 5＝ ｛ １,
７ ｝ 也都是 （ Ａ,|） 中的链 。
[定义 ]反链：
设 （ Ａ,? Ｒ ） 为半序集,Ｂ Ａ,对?
ａ,ｂ ∈ Ｂ （ ａ ≠ ｂ ）,（ ａ,ｂ ）?Ｒ,
（ ｂ,ａ ）?Ｒ,则称Ｂ为 （ Ａ,? Ｒ ） 中的反链 。
当Ｂ为有限集时,｜Ｂ｜为反链的长度 。
注,反链中的元素都互不相关 。
例如,（ Ａ,Ｒ 2）
Ｂ 1＝ ｛ ２,３,５,７ ｝ ｜Ｂ 1｜＝４
Ｂ 2＝ ｛ ４,６,９ ｝ ｜Ｂ 2｜＝３
Ｂ 3＝ ｛ ８,６,９,５,７ ｝ ｜Ｂ 3｜＝５
…
都是反链 。
[定义 ]极大元与极小元：
设 （ Ｐ,≤） 是半序集,Ａ?Ｐ,若ａ
∈ Ａ,且在Ａ中找不到一个元素ｂ （ ｂ ≠
ａ ）,使ａ ≤ｂ （ ｂ ≤ａ ）,则称ａ为Ａ中的极大元 （ 极小元 ） 。
例,（ Ｎ,|） 是半序集,
Ａ＝ ｛ ２,３,４,５,６,７,８,９ ｝
则 Ａ中极大元：８,６,９,５,７
极小元：２,３,５,７
注：
极大元,极小元并不要求唯一,且同一元素,
可以既是极大元,又是极小元,如５,７ 。
注,
极大元,极小元必须是子集Ａ中的元素 。
[定义 ]最大元与最小元：
设 （ Ｐ,? ） 是半序集,Ａ?Ｐ,
若ａ ∈ Ａ,?ｂ ∈ Ａ,ｂ? ａ (ａ? ｂ ）,
则称ａ为Ａ的最大元 （ 最小元 ） 。
例,上例其 Hasse图如下图所示结论：
子集Ａ中是不存在最大元 （ 最小元 ） 的 。
例,Ｂ＝ ｛ ａ,ｂ,ｃ ｝,
Ｒ 3＝ ｛（ ｓ 1,ｓ 2） ｜ｓ 1?ｓ 2,ｓ 1，
ｓ 2∈ ｐ （ Ｂ ）｝,（ ｐ （ Ｂ ）,? ） 是半序集 。
设Ａ＝ ｛ Ф,｛ ａ ｝,｛ ｂ ｝,｛ ｃ ｝,
｛ ａ,ｂ ｝,｛ ａ,ｃ ｝,｛ ｂ,ｃ ｝｝
其 Hasse图如下图所示结论：
A存在最小元 Ф,没有最大元。
注：
最大元 （ 最小元 ） 本身应属于子集Ａ,
且与Ａ中任一元素都有关系 。
[定义 ]上界与下界：
设 （ Ｐ,≤） 是半序集,Ａ?Ｐ,
若ａ ∈ Ｐ,对?ｂ ∈ Ａ,ｂ ≤ａ （ ａ ≤ｂ ）
称ａ为Ａ的上界 （ 下界 ） 。
注：
（ 1） 上例中,Ａ无最大元,但存在Ａ的上界 ｛ ａ,ｂ,ｃ ｝ 。
（ 2） Ф为Ａ的最小元,也是Ａ的下界
（ 3） 最大 （ 小 ） 元是Ａ的一个上 （ 下 ） 界
（ 4） 上 （ 下 ） 界可以不唯一,也可以不存在
[定义 ]上确界与下确界：
设 （ ｐ,? ） 是半序集,Ａ?Ｐ,
若ａ是Ａ的一个上界 （ 下界 ）,而?Ａ
的上界 （ 下界 ） ｂ,都有ａ? ｂ （ ｂ?
ａ ）,则称ａ是Ａ的上确界 （ 下确界 ） 。
注：
上确界：最小上界下确界：最大下界如果存在上 （ 下 ） 确界,则上 （ 下 ）
确界一定是唯一的例：
（ ｐ （ Ｂ ）,?） 中取Ａ ’ ＝ ｛ Ф,
｛ ｂ ｝,｛ ｃ ｝｝,则
｛ ｂ,ｃ ｝ 与 ｛ ａ,ｂ,ｃ ｝ 是Ａ ’ 的上界,｛ ｂ,ｃ ｝ 是Ａ ’ 的上确界 。
例：
ｐ＝ ｛ ａ,ｂ,ｃ,ｄ,ｅ ｝
Ａ＝ ｛ ａ,ｂ,ｃ ｝,（ ｐ,? ）
注：
存在上（下）界，并不一定存在上
（下）确界。
结论：（ 1）ｄ，ｅ是Ａ的上界
（ 2）ｄ与ｅ无法比大小，不存在上确界
（ 3）Ａ的下界不存在，不存在下确界
[引理 1]：
设 （ Ｐ,≤） 是半序集,Ａ是Ｐ的非空有限子集,则Ａ一定存在极大 （ 小 ） 元 。
证,若｜Ａ｜＝１,则 A中唯一元素既是极大元,也是极小元 。
假定｜Ａ｜＝ｎ时存在极大 （ 小 ） 元当｜Ａ｜＝ｎ＋１时,则将 A分成由ｎ个元素组成的子集 Ａ ’ 与元素ａ 。
由假定,Ａ ’ 存在极大元 ａ M,极小元ａ
m，
若ａ M≤ａ,则ａ为极大元,否则为ａ M，
因为若ａ M≤ａ,且存在 b≤Ａ ’,而
ａ ≤b,由传递性ａ M ≤ b,与ａ M为极大元
（ Ａ ’ ） 矛盾 。
同理,若ａ ≤ａ m,则 a为 极小元,否则为
ａ m。
[引理 2]：
设Ｍ是非空有限子集Ａ的极大元集合,
则Ｍ是Ａ的反链 。
反证：
若Ｍ不是反链,则?ａ,ｂ ∈ Ｍ （ ａ ≠
ｂ ）,（ ａ,ｂ ） ∈ Ｒ或 （ ｂ,ａ ） ∈ Ｒ,即
ａ? ｂ或ｂ? ａ,则ａ或ｂ不是极大元,矛盾 。
[定理 1]：
设 （ Ｐ,? ） 是有限的半序集,Ｐ 中最长链长度为ｎ,则 Ｐ 可以划分为ｎ个互不相交的反链 。
证,（ 1） ｎ＝１,Ｐ中任两个元素不相关,
Ｐ本身是反链 。
(2) 假设ｎ时定理成立,即当Ｐ中最长链长为ｎ时,可以划分为ｎ个互不相交的反链 。
(3)当Ｐ中最长链长为ｎ＋１,由引理 1，
极大元一定存在,设Ｍ是极大元集合,由引理 2,Ｍ是Ｐ的一个反链 。
如果去掉Ｍ,（ Ｐ－Ｍ,≤） 也是半序集,则Ｐ－Ｍ中最长链长为ｎ,由假设,Ｐ
－Ｍ可以划分为 ｎ个 互不相交的 反链,添上
Ｍ,可知Ｐ可划分为ｎ +1个互不相交的反链 。
例：Ａ＝ ｛ １,２,３,４,５,６,７,８,
９ ｝,半序集 （ Ａ,６ ）,最长链为４,Ｂ＝
｛ １,２,４,８ ｝
Ａ 1
Ａ 2＝ ｛ ２,３,５,７ ｝
Ａ 3＝ ｛ ４,６,９ ｝
Ａ 4＝ ｛ ８ ｝
Ｂ 4＝ ｛ ８,６,９,５,７ ｝
Ｂ 3＝ ｛ ４,３ ｝
Ｂ 2＝ ｛ ２ ｝
Ｂ 1＝ ｛ １ ｝
注：
反链的取法并不唯一,而最长链中的元素必然分别落在每个反链里 。
说明：
若 Ｐ r（ Ａ ） ＝ ｛ Ａ 1,Ａ 2,…,Ａ n｝,是 A
的一个分划,则可定义一个半序关系,当 j-
i=1时,取 a?Ai,b?Aj,使 (a,b)?R1,且 Ai,,Aj
中每个元素至少取到一次并对? a?A,(a,a)?R1
然后取 R = R1*（ 闭包 ）
这样 R是半序关系,并使每个 Ai是反链,
且最长链是 Ａ 1,Ａ 2,…,Ａ n中各取一个元素组成的 。
[定理 2]：每个Ａ的分划
ｐ r（ Ａ ） ＝ ｛ Ａ 1,Ａ 2,…,Ａ n｝,都可以找到一个半序关系Ｒ,使Ａ 1,Ａ 2,…,Ａ n都是 （ Ａ,Ｒ ） 的反链,而 （ Ａ,Ｒ ） 的最长链由Ａ 1,Ａ 2,…,Ａ n中各取一个元素组成 。
例：
取Ｒ 1＝ ｛（ １,２ ）,（ １,３ ）,
（ １,５ ）,（ １,７ ）,（ ２,６ ）,
（ ２,４ ）,（ ３,６ ）,（ ３,９ ）,
（ ４,８ ）,（ １,１ ）,（ ２,２ ）,
（ ３,３ ）,（ ４,４ ）,（ ５,５ ）,
（ ６,６ ）,（ ７,７ ）,（ ８,８ ）,
（ ９,９ ）｝
令Ｒ＝
1R,则 （Ａ，Ｒ）＝ （Ａ，１）。
但若取,
Ｒ 1＝ ｛（ １,２ ）,（ １,３ ）,（ １,５ ）,
（ １,７ ）,（ ２,４ ）,（ ２,６ ）,
（ ２,９ ）,（ ６,８ ）,（ ５,９ ）,
（ １,１ ）,（ ２,２ ）,（ ３,３ ）,
（ ４,４ ）,（ ５,５ ）,（ ６,６ ）,
（ ７,７ ）,（ ８,８ ）,（ ９,９ ）｝
令Ｒ＝
1
R,是无法得到 （Ａ，／）的，
可见，由互不相交的反链构造出来的半序集并不是唯一的。
[定理 3]：
设半序集 （ ｐ,? ） 包含ｍ ·ｎ＋
１个或以上个元素,则ｐ至少有一个链长? ｎ＋１ （ 或ｍ＋１ ） 或至少有一个反链长? ｍ＋１ （ 或ｎ＋１ ） 。
证：
若ｐ的最长链长? ｎ,反链长?
ｍ,由定理 1,ｐ可划分为不超过ｎ个反链,则ｐ至多有ｎ ·ｍ个元素,与ｐ
的元素个数矛盾 。
例１：
ａ ·ｂ＋１个自然数的集合ｐ
（（ ｐ,|） 是半序集 ）
或者有
（ ａ＋１ ） （ 或 （ ｂ＋１ ）） 个数一个被一个整除或者有
（ ｂ＋１ ） （ 或 （ ａ＋１ ）） 个数互素
[定义 ]良序集：
设 （ Ａ,Ｒ ） 是半序集,若Ａ的非空子集都存在最小元,则称Ｒ是良序关系,（ Ａ,
Ｒ ） 为良序集 。
注,（ 1） 良序集是全序集
（ 2） 全序集未必是良序的,如：
实数全体,任两个实数都能比大小,
但子集 ｛ 1/n｝ 的最小元找不到 。
但,有限的全序集自然是良序的 。
§ １二元关系
[定义 ]相关,按照某种规则,确定二个对象或多个对象之间有关系,称这二个对象或多个对象是相关的 。
注意,相关性与指定的规则有关 。
(1)扑克牌中的方块ｋ与梅花ｋ
同花关系：不相关同点关系：相关
(2)父子二人同辈关系：不相关注：
二元关系：二个对象之间相关的关系多元关系：多个对象之间的关系多元关系常化成二元关系来研究无序的二元关系：方块ｋ与梅花ｋ，谁在前，谁在后都还是同点的有序的二元关系：父子关系，不能交换父与子的次序又如,
（ 1） ａ＋ｂ＝偶数,ａ与ｂ是无序的用 ［ ａ,ｂ ］ 表示无序对
（ 2） ａ? ｂ,ａ与ｂ是有序的二元关系,叫作ａ相关于ｂ,记成 ａｒｂ,用 （ ａ,ｂ ） 表示有序对
（ 3） 无序的二元关系可用有序的二元关系表示即 （ ａ,ｂ ） 与 （ ｂ,ａ ） 都属于这种二元关系定义 2,二元关系 ----按照某种规定,定义了一个有序对 （ ａ,ｂ ） 的集合Ｒ,其中ａ ∈ Ａ,ｂ ∈
Ｂ,称Ｒ为Ａ到Ｂ的一个二元关系 。
注意,二元关系是指满足某规律的有序对的全体 。
Ｒ＝ ｛（ ａ,ｂ ） ｜ａ ∈ Ａ,ｂ ∈ Ｂ,ａｒｂ ｝
其中ａｒｂ读作ａ相关于ｂ 。
定义 3,当Ａ＝Ｂ时，Ｒ是Ａ到Ａ的二元关系,
称为Ａ上的二元关系。
例：Ｒ＝ ｛（ ａ,ｂ ） ｜ ａ /ｂ,ａ,ｂ ∈ Ｎ ｝
是自然数集Ｎ上的二元关系定义,二元关系的表示：因为二元关系本身也是集合,也可用穷举法,描述法来表示,还可用表格,
图示,矩阵法表示 。
例如：
Ａ＝ ｛ 张三,李四,王五,赵六 ｝
Ｂ＝ ｛ １００米,跳高,铅球,足球,跨栏 ｝
Ｒ＝ ｛（ 张三,铅球 ）,（ 张三,足球 ）,
（ 李四,１００米 ）,（ 李四,跳高 ）,
（ 王五,跨栏 ）,（ 赵六,１００米 ）｝
是运动会的报名表 。
100 米 跳高 铅球 足球 跨栏张三 √ √
李四 √ √
王五 √
赵六 √
Ａ＝ ｛ ａ,ｂ,ｃ,ｄ ｝
Ｂ＝ ｛ １,２,３,４,５ ｝
表格表示法：用表格表示一目了然
a
b
c
d
1
2
3
4
5
图示法：关系图，直观相关矩阵法表示：
把Ａ,Ｂ集合内元素排好序
Ｒ＝ )(
00001
10000
00011
01100
ij
a
d
c
b
a
１ ２ ３ ４
由于直交积Ａ × Ｂ＝ ｛（ ａ,ｂ ） ｜ａ ∈ Ａ,ｂ ∈
Ｂ ｝,二元关系Ｒ＝ ｛（ ａ,ｂ ） ｜ａ ∈ Ａ,ｂ ∈ Ｂ,
ａｒｂ ｝,可见二元关系是直交积Ａ × Ｂ的子集 。 若Ｒ
＝Ａ × Ｂ,则相关矩阵元素全为１,
Ｒ＝
111
111
111
注：
（ 1） 若Ｒ＝Ａ × B,称此二元关系为普遍关系
（ 2） 设Ａ＝ ｛ ａ 1,ａ 2,…,ａ n｝
Ｒ＝ ｛（ ａ i,ａ j） ｜ａ i,ａ j∈ Ａ ｝
若Ｒ＝ ｛（ ａ i,ａ i） ｜ａ i∈ Ａ ｝
称Ｒ为恒等关系,用Ｉ A表示,是单位矩阵
A =
1000
0100
0010
0001
把二元关系看成函数关系
Ｒ＝ ｛（ ａ,ｂ ） ｜ａｒｂ,ａ ∈ Ａ,ｂ ∈ Ｂ ｝
Ａ称为Ｒ的定义域,记Ａ＝ｄｏｍＲ
Ｂ称为Ｒ的值域,记Ｂ＝Ｒａｎｇｅ Ｒ
当定义域与值域交换得
Ｒ C＝ ｛（ ｂ,ａ ） ｜ （ ａ,ｂ ） ∈ Ｒ,ａ ∈ Ａ,
ｂ ∈ Ｂ ｝,称为Ｒ的逆关系 。
§ ２ 二元关系的运算二元关系是集合,集合存在并,
交,差,非和对称差的运算 。
故二元关系也存在这样的运算 。
设Ｒ 1和Ｒ 2是Ａ到Ｂ的二元关系,则
（ 1） Ｒ 1∪ Ｒ 2＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ 1
或 （ ａ,ｂ ） ∈ Ｒ 2｝
（ 2） Ｒ 1∩ Ｒ 2＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ 1
且 （ ａ,ｂ ） ∈ Ｒ 2｝
（ 3） Ｒ 1-Ｒ 2＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ 1
但 （ ａ,ｂ ）? Ｒ 2｝
（ 4 ） 1R ＝ ｛ ( a,b) ｜ ( a,b) ∈ A*B,但 （ａ，ｂ）? Ｒ 1 ｝
（ 5） Ｒ 1?Ｒ 2＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ 1∪ Ｒ 2
但 （ ａ,ｂ ）?Ｒ 1∩Ｒ 2｝
例１：Ａ＝ ｛ １,２,３,４ ｝, Ｒ＝ ｛ （ａ，ｂ）｜ａ，ｂ∈Ａ,2
ba?
Ｓ＝ ｛ （ａ，ｂ）｜ａ，ｂ∈Ａ，
3
ba?
∈Ｉ,a － b ＞０｝
求：Ｒ∪Ｓ，Ｒ∩Ｓ，
R
，Ｒ－Ｓ，Ｓ－Ｒ，Ｓ
Ｒ＝ ｛（ １,１ ）,（ ２,２ ）,（ ３,３ ）,
（ ４,４ ）,（ １,３ ）,（ ３,１ ）,
（ ２,４ ）,（ ４,２ ）｝
Ｓ＝ ｛（ ４,１ ）｝
Ｒ ∪ Ｓ＝ ｛（ １,１ ）,（ ２,２ ）,（ ３,３ ）,
（ ４,４ ）,（ １,３ ）,（ ３,１ ）,（ ２,４ ）,
（ ４,２ ）,（ ４,１ ）｝
注：
二元关系的矩阵运算：
相关矩阵可表示二元关系,可用矩阵的逻辑运算来研究二元关系的运算 。
R ＝ ｛ （１，２）,（２，１）,（１，４）,（４，１），
（２，３）,（３，２）,（３，４）,（４，３）｝
Ｒ－Ｓ＝Ｒ，Ｓ－Ｒ＝Ｓ，Ｓ?
R∩Ｓ＝ Φ
设,Ａ＝｛ａ 1，ａ 2,…，ａ n
Ｂ＝｛ｂ 1，ｂ 2,…，ｂ m
Ｒ 1＝（ｃ ij）
Ｒ 2＝（ｄ ij）
其中,
逻辑加 (∨),０ ∨ ０＝０,０ ∨ １＝１,
１ ∨ ０＝１,１ ∨
逻辑乘 (∧),０ ∧ ０＝０,０ ∧ １＝０,
１ ∧ ０＝０,１ ∧ １＝１
则,Ｒ
1
∪Ｒ
2
＝ （ c
ij
∨ｄ
ij
Ｒ
1
∩Ｒ
2
＝ （ｃ
ij
∧ｄ
ij
）
Ｒ
1
－Ｒ
2
＝ （ｃ
ij
∧ ijd
1R ＝ （ ij
C
）
逻辑非 （－）,0 ＝１， 1 ＝０
Ｒ＝
1010
0101
1010
0101
， Ｓ＝
0001
0000
0000
0000
则用矩阵的逻辑运算,
Ｒ∪Ｓ＝
1011
0101
1010
0101
=S? R
Ｒ∩Ｓ ＝
0000
0000
0000
0000
＝
0101
1010
0101
1010
R,
Ｒ－Ｓ＝Ｒ，
２,
[定义 ]：
设Ｒ 1为Ａ到Ｂ的二元关系,Ｒ 2为Ｂ到Ｃ的二元关系,
Ｒ 1＝ ｛（ ａ,ｂ ） ｜ａｒ 1ｂ,ａ ∈ Ａ,ｂ ∈ Ｂ ｝
Ｒ 2＝ ｛（ ｂ,ｃ ） ｜ｂｒ 2ｃ,ｂ ∈ Ｂ,ｃ ∈ Ｃ ｝
则Ｒ 1·Ｒ 2是由Ａ到Ｃ的二元关系,称为Ｒ 1,Ｒ 2的复合关系
Ｒ 3＝ ｛（ ａ,ｃ ） ｜ （ ａ,ｂ ） ∈ Ｒ 1，
且 （ ｂ,ｃ ） ∈ Ｒ 2 ｝
记 Ｒ 3＝Ｒ 1·Ｒ 2。
例２：
Ｒ是父子关系,则Ｒ ２ ＝Ｒ ·Ｒ是祖孙关系 。
例３：
Ａ＝ ｛
4321
aaaa
李兰，陈平，王兵，张华
Ｂ＝ ｛
4321
bbbb
遥感，自动化，硬件，软件
C ＝ {
4321
cccc
离散数学，操作系统，电子线路，工程制图 ｝
则：Ｒ 1＝ ｛（ ａ 1,ｂ 1）,（ ａ 1,ｂ 3）,
（ ａ 2,ｂ 2）,（ ａ 2,ｂ 4）,
（ ａ 3,ｂ 3）,（ ａ 3,ｂ 4）,
（ ａ 4,ｂ 1）,（ ａ 4,ｂ 4） ｝
是选双学位专业的 二元关系 。
Ｒ 2＝ ｛（ ｂ 1,ｃ 3）,（ ｂ 1,ｃ 4）,（ ｂ 2,ｃ 2）,
（ ｂ 2,ｃ 3）,（ ｂ 2,ｃ 4）,（ ｂ 3,ｃ 1）,
（ ｂ 3,ｃ 2）,（ ｂ 4,ｃ 2）,（ ｂ 4,ｃ 4）｝
是各专业本学期必修课的二元关系 。
Ｒ 3＝Ｒ 1·Ｒ 2＝ ｛（ ａ 1,ｃ 1）,（ ａ 1,ｃ 2）,
（ ａ 1,ｃ 3）,（ ａ 1,ｃ 4）,
（ ａ 2,ｃ 2）,（ ａ 2,ｃ 3）,
（ ａ 2,ｃ 4）,（ ａ 3,ｃ 1）,
（ ａ 3,ｃ 2）,（ ａ 3,ｃ 4）,
（ ａ 4,ｃ 2）,（ ａ 4,ｃ 3）,
（ ａ 4,ｃ 4）｝
是选双学位学生本学期必修课的二元关系
Ａ＝ )(
ij
a
nm?
，
Ｂ＝ )( jkb
Ln?
，
则,Ｃ＝Ａ·Ｂ＝ )(
ik
c
Lm?
ｃ ik ＝ jkij
n
j
baV?
1
普通的矩阵乘法：
而二元关系的复合的矩阵布尔型乘法：
而 ｃ
ik
＝?
n
j
jkij ba
1
对例 3
Ｒ
1
＝
1001
1100
1010
0101
,Ｒ
2
=
1010
0011
1110
1100
Ｒ
3
＝Ｒ
1
·Ｒ
2
＝
1110
1011
1110
1111
在行处标上姓名,列处标上课程,就知谁该必修哪些课了 。
若Ｒ是Ａ上二元关系,
Ｒ＝ ｛（ ａ,ｂ ） ｜ａｒｂ,ａ ∈ Ａ,ｂ ∈ Ａ ｝
若设,
Ｒ 1＝Ｒ
(1)Ｒ 2＝Ｒ ·Ｒ＝Ｒ 2＝ ｛（ ａ,ｃ ） ｜ （ ａ,ｂ ）,
（ ｂ,ｃ ） ∈ Ｒ ｝
(2)设Ｒ n＝Ｒ ·Ｒ …Ｒ＝Ｒ n已定义,
Ｒ n+1＝Ｒ n·Ｒ＝Ｒ n·Ｒ＝Ｒ n+1
= {（ ａ,ｃ ） ｜ （ ａ,ｂ ） ∈ Ｒ ｎ,
（ ｂ,ｃ ） ∈ Ｒ ｝
例４：
Ｒ＝ ｛（ ０,０ ）,（ ０,３ ）,
（ ２,３ ）,（ ３,２ ）,
（ ２,１ ）,（ ２,０ ） ｝
是有限集 ｛ ０,１,２,３ ｝ 上的二元关系
Ｒ的关系图：
Ｒ 2＝ ｛（ ０,０ ）,（ ０,２ ）,（ ０,３ ）,
（ ２,０ ）,（ ２,２ ）,（ ２,３ ）,
(３,０ ）,（ ３,１ ）,（ ３,３ ） ｝
Ｒ 2的关系图中不存在 （３，２），
（２，１），故Ｒ?Ｒ 2
Ｒ n的关系图的构造：
可由Ｒ的关系图来构造，从Ｒ的每个结点 ai出发，数 n条边。凡通过数 n条边能到达的结点 aj，则有（ ai,aj） ∈ Ｒ n。关系图中从ａ i出发到ａ j的边是存在的。
这样处理容易出错，用相关矩阵的布尔型乘法来做，简单，又不容易错，还适宜于计算机处理。
Ｒ 2 ＝Ｒ·Ｒ＝
1011
1101
0000
1101
0100
1011
0000
1001
0100
1011
0000
1001
0100
1011
0000
1001
R
二元关系的逆关系：运算设Ｒ,Ｓ是Ａ到Ｂ的二元关系,Ｔ是Ｂ到Ｃ的二元关系,Ｐ是Ｃ到Ｄ的二元关系 。 则：
(1) （Ｒ∪Ｓ）
c
＝Ｒ
c
∪Ｓ
c
(2) （Ｒ∩Ｓ）
c
＝Ｒ
c
∩Ｓ
c
(3) )( R
C
＝
)(
c
R
(4) （Ｒ－Ｓ）
C
＝Ｒ
C
－Ｓ
C
(5) （Ａ×Ｂ）
C
(6) R ＝
(7) （Ｓ·Ｔ）
C
＝Ｔ
C
·Ｓ
C
( 8 ) （Ｒ·Ｔ）·Ｐ＝Ｒ·
( 9 )
且 （Ｒ∩Ｓ）·Ｔ?
( 1 0 ) Ｒ
Ｓ? Ｒ
C?
Ｓ
C
证明其中,
(1)任意 （ ｘ,ｙ ） ∈ （ Ｒ ∪ Ｓ ） C
（ ｙ,ｘ ） ∈ （ Ｒ ∪ Ｓ ）
（ ｙ,ｘ ） ∈ Ｒ 或 （ ｙ,ｘ ） ∈
（ ｘ,ｙ ） ∈ Ｒ C 或 （ ｘ,ｙ ） ∈ Ｓ C
（ ｘ,ｙ ） ∈ Ｒ C ∪ Ｓ C
( 4 ) （Ｒ－Ｓ）
C ＝ （Ｒ∩ S ） C
)ii
R
C S? C )iii
R
C? S C
= R
c - s c
(7) （ Ｓ ·Ｔ ） C＝Ｔ C·Ｓ C
证：
对?（ ｘ,ｙ ） ∈ （ Ｓ ·Ｔ ） C,有
（ ｙ,ｘ ） ∈ Ｓ ·
ｚ ∈ Ｂ,使 （ ｙ,ｚ ） ∈ Ｓ,
（ ｚ,ｘ ） ∈
即,（ ｚ,ｙ ） ∈ Ｓ C，
（ ｘ,ｚ ） ∈ Ｔ C
（ ｘ,ｙ ） ∈ Ｔ C·Ｓ C
证明：等式不成立若?ａ ∈ Ａ,ｂ 1,ｂ 2∈ Ｂ,ｃ ∈ Ｃ,且
（ ａ,ｂ 1） ∈ Ｒ,（ ａ,ｂ 2） ∈ Ｓ,
（ ａ,ｂ 1）?Ｓ,（ ａ,ｂ 2）?Ｒ,
（ ｂ 1,ｃ ） ∈ Ｔ,（ ｂ 2,ｃ ） ∈ Ｔ,
显然 （ ａ ｃ ） ∈ Ｒ ·Ｔ ∩ Ｓ ·Ｔ
但 （ ａ,ｃ ）? （ Ｒ ∩ Ｓ ） ·Ｔ
(10) 证：
（ x,y) ∈ Rc? (y,x) ∈ R
(y,x) ∈ s? (x,y) ∈ Sc注：
Ｒ ·Ｔ ∩ Ｓ ·Ｔ?（Ｒ ∩ Ｓ） ·Ｔ不一定成立，
由于 （Ｒ ∩ Ｓ） ·Ｔ?Ｒ ·Ｔ ∩ Ｓ ·Ｔ
若上式成立，
则（Ｒ ∩ Ｓ） ·Ｔ =Ｒ ·Ｔ ∩ Ｓ ·Ｔ
§ ３
设Ｒ是Ａ上的二元关系,Ｒ =(rij)n*n
(1)自反性,
对?ａ ∈ Ａ，（ａ，ａ） ∈ Ｒ，则 Ｒ称为自反的二元关系。
显然,rii＝ 1（ ｉ＝１,２,…,n)
反自反性,
对?ａ ∈ Ａ,（ ａ,ａ ）?Ｒ,则Ｒ称为反自反的二元关系 。
即 rii＝０ （ ｉ＝１,２,…,n)
注,
自反和反自反性互斥,但不互补 。
如,rij中既有 0又有 1,则 R既不是自反的也不是反自反的 。
(2）
若ａ ≠ ｂ,a（ ａ,ｂ ） ∈ Ｒ,必有 （ ｂ,ａ ）
∈ Ｒ,称Ｒ为对称的二元关系即Ｒ的相关矩阵为对称阵,ａ ij＝ａ ji
反对称性：
若ａ ≠ ｂ,（ ａ,ｂ ） ∈ Ｒ,
则 （ ｂ,ａ ）?Ｒ,称Ｒ为反对称的二元关系 。
注,
（ 1
rij∧ rji ＝０（ｉ ≠
（ 2）若 rij＝１，则 rji=０，但 rij＝０时，
不要求 rji＝１，即 rij＝ rji＝０是允许的。
(3) 对称性与反对称性既不互斥，又不互补例：
恒等关系,既是对称的，又是反对称的；
而相关矩阵是
1001
0100
0100
1001
的二元关系，
是既不对称，又不是反对称的。
３）传递性,
若 （ａ，ｂ）,（ｂ，ｃ）∈Ｒ，
则 （ a,ｃ）∈Ｒ，称Ｒ为传递的二元关系。
即,（ rr
jkij
）∨ r
ik
注,rij,rjk中有一个不是１,
则 =1,rik就可以任意 。
即若 (ａ,ｂ ),(ｃ,ｄ )中有 1 个不属于 R，
则讨论 （ a,c)是否属于 R,无意义 。
即没有传递的条件,也不需传递的结果 。 如,
Ａ＝ ｛ a,b,c,d｝,Ｒ＝ ｛（ ａ,ｂ ）,（ ｃ,ｄ ）｝
rr jkij ^
二元关系的性质对应于关系图,有：
（ 1） 自反性：每个顶点都有自回路,
（ 2） 反 自反性：每个顶点都没有自回路；
（ 3） 对称性：任二个顶点间或没有边,或有二条相对而指的有向边；
（ 4） 反对称性：任二个顶点至多只有一条有向边；
（ 5） 传递性：若ｘ到ｙ有边,ｙ到ｚ有边,
则ｘ到ｚ必有边 。
注,由对称性与传递性可推出自反性 。
理由,若 （ ａ,ｂ ） ∈ Ｒ,由对称性,
有 （ ｂ,ａ ） ∈ Ｒ,由传递性有 （ ａ,ａ ） ∈ Ｒ 。
如：
R的相关矩阵是 全 0矩阵,是对称的,
传递的,反自反的,但不是自反的 。
错误原因：不是?ａ,
ｂ,使 （ ａ,ｂ ） ∈ Ｒ 。
例１：Ｒ 1＝ ｛（ ａ,ｂ ） ｜ａ ≤ｂ,ａ,ｂ ∈ Ｎ ｝
自反的,rii=1;
不对称的,(1,2) ∈ R1,而 (2,1)? R1
反对称的,传递的 。
注：将 ≤改为＜,则无自反性,且是反自反的 。
例２：Ｒ 2＝ ｛（ ａ,ｂ ） ｜ａ｜ｂ,ａ,ｂ ∈ Ｎ ｝
自反的,不对称的,反对称的,传递的 。
例３：Ｒ 3＝ ｛（ Ｓ 1,Ｓ 2） ｜Ｓ 1?Ｓ 2,Ｓ 1，
Ｓ 2∈ Ｐ （ Ｓ ）｝ 其中Ｐ （ Ｓ ） 是Ｓ的幂集 。
自反的,不对称的,反对称的,传递的 。
注：若?改为?,则无自反性 。
例４：
Ｒ 4＝ ｛（ ａ,ｂ ） ｜ａ＋ｂ＝偶数,
ａ,ｂ ∈ Ｎ ｝
自反的,对称的,传递的,
因：ａ＋ｂ＝偶,ｂ＋ｃ＝偶,
则：０＜ａ＋ｃ＝ （ ａ＋ｂ ） ＋ （ ｂ＋
ｃ ） －２ｂ＝偶数与偶数之差＝偶数 。
例５：
Ｒ 5＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ＝１
（ 互素 ）,ａ,ｂ ∈ Ｎ ｝
对称的,但不是自反的,也无传递性 。
[定理 1],设Ｒ是Ａ上的二元关系,则Ｒ ∪ Ｉ A一定是自反的,而且是包含Ｒ,具有自反性的最小关系 。
（ 其中Ｉ A是Ａ上恒等关系 ） 。
[定义 1]：称Ｒ ∪ Ｉ A是Ｒ的自反闭包,记为 r(R） 。
证明,对?ｘ ∈ Ａ,（ ｘ,ｘ ） ∈ Ｉ A?Ｒ ∪ Ｉ A，
且Ｒ?Ｒ ∪ Ｉ A。
若Ｒ ’ 为包含Ｒ且具有自反性,则Ｉ A?
Ｒ ’,Ｒ?Ｒ ’,Ｉ A∪ Ｒ?Ｒ ’ 。 即Ｉ A∪ Ｒ为最小 。
[推论 1],当且仅当Ｒ是自反闭包,Ｒ具有自反性 。
证明：
（ 1） Ｒ是自反闭包,R=Ｉ A∪ Ｒ?Ｉ A?Ｒ ;
（ 2） Ｒ具有自反性,Ｉ A?Ｒ,Ｒ ∪ Ｉ A＝Ｒ；
[定理 2]：设Ｒ是Ａ上的二元关系,则Ｒ ∪ Ｒ c是对称的,包含Ｒ的最小关系,
（ 其中Ｒ C是Ｒ的逆关系 ） 。
[定义 2],称Ｒ ∪ Ｒ C是Ｒ的对称闭包,记为 s(R)。
证明,若 （ ａ,ｂ ） ∈ Ｒ ∪ Ｒ C,则
（ ａ,ｂ ） ∈ Ｒ 或 （ ａ,ｂ ） ∈ Ｒ C，
（ ｂ,ａ ） ∈ Ｒ C 或 （ ｂ,ａ ） ∈ Ｒ
故 （ ｂ,ａ ） ∈ Ｒ ∪ Ｒ C（ 对称性 ）,
若Ｒ ’ 为包含Ｒ,对称的二元关系,
则对?（ ａ,ｂ ） ∈ Ｒ ∪ Ｒ C，
若 （ ａ,ｂ ） ∈ Ｒ?（ ａ,ｂ ） ∈ Ｒ ’ ；
若 （ ａ,ｂ ） ∈ Ｒ C?（ ｂ,ａ ） ∈ Ｒ,
（ ｂ,ａ ） ∈ Ｒ ’
又Ｒ ’ 具有对称性,（ ａ,ｂ ） ∈ Ｒ ’,
故Ｒ ∪ Ｒ C?Ｒ ’ 。
[推论 2]：当且仅当Ｒ是对称闭包时,Ｒ具有对称性 。
证明,（ 1） Ｒ具有对称性,
若 （ ａ,ｂ ） ∈ Ｒ,则 （ ｂ,ａ ） ∈ Ｒ,
又 （ ｂ,ａ ） ∈ Ｒ c
即?（ ｂ,ａ ） ∈ Ｒ c,（ ａ,ｂ ） ∈ Ｒ
（ ｂ,ａ ） ∈ Ｒ
Ｒ C? Ｒ?Ｒ ∪ Ｒ C＝Ｒ；
(2） Ｒ是对称闭包时,Ｒ＝Ｒ ∪ Ｒ C?Ｒ具有对称性 。
[定义 3],传递扩张设Ｒ＝ ｛（ ａ,ｂ ） ｜ａｒｂ,ａ,ｂ ∈ Ａ ｝,
则称Ｒ 1＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ,或?Ｃ
∈ Ａ,使 （ ａ,ｃ ）,（ ｃ,ｂ ） ∈ Ｒ ｝ 为Ｒ的传递扩张 。
(1)Ｒ?Ｒ 1
(2)Ｒ 1不一定是传递的,如：
Ｒ＝ ｛（ ａ,ｂ ）,（ ｂ,ｃ ）,（ ｃ,ｄ ）｝
Ｒ 1＝ ｛（ ａ,ｂ ）,（ ｂ,ｃ ）,（ ｃ,ｄ ）,
（ ａ,ｃ ）,（ ｂ,ｄ ）｝
由 （ ａ,ｃ ）,（ ｃ,ｄ ）,（ ａ,ｂ ）,
（ ｂ,ｄ ） 又产生了新的传递条件,而 （ ａ,ｄ ）
Ｒ 1,Ｒ 1不是传递的 。
(3) 当且仅当Ｒ是传递的,Ｒ＝Ｒ 1。
证明：,?”,Ｒ是传递的,（ ＲＲ 1）
对?（ ａ,ｂ ） ∈ Ｒ 1,有
（ ａ,ｂ ） ∈ Ｒ 或? c∈ Ａ,
使 （ ａ,ｃ ）,（ ｃ,ｂ ） ∈ Ｒ,
由Ｒ的传递性,（ ａ,ｂ ） ∈ Ｒ,
故Ｒ 1Ｒ,得Ｒ＝Ｒ 1。
,?”,Ｒ＝Ｒ 1
若 （ ａ,ｃ ） ∈ Ｒ,（ ｃ,ｂ ） ∈ Ｒ,
则 （ ａ,ｂ ） ∈ Ｒ 1＝Ｒ,Ｒ是传递的 。
注,（ 1） 若Ｒ 1不是传递的,可扩张到Ｒ 2，
Ｒ 3,…Ｒ k ；
（ 2） 若Ｒ k是传递的,则Ｒ k+1＝Ｒ k。
[定义 3]：
设Ｒ 0＝Ｒ,Ｒ k+1是Ｒ k的传递扩张 （ ｋ＝０,１,
２,…）,则称Ｒ *＝Ｒ 0∪ Ｒ 1∪ Ｒ 2∪ …∪ Ｒ k∪ …为Ｒ
的传递闭包,也记作 t(R)。
[定理 3] 传递闭包Ｒ *＝Ｒ ∪ Ｒ 2∪ …∪ Ｒ k∪ …
证明,Ｒ 2＝Ｒ ·Ｒ＝｛（ａ，ｂ）｜
（ａ，ｃ），（ｃ，ｂ） ∈
Ｒ 1＝｛（ａ，ｂ）｜（ａ，ｂ） ∈ Ｒ
或（ａ，ｃ）,（ｃ，ｂ） ∈ Ｒ｝
＝Ｒ ∪ Ｒ 2
Ｒ 2＝｛（ａ，ｂ）｜（ａ，ｂ） ∈ Ｒ 1，
或 （ａ，ｃ），（ｃ，ｂ） ∈ Ｒ 1｝
（ 1） 若 （ ａ,ｃ ）,（ ｃ,ｂ ） ∈ Ｒ,
则 （ ａ,ｂ ） ∈ Ｒ ·Ｒ,
（ 2） 若其一,如 (ａ,ｃ ） ∈ Ｒ
另一,如 (c,ｂ ） ∈ Ｒ ·Ｒ
则 （ ａ,ｂ ） ∈ Ｒ ·Ｒ ·Ｒ ∈ Ｒ 3，
（ 3） 若 （ ａ,ｃ ）,（ ｃ,ｂ ） ∈ Ｒ ·Ｒ
则 （ ａ,ｂ ） ∈ Ｒ ·Ｒ ·Ｒ ·Ｒ ∈ Ｒ 4 ＝Ｒ 22，
即Ｒ 2＝Ｒ ∪ Ｒ 2∪ Ｒ 3∪ Ｒ 4
假设Ｒ k＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ,或 …，
或 （ ａ,ｂ ） ∈ Ｒ 2k ｝
则 Ｒ k+1＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ k，
或 （ ａ,ｃ ）,（ ｃ ｂ ） ∈ Ｒ k｝
当 （ ａ,ｃ ） ∈ Ｒ i,（ ｃ,ｂ ） ∈ Ｒ j，
（ ｉ,ｊ＝１,２,…,2k）
（ ｉ＋ｊ＝２,３,…,２ k+1）
有Ｒ k+1＝ ｛（ ａ,ｂ ） ｜ （ ａ,ｂ ） ∈ Ｒ,或 … 或
（ ａ,ｂ ） ∈ Ｒ 2k+1 ｝ ＝Ｒ ∪ Ｒ 1 ∪ Ｒ 2∪ Ｒ 3∪ …∪ Ｒ 2k+1
故，Ｒ的闭包
*
R ＝Ｒ∪Ｒ
1
∪Ｒ
2
∪?∪Ｒ
k
∪?
＝?
0k
k
R
＝Ｒ∪Ｒ
2
∪Ｒ
3
∪?∪
k
R
2
∪?
＝?
1k
k
R
[定理 4],传递闭包 Ｒ *一定是传递的 。
证明：设 （ ａ,ｂ ） （ ｂ,ｃ ） ∈ Ｒ *,则
ｉ,ｊ,使 （ ａ,ｂ ） ∈ Ｒ i，
（ ｃ,ｂ ） ∈ Ｒ j，
故 （ ａ,b） ∈ Ｒ (i+j)?Ｒ *
传递扩张的实际意义：
举 例,
Ｒ＝ ｛（ ａ,ｂ ） ｜ａ与ｂ是父子关系 ｝
Ｒ ·Ｒ＝ ｛（ ａ,ｂ ） ｜ａ与ｂ是祖孙关系 ｝
Ｒ １ ＝ ｛（ ａ,ｂ ） ｜ａ与ｂ是三代以内男性直系亲属 ｝
…
证明：
对?（ ｘ,ｙ ） ∈ Ｒ *,?ｋ,使 （ ｘ,ｙ ）
∈ Ｒ k,表明在Ａ中存在不同元素ａ 1,ａ 2,…，
ａ k-1,使 （ ｘ,ａ 1）,（ ａ 1,ａ 2）,（ ａ 2，
ａ 3）,…,（ ａ k-1,ｙ ） ∈ Ｒ 。
若ｋ＞ｎ,由鸽洞原理,则ａ 1,ａ 2,…，
ａ k-1,ｙ中至少有两个相同,不妨设ａ i＝ｙ,
（ ｉ? ｋ－１ ） 。
[定理 5]：
设｜Ａ｜＝ｎ,Ｒ是Ａ上二元关系,
则存在正整数ｋ,ｋ? ｎ,使 Ｒ * ＝Ｒ
∪ Ｒ 2∪ …∪ Ｒ k。
于是（ｘ，ａ 1）,…（ａ i，ａ i-1 ） ∈ Ｒ,
（ａ i-1,ｙ） ∈ Ｒ，
故（ｘ，ｙ） ∈ Ｒ i，
即 若ｋ＞ｎ，必存在比ｋ的正整数ｉ，
使（ｘ，ｙ） ∈ Ｒ i。
注：
定理说明,可用Ｒ ∪ Ｒ 2∪ …∪ Ｒ n来求 Ｒ * 。
例６,
设Ａ＝ ｛ １,２,３ ｝,
Ｒ＝ ｛（ １,１ ）,（ １,２ ）,(２,３ ）｝
求 Ｒ * 。
解,Ｒ＝
000
100
011
,Ｒ
2
＝
000
000
111
＝Ｒ
3
故
R
＝Ｒ∪Ｒ
2
∪Ｒ
3
＝
000
100
111
R
＝ ｛ （１，１）,（１，２）,（１，３）,（２，３）｝
设Ｒ是ｎ个元素集合上的二元关系
(1)
(2)ｉ ← １；
(3)ｆｏｒ ｊ＝１ ｔｏ ｎ
iｆ ａ j,i＝１ ｔｈｅｎ
ｆｏｒ ｋ＝１ ｔｏ ｎ ｄｏ
ａ j,k← ａ j,k∨ ａ i,k
(4)ｉ =ｉ＋１；
(5) iｆ ｉ ≤ｎ,ｔｈｅｎ go (3)
ｅｌｓｅ ｓｔｏｐ
注,当｜Ａ｜＝ｎ较大时,用定理 5计算 Ｒ *
工作量非常大 。
注,（ 1） 结果 (aij)nxn是Ｒ *的相关矩阵 。
（ 2） 算法的复杂度为ｎ 3。
例 6：重新计算Ｒ *
例７：Ａ＝ ｛ ａ,ｂ,ｃ,ｄ ｝
Ｒ＝ ｛（ ａ,ｂ ）,（ ｂ,ｃ ）,
（ ｃ,ｄ ） ｝
计算Ｒ *。
0000
1000
0100
0010
R
(1)i=1 由于 aj1=0(j=1,2,3,4) 不改动
(2)i=2 j=1,aji=1? a13=1
(3)i=3
0000
1000
0100
0110
j=1,a13=1? a14=1
j=2,a23=1? a24=1
即
Ｒ * ＝｛（ａ，ｂ），（ａ，ｃ），
（ａ，ｄ），（ｂ，ｃ），
（ｂ，ｄ），（ｃ，ｄ）｝
§ ４ 等价关系
４,１ 等价关系
[定义 1] 等价关系,
Ａ上的二元关系Ｒ,如果Ｒ是
(1） 自反的
(2） 对称的
(3) 传递的称Ｒ为等价关系 。
（ ａ,ｂ ） ∈ Ｒ,称ａ与ｂ等价,记作ａ～ｂ 。
[定义 4.2] 等价类,把Ａ中的等价元素归为一类,
称为等价类 。
注：
等价关系Ｒ把Ａ的元素分为若干类,各类之间没有公共元素 。 确定的Ｒ是对集合Ａ进行的分划 。
[定义 4.3]集合的分划：把集合Ａ分为若干子集
Ａ 1,Ａ 2,…,满足：
（ 1） 当ｉ ≠ ｊ时Ａ i∩ Ａ j＝?
（ 2）?ａ ∈ Ａ,?ｉ,
使ａ ∈ Ａ i（ ｉ＝１,２,…）
则集合 Pr（ Ａ ） ＝ ｛ Ａ 1,Ａ 2,…,Ａ n,…｝ 称为
Ａ的一个分划 。
注：
（１）
P （Ａ）? ｐ （Ａ） （Ａ的幂集）
（２）当且仅当Ａ＝? 时,?P （Ａ）＝ｐ （Ａ）＝ ｛? ｝
（３）Ａ非空时?P （Ａ）? ｐ （Ａ）
[定理 1]：
Ａ在等价关系Ｒ下的等价类正是Ａ的一种分划,Ａ的任一种分划,也必有Ａ上的一个等价关系Ｒ与之对应 。
证明：
Ｒ是等价关系,?ａ ∈ Ａ,由Ｒ的自反性,
（ ａ,ａ ） ∈ Ｒ,即ａ与ａ属于同一等价类,
也即?ｉ,ａ ∈ Ａ i
若ｉ ≠ｊ,Ａ i≠Ａ j,而Ａ i∩Ａ j ≠?,则?ｃ
∈ Ａ i∩Ａ j,ｃ ∈ Ａ i,且ｃ ∈ Ａ j,
对?ａ ∈ Ａ i,ａ～ｃ,ｃ ∈ Ａ j
对?ｂ ∈ Ａ j,ｂ～ｃ,即ｃ～ｂ (对称性 )
由Ｒ传递性,ａ～ｂ
由ａ,ｂ的任意性,故Ａ i＝Ａ j
若Ａ已进行了分划,则构造二元关系Ｒ 。
(1)?ａ ∈ Ａ,使 （ ａ,ａ ） ∈ Ｒ,
(2)分别对每一等价类内所有两个不同元素ａ,
ｂ,（ ａ,ｂ ） ∈ Ｒ,使 （ ｂ,ａ ） ∈ Ｒ,
显然,Ｒ是自反的,对称的,而且也是传递的,因为若 （ ａ,ｂ ） ∈ Ｒ,（ ｂ,ｃ ）
∈ Ｒ,则ａ,ｂ,ｃ均在同一等价类内,
故 （ ａ,ｃ ） ∈ Ｒ 。
与Ａ i和Ａ j 为不同的等价类矛盾 。
故Ａ i∩Ａ j ≠?
所以,Ｒ完成了等价类的分划例１：
Ａ＝ ｛ ５２张扑克 ｝
Ｒ 1＝ ｛（ ａ,ｂ ） ｜ａ与ｂ同花,ａ,ｂ是扑克 ｝
Ｒ 2＝ ｛（ ａ,ｂ ） ｜ａ与ｂ同点,ａ,ｂ是扑克 ｝
则,Ｒ 1把Ａ分为四类同花类,
Ｒ 2把Ａ分为１３类同点类 。
例２：
Ａ＝ ｛ ０,１,２,３,４,５ ｝
Ｒ＝ ｛（ ０,０ ）,（ １,１ ）,（ ２,
２ ）,（ ３,３ ）,（ １,２ ）,（ １,３ ）,
（ ２,１ ）,（ ２,３ ）,（ ３,１ ）,（ ３,
２ ）,（ ４,４ ）,（ ４,５ ）,（ ５,４ ）,
（ ５,５ ）｝
Ｒ 是等价关系,但不直观,用关系图表示 。
三个不连通的图二元关系 R是自反的,对称的,传递的,
且 把 Ａ 分 成 了 三 个 等 价 类,（ Ａ ） ＝
｛｛ ０ ｝,｛ １,２,３ ｝,｛ ４,５ ｝｝
[定义 ]：商集的元素个数 （ 即Ａ在Ｒ下的等价类个数 ） 称为Ｒ的秩,
[定义 ] 商集：等价关系 R将 A分成若干等价类,每个类选个代表组成新的集合称为 A关于 R的商集,表示为 A/R。
例：在上例中
A/R＝ ｛［ ０ ］,［ １ ］,［ ４ ］｝
例３：
Ｒ＝ ｛（ ａ,ｂ ） ｜ａ ≡ ｂ （ ｍｏｄ３ ）,
ａ,ｂ ∈ Ｉ ｝ 是整数集合Ｉ上模３同余的二元关系,
证明 R是等价关系 。
证明：由于３｜ （ ａ－ｂ ） ａ ≡ ｂ （ ｍｏｄ３ ）
(1) ３｜ （ ａ－ａ ）,
(2)若３｜ （ ａ－ｂ ）,则３｜ （ ｂ－ａ ）
(3)若３｜ （ ａ－ｂ ）,３｜ （ ｂ－ｃ ）,则
ａ－ｃ＝ （ ａ－ｂ ） ＋ （ ｂ－ｃ ）
３｜ （ ａ－ｃ ）
满足传递性,
商集：Ｉ／Ｒ＝ ｛［ ０ ］,［ １ ］,［ ２ ］｝
其中 ［ ０ ］ ＝ ｛ …,－６,－３,０,３,６,…｝
［ １ ］ ＝ ｛ …,－５,－２,１,４,７,…｝
［ ２ ］ ＝ ｛ …,－４,－１,２,５,８,…｝
例４：
Ｎ的一个分划为：若１０ i-1? ａ＜１０ i，
则ａ ∈ Ａ i,对应的等价关系
Ｒ＝ ｛（ ａ,ｂ ） ｜ａ与ｂ有相同位数,
ａ,ｂ ∈ Ｎ ｝ 相同位的数归为一类,此Ｒ把
Ｎ分划为可列个等价类 。
[定义 ]相 容关系：
Ａ上的二元关系Ｒ,若是自反的,
对称的,称Ｒ为相容关系 。
等价关系必然是相容关系 。
[定理 2]：
若Ｒ 1,Ｒ 2是Ａ上的等价关系,则Ｒ 1∩ Ｒ 2也是等价关系 。
证明：Ｒ 1∩ Ｒ 2＝Ｒ 3,Ｒ 3传递 。
(1）?ａ ∈ Ａ,由Ｒ 1,Ｒ 2自反
（ ａ,ａ ） ∈ Ｒ 1,（ ａ,ａ ） ∈ Ｒ 2,于是
（ ａ,ａ ） ∈ Ｒ 1∩ Ｒ 2＝Ｒ 3,Ｒ 3自反
(2)若 （ ａ,ｂ ） ∈ Ｒ 3,则 （ ａ,ｂ ） ∈ Ｒ 1
且 （ ａ,ｂ ） ∈ Ｒ 2,由Ｒ 1,Ｒ 2对称
（ ｂ,ａ ） ∈ Ｒ 1,（ ｂ,ａ ） ∈ Ｒ 2
于是 （ ｂ,ａ ） ∈ Ｒ 1∩ Ｒ 2＝Ｒ 3,Ｒ 3对称
４,２ 等价关系的运算
222
111
),(),(,),(
),(),(,),(
RcaRcbRba
RcaRcbRba
(3)若 （ ａ,ｂ ） ∈ Ｒ 3,（ ｂ,ｃ ） ∈ Ｒ 3
于是 （ ａ,ｃ ） ∈ Ｒ 1∩ Ｒ 2＝Ｒ 3,Ｒ 3传递 。
归纳以上三点,Ｒ 3＝Ｒ 1∩Ｒ 2也是等价的二元关系 。
[定理 3],若Ｒ 1,Ｒ 2是Ａ上等价关系,则Ｒ 1∪ Ｒ 2
是相容关系 。
注：Ｒ 1∪ Ｒ 2 不一定 是等价关系 。
证明：
设Ｒ 4＝Ｒ 1∪ Ｒ 2
(1)?ａ ∈ Ａ,（ ａ,ａ ） ∈ Ｒ 1,（ ａ,
ａ ） ∈ Ｒ 2,于是 （ ａ,ａ ） ∈ Ｒ 1∪ Ｒ 2＝Ｒ 4。
(2） 若 （ ａ,ｂ ） ∈ Ｒ 4,（ ａ,ｂ ） ∈
Ｒ 1或 （ ａ,ｂ ） ∈ Ｒ 2由Ｒ 1,Ｒ 2对称性,（ ｂ,
ａ ） ∈ Ｒ 1或 （ ｂ,ａ ） ∈ Ｒ 2，
于是 （ ｂ,ａ ） ∈ Ｒ 1∪ Ｒ 2＝Ｒ 4
注：Ｒ 4＝Ｒ 1∪ Ｒ 2是相容的,即
Ｒ 1∪ Ｒ 2不一定是等价关系若 （ ａ,ｂ ） ∈ Ｒ 4,（ ｂ,ｃ ） ∈ Ｒ 4
（ ａ,ｂ ） 与 （ ｂ,ｃ ） 可能分别属于
Ｒ 1与Ｒ 2,无法保证Ｒ 1∪ Ｒ 2的传递性 。
例５：
Ａ＝ ｛ ａ,ｂ,ｃ ｝
Ｒ 1＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,
（ ｃ,ｃ ）,（ ａ,ｂ ）,（ ｂ,ａ ）｝
Ｒ 2＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,
（ ｃ,ｃ ）,（ ｂ,ｃ ）,（ ｃ,ｂ ）｝
Ｒ 4＝Ｒ 1∪ Ｒ 2＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,
（ ｃ,ｃ ）,（ ａ,ｂ ）,（ ｂ,ａ ）,
（ ｂ,ｃ ）,（ ｃ,ｂ ）｝
显然,（ ａ,ｂ ）,（ ｂ,c） ∈ Ｒ 1∪ Ｒ 2
但 （ ａ,c）?Ｒ 1∪ Ｒ 2（ 不具有传递性 ）,
但 （ Ｒ 1∪ Ｒ 2） *一定是传递的 。
[定理 4],若Ｒ 1,Ｒ 2是Ａ上等价关系,
则 （ Ｒ 1∪ Ｒ 2） *也是Ａ上等价关系 。
证明：
(1)?ａ ∈ Ａ,（ ａ,ａ ） ∈ （ Ｒ 1∪ Ｒ 2）
（ Ｒ 1∪ Ｒ 2） *
(2)（ Ｒ 1∪ Ｒ 2） 是对称的,只需证明对称的二元关系的传递扩张还是对称的 。
设Ｒ是Ａ上对称的二元关系,Ｒ 1是Ｒ的传递扩张,若 （ ａ,ｂ ） ∈ Ｒ 1,则 （ ａ,ｂ ） ∈ Ｒ
或 （ ａ,ｂ ） ∈ Ｒ ·Ｒ,
a,若 （ ａ,ｂ ） ∈ Ｒ,（ ｂ,ａ ） ∈ Ｒ,
故 (ｂ,ａ )∈ Ｒ 1;
由 （ Ｒ 1∪ Ｒ 2） 对称?（ Ｒ 1∪ Ｒ 2） 1也对称,…，
对任一ｋ,（ Ｒ 1∪ Ｒ 2） k也对称 。
若 （ ａ,ｂ ） ∈ （ Ｒ 1∪ Ｒ 2） *,则?ｋ,
使 （ ａ,ｂ ） ∈ （ Ｒ 1∪ Ｒ 2） k，
故 （ ｂ,ａ ） ∈ （ Ｒ 1∪ Ｒ 2） k? （ Ｒ 1∪ Ｒ 2） *，
于是 （ Ｒ 1∪ Ｒ 2） *是对称的 。
（ 3） 任一传递闭包都具有传递性 。
即证 。
b,若（ａ，ｂ） ∈ Ｒ ·Ｒ，则ｃ，使
（ａ，ｃ），（ｃ，ｂ） ∈ Ｒ
（ｂ，ｃ），（ｃ，ａ） ∈ Ｒ
（ｂ，ａ） ∈ Ｒ ·Ｒ
（ｂ，ａ） ∈ Ｒ 1
等价关系对应于集合的一种分划 。
设Ｒ 1,Ｒ 2是Ａ上等价关系,对应的分划为
π1,π2，
π1·π2对应于Ｒ 1∩Ｒ 2,称为 二个分划的积,
使分划分更细；
π1＋ π2对应于 （ Ｒ 1∪ Ｒ 2） *,称为两个 分划的和,使分划比 π1,π2要粗 。
例６：
Ａ＝ ｛ ａ,ｂ,ｃ,ｄ,ｅ,ｆ,ｇ,ｈ,
ｉ,ｊ,ｋ ｝
４,３ 等价关系的运算与分划的关系
Ｒ 1? π 1 ＝ ｛
4
3
2
1
,,,
AAAA
jkhie fga b c d ｝
Ｒ
2
π
2
＝ ｛
43
21
,,,
BBBB
ge fi kdia b c h ｝
Ｒ 1＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,（ ｃ,ｃ ）,（ ｄ,
ｄ ）,（ ｅ,ｅ ）,（ ｆ,ｆ ）,（ ｇ,ｇ ）,（ ｈ,
ｈ ）,（ ｉ,ｉ ）,（ ｊ,ｊ ）,（ ｋ,ｋ ）,（ ａ,
ｂ ）,（ ａ,ｃ ）,（ ａ,ｄ ）,（ ｂ,ｃ ）,（ ｂ,
ｄ ）,（ ｃ,ｄ ）,（ ｂ,ａ ）,（ ｃ,ａ ）,（ ｄ,
ａ ）,（ ｃ,ｂ ）,（ ｄ,ｂ ）,（ ｄ,ｃ ）,（ ｅ,
ｆ ）,（ ｅ,ｇ ）,（ ｆ,ｇ ）,（ ｆ,ｅ ）,（ ｇ,
ｅ ）,（ ｇ,ｆ ）,（ ｈ,ｉ ）,（ ｉ,ｈ ）,（ ｊ,
ｋ ）,（ ｋ,ｊ ）｝
Ｒ 2＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,（ ｃ,ｃ ）,
（ ｄ,ｄ ）,（ ｅ,ｅ ）,（ ｆ,ｆ ）,
（ ｇ,ｇ ）,（ ｈ,ｈ ）,（ ｉ,ｉ ）,
（ ｊ,ｊ ）,（ ｋ,ｋ ）,（ ａ,ｂ ）,
（ ａ,ｃ ）,（ ａ,ｈ ）,（ ｂ,ｃ ）,
（ ｂ,ｈ ）,（ ｃ,ｈ ）,（ ｂ,ａ ）,
（ ｃ,ａ ）,（ ｈ,ａ ）,（ ｃ,ｂ ）,
（ ｈ,ｂ ）,（ ｈ,ｃ ）,（ ｄ,ｉ ）,
（ ｉ,ｄ ）,（ ｅ,ｆ ）,(ｅ,ｊ ）,
（ ｅ,ｋ ）,( f,j ),（ ｆ,ｋ ）,
（ ｊ,ｋ ）,（ ｆ,ｅ ）,（ ｊ,ｅ ）,
（ ｋ,ｅ ）,（ ｊ,ｆ ）,（ ｋ,ｆ ）,
（ ｋ,ｊ ）｝
Ｒ 1∩ Ｒ 2＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,
（ ｃ,ｃ ）,（ ｄ,ｄ ）,（ ｅ,ｅ ）,
（ ｆ,ｆ ）,（ ｇ,ｇ ）,（ ｈ,ｈ ）,
（ ｉ,ｉ ）,（ ｊ,ｊ ）,（ ｋ,ｋ ）,
（ ａ,ｂ ）,（ ａ,ｃ ）,（ ｂ,ｃ ）,
（ ｅ,ｆ ）,（ ｊ,ｋ ）,（ ｂ,ａ ）,
（ ｃ,ａ ）,（ ｃ,ｂ ）,（ ｆ,ｅ ）,
（ ｋ,ｊ ）
Ｒ 1∪ Ｒ 2＝ ｛（ ａ,ａ ）,（ ｂ,ｂ ）,（ ｃ,ｃ ）,
（ ｄ,ｄ ）,（ ｅ,ｅ ）,（ ｆ,ｆ ）,（ ｇ,ｇ ）,
（ ｈ,ｈ ）,（ ｉ,ｉ ）,（ ｊ,ｊ ）,（ ｋ,ｋ ）,
（ ａ,ｂ ）,（ ａ,ｃ ）,（ ａ,ｄ ）,（ ｂ,ｃ ）,
（ ｂ,ｄ ）,（ ｃ,ｄ ）,（ ｂ,ａ ）,（ ｃ,ａ ）,
（ ｄ,ａ ）,（ ｃ,ｂ ）,（ ｄ,ｂ ）,（ ｄ,ｃ ）,
（ ａ,ｈ ）,（ ｂ,ｈ ）,（ ｃ,ｈ ）,（ ｈ,ａ ）,
（ ｈ,ｂ ）,（ ｈ,ｃ ）,（ ｅ,ｆ ）,（ ｅ,ｇ ）,
（ ｆ,ｇ ）,（ ｆ,ｅ ）,（ ｇ,ｅ ）,（ ｇ,ｆ ）,
（ ｈ,ｉ ）,（ ｉ,ｈ ）,（ ｊ,ｋ ）,（ ｋ,ｊ ）,
（ ｄ,ｉ ）,（ ｉ,ｄ ）,（ ｅ,ｊ ）,（ ｅ,ｋ ）,
（ ｆ,ｊ ）,（ ｆ,ｋ ）,（ ｊ,ｅ ）,（ ｋ,ｅ ）,
（ ｊ,ｆ ）,（ ｋ,ｆ ）｝
但Ｒ 1∪ Ｒ 2不是传递的,如,（ ｃ,ｈ ）,
（ ｈ,ｉ ） ∈ Ｒ 1∪ Ｒ 2,而 （ ｃ,ｉ ）?Ｒ 1∪ Ｒ 2。
把Ｒ 1∪ Ｒ 2扩张到传递性满足,就是 （ Ｒ 1∪ Ｒ 2） *。
Ｒ
1
∩Ｒ
2
π
1
· π
2
＝ ｛
34
2313
4422
2111
,,,,,,
BA
BABA
BABA
BABA
jkihgefda b c
｝
凡是在 π
1
,π
2
中有一个要求把它们拆开的
（Ｒ
1
∪Ｒ
2
）
*?
｛
4342
2131
,
BBAA
BBAA
e fg jka b c d i h
｝
例７,
Ａ＝ ｛ ５２张扑克牌 ｝
Ｒ 1＝ ｛（ ａ,ｂ ） ｜ａ与ｂ同花,
ａ,ｂ是扑克 ｝
π 1
Ｒ 2＝ ｛（ ａ,ｂ ） ｜ａ与ｂ同点,
ａ,ｂ是扑克 ｝
π 2
Ｒ 1∩ Ｒ 2? π 1·π 2把扑克分成５２张单张
（ Ｒ 1∪ Ｒ 2） *? π 1＋ π 2把５２张扑
[定义 ]平凡分划,
集合 A的最粗或最细的分划,称为 平凡分划 。
注,
（ 1） 等价关系,用穷举法很难判别
（ 2） 用关系图比较直观,明确
（ 3） 用集合的分划来研究等价关系
§ ５ 半序关系
[定义 ],半序关系 （ 偏序关系 ）
Ｒ是Ａ上的二元关系,如果Ｒ满足：
(1) 自反的
(2） 反对称的
(3) 传递的则称Ｒ是Ａ上半序关系 。
例：
Ａ＝ ｛ １,２,３,４,５,６,７,８,９ ｝
Ｂ＝ ｛ ａ,ｂ,ｃ ｝
Ｒ 1＝ ｛（ ａ,ｂ ） ｜ ａ? ｂ,ａ,ｂ ∈ Ａ ｝
Ｒ 2＝ ｛（ ａ,ｂ ） ｜ ａ |ｂ,ａ,ｂ ∈ Ａ ｝
Ｒ 3＝ ｛（ ｓ 1,ｓ 2） ｜ｓ 1?ｓ 2，
ｓ 1,ｓ 2∈ ｐ （ Ｂ ）｝
记号：
Ｒ ={（ ａ,ｂ ） |ａ ≤Ｒ b,ａ,ｂ ∈ Ａ ｝ 其中 ≤Ｒ 可为?,|,?
注：
（ 1） 用矩阵表示半序关系,不能明显看到二元关系的特征 。
（ 2） 用简化的关系图表示较适合 。
(1)自反性：每个顶点都有自回路,省去 。
(2)反对称性：两个顶点间只可能有一个箭头从左 → 右,或从下 → 上的方向从小到大安置顶点,可省略箭头 。
(3)传递性：由于有 （ ａ,ｂ ）,（ ｂ,ｃ ） ∈ R
则 （ ａ,ｃ ） ∈ R
故只画 （ ａ,ｂ ）,（ ｂ,ｃ ） 对应的边省略边 （ ａ,ｃ ） 。
[定义 ],Ｈａｓｓｅ图设 ≤是Ａ上的一个半序关系,如果
ａ ≤ｂ,则将ａ画在ｂ下面,且不?ｃ,
使ａ ≤ｃ,ｃ ≤ｂ,则ａ,ｂ间用直线连接 。 并符合简化的关系图的绘制,
称这样得到关系图为Ｈａｓｓｅ图 。
例中半序关系的Ｈａｓｓｅ图如下：
1
2
3
4
5
6
7
8
9
R1
[定义 ] 全序,
Ａ上半序关系Ｒ,如果?ａ,ｂ ∈ Ａ,都有
ａ ≤ｂ,或ｂ ≤ａ,则称Ｒ为Ａ上的全序关系 。
注：
（ 1） 全序的含义：Ａ中每两个元素均能比大小,即任何两个元素都相关 。
（ 2） 半序则是部分有序 。
（ 3） Ｒ 1是全序,Ｒ 2,Ｒ 3都是半序如：Ｒ 2中,｛ １,２,６ ｝,｛ １,２,
４,８ ｝,｛ １,３,９ ｝ 都排成了序,但２
与３,５与７,７与９ …,在整除的意义上来说无法排出大小来 。
[定义 ]半序集：
集合Ａ及Ａ上的一个半序关系Ｒ组成的二元组 （ Ａ,Ｒ ）,称为半序集,记为
（ Ａ,? Ｒ ） 或 （ Ａ,≤） 。
注：
（ 1） 同一集合上的两个不同的半序关系,
所构成两个半序集,如：
Ｒ 1和Ｒ 2都定义在Ａ＝ ｛ １,２,３,４,
５,６,７,８,９ ｝ 上,但 （ Ａ,Ｒ 1） 与
（ Ａ,Ｒ 2） 显然不是一样的半序集 。
[定义 ]全序集：
半序集 （ Ａ,? Ｒ ） 中的半序关系? Ｒ 是Ａ上的全序,则此 （ Ａ,? Ｒ ）
称为全序集 。
（ Ａ,Ｒ 1） 是全序集 。 显然,全序集是半序集的特例 。 又如,（ － ∞,＋ ∞）
实数全体,在 ≤下是全序集；平面上点集,
也可以规定一种? Ｒ,模长大的大,模长相等的情况下,以幅角的大小来比大小,
因此,平面上点集也是全序集 。 （ Ｎ,≤）
当然也是全序集 。
注,
实数全体,平面点集是无法用Ｈａｓ
ｓｅ图表示的 。 一般来说,对有限集用Ｈ
ａｓｓｅ图比较好,对可列集只能示意一下,对不可列无限集是没法表示的,因为任二个数之间一定还有别的数 。
[定义 ]链：
设 （ Ａ,≤Ｒ ） 是半序集,,若
（ Ｂ,≤Ｒ ） 是全序集,则称Ｂ为 （ Ａ,≤
Ｒ ） 中的链 （ Ｃｈａｉｎ ） 。
当Ｂ是有限集时,Ｂ的基数｜Ｂ｜称为链长 。
例：
在上例 Ｈａｓｓｅ图 （ Ａ,Ｒ 2） 中,
取Ｂ 1＝ ｛ １,２,４,８ ｝,Ｒ 2＝ |（ 整除 ）,则
（ Ｂ 1,Ｒ 2） 是全序关系,Ｂ 1是半序集 （ Ａ,|） 中链长为４的链 。
Ｂ 2＝ ｛ １,２,６ ｝,Ｂ 3＝ ｛ １,
３,９ ｝,Ｂ 4＝ ｛ １,５ ｝,Ｂ 5＝ ｛ １,
７ ｝ 也都是 （ Ａ,|） 中的链 。
[定义 ]反链：
设 （ Ａ,? Ｒ ） 为半序集,Ｂ Ａ,对?
ａ,ｂ ∈ Ｂ （ ａ ≠ ｂ ）,（ ａ,ｂ ）?Ｒ,
（ ｂ,ａ ）?Ｒ,则称Ｂ为 （ Ａ,? Ｒ ） 中的反链 。
当Ｂ为有限集时,｜Ｂ｜为反链的长度 。
注,反链中的元素都互不相关 。
例如,（ Ａ,Ｒ 2）
Ｂ 1＝ ｛ ２,３,５,７ ｝ ｜Ｂ 1｜＝４
Ｂ 2＝ ｛ ４,６,９ ｝ ｜Ｂ 2｜＝３
Ｂ 3＝ ｛ ８,６,９,５,７ ｝ ｜Ｂ 3｜＝５
…
都是反链 。
[定义 ]极大元与极小元：
设 （ Ｐ,≤） 是半序集,Ａ?Ｐ,若ａ
∈ Ａ,且在Ａ中找不到一个元素ｂ （ ｂ ≠
ａ ）,使ａ ≤ｂ （ ｂ ≤ａ ）,则称ａ为Ａ中的极大元 （ 极小元 ） 。
例,（ Ｎ,|） 是半序集,
Ａ＝ ｛ ２,３,４,５,６,７,８,９ ｝
则 Ａ中极大元：８,６,９,５,７
极小元：２,３,５,７
注：
极大元,极小元并不要求唯一,且同一元素,
可以既是极大元,又是极小元,如５,７ 。
注,
极大元,极小元必须是子集Ａ中的元素 。
[定义 ]最大元与最小元：
设 （ Ｐ,? ） 是半序集,Ａ?Ｐ,
若ａ ∈ Ａ,?ｂ ∈ Ａ,ｂ? ａ (ａ? ｂ ）,
则称ａ为Ａ的最大元 （ 最小元 ） 。
例,上例其 Hasse图如下图所示结论：
子集Ａ中是不存在最大元 （ 最小元 ） 的 。
例,Ｂ＝ ｛ ａ,ｂ,ｃ ｝,
Ｒ 3＝ ｛（ ｓ 1,ｓ 2） ｜ｓ 1?ｓ 2,ｓ 1，
ｓ 2∈ ｐ （ Ｂ ）｝,（ ｐ （ Ｂ ）,? ） 是半序集 。
设Ａ＝ ｛ Ф,｛ ａ ｝,｛ ｂ ｝,｛ ｃ ｝,
｛ ａ,ｂ ｝,｛ ａ,ｃ ｝,｛ ｂ,ｃ ｝｝
其 Hasse图如下图所示结论：
A存在最小元 Ф,没有最大元。
注：
最大元 （ 最小元 ） 本身应属于子集Ａ,
且与Ａ中任一元素都有关系 。
[定义 ]上界与下界：
设 （ Ｐ,≤） 是半序集,Ａ?Ｐ,
若ａ ∈ Ｐ,对?ｂ ∈ Ａ,ｂ ≤ａ （ ａ ≤ｂ ）
称ａ为Ａ的上界 （ 下界 ） 。
注：
（ 1） 上例中,Ａ无最大元,但存在Ａ的上界 ｛ ａ,ｂ,ｃ ｝ 。
（ 2） Ф为Ａ的最小元,也是Ａ的下界
（ 3） 最大 （ 小 ） 元是Ａ的一个上 （ 下 ） 界
（ 4） 上 （ 下 ） 界可以不唯一,也可以不存在
[定义 ]上确界与下确界：
设 （ ｐ,? ） 是半序集,Ａ?Ｐ,
若ａ是Ａ的一个上界 （ 下界 ）,而?Ａ
的上界 （ 下界 ） ｂ,都有ａ? ｂ （ ｂ?
ａ ）,则称ａ是Ａ的上确界 （ 下确界 ） 。
注：
上确界：最小上界下确界：最大下界如果存在上 （ 下 ） 确界,则上 （ 下 ）
确界一定是唯一的例：
（ ｐ （ Ｂ ）,?） 中取Ａ ’ ＝ ｛ Ф,
｛ ｂ ｝,｛ ｃ ｝｝,则
｛ ｂ,ｃ ｝ 与 ｛ ａ,ｂ,ｃ ｝ 是Ａ ’ 的上界,｛ ｂ,ｃ ｝ 是Ａ ’ 的上确界 。
例：
ｐ＝ ｛ ａ,ｂ,ｃ,ｄ,ｅ ｝
Ａ＝ ｛ ａ,ｂ,ｃ ｝,（ ｐ,? ）
注：
存在上（下）界，并不一定存在上
（下）确界。
结论：（ 1）ｄ，ｅ是Ａ的上界
（ 2）ｄ与ｅ无法比大小，不存在上确界
（ 3）Ａ的下界不存在，不存在下确界
[引理 1]：
设 （ Ｐ,≤） 是半序集,Ａ是Ｐ的非空有限子集,则Ａ一定存在极大 （ 小 ） 元 。
证,若｜Ａ｜＝１,则 A中唯一元素既是极大元,也是极小元 。
假定｜Ａ｜＝ｎ时存在极大 （ 小 ） 元当｜Ａ｜＝ｎ＋１时,则将 A分成由ｎ个元素组成的子集 Ａ ’ 与元素ａ 。
由假定,Ａ ’ 存在极大元 ａ M,极小元ａ
m，
若ａ M≤ａ,则ａ为极大元,否则为ａ M，
因为若ａ M≤ａ,且存在 b≤Ａ ’,而
ａ ≤b,由传递性ａ M ≤ b,与ａ M为极大元
（ Ａ ’ ） 矛盾 。
同理,若ａ ≤ａ m,则 a为 极小元,否则为
ａ m。
[引理 2]：
设Ｍ是非空有限子集Ａ的极大元集合,
则Ｍ是Ａ的反链 。
反证：
若Ｍ不是反链,则?ａ,ｂ ∈ Ｍ （ ａ ≠
ｂ ）,（ ａ,ｂ ） ∈ Ｒ或 （ ｂ,ａ ） ∈ Ｒ,即
ａ? ｂ或ｂ? ａ,则ａ或ｂ不是极大元,矛盾 。
[定理 1]：
设 （ Ｐ,? ） 是有限的半序集,Ｐ 中最长链长度为ｎ,则 Ｐ 可以划分为ｎ个互不相交的反链 。
证,（ 1） ｎ＝１,Ｐ中任两个元素不相关,
Ｐ本身是反链 。
(2) 假设ｎ时定理成立,即当Ｐ中最长链长为ｎ时,可以划分为ｎ个互不相交的反链 。
(3)当Ｐ中最长链长为ｎ＋１,由引理 1，
极大元一定存在,设Ｍ是极大元集合,由引理 2,Ｍ是Ｐ的一个反链 。
如果去掉Ｍ,（ Ｐ－Ｍ,≤） 也是半序集,则Ｐ－Ｍ中最长链长为ｎ,由假设,Ｐ
－Ｍ可以划分为 ｎ个 互不相交的 反链,添上
Ｍ,可知Ｐ可划分为ｎ +1个互不相交的反链 。
例：Ａ＝ ｛ １,２,３,４,５,６,７,８,
９ ｝,半序集 （ Ａ,６ ）,最长链为４,Ｂ＝
｛ １,２,４,８ ｝
Ａ 1
Ａ 2＝ ｛ ２,３,５,７ ｝
Ａ 3＝ ｛ ４,６,９ ｝
Ａ 4＝ ｛ ８ ｝
Ｂ 4＝ ｛ ８,６,９,５,７ ｝
Ｂ 3＝ ｛ ４,３ ｝
Ｂ 2＝ ｛ ２ ｝
Ｂ 1＝ ｛ １ ｝
注：
反链的取法并不唯一,而最长链中的元素必然分别落在每个反链里 。
说明：
若 Ｐ r（ Ａ ） ＝ ｛ Ａ 1,Ａ 2,…,Ａ n｝,是 A
的一个分划,则可定义一个半序关系,当 j-
i=1时,取 a?Ai,b?Aj,使 (a,b)?R1,且 Ai,,Aj
中每个元素至少取到一次并对? a?A,(a,a)?R1
然后取 R = R1*（ 闭包 ）
这样 R是半序关系,并使每个 Ai是反链,
且最长链是 Ａ 1,Ａ 2,…,Ａ n中各取一个元素组成的 。
[定理 2]：每个Ａ的分划
ｐ r（ Ａ ） ＝ ｛ Ａ 1,Ａ 2,…,Ａ n｝,都可以找到一个半序关系Ｒ,使Ａ 1,Ａ 2,…,Ａ n都是 （ Ａ,Ｒ ） 的反链,而 （ Ａ,Ｒ ） 的最长链由Ａ 1,Ａ 2,…,Ａ n中各取一个元素组成 。
例：
取Ｒ 1＝ ｛（ １,２ ）,（ １,３ ）,
（ １,５ ）,（ １,７ ）,（ ２,６ ）,
（ ２,４ ）,（ ３,６ ）,（ ３,９ ）,
（ ４,８ ）,（ １,１ ）,（ ２,２ ）,
（ ３,３ ）,（ ４,４ ）,（ ５,５ ）,
（ ６,６ ）,（ ７,７ ）,（ ８,８ ）,
（ ９,９ ）｝
令Ｒ＝
1R,则 （Ａ，Ｒ）＝ （Ａ，１）。
但若取,
Ｒ 1＝ ｛（ １,２ ）,（ １,３ ）,（ １,５ ）,
（ １,７ ）,（ ２,４ ）,（ ２,６ ）,
（ ２,９ ）,（ ６,８ ）,（ ５,９ ）,
（ １,１ ）,（ ２,２ ）,（ ３,３ ）,
（ ４,４ ）,（ ５,５ ）,（ ６,６ ）,
（ ７,７ ）,（ ８,８ ）,（ ９,９ ）｝
令Ｒ＝
1
R,是无法得到 （Ａ，／）的，
可见，由互不相交的反链构造出来的半序集并不是唯一的。
[定理 3]：
设半序集 （ ｐ,? ） 包含ｍ ·ｎ＋
１个或以上个元素,则ｐ至少有一个链长? ｎ＋１ （ 或ｍ＋１ ） 或至少有一个反链长? ｍ＋１ （ 或ｎ＋１ ） 。
证：
若ｐ的最长链长? ｎ,反链长?
ｍ,由定理 1,ｐ可划分为不超过ｎ个反链,则ｐ至多有ｎ ·ｍ个元素,与ｐ
的元素个数矛盾 。
例１：
ａ ·ｂ＋１个自然数的集合ｐ
（（ ｐ,|） 是半序集 ）
或者有
（ ａ＋１ ） （ 或 （ ｂ＋１ ）） 个数一个被一个整除或者有
（ ｂ＋１ ） （ 或 （ ａ＋１ ）） 个数互素
[定义 ]良序集：
设 （ Ａ,Ｒ ） 是半序集,若Ａ的非空子集都存在最小元,则称Ｒ是良序关系,（ Ａ,
Ｒ ） 为良序集 。
注,（ 1） 良序集是全序集
（ 2） 全序集未必是良序的,如：
实数全体,任两个实数都能比大小,
但子集 ｛ 1/n｝ 的最小元找不到 。
但,有限的全序集自然是良序的 。
