离散数学-第六章

1第六章关系§6.1关系及其性质§6.2关系的运算§6.3次序关系§6.4等价关系与划分2§6.1关系及其性质重点：1.关系的表示2.关系的性质3一、关系的定义定义6.1(关系):X到Y的关系:

若R是XY的子集(即RX

Y

),则称R为X到Y的二元关系，简称为关系。当X=Y时,称R为X上的二元关系。若<x,y>R,则可表示成xRy,读做“x与y有关系R”若<x,y>R,则记作xRy,读作“x与y不存在关系R”¯4例1:A={1,2,3},B={a,b}R={<1,a>,<1,b>,<2,b>}是A到B的关系。例2：实数集合上的大于关系“>”表示如下：

>={<x,y>|x,y是实数且x>y}

空关系：设X是集合，XX的子集，称为X上的空关系。X上的全域关系:UX={<xi,xj>|xi，xjX}=XXX上的恒等关系：IX={<x,x>|xX}5例3：设X={0,1,2}UX={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<2,2>}IX={<0,0>,<1,1>,<2,2>}定义6.2

设RXY,dom(R)={xX|yY:<x,y>R},为R的定义域

ran(R)={yY|xX:<x,y>R},为R的值域

显然，dom(R)X，ran(R)Y6二、关系的表示关系矩阵：设X={x1,……,xm},Y={y1,……,yn},R是X到Y的二元关系。

R的关系矩阵，记作MR=(rij)mn,其中

0若xiRyjrij=1若xiRyj¯（仅讨论从有限集到有限集的二元关系）7R的关系矩阵是:100111例6.3设X={x1,x2},Y={y1,y2,y3},R是X到Y的关系。

R={<x1,y1>,<x2,y1>,<x2,y2>,<x2,y3>}82.关系图:设X是有穷集合,则X上的二元关系R的关系图可构造如下:

X集合中的元素称为顶点

,并用点或小圈表示,对于元素xi

和xj,分别标以顶点xi

和xj。如果xiRxj

，即<xi,xj>R,就用一条带箭头的弧线把xi

和xj连接起来，箭头的方向由xi

指向xj；如果

xiRxj且xjRxi,则在xi

和xj之间画上两条方向相反的弧线;

如果

xiRxi，则画一条从xi

出发又返回顶点xi的弧线，称这一条弧线为自环

.当R中所有有序偶处理完毕后,便得到关系R的图

.91234图6.4集合X上的关系图例6.4:设X={1,2,3,4},R是集合X上的关系,R={<1,2>,<2,2>,<2,4>,<3,2>,<3,4>,<4,1>,<4,3>}则R的关系图如下：10三、关系的性质(自反、反自反、对称、反对称、传递)定义6.3设R是非空集合X上的二元关系R是自反的

x(xX<x,x>R)在R的关系图中，每个顶点均有自环；在R的关系矩阵中，主对角线的元素均为1。R是反自反的

x(xX<x,x>R)在R的关系图中，每个顶点均无自环；在R的关系矩阵中，主对角线的元素均为0。11R是对称的

xy(xXyX<x,y>R<y,x>R)在R的关系图中，任意两个不同顶点之间：或者无弧或者有两条方向相反的弧；R的关系矩阵是对称矩阵.R是反对称的

xy(xXyX<x,y>R<y,x>Rx=y)xy(xXyX<x,y>Rxy<y,x>R)在R的关系图中，任意不同顶点之间至多有一条弧；在R的矩阵中,若ij且

rij=1,则rji=0。12R是传递的xyz(xXyXzX<x,y>R<y,z>R<x,z>R)在R的关系图中，若顶点x到顶点y有一条路径，则必有从x到y的一条弧（处处有捷径）。从关系矩阵中不易看出传递关系的特征。例(1)X上的恒等关系是自反、对称、反对称、传递的

(2)X上的“<”是反自反、反对称、传递的思考题(1)非空集X上的空关系？？？(2)空集上的空关系？？？13指出下列二元关系所具有的性质:例:设X={1,2,3},集合X上的二元关系R1={<1,2>,<2,3>,<3,1>}R2={<1,2>,<1,3>}R3={<1,2>,<1,3>,<2,3>,<3,2>}R4={<1,2>,<2,1>,<1,3>,<3,1>,<1,1>,<2,2>,<3,3>}14关系图和关系矩阵中五种性质的表述R自反反自反对称反对称传递MR对角线元素全1对角线元素全0对称矩阵aij.aji=0(ij)若有k使aik.akj=1,则aij=1GR所有结点都有自圈所有结点都无自圈

