1.2 关系

1.2.1 二元关系

定义1.5 二元关系的定义。

设A和B为两个集合，则A×B的任何一个子集称为A到B的一个二元关系。

若R为A到B的关系，当（a,b）∈R时，可记为aRb。

二元关系简称为关系。

若A=B，则称为A上的二元关系。

例1.2 关系的例子。

设A为正整数集合，则A上的关系“<”是集合

{（a,b）|a,b∈A，且a<b}

即

思考：如果集合A和B都是有穷集合，则A到B的二元关系有多少个？A到B的一个二元关系，最多可以有多少个元素？最少可以有多少个元素？

1.2.2 等价关系

设R是集合A上的关系，那么

若对A中的任一元素a，都有aRa，则称R为自反的。

若对A中的任何元素a和b，从aRb能够推出bRa，则称R为对称的。

若对A中的任何元素a，b和c，从aRb和bRc能够推出aRc，则称R为传递的。

定义1.6 等价关系的定义。

若关系R同时是自反的、对称的和传递的，则称之为等价关系。

等价关系的一个重要性质为：集合A上的一个等价关系R可以将集合A划分为若干互不相交的子集，称为等价类。

对A中的每个元素a，使用[a]表示a的等价类，即

[a]={b|aRb}

等价关系R将集合A划分成的等价类的数目，称为该等价关系的指数。

例1.3 等价关系的例子。

考虑非负整数集合N上的模3同余关系R：

R={（a,b）|a,b∈N, 且a mod 3=b mod 3}

则集合

{0,3,6,…,3n,…}

形成一个等价类，记为[0]。

集合

{1,4,7,…,3n+1,…}

形成一个等价类，记为[1]。

集合

{2,5,8,…,3n+2,…}

形成一个等价类，记为[2]。

N=[0]∪[1]∪[2]

R的指数为3。

1.2.3 关系的合成

关系是可以合成的。

定义1.7 关系合成的定义。

设R1⊆A×B是集合A到B的关系，设R2⊆B×C是集合B到C的关系，则R1和R2的合成是集合A到C的（二元）关系。

R1和R2的合成记为R1 〇R2，

R1 〇R2={（a,c）|（a,b）∈R1, 且（b,c）∈R2}

例1.4 关系合成的例子。

设R1和R2是集合{1,2,3,4}上的关系，

R1={（1,1）,（1,2）,（2,3）,（3,4）}

R2={（2,4）,（4,1）,（4,3）,（3,1）,（3,4）}

则

R1 〇R2={（1,4）,（2,1）,（2,4）,（3,1）,（3,3）}

R2 〇R1={（4,1）,（4,2）,（4,4）,（3,1）,（3,2）}

定义1.8 关系的n次幂的定义。

设R是S上的二元关系，则关系的n次幂Rn如下递归定义：

R0={（a,a）|a∈S}

Ri=Ri−1 〇R, i=1,2,3,…

定义1.9 关系的闭包定义。

设R是S上的二元关系，R的正闭包R+定义为

（1）R∈R+

（2）若（a,b）,（b,c）∈R+，则（a,c）∈R+

（3）除（1）和（2）外，R+不再含有其他任何元素，即

R+=R∪R2∪R3∪…

且当S为有穷集时，有

R+=R∪R2∪R3∪…∪R|S|

设R是S上的二元关系，R的克林包R*定义为

R*=R0∪R+

例1.5 关系闭包的例子。

设R1和R2是集合{a,b,c,d,e}上的二元关系：

R1={（a,b）,（c,d）,（b,d）,（b,b）,（d,e）}

R2={（a,a）,（b,c）,（d,c）,（e,d）,（c,a）}

求R1 〇R2,R1+,R1*。

（1）R1 〇R2={（a,c）,（c,c）,（b,c）,（d,d）}

（2）R1+={（a,b）,（c,d）,（b,d）,（b,b）,（d,e）,（a,d）,（a,e）,（c,e）,（b,e）}

（3）R1*={（a,a）,（b,b）,（c,c）,（d,d）,（e,e）}∪R1+