等價(jià)關(guān)系與劃分課件

例：設(shè)整數(shù)集I上的模2同余關(guān)系為R,這是I上的等價(jià)關(guān)系。在R下，把I中所有與0有關(guān)系即與0等價(jià)的整數(shù)劃分為一類，記為E；與1等價(jià)的所有整數(shù)劃分為一類，記為O集合I中的元素或者屬于E，或者屬于O,且它們互不相交。由關(guān)系R把I分為兩類：E和O，這就是I的一個(gè)劃分。例：設(shè)整數(shù)集I上的模2同余關(guān)系為R,這是I上的等價(jià)關(guān)系。1三、等價(jià)關(guān)系與劃分定義2.14：設(shè)R是A上的等價(jià)關(guān)系,對于每個(gè)aA,與a等價(jià)的元素全體所組成的集合稱為由a生成的關(guān)于R的等價(jià)類,記為[a]R,即[a]R={x|xA,xRa},a稱為該等價(jià)類的代表元。在不會引起誤解的情況下,可把[a]R簡記為[a]。定義2.15：設(shè)R是A上的一個(gè)等價(jià)關(guān)系,關(guān)于R的等價(jià)類全體所組成的集合族稱為A上關(guān)于R的商集,記為A/R,即A/R={[a]|aA}。三、等價(jià)關(guān)系與劃分2例：整數(shù)集I上的模2同余關(guān)系R，其等價(jià)類為[0],[1]。其中[0]={…,-4,-2,0,2,4,…}=[2]=[4]=[-2]=[-4]=…[1]={…,-3,-1,1,3,…}=[3]=[-1]=[-3]=…因此A/R={[0],[1]}例:整數(shù)集I上的模n同余關(guān)系是I上的等價(jià)關(guān)系。I上關(guān)于R的等價(jià)類為：[0]={…,-2n,-n,0,n,2n,…}[1]={…,-2n+1,-n+1,1,n+1,2n+1,…}…[n-1]={…,-n-1,-1,n-1,2n-1,3n-1,…}這些類又稱I上模n同余類。I上關(guān)于R的商集I/R={[0],[1],…,[n-1]}例：整數(shù)集I上的模2同余關(guān)系R，其等價(jià)類為[0],[1]。3定理2.13：設(shè)R是A上的等價(jià)關(guān)系,則(1)對任一aA,有a[a];(2)若aRb,則[a]=[b];(3)對a,bA,如果(a,b)R,則[a]∩[b]=;此定理的(1)說明A中每個(gè)元素所產(chǎn)生的等價(jià)類是非空的定理的(2)、(3)說明：互相等價(jià)的元素屬于同一個(gè)等價(jià)類，而不等價(jià)的元素其所對應(yīng)的等價(jià)類之間沒有公共元素定理的(4)說明：A上等價(jià)關(guān)系R所對應(yīng)的等價(jià)類的并就等于A.由此定理說明A上等價(jià)關(guān)系R所對應(yīng)的等價(jià)類集合是A的一個(gè)劃分。該定理告訴我們，給定一個(gè)等價(jià)關(guān)系就唯一確定一個(gè)劃分。定理2.13：設(shè)R是A上的等價(jià)關(guān)系,則此定理的(1)說明4證明：(1)對任一aA，因?yàn)镽是A上的等價(jià)關(guān)系，所以有aRa(R自反)，則a[a]。(2)對a,bA,aRb,分別證明[a][b]，[b][a]。對任意x[a](目標(biāo)證明x[b]，即xRb)。下面證明[b][a]對任意x[b](目標(biāo)證明x[a]，即xRa)。(3)對a,bA,如果(a,b)R,則[a]∩[b]=采用反證法。假設(shè)[a]∩[b]≠，則至少存在x[a]∩[b]。證明：(1)對任一aA，因?yàn)镽是A上的等價(jià)關(guān)系，所以有aR5等價(jià)關(guān)系與劃分課件6例：設(shè)A={1,2,3,4}，R={(1,1),(2,2),(3,3),(4,4),(1,3),(2,4),(3,1),(4,2)}為等價(jià)關(guān)系。其等價(jià)類為[1]={1,3}[2]={2,4}[3]={1,3}[4]={2,4}劃分={[1],[2]}前面是給定等價(jià)關(guān)系唯一確定劃分，反過來，給定一個(gè)劃分，也可唯一確定一個(gè)等價(jià)關(guān)系。例：設(shè)A={1,2,3,4}，R={(1,1),(2,2),7設(shè)非空集A上劃分={A1,A2,…,An}，定義A上二元關(guān)系R：aRb當(dāng)且僅當(dāng)存在Ai,使得a,bAi。即R=(A1A1)∪(A2A2)∪…∪(AnAn)容易證明R是等價(jià)關(guān)系。定理2.14：集合A上的任一劃分可以確定A上的一個(gè)等價(jià)關(guān)系R。例：設(shè)A={a,b,c}的一個(gè)劃分={{a,b},{c}},由確定A上的一個(gè)等價(jià)關(guān)系R：R=({a,b}{a,b})∪({c}{c})={(a,a),(a,b),(b,a),(b,b),(c,c)}設(shè)非空集A上劃分={A1,A2,…,An}，定義A上二元關(guān)8定理2.15:設(shè)R1和R2是A上的等價(jià)關(guān)系,R1=R2當(dāng)且僅當(dāng)A/R1=A/R2。定理2.13和定理2.15說明集合A上的任一等價(jià)關(guān)系可以唯一地確定A的一個(gè)劃分。定理2.14和定理2.15說明集合A的任一劃分可以唯一地確定A上的一個(gè)等價(jià)關(guān)系。集合A上給出一個(gè)劃分和給出一個(gè)等價(jià)關(guān)系是沒有什么實(shí)質(zhì)區(qū)別的。設(shè)集合A上的等價(jià)關(guān)系為R1和R2,它們通過并和交運(yùn)算而得到的關(guān)系是不是等價(jià)關(guān)系?若是,其對應(yīng)的劃分與原來的兩個(gè)劃分有何聯(lián)系。定理2.15:設(shè)R1和R2是A上的等價(jià)關(guān)系,R1=R2當(dāng)且9四、劃分的積與和1.劃分的積定理2.16：設(shè)R1和R2是A上的等價(jià)關(guān)系,則R1∩R2是A上的等價(jià)關(guān)系。定義2.16：設(shè)R1和R2是A上的等價(jià)關(guān)系,由R1和R2確定的A的劃分分別為1和2,A上的等價(jià)關(guān)系R1∩R2所確定的A的劃分,稱為1與2劃分的積,記為1·2。定義2.17：設(shè)和'是A的劃分,若'的每一塊包含在的一塊中,稱'細(xì)分,或稱'加細(xì)。四、劃分的積與和10例：'={{1},{2},{3,4}}，={{1,2},{3,4}}因?yàn)閧1}{1,2}，{2}{1,2}，{3,4}{3,4}，所以'細(xì)分若'細(xì)分,則與它們對應(yīng)的二元關(guān)系R'和R它們之間有何聯(lián)系？例：'={{1},{2},{3,4}}，={{1,2},11(1)若'細(xì)分,則與它們對應(yīng)的二元關(guān)系R'和R滿足R'R。證明：對任意(a,b)R‘，目標(biāo)是(a,b)R(2)若R'R，是否有'細(xì)分？證明：對任意S‘’,目標(biāo)是SS‘S定理2.17：設(shè)',是A的劃分,它們確定A上的等價(jià)關(guān)系分別為R,R',則'細(xì)分當(dāng)且僅當(dāng)R'R。(1)若'細(xì)分,則與它們對應(yīng)的二元關(guān)系R'和R滿足R'12定理2.18：設(shè)1,2是A的劃分,則(1)1·2細(xì)分1與2。(2)設(shè)'是A的劃分,若'細(xì)分1與2,則'細(xì)分1·2。證明：(1)設(shè)1和2分別對應(yīng)的A上關(guān)系是R1和R2，則1·2對應(yīng)的關(guān)系為R1∩R2。(2)設(shè)'對應(yīng)A上關(guān)系是R'，1和2分別對應(yīng)的A上關(guān)系是R1和R2，則1·2對應(yīng)的關(guān)系為R1∩R2。定理2.18：設(shè)1,2是A的劃分,則132.劃分的和設(shè)集合A上的等價(jià)關(guān)系為R1和R2,容易證明R1∪R2是A上的自反和對稱關(guān)系,但不是A上的等價(jià)關(guān)系。然而R1∪R2的傳遞閉包是A上的等價(jià)關(guān)系。定理2.19:設(shè)R1和R2是集合A上的等價(jià)關(guān)系,則(R1∪R2)+是A上的等價(jià)關(guān)系。定義2.18:設(shè)R1和R2是A上的等價(jià)關(guān)系,R1和R2確定A的劃分分別為1和2。A上的等價(jià)關(guān)系(R1∪R2)+所確定A的劃分稱為1與2劃分的和,記為1+2。2.劃分的和14定理2.20：設(shè)1,2是A的劃分,則(1)1與2細(xì)分1+2；(2)設(shè)'是A的劃分,若1與2細(xì)分',則1+2細(xì)分'。證明：(1)設(shè)1和2分別對應(yīng)的A上關(guān)系是R1和R2，則1+2對應(yīng)的關(guān)系為(R1∪R2)+

。(2)設(shè)'對應(yīng)A上關(guān)系是R'，1和2分別對應(yīng)的A上關(guān)系是R1和R2，則1+2對應(yīng)的關(guān)系為(R1∪R2)+

。定理2.20：設(shè)1,2是A的劃分,則152.7次序關(guān)系集合中還有一種重要的關(guān)系：次序關(guān)系。它可用來比較集合中元素的次序,其中最常用的是偏序關(guān)系和全序關(guān)系。1.偏序關(guān)系定義2.19,2.20:設(shè)R是集合A上的二元關(guān)系,若R是自反的,反對稱的和傳遞的,則稱R是A上的偏序關(guān)系。又記為≤(注意,此符號在這里并不意味著小于或等于)。若集合A具有偏序關(guān)系R,則稱A為偏序集,記為(A,R)。2.7次序關(guān)系集合中還有一種重要的關(guān)系：次序關(guān)系。它可用16實(shí)數(shù)集R上的小于或等于關(guān)系≦；正整數(shù)集Z+上的整除關(guān)系；集合A的冪集P(A)上的包含關(guān)系。由于它們都是偏序關(guān)系，因此(R,≦)(Z+,|),(P(A),)都是偏序集。偏序集必須有一個(gè)具體給定的偏序關(guān)系例：A={1,2},P(A)={,{1},{2},{1,2}},則A的冪集P(A)上的包含關(guān)系{(,),(,{1}),(,{2}),(,{1,2}),({1},{1}),({1},{1,2}),({2},{2}),({2},{1,2}),({1,2},{1,2})}實(shí)數(shù)集R上的小于或等于關(guān)系≦；17定義：對于集合A上的偏序關(guān)系R,如果A中兩個(gè)元素a,b有aRb,則稱a與b是可比較的。在上例中，與,{1},{2}與{1,2}都是可以比較的，而{1}與{2}無包含關(guān)系，故不可比較由此可見：偏序集合中任意兩個(gè)元素不一定可比較的。但對于實(shí)數(shù)集上的小于或等于關(guān)系≦，對任意兩個(gè)實(shí)數(shù)x,y,或者x≦y,或者y≦x，必有一個(gè)成立，故x和y是可以比較的。全序關(guān)系定義：對于集合A上的偏序關(guān)系R,如果A中兩個(gè)元素a,b有a18定義2.22,2.23：設(shè)≤是集合A上的二元關(guān)系,如果對于A中任意兩個(gè)元素a,bA,必有a≤b或b≤a,則稱≤是A上的全序關(guān)系(或稱線性次序關(guān)系)。而該集合稱為全序集或線性次序集,記為(A,≤)。整數(shù)集I上的小于或等于關(guān)系≦是全序關(guān)系,但I(xiàn)上的整除關(guān)系/不是全序關(guān)系。而前面給出的冪集P(A)上的關(guān)系也不是全序關(guān)系。定義2.22,2.23：設(shè)≤是集合A上的二元關(guān)系,如果對192．Hasse圖偏序集(A,R)可以通過圖形表示,該圖叫哈斯圖。是對關(guān)系圖的簡化。(1)由于偏序關(guān)系是自反的，即對每個(gè)元素a,都有aRa，因此在圖上省去自環(huán)(2)由于偏序關(guān)系是傳遞的，即若有aRb,bRc則必有aRc,因此省去a與c之間的連線(3)對于aRb,規(guī)定b在a的上方，則可省去箭頭。這樣的圖稱為哈斯圖。2．Hasse圖20A={1,2},畫出A的冪集P(A)上的包含關(guān)系的哈斯圖P(A)={,{1},{2},{1,2}}A={1,2},畫出A的冪集P(A)上的包含關(guān)系的哈斯圖21例A={2,3,6,12,24,36},畫出偏序集(A,/)的哈斯圖。例A={2,3,6,12,24,36},畫出偏序22設(shè)A上的小于等于關(guān)系≦,A={1,2,3,4,5,6},畫出偏序集(A,≦)的哈斯圖。設(shè)A上的小于等于關(guān)系≦,A={1,2,3,4,5,233.擬序關(guān)系定義2.21:集合A上的二元關(guān)系R是反自反的和傳遞的,稱R為A上的擬序關(guān)系。稱(A,R)為擬序集,或記為(A,<)(注意,此符號<在這里也不意味著小于)。常見的擬序關(guān)系有：實(shí)數(shù)集R上的小于關(guān)系<；集合A的冪集P(A)上的真包含關(guān)系。3.擬序關(guān)系24定理2.2