结点间有向边都成对出现结点间无成对出现的有向边处处有捷径15图6.5给出了一些关系图，指出由这些图给定的关系所具有的性质，并写出对应的关系矩阵。x5x1x2x3x1x2x3x4(a)(b)x1x2x3x4(c)图6.5关系图(d)x2x1x3x416解图6.5(a)的关系是反对称的,反自反的.

图6.5(b)的关系是自反的、对称的、反对称的、和可传递的。图6.5(c)的关系是自反的，对称的。图6.5(d)的关系是反自反的、反对称的、传递的。关系图：直观、形象关系矩阵：便于计算机处理17思考题：设A为恰有n个元素的有限集，1）A上共有多少个不同的自反关系？2）A上共有多少个不同的反自反关系？3）A上共有多少个不同的对称关系？4）A上共有多少个不同的反对称关系？5）A上共有多少个不同的既是对称又反对称的关系？18§6.2关系的运算重点掌握关系的复合、逆、自反闭包、对称闭包、传递闭包等定义及运算定义6.4设R和S是从集合A到B的关系,取全集为A×B,则R∩S,R∪S,R－S,～R仍是A到B的关系，并且对于任意x∈A,y∈B:x(R∩S)yxRy∧xSyx(R∪S)yxRy∨xSyx(R－S)yxRy∧xSyx(～R)yxRy¯¯19例4.12设R和S是集合A＝｛1,2,3,4｝上的关系，

R＝｛〈x,y〉｜x－y是2的非零整倍数｝

S＝｛〈x,y〉｜x－y是3的非零整倍数｝求：R∩S，R∪S，R－S和～R。解R＝｛〈1,3〉,〈3,1〉,〈2,4〉,〈4,2〉｝

S＝｛〈1,4〉,〈4,1〉｝则R∩S＝R∪S＝{〈1,3〉,〈3,1〉,〈2,4〉,〈4,2〉,〈1,4〉,〈4,1〉}R－S＝{〈1,3〉,〈3,1〉,〈2,4〉,〈4,2〉}

～R＝{〈1,1〉,〈1,2〉,〈1,4〉,〈2,1〉,〈2,2〉,〈2,3〉,〈3,2〉,〈3,3〉,〈3,4〉,〈4,1〉,〈4,3〉,〈4,4〉}20定义6.5设R是X到Y的关系，S是Y到Z的关系，则R·S＝｛〈x,z〉｜y

Y使得:xRy∧ySz)｝为X到Z的关系,称为R和S的复合关系。R·SRS21例4.13设R＝｛〈1,2〉,〈2,2〉,〈3,4〉｝,S＝｛〈1,3〉,〈2,5〉,〈3,1〉,〈4,2〉｝求:R·S,S·R,(R·S)·R，R·(S·R)，R·R。解:R·S={<1,5>,<2,5>,<3,2>}S·R={<1,4>,<3,2>,<4,2>}R·R={<1,2>,<2,2>}显然，dom(R·S)dom(R)，ran(R·S)ran(S)。

R·S≠S·R，故关系的复合运算不满足交换律。

(R·S)·R={<3,2>}R·(S·R)={<3,2>}可证：关系的复合运算满足结合律。22定理6.1设R，S，P分别是X到Y、Y到Z、Z到W的关系，则(R·S)·P＝R·(S·P)。证明:对任意〈x,w〉:

〈x,w〉∈(R·S)·P

z∈Z(〈x,z〉∈R·S∧〈z,w〉∈P)

z∈Z(y∈Y(〈x,y〉∈R∧〈y,z〉∈S)∧〈z,w〉∈P)

y∈Y(〈x,y〉∈R∧z∈Z(〈y,z〉∈S∧〈z,w〉∈P))

y∈Y(〈x,y〉∈R∧〈y,w〉∈S·P)〈x,w〉∈R·(S·P)故(R·S)·P＝R·(S·P)。23例6.8设R和S是整数集合Z上的两个关系，R＝｛〈x,2x〉｜x∈Z｝，S＝｛〈x,7x〉｜x∈Z｝求：R·S，R·R，R·R·R和R·S·R。解 R·S＝｛〈x,14x〉｜x∈Z｝

