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+