课堂演示2013dm集合的积集

1、第七章 关系7.1 集合的笛卡尔积集 7.2 二元关系的基本概念 7.3 二元关系的性质7.4 二元关系的闭包运算7.5 等价关系和集合的划分 7.6 偏序关系和格 7.7 链与反链 等价关系定义1 A是一个非空集, R是A上的一个二元关系， 若R有自反性、 对称性、 传递性， 则说R是A上的等价关系。等价类、代表元 若R是A上的等价关系， a是A中任意一个元素，集合 xA(x,a) R 称为集合A关于关系R的一个等价类，记 aR= xA(x,a) R, 其中a叫代表元。例1A=1,2,3,R=(1,1), (2,2), (3,3), (1,2), (2,1) 则R是A上一个等价关系。 显然

2、1R1,2 2R1,2 3R3 1 2 3例 试画出关系图 A=1,2,3,4,5,6,7,8 R=(x,y) x,y A, xy(mod 3)其中xy(mod 3)的含义就是x-y可以被3整除.14736258例2 (p83)设A是计算机系的学生的集合， R是A上一个二元关系，使得 (a, b) R当且仅当a和b住在同一宿舍里。还可以引入A上的其它等价关系如下：R是A上一个二元关系，使得(a, b) R当且仅当a和b是学习相同的专业R是A上一个二元关系，使得(a, b) R当且仅当a和b同龄不难验证， R是A上一个等价关系。例3 (p83) Z是整数集，在Z上定义一个二元关系R：对于任意的

3、x,yZ, (x,y) R当且仅当x与y被5除余数相同。R是Z上的等价关系。显然, x与y被5除同余的充要条件是5|(x-y), 这里符号a|b表示a整除b，a与b是两个整数。对于 xZ，有5|(x-x), 即(x,x) R，亦即R有自反性。对于 x,yZ，若(x,y) R, 即5|(x-y)， 也即5|(y-x), 所以(y,x) R， 亦即R有对称性。对于 x,y,zZ，若(x,y) R, 且(y,z) R， 即5|(x-y)，且5|(z-y)，则 5|(x-y)+(y-z)， 亦即5|(x-z)，所以(x,z) R，亦即R有传递性。故R是A上的等价关系。例设A=1,2,3,并设是AA上的

4、关系，其定义为：若ad=bc， 则(a,b) (c,d)。证明 是一个等价关系。 证： (1) 自反性 对于(a,b)AA, 因为ab=ba， 则有(a,b) (a,b) 。 (2) 对称性 如果(a,b) (c,d)，即有 ad=bc， 即有 cb=da， 故有(c,d) (a,b)。 (3) 传递性 如果(a,b) (c,d)，(c,d) (e,f)， 即有 ad=bc, cf=de, 于是有 adcf=bcde 即 af=be, 故有 (a,b)(e,f)商集合 定义2 A是一个非空集合，R是A上的一个等价关系，集合xRxA 叫集合A的商集合，记为 A/R= xRxA 例 A=1,2,3

5、, 显然 A/R= 1R , 3R = 1,2 , 3 1 2 3例 Z是整数集，在Z上定义一个二元关系R： 对于任意的 x,yZ, (x,y) R 当且仅当x与y被5除余数相同。 则 Z/R= 0R, 1R, 2R, 3R, 4R 这里 0R=xZnZ, x=5n1R=xZnZ, x=5n+12R=xZnZ, x=5n+23R=xZnZ, x=5n+34R=xZnZ, x=5n+4定理1 A是一个非空集合，R是A上的一个等价关系，则有(1) xR=A，(2) 对于任意的x,yA， 若xRyR，则xR=yR。xA证明(1) 显然，对于任意的xA，有xRA， 所以 xR A. 反之，对于任意的x

6、 A，则x x， 即 x xR ， 所以 A xR xAxAxA定理1 证明 若xRyR，则xR=yR 证明(2): 对于任意的x,y A，若xRyR， 则存在axRyR。 由axR，得(a,x)R； 再由R的对称性，有(x,a) R。 由ayR, 有(a,y) R。 利用R的传递性，得(x,y)R。 下面开始证明xR=yR。 对于任意的z xR，有(z,x) R, 又因为刚才已得到(x,y) R， 由R的传递性，得到(z,y) R, 所以有z yR。从而证得 xRyR。 同理可证yRxR。 所以最后得到xR=yR。定理1 A是一个非空集合，R是A上的一个等价关系，则有(1) xR=A，(2)

7、 对于任意的x,yA，若xRyR， 则xR=yR。(3) xR, 且xRA.(4) 若xRy, 则xR=yR.(5) 若xRy, 则xRyR=xA集合的划分定义3 A是一个非空集合，一个集合 = AB， A，且AA 称做集合A的一个划分，若 A=A 对于任意的,B，若AA，则 A=A，其中B是下标集。B例 商集合 A/R 是集合A上的一个划分。例考虑集合A=a,b,c,d的下列子集族: a, b,c, d a,b,c,d a,b,c,a,d , a,b, c,d a, b,c试判断这些子集是不是一个划分.集合的划分等价关系若给定集合A上的一个划分，可以在A上定义一个二元关系R，使得R成为A上的