R·R＝｛〈x,4x〉｜x∈Z｝

R·R·R＝｛〈x,8x〉｜x∈Z｝

R·S·R＝｛〈x,28x〉｜x∈Z｝定义4.16设R是集合A上的关系，n是自然数，R的n次幂Rn定义如下：(1)R0

是集合A上的恒等关系IA，即R0＝IA；(2)Rn＋1＝Rn·

R。显然，R1＝R0·

R＝IA·

R＝R

24对n归纳易证，对于任意m,n∈N，(1)Rm·

Rn＝Rm＋n(2)(Rm)n＝Rmn两个关系的复合，也可用矩阵运算来表示。用矩阵运算求两个关系的复合多用于一个集合上的关系的复合。为了不失一般性，下面介绍A到B的关系和B到C的关系的复合。关系复合的矩阵表示：25设A＝｛a1,a2,…,am｝,B＝｛b1,b2,…,bp｝,C＝｛c1,c2,…,cn｝,R是A到B的关系，S是B到C的关系，关系矩阵MR＝(rij)m×p

，MS＝(sij)p×n,则

R·S的关系矩阵MR·S

＝(tij)m×n

，其中

tij＝(ri1∧s1j)

∨(ri2∧s2j)

∨…∨(rip∧spj)

＝(rik∧skj)

因为由复合关系的定义，〈ai,cj〉∈R·S当且仅当，存在bk使得〈ai,bk〉∈R且〈bk,cj〉∈S。即rik＝skj＝1。故rik∧skj＝1。也就是说，ri1∧s1j，ri2∧s2j，…，rip∧spj中至少有一个是1，即(ri1∧s1j)

∨(ri2∧s2j)

∨…∨(rip∧spj)＝1。∨pK=126例：设A＝｛a,b,c,d｝上的关系R＝｛〈a,b〉,〈b,a〉,〈b,c〉,〈c,d〉｝,求R2的关系矩阵。解：

MR＝MR2＝*＝27显然，dom(R－1)＝ran(R)，ran(R－1)＝dom(R)，

R－1

的逆关系是R，即(R－1)－1

＝R。若R和S都是关系，则(R∪S)－1

＝R－1∪S－1

。R－1

的关系矩阵是:R的关系矩阵MR的转置矩阵。将R的关系图中的每条有向边的方向反向，就得到R－1

的关系图。定义6.7将关系R中每个有序偶的第一元和第二元对换所得到的关系,称为R的逆关系，记作R－1，

R－1＝｛〈x,y〉｜〈y,x〉∈R｝。例如R＝｛〈a,1〉,〈a,3〉,〈b,1〉,〈b,2〉,〈c,1〉｝

R－1＝｛〈1,a〉,〈3,a〉,〈1,b〉,〈2,b〉,〈1,c〉｝28关系复合的性质

设二元关系R1

AB，R2,R3

BC，R4

CD：若R2

R3，则R1oR2

R1oR3

且R2oR4

R3oR4；

R1o(R2∪R3)=(R1oR2)∪(R1oR3)；

(R2∪R3)oR4=(R2oR4)∪(R3oR4)；

R1o(R2∩R3)(R1oR2)∩(R1oR3)；

(R2∩R3)oR4

(R2oR4)∩(R3oR4)；

(R1oR2)–1=R2–1

oR1–1；

(R1oR2)oR4=R1o(R2oR4)。29思考题

设R1

和R2

都是集合A上的二元关系，证明或用反例推翻以下的论断：a)若R1和R2都是自反的，则R1

oR2(R12)也是自反的；b)若R1和R2都是反自反的，则R1

oR2(R12)也是反自反的；c)若R1和R2都是对称的，则R1

oR2(R12)也是对称的；d)若R1和R2都是传递的，则R1

oR2(R12)也是传递的。30定理6.2设R和S是关系，则(R·S)－1＝S－1

·R－1。证明对于任意〈z,x〉，

〈z,x〉∈(R·S)－1

〈x,z〉∈R·S

y(〈x,y〉∈R∧〈y,z〉∈S)

y(〈y,x〉∈R－1∧〈z,y〉∈S－1)

〈z,x〉∈S－1·R－1因此，(R·S)－1＝S－1·R－1

