課堂演示2013dm集合的積集

1、第七章 關(guān)系7.1 集合的笛卡爾積集 7.2 二元關(guān)系的基本概念 7.3 二元關(guān)系的性質(zhì)7.4 二元關(guān)系的閉包運算7.5 等價關(guān)系和集合的劃分 7.6 偏序關(guān)系和格 7.7 鏈與反鏈 等價關(guān)系定義1 A是一個非空集, R是A上的一個二元關(guān)系， 若R有自反性、 對稱性、 傳遞性， 則說R是A上的等價關(guān)系。等價類、代表元 若R是A上的等價關(guān)系， a是A中任意一個元素，集合 xA(x,a) R 稱為集合A關(guān)于關(guān)系R的一個等價類，記 aR= xA(x,a) R, 其中a叫代表元。例1A=1,2,3,R=(1,1), (2,2), (3,3), (1,2), (2,1) 則R是A上一個等價關(guān)系。 顯然

2、1R1,2 2R1,2 3R3 1 2 3例 試畫出關(guān)系圖 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)設(shè)A是計算機系的學生的集合， R是A上一個二元關(guān)系，使得 (a, b) R當且僅當a和b住在同一宿舍里。還可以引入A上的其它等價關(guān)系如下：R是A上一個二元關(guān)系，使得(a, b) R當且僅當a和b是學習相同的專業(yè)R是A上一個二元關(guān)系，使得(a, b) R當且僅當a和b同齡不難驗證， R是A上一個等價關(guān)系。例3 (p83) Z是整數(shù)集，在Z上定義一個二元關(guān)系R：對于任意的

3、x,yZ, (x,y) R當且僅當x與y被5除余數(shù)相同。R是Z上的等價關(guān)系。顯然, x與y被5除同余的充要條件是5|(x-y), 這里符號a|b表示a整除b，a與b是兩個整數(shù)。對于 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上的等價關(guān)系。例設(shè)A=1,2,3,并設(shè)是AA上的

4、關(guān)系，其定義為：若ad=bc， 則(a,b) (c,d)。證明 是一個等價關(guān)系。 證： (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上的一個等價關(guān)系，集合xRxA 叫集合A的商集合，記為 A/R= xRxA 例 A=1,2,3

5、, 顯然 A/R= 1R , 3R = 1,2 , 3 1 2 3例 Z是整數(shù)集，在Z上定義一個二元關(guān)系R： 對于任意的 x,yZ, (x,y) R 當且僅當x與y被5除余數(shù)相同。 則 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上的一個等價關(guān)系，則有(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上的一個等價關(guān)系，則有(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試判斷這些子集是不是一個劃分.集合的劃分等價關(guān)系若給定集合A上的一個劃分，可以在A上定義一個二元關(guān)系R，使得R成為A上的

8、一個等價關(guān)系，且有 A/R 定理2 (p84)A是一個非空集合，是A上的一個劃分， = AB，AA在A上定義一個二元關(guān)系R： 對于任意的x,yA， (x,y) R當且僅當存在B，x,yA. 則 R是A上一個等價關(guān)系，而且 A/R定理2 先證 R是A上的等價關(guān)系對于任意的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上的等價關(guān)系。定理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 求該劃分所對應(yīng)的等價關(guān)系.解: R=(a,a), (b,b), (c,c), (b,c),(c,b),(d,d)例 設(shè)A=1,2,3,求出A上所有的等價關(guān)系.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， 它們相應(yīng)的等價關(guān)系分別為R1和R2 。 則 R1R2 當且僅當 是 1 是2 的加細。定理3的證明：“”若R1R2 則 1 是2 的加細對于任意的B，A1，存在 aA，A=aR1。對于任意的x aR1=A，所以有(x,a) R1。根據(jù)假設(shè)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根據(jù)假設(shè)1是2的加細，則存在B，AA于是yR1=AA，yA，且xA故(x,y) R2.所以R1R2得證。例設(shè)A是南京理工大學的學生組成的集合。學生們分別屬于不同的分院，按學院劃分R1是A的一個劃分。學生們也分別屬于不同的系，按系劃分R2也是 A的一個劃分。顯然， R1與R2都是等價關(guān)系，而且 R2R1所以，R2是R1的加細。例 (2

13、006年碩士研究生試題)已知R是A上的等價關(guān)系, 證明R2也是A上的等價關(guān)系。證: (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上自反的、對稱的二元關(guān)系, 證明t(R)是A上的等價關(guān)系。證明： 因為t(R)= Ri是傳遞閉包，即滿足傳遞性，即要證明自反性與對稱性。顯然，只需要證明Ri具有自反性與對稱