8、一个等价关系，且有 A/R 定理2 (p84)A是一个非空集合，是A上的一个划分， = AB，AA在A上定义一个二元关系R： 对于任意的x,yA， (x,y) R当且仅当存在B，x,yA. 则 R是A上一个等价关系，而且 A/R定理2 先证 R是A上的等价关系对于任意的xA，存在B，xA， 即有x, xA, 所以有(x,x)R， 故R是自反的。对于任意的x,yA，若(x,y) R， 则存在B, x,yA, 即有y,xA, 所以有(y,x) R, 故R是对称的。对于任意x,y,zA，若(x,y) R 且(y,z) R， 则存在B，x,yA， 而且又存在B，y,zA。 因为 yAA，所以AA， 则

9、A=A，即xA，所以(x,z) R， 故R是传递的。所以 R是A上的等价关系。定理2 证明 A/R= 首先证明 A/R 。 对于任意的xRA/R ， 因为xA，故存在B，XA， 可以证明xR=A。 所以 A/R。再证明A/R。 对于任意的A， 因为A ，故存在xA， 可以证明有xR=A，即A=xR A/R。 所以 A/R。定理2 证明 A/R 对于任意的xRA/R ，因为xA，所以存在B，XA。 要证明xR=A。 对于任意的aA，有(a,x) R，则axR， 即有AxR； 反之, 对于任意的a xR，所以(a,x) R， 即存在B，a,xA。 因为xAA，所以AA，所以A=A， 从而有aA，所

10、以xRA。故xR=A。所以 A/R。例考虑集合A=a,b,c,d的一个划分: a, b,c, d 求该划分所对应的等价关系.解: R=(a,a), (b,b), (c,c), (b,c),(c,b),(d,d)例 设A=1,2,3,求出A上所有的等价关系.213213213213213 1 2 3 4 5R1=(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)R2=(1,1),(2,2),(2,3),(3,2),(3,3)R3=(1,1),(1,3),(3,1),(3,3),(2,2)R4=(1,1),(1,2),(2,1),(2,2),

11、(3,3)R5=(1,1),(2,2),(3,3)划分加细定义4 A是一个非空集合。1与2 是集合A上的两个划分，其中 1= AB，AA, 2= AB，AA, 若对于任意的B， 存在B，使得AA ， 则称1 是2 的加细。划分加细定理3 A是一个非空集合， 1与2 是A上的两个划分: 1= AB，AA, 2= AB，AA， 它们相应的等价关系分别为R1和R2 。 则 R1R2 当且仅当 是 1 是2 的加细。定理3的证明：“”若R1R2 则 1 是2 的加细对于任意的B，A1，存在 aA，A=aR1。对于任意的x aR1=A，所以有(x,a) R1。根据假设R1R2，得到(x,a) R2，所以

12、有x aR2。因为aR2A/R2=2 ，所以存在 B，aR2=A 2，所以得到xA，从而得到AA。所以1 是2 的加细。定理3的证明“”若1 是2 的加细，则R1R2。 对于任意的x,yA，若(x,y) R1，即x yR1，又因为A/R1=1，所以存在B，yR1=A根据假设1是2的加细，则存在B，AA于是yR1=AA，yA，且xA故(x,y) R2.所以R1R2得证。例设A是南京理工大学的学生组成的集合。学生们分别属于不同的分院，按学院划分R1是A的一个划分。学生们也分别属于不同的系，按系划分R2也是 A的一个划分。显然， R1与R2都是等价关系，而且 R2R1所以，R2是R1的加细。例 (2

13、006年硕士研究生试题)已知R是A上的等价关系, 证明R2也是A上的等价关系。证: (1) 自反性 对于aA, 因为R是自反的，即有 (a,a) R，故由定义知 (a,a) R2。 (2) 对称性 对于(a,b) R2, 由定义知: 存在c,使得(a,c) R，且 (c,b) R.由于R是对称的，有(c,a) R，且 (b,c) R.由R2定义知有 (b,a) R2。 (3) 传递性 对于(a,b) R2, (b,c) R2, 存在x,y,有：(a,x) R，且 (x,b) R.(b,y) R，且 (y,c) R.由于R具有传递性，则有 (x,c) R进而，由定义知，(a,c) R2.例 (2004年硕士研究生试题)已知R是集合A上自反的、对称的二元关系, 证明t(R)是A上的等价关系。证明： 因为t(R)= Ri是传递闭包，即满足传递性，即要证明自反性与对称性。显然，只需要证明Ri具有自反性与对称