。31二元关系性质的判断条件

引理6.1设R为A上的二元关系，则有条件成立：

R为自反的

iffIA

R；

R为反自反的

iff

IAR=；

R为对称的

iffR=R–1

；

R为反对称的

iffR

R–1

IA；

R为传递的

iff

RoRR

。32定义6.8设R是集合A上的关系。关系R´

称为R的自反（对称、传递）闭包，当且仅当R´满足以下三个条件：(1)R´是自反的（对称的、传递的）；(2)R

R´

；(3)对于A上的任何自反（对称、传递）关系R，如果RR

，则R´

R。将R的自反(对称、传递)闭包分别记作r(R),s(R),t(R)

可以证明：

R的自反、对称、传递闭包r(R),s(R),t(R)的存在性与唯一性。33由定义6.8可知：1）R是自反的当且仅当r(R)＝R；2）R是对称的当且仅当s(R)＝R；3）R是传递的当且仅当t(R)＝R。定理6.3设R是集合A上的关系，则r(R)＝R∪IA

。证明：显然R∪IA是自反的，且R

R∪IA

,由自反闭包r(R)的定义可知，r(R)

R∪IA。另外,r(R)

是A上的自反关系且Rr(R)

,因此

IA

r(R),故R∪IAr(R)。所以，r(R)＝R∪IA

。34定理6.4设R是集合A上的关系，则s(R)＝R∪R–1

。证明:因(R∪R–1)–1＝R–1∪(R–1)–1＝R–1∪R＝R∪R–1,由引理6.1可知，R∪R–1

是对称的。显然R’R∪R–1。设R´是A上任意对称关系且RR´

，则R–1(R')–1。因为R´是对称的，由引理6.1，(R´)–1＝R´

,故R－1R´，所以R∪R－1

R´

。由对称闭包定义知，s(R)＝R∪R－1

定理6.5设R是集合A上的关系，则

t(R)＝R∪R2∪R3∪…=证明：只要证明t(R)与互相包含即可。首先用归纳法证：对于任意n1，

Rn

t(R)。由传递闭包的定义可知，Rt(R)。35设对于任意n1,

Rnt(R),

下面证明：Rn+1t(R)。设<x,y>Rn+1，由于Rn+1=Rn·

R，则存在zA，使得<x,z>Rn，<z,y>R。根据归纳假设和归纳基础，有<x,z>t(R)和

<z,y>t(R)，由此可得<x,y>t(R)，则Rn+1t(R)。由于对于所有的n1，均有Rnt(R)。因此

t(R)

再证t(R)

显然R。只要再证是传递的即可。设任意<x,y>，<y,z>，则存在正整数s和k，使得<x,y>Rs,<y,z>Rk,这样<x,z>Rs+k，因此有<x,z>，所以是传递的。由t(R)的最小性，得t(R)。36定理6.6

设R是集合A上的关系，A有n个元素，则

t(R)＝证明:只需证:对于任意k0，

Rn+k

例：设集合A＝｛a,b,c｝上的关系R＝{〈a,b〉,〈b,c〉,〈c,c〉}，求：r(R),s(R),t(R)。解r(R)＝R∪IA＝{〈a,b〉,〈b,c〉,〈c,c〉,〈a,a〉,〈b,b〉}S(R)＝R∪R－1＝｛〈a,b〉,〈b,c〉,〈c,c〉,〈b,a〉,〈c,b〉｝

R2＝｛〈a,c〉,〈b,c〉,〈c,c〉｝

R3=｛〈a,c〉,〈b,c〉,〈c,c〉｝=R2t(R)＝R∪R2＝｛〈a,b〉,〈b,c〉,〈c,c〉,〈a,c〉｝37例6.10设集合A＝｛a,b,c,d｝,A上的关系R＝｛〈a,b〉,〈b,a〉,〈b,c〉,〈c,d〉｝，试画出t(R)关系图。R关系图abcdt(R)关系图bacd38闭包的性质性质1设二元关系R1，R2

A2

且R1

R2，则i)r(R1)r(R2)；

s(R1)s(R2)；

t(R1)t(R2)。性质2设二元关系RA2，i)若R是自反的，则s(R)和t(R)也是自反的；ii)若R是对称的，则r(R)和t(R)也是对称的；iii)若R是传递的，则r(R)也是传递的。性质3设二元关系RA2，则

