等价关系(85)

第八章關係(Relations)§8.1RelationsandProperties§8.2n-aryRelationsandTheirApplications§8.3RepresentingRelations§8.4ClosuresofRelations§8.5EquivalenceRelations§8.6PartialOrderings等價關係(§8.5)定義：集合A上的關係，如果有反身性、對稱性和遞移性，則稱之為等價關係(equivalencerelation)。在等價關係中，兩個有關係的元素可視為等價的(equivalent)，記為a~b。例：設R是整數集合上的關係，aRb若且唯若a=b或a=b。並不難證明R是有反身性、對稱性和遞移性的。因此R是等價關係。而3~3。例：設R是實數集合上的關係，aRb若且唯若ab是整數。試問R是等價關係嗎？解：對所有的實數a來說，aa=0是整數，因此對所有的實數aRa，即，R是有反身性的。假設aRb，那麼ab是整數，ba也會是整數。因此有bRa。即，故R是有對稱性的。如果aRb和bRc，那麼ab和bc都是整數，所以ac=(ab)＋(bc)也是整數，因此aRc。故R是有遞移性的。綜合上述，可知R是個等價關係。模m同餘設m是大於1的正整數。證明關係R={(a,b)｜ab(modm)}是整數集合上的等價關係。解：ab(modm)若且唯若m整除ab。aa=0能被m整除，故aa(modm)，因而模m同餘關係是有反身性的。假設ab(modm)，那麼ab能被m整除，即ab=km，其中k是整數。因此ba=(k)m，即ba(modm)。故模m同餘關係是有對稱性的。接著假設ab(modm)和bc(modm)，可知m整除ab和bc。因此存在整數k和l，使得ab=km和bc=lm。將兩個等式相加，ac=(ab)＋(bc)=km＋lm=(k＋l)m。故ac(modm)。即，模m同餘關係是有遞移性的。綜合上述，可知模m同餘關係是等價關係。例：設R是英文字母所形成之字串集合上的關係，aRb若且唯若l(a)=l(b)，其中l(x)表示字串x的長度。試問R是等價關係嗎？解：因為l(a)=l(a)，只要a是一個字串，就有aRa，故R是有反身性的。假設aRb，即l(a)=l(b)，那麼有bRa，因為l(b)=l(a)。因此R是有對稱性的。假設aRb和bRc，則l(a)=l(b)和l(b)=l(c)。因此l(a)=l(c)，即aRc。所以R是有遞移性的。由於R是反身、對稱和遞移的，故R是等價關係。例：令n為正整數，S為位元字串集合。假設Rn為S上的關係，sRnt若且唯若s=t，或是兩字串s與t之前n個字元完全一樣。故，字串長度小於n的都只與自身有關係。證明對所有的位元字串集合和正整數n，Rn都是S上的等價關係。解：關係Rn是有反身性的，因為對S中的字串s而言，s=s，即sRns。若sRnt，則s=t，或是兩字串s與t之前n個字元完全一樣。也可說t=s，或是兩字串t與s之前n個字元完全一樣。所以tRns，即Rn是有對稱性的。假設sRnt與tRnu，則s=t，或是兩字串s與t之前n個字元完全一樣；以及t=u，或是兩字串t與u之前n個字元完全一樣。所以，我們可推論出s=u（兩字串的長度都不大於n），或是兩字串s與u之前n個字元完全一樣（兩字串的長度都大於等於n）。所以sRnu，也就是Rn是有遞移性的。由上述證明可得Rn是個等價關係。例：證明正整數集合上的“整除”關係不是等價關係。解：由前面章節中的範例，我們知道“整除”關係是有反身性與遞移性的。然而，它並沒有對稱性（例如：24但42）。所以，正整數上的“整除”關係並不是等價關係。例：令R為實數集合上的關係。xRy若且唯若x與y的差小於1，也就是xy1。證明R不是個等價關係。解：R有反身性：當x為實數時，xx=01。若xRy，則xy1。由於yx=xy1，故yRx。所以，R是有對稱性的。但是，R沒有遞移性。令x=2.8，y=1.9，z=1.1，則xRy，因為xy=2.81.9=0.91。而且yRz，因為yz=1.91.1=0.81。然而xRz，因為xz=2.81.1=1.71。等價類定義：設R是集合A上的等價關係。與A中的元素a有關係的所有元素的集合稱做a的等價類(equivalenceclass)，記作[a]R，當只考慮一個關係時，可以省去下標R寫作[a]。換句話說，如果R是集合A上的等價關係，元素a的等價類是[a]R={s︱(a,s)R}。其中a稱為這個等價類的代表元(representative)。所有在等價類中的元素都可以當作這個等價類的代表。例：就aRb若且唯若a=b或a=b這個在整數集合上的等價關係而言，其等價類為何？解：在這個等價關係中一個整數等價於自身和它的加法反元素，即[a]={a,a}。這個集合包含兩個不同的整數，除非a=0。例如，[7]={7,7}、[5]={5,5}、[0]={0}。例：就aRb若且唯若ab是整數這個在實數上的等價關係而言，其等價類為何？解：[a]={a+kk為整數}。其中[0]為所有整數所成的集合。例：對於模4同餘關係，0和1的等價類分別是什麼？解：0的等價類包含滿足a0(mod4)的所有整數a。這個類中的元素是被4整除的整數。因此，就這個關係而言，0的等價類是[0]={…,8,4,0,4,8,…}。1的等價類包含滿足a1(mod4)的所有整數a。這個類中的元素是被4整除餘數為1的整數。因此，就這個關係而言，1的等價類是[1]={…,7,3,1,5,9,…}。用任何正整數m代替4很容易能把前例加以推廣。模m同餘關係的等價類別叫做模m同餘類(congruenceclassesmodulem)。整數a之模m的同餘類記作[a]m，[a]m={…,a2m,am,a,a＋m,a＋2m,…}。由前例得出[0]4={…,8,4,0,4,8,…}[1]4={…,7,3,1,5,9,…}。例：若R3為位元字串集合S上的關係。sR3t若且唯若s=t，或是兩字串s與t之前3個字元完全一樣。字串0111所在的等價類為何？解：與0111等價的字串，其前三個位元與0111相同，也就是其前三個位元必須是011。所以，,01111,01110,01101,01100,0111,0110,01101113R等價類與分割定理：設R是集合A上的等價關係。當a與b是A中的元素時，下面的命題是等價的。(i)aRb(ii)[a]=[b](iii)[a][b]≠Ø證明：(i)(ii)。假設aRb，若c[a]，則aRc。根據aRb與R的對稱性，有bRa。又由於R是有遞移性的，而且bRa和aRc，得到bRc，因而有c[b]。得證[a][b]。同理可證[b][a]。故[a]=[b]。(ii)(iii)。假設[a]=[b]。因為[a]是非空的(由於R的反身性，a[a])。故，[a][b]=[a]≠Ø。(iii)(i)。假設[a][b]≠Ø。則存在元素c使得c[a]以及c[b]。換句話說，aRc和bRc。由對稱性有cRb。再根據遞移性，aRc和cRb，可得aRb。集合S的分割(partition)是一組S之不相交非空子集，而且它們的聯集正好等於S。換句話說，一組子集A，I(其中I是一個指標集合)構成S的分割若且唯若(1)對所有的IA≠Ø(2)當≠AA=Ø(3)例：假設S={1,2,3,4,5,6}。集合A1={1,2,3}、A2={4,5}和A3={6}構成S的一個分割。因為這些集合互不相交，而且聯集是S。SAI定理：設R是集合S上的等價關係。那麼R的等價類構成S的分割。反之，設定集合S的分割{A︱I}，則存在著等價關係R，它以集合A，I作為等價類。例：列出等價關係R中的有序對，由給定的等價類A1={1}、A2={2,3}和A3={4}來產生。解：在分割中的子集合為R的等價類。序對(a,b)R若且唯若a和b是在同一個分割子集合內。序對(1,1)屬於R，因為A1={1}是一個等價類別；序對(2,2),(2,3),(3,3)和(3,2)屬於R，因為A2={2,3}；最後序對(4,4)屬於R，因為A3={4}是一個等價類別。除了已列出的序對之外，沒有其他的序對屬於R。即，R={(1,1),(2,2),(2,3),(3,3),(3,2),(4,4)}例：由模4同餘產生的整數分割之集合是什麼？解：存在4個同餘類：[0]4,[1]4,[2]4和[3]4。它們是集合[0]4={…,8,4,0,4,8,…}[1]4={…,7,3,1,5,9,…}[2]4={…,6,2,2,6,10,…}[3]4={…,5,1,3,7,11,…}這些同餘類別是不相交的，並且每個整數恰好在它們之中的一個。換句話說，正如定理所說，這些同餘類別構成一個分割。例：sR3t若且唯若s=t，或是兩字串s與t之前3個字元完全一樣的。關係R3中所有位元字串集合的分割為何？}0{03R}1{13R}00{003R}01{013R}10{103R}11{113R},11111,11110,11101,11100,1111,1110,111{111},11011,11010,11001,11000,1101,1100,110{110},10111,10110,10101,10100,1011,1010,101{101},10011,10010,10001,10000,1001,1000,100{100},01111,01110,01101,01100,0111,0110,011{011},01011,01010,01001,01000,0101,0100,010{010},00111,00110,00101,00100,0011,0010,001{001},00011,00010,00001,00000,0001,0000,000{00033333333RRRRRRRR