等价关系85.ppt
18页
第八章 關係(Relations),§8.1 Relations and Properties §8.2 n-ary Relations and Their Applications§8.3 Representing Relations§8.4 Closures of Relations§8.5 Equivalence Relations§8.6 Partial Orderings,等價關係(§8.5),定義：集合A上的關係，如果有反身性、對稱性和遞移性，則稱之為等價關係(equivalence relation) 在等價關係中，兩個有關係的元素可視為等價的(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 (mod m)} 是整數集合上的等價關係解：a b (mod m)若且唯若m整除a b a a = 0能被m整除，故a a(mod m)，因而模m同餘關係是有反身性的 假設a b (mod m)，那麼a b能被m整除，即a b = km，其中k是整數因此b a = (k)m，即b a (mod m)故模m同餘關係是有對稱性的 接著假設a b (mod m)和b c (mod m)，可知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 (mod m)即，模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是個等價關係例：證明正整數集合上的“整除”關係不是等價關係解：由前面章節中的範例，我們知道“整除”關係是有反身性與遞移性的 然而，它並沒有對稱性（例如：24但42）所以，正整數上的“整除”關係並不是等價關係例：令R為實數集合上的關係xRy若且唯若x與y的差小於1，也就是x y< 1證明R不是個等價關係解：R有反身性：當x為實數時，x x= 0 < 1 若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.9 < 1 而且yRz，因為y z=1.9 1.1= 0.8 < 1 然而xRz，因為x z=2.8 1.1= 1.7 > 1等價類,定義：設R是集合A上的等價關係與A中的元素a有關係的所有元素的集合稱做a的等價類(equivalence class)，記作[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 + kk為整數}其中[0] 為所有整數所成的集合例：對於模4同餘關係，0和1的等價類分別是什麼？解： 0的等價類包含滿足a 0 (mod 4)的所有整數a這個類中的元素是被4整除的整數因此，就這個關係而言，0的等價類是[0] = {…, 8, 4, 0, 4, 8, …} 1的等價類包含滿足a 1 (mod 4)的所有整數a這個類中的元素是被4整除餘數為1的整數因此，就這個關係而言，1的等價類是[1] = {…, 7, 3, 1, 5, 9, …}。
用任何正整數m代替4很容易能把前例加以推廣模m同餘關係的等價類別叫做模m同餘類(congruence classes module m)整數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所以，,,等價類與分割,定理：設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) 對所有的 I A ≠ Ø (2) 當 ≠ A A = Ø (3)例：假設S = {1, 2, 3, 4, 5, 6} 集合A1 = {1, 2, 3}、A2 = {4, 5}和A3 = {6}構成S的一個 分割因為這些集合互不相交，而且聯集是S定理：設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中所有位元字串集合的分割為何？,,,,,,,,。