rs(R)=sr(R)；

rt(R)=tr(R)；

st(R)ts(R)。39§6.3

次序关系重点:偏序关系画哈斯图求偏序集合中的特殊元素次序关系包括：偏序关系，全序关系，严格偏序关系，良序关系。40定义6.9（偏序关系）集合P上的关系R称为P上的偏序关系，当且仅当R是自反的、反对称的和传递的。例：〈N,≤〉,〈N,≥〉,〈P(A),〉,〈I+,|〉都是偏序结构定义6.10（全序关系）设〈P,≤〉是一个偏序结构，如果对于任意x，y∈P，或者x≤y，或者y≤x，则称≤为P上的全序或线序，并称〈P,≤〉为全序结构

或链。即

(x)(y)(x∈P∧y∈Px≤y∨y≤x)

用“≤”表示偏序关系，并用〈P,≤〉表示偏序结构。

如果x,y∈P且x≤y，则称“x小于或等于y”或“x在y之前”。41对于偏序集合〈P,≤〉，x,y∈P，如果有x≤y或者y≤x，就说P的元素x和y是可比的。例：〈N,≤〉,〈N,≥〉都是全序结构。它们中的任意元素x和y都是可比的而〈P(A),〉,〈I+,|〉都不是全序结构定义6.11（严格偏序关系，又称拟序关系）R是集合P上的严格偏序关系，当且仅当R是反自反的和传递的。

用“＜”表示严格偏序关系，并称“x小于y”，称〈P,＜〉为严格偏序（拟序）结构。42例〈N,＜〉,〈N,＞〉,〈P(A),〉都是严格偏序结构证明若R是P上严格偏序关系，则R是反对称的。证明：假设R不是反对称的，则存在x,y∈P且x≠y，使得〈x,y〉∈R且〈y,x〉∈R因为R是传递的，所以〈x,x〉∈R，这与R反自反矛盾。由上述证明可知，P上的严格偏序关系和偏序关系有如下关系：＜＝≤－IP

例如：x＜yx≤y∧x≠y

43

y遮盖

xx＜y∧

z(z∈P∧x＜z∧z＜y)例:P＝｛1，2，3，4｝,≤是P上的小于或等于关系，则4遮盖3，3遮盖2，2遮盖了1。若≤是P上的大于或等于关系，则上述遮盖关系恰好相反哈斯图：在偏序结构〈P,≤〉中，对于任何两个元素x,y∈P，如果x＜y且不存在任何其它元素z∈P，使得x＜z和z＜y，则称y遮盖（覆盖）x。偏序结构通常用简化的关系图来表示，这种关系图称为偏序结构图或哈斯图。44哈斯图画法如下：集合的每一个元素用一个点表示，对于x,y∈P，如果x＜y，则点x画在点y之下，如果y遮盖x，就在x和y之间画一条直线，在哈斯图中省略了自环，并约定弧的指向向上，不画箭头。例：画出满足下列条件的哈斯图.⑴Pa＝｛1，2，3，4｝，并设≤是Pa上的小于或等于关系。1234｛a,b,c｝｛a,b｝｛a｝⑵Pb＝｛

,｛a｝,｛a,b｝,｛a,b,c}}，并设是Pb上的包含关系。解：见右图解：见右图45例：设X={2，3，6，12，24，36}，≤为整除关系，如果x整除y，便有x≤y.画出〈X,≤〉的哈斯图.336261224解：见右图解：见右图例设A={a，b，c},

是幂集(A)上的包含关系，画出〈(A),〉的哈斯图{a,b,c}{a,b}{a,c}{b,c}{a}{b}{c}46⑴b是B的最大元b∈B∧x(x∈Bx≤b)⑷b是B的最大下界b是B的下界,且对B的任意下界x,都有x≤b。

偏序结构中的特殊元素：定义6.12设〈A,≤〉是偏序结构，并且BA，则⑵b是B的最小元b∈B∧x(x∈Bb≤x)⑶b是B的极大元b∈B∧x(x∈Bb＜x)⑷b是B的极小元b∈B∧x(x∈Bx＜b)

