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

。(2)設'對應A上關系是R'，1和2分別對應的A上關系是R1和R2，則1+2對應的關系為(R1∪R2)+

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