定义6.13设〈A,≤〉是偏序结构，并且BA，则⑴b是B的上界b∈A∧x(x∈Bx≤b)⑵b是B的下界b∈A∧x(x∈Bb≤x)⑶b是B的最小上界b是B的上界,且对B的任意上界x,都有b≤x。47⑶若B是有穷集，则B的极大元、极小元必存在，但B的最大元、最小元不一定存在。例：设集合A＝｛1,2,3,4,5,6｝,≤关系是整除关系，画出哈斯图，并指出A的极大元、极小元、最大元、最小元、上界、下界、最小上界、最大下界.由上述定义可知：⑴B的最大元、最小元若存在，则唯一；⑵B的极大元、极小元若存在，不一定唯一；A的极大元：4,5,6极小元：1

最大元：无最小元：1

上界：无下界：1

最小上界：无最大下界：1

12364548定义6.14（良序结构）：一个偏序结构〈P,≤〉，如果P的每一个非空子集都有一个最小元，则称≤为良序关系，〈P,≤〉为良序结构。例〈N,≤〉是全序结构，也是良序结构；

〈I,≤〉是全序结构，但不是良序结构。（why？）

〈Q+,≤〉,〈R+

,≤〉是全序结构，但都不是良序结构。

（why？）由定义可知，每个良序结构都是全序结构（why？）但并非每个全序结构都是良序的，当然有穷的全序结构一定是良序的。49良序的充要条件定理A若≤为集合P上的偏序关系，则≤为P上良序关系，当且仅当1）≤为P上的全序关系；2）P的每个非空子集都有极小元。定理B设〈A,≤〉为全序结构，则〈A,≤〉是良序结构的充要条件是：不存在A中元素的无穷序列a0,a1,a2,…,使得对每个iN，皆有ai+1<ai

。简而言之，就是：不存在A中元素的无穷递降序列。

50§6.4等价关系与划分例6.18设R是集合A=｛1,2,3,4,5,6,7｝上的关系，

R={〈x,y〉|x∈A∧y∈A∧3|(x－y)｝(模3同余关系)证明R是一个等价关系，并画出其关系图。

证明：略其关系图如右图所示，可见R的确是A上自反、对称、传递的关系，故R是A上的等价关系。定义(等价关系)

如果集合A上的关系R是自反、对称、传递的，则称R为A上的等价关系。51例：设集合X是整数集合I的任意子集，证明：

X上的模m同余关系是等价关系。证明：自反性：对于任意xX，显然xx(modm)。对称性:对于任意x,yX,若xy(modm),则存在kI，使得x-y=k*m，故y-x=(-k)*m，因此yx(modm)。传递性:对于任意x,y,zX,若xy(modm),yz(modm),则存在k,nI使得x–y=k*m,y–z=n*m，于是有x–z=(k+n)*m，因此xz(modm)综上所述，模m同余关系是等价关系。可以证明:对于任意正整数m，模m同余关系是等价关系。若x和y有模m同余关系，一般记作xy(modm)52定义(等价类)设R是集合A上的等价关系。对于每个x∈A，A中与x有关系R的元素的集合称为x关于R的等价类，简称为x的等价类，记作[x]R，即:[x]R＝｛y｜y∈A∧x

Ry｝，显然[x]R

A对上例给出的集合A=｛1,2,3,4,5,6,7｝上的关系R，A中各元素的等价类如下：[1]R=[4]R=[7]R=｛1,4,7｝[2]R=[5]R=｛2,5｝[3]R=[6]R=｛3,6｝53定理设R是非空集合A上的等价关系，则有：(1)对于每个x∈A，x[x]R

，即[x]R是A的非空子集。(2)[x]R

＝[y]R当且仅当xRy。(3)若x,y∈A且xy，则[x]R

[y]R=

。(4)[x]R

＝A,其中[x]R表示所有等价类的并集。证明：(1)因R自反，任取

x∈A均有xRx，故

x∈[x]R

，因此，[x]R。(2)设[x]R

＝[y]R，因为y∈[y]R,所以y∈[x]R,由[x]R的定义，可得：xRy

。设xRy,任取

z∈[y]R,则有

yRz,因R传递,故xRz，因此z∈[x]R,故[y]R

[x]R

。因R对称，所以有yRx，同理可证：[x]R

[y]R

。因此，[x]R=[y]R54（3）假设[x]R

[y]R

，则z使z∈[x]R

且z∈[y]R，即xRz，yRz，因R是对称的，故zRy，因R是传递的，所以有xRy，这与xy的题设相矛盾！因此，[x]R

[y]R

。（4）任取

x∈A，则[x]R

A。所以有[x]R

A。任取

z∈A，有z∈[z]R，[z]R[x]R

，故有z∈[x]R

。因此，A

[x]R

，所以[x]R

＝A。55定义设A是非空集合,πρ(A)(即π包含

A的若干子集)。若π满足以下三个条件，则称π为A上的一个划分:(1)对于每个S∈π，S≠；(2)对于任意B,C∈π，若B≠C，则BC＝；（若BC≠，则B＝C）(3)＝A。定义设R是集合A上的等价关系，所有等价类组成的集合称为A关于R的商集，记作A/R，即:

A/R＝｛[x]R｜x∈A｝例：上例中集合A＝｛1,2,3,4,5,6,7｝关于其等价关系R的商集A/R＝｛{1,4,7},{2,5},{3,6}｝56例：设A＝｛a,b,c｝，给定下列A的子集的集合：B＝｛｛a｝,｛b,c｝｝C＝｛｛a,b,c｝｝D＝｛｛a｝,｛b｝,｛c｝｝E＝｛｛a,b｝,｛b,c｝｝F＝｛｛a｝,｛c｝｝G＝｛,｛a｝,｛b｝,｛c｝｝问：这些集合中哪些是A上的划分？把π中的元素称为划分块，π中划分块的个数称为秩,有有穷个划分块的划分称为有穷划分,否则称为确无穷划分.57定理非空集合A上的等价关系R,决定了A上的一个划分，这个划分就是商集A/R。证明：根据商集定义A/R＝｛[x]R｜∈A｝、等价类的性质定理和划分的定义,商集A/R确是A上的一个划分。定理设π是非空集合A上的一个划分，若令：

Rπ

＝{〈x,y〉|存在S∈π使得x,y∈S｝即:xRπy当且仅当x和y在π的同一个划分块中，则Rπ必是A上的等价关系且

A／Rπ=π。称Rπ

为由π确定的等价关系。证明：首先证明：

Rπ

具有自反性、对称性、传递性。1）自反性:任取x∈A，由划分的定义可知:存在S∈π使得x∈S。所以，x,x∈S，故有xRπx

。582）对称性：设xRπy，于是存在S∈π使得x，y∈S，故有yRπx。3）传递性：设xRπy，yRπz，于是存在S∈π,T∈π使得x，y∈S且y，z∈T。由于π是划分，则由S与T有公共元y

可知：ST≠，故必有S=T，因此z∈S，所以xRπz。因此，Rπ

是A上的等价关系。

然后证明：

A／Rπ=π:先证明πA／Rπ:

任取S∈π,存在x∈S，则必有S=[x]R（why?）由[x]R∈A／Rπ,因此

S∈A／Rπ。后证明

A／Rπ

π:

59任取[x]R

∈A／Rπ

，其中x∈A。因π为A上的一个划分，则必有S∈π，使得x∈S，故必有S=[x]R

（why?）

因此，[x]R

∈π。由上述定理，可得如下结论：若A上的一个划分为π={C1,C2,…,Cn}，则π确定的等价关系就是:Rπ=（C1

C1）（

C2

C2）

…

（Cn

Cn）60上述定理表明，由等价关系能够产生一个划分。同样，由一个划分也可以产生一个等价关系。例:UX,IX分别是X上的全域关系和恒等关系，则

X/UX={X}，X/IX={{x}xX}例:设R是N上的“模6同余”关系，即：R={<x,y>|xNyN

6|(x-y)

},求各元素的等价类和商集解：等价类是：[0]R={0，6，12，18，…，}={xx=6nnN}[1]R={1，7，13，19，…，}={xx=6n+1nN}…[5]R={5，11，17，23，…，}={xx=6n+5nN}61下接第七章例:X={a,b,c,d,e},划分π={{a,b},{c},{d,e}},求划分π确定的X上的等价关系R。解：R={<a,b>,<b,a>,<d,e>,<e,d>}IXN/R={[0]R，[1]R

，[2]R

，[3]R

，[4]R

，[5]R

}62思考题1)有人说：“如果集合A上的二元关系R是对称的和传递的，则R必是自反的”。并给出了如下的证明：如果<x,y>R，则由R是对称的可知<y,x>R，从而由R是传递的得到<x,