【正文】 定義 (equivalence relation) 設(shè)二元關(guān)系 R? A A。這里 A是非空的集合。 R是 A上的等價(jià)關(guān)系 ?R是自反的、對(duì)稱的、傳遞的。 ? 顯然 ?(R) = ?(R) = A (因?yàn)榈葍r(jià)關(guān)系是自反的 )； 例 。 例 2 .平面幾何中的三角形間的相似關(guān)系是等價(jià)關(guān)系。 例 3 .平面幾何中的三角形間的全等關(guān)系是等價(jià)關(guān)系。 61 離散數(shù)學(xué) 例 4 .平面幾何中的直線間的平行關(guān)系是等價(jià)關(guān)系。 例 5 .設(shè) N是自然數(shù)集， m是一正整數(shù)， R={(a,b) :a?N ? b?N ? a ? b (mod m)} 由等價(jià)關(guān)系的定義知 R是 N上等價(jià)關(guān)系；我們稱 R是 N上的模 m同余關(guān)系。 例 A上的幺關(guān)系、全關(guān)系都是等價(jià)關(guān)系。 例 A上的空關(guān)系不是等價(jià)關(guān)系 (因?yàn)榭贞P(guān)系不自反 ) 。 例 二元關(guān)系 R? A A,這里 A={a,b,c} , R={(a,a), (b,b), (c,c), (b,c),(c,b)} 則 R是 A上的等價(jià)關(guān)系。其關(guān)系圖如下 62 離散數(shù)學(xué) ?等價(jià)關(guān)系的實(shí)質(zhì)是將集合 A中的元素進(jìn)行分類。 定義 類 (塊 )(equivalence classes(block)) 設(shè) R是非空集合 A上的等價(jià)關(guān)系。對(duì)任何元素 a?A，由a生成的 (或者說是 由 a誘導(dǎo)出的 )關(guān)于 R的等價(jià)類定義為 {b :b?A?bRa} 記為 ?a?R. (顯然有 ?a?R ? A) 。同時(shí)稱 a為等價(jià)類 ?a?R的代表元。 b c a 63 離散數(shù)學(xué) 定義 3. 設(shè) R是非空集合 A上的等價(jià)關(guān)系。我們定義 集合 ? R = {?a?R : a?A} (注意：應(yīng)去掉重復(fù)的類！ ) 為集合 A關(guān)于等價(jià)關(guān)系 R的商集。記為 A/R。稱 A/R中元素的個(gè)數(shù)為 R的秩。 例 N是自然數(shù)集， m是一個(gè)正整數(shù)。 R是 N上的模 m同余關(guān)系，即 R={(a,b) : a? N ? b? N ? a ? b (mod m)} 。 對(duì)于任何 自然數(shù) a， b? N ， aRb ? a ? b (mod m)?(?k?I)(ab=km) ； 由等價(jià)關(guān)系的定義知 R是 N上的等價(jià)關(guān)系； 對(duì)于任何 自然數(shù) a? N ，以 a為代表元的等價(jià)類 ?a?R = ?a?m ={b :b?N?b ? a (mod m)}； 自然數(shù)集 N關(guān)于等價(jià)關(guān)系 R的商集 64 離散數(shù)學(xué) N/R= ? R = {?0?R,?1?R,?2?R,?3?R,…, ?m1?R } ； 或者記作 Nm = N/? = ?? = {?0?m,?1?m,?2?m,?3?m,…, ?m1?m}； 商集 N/R共有 m個(gè)等價(jià)類，故 R的秩為 m； 特別地，取 m =5，則有 N５ = {?0?５ ,?1?５ ,?2?５ ,?3?５ ,?4?5}； 又如 ?3?５ ={3,8,13, …,5k+3, …} (這里： k?N) 。 例 8中 等價(jià)關(guān)系 R的 等價(jià)類為 ?a?R = {a}, ?b?R = ?c?R = {b,c} ； 其商集為 A/R= ?R = {?a?R , ?b?R }={{a},{b,c}}； 故其秩為 2。 65 離散數(shù)學(xué) 定理 1. 設(shè) R是非空集合 A上的等價(jià)關(guān)系。對(duì)任意的 a,b?A，有 (1)a??a?R (故 ?a?R ≠?) ； (2)aRb (即 (a,b)?R) ? ?a?R = ?b?R ； (3)() ?a?R∩ ?b?R≠? ? ?a?R = ?b?R (? aRb，即 (a,b)?R) ； () (a,b)?R ? ?a?R∩ ?b?R = ? ； (4)兩個(gè)等價(jià)類 ?a?R和 ?b?R ，要么完全重合 (即 ?a?R = ?b?R )，要么不交 (即 ?a?R∩ ?b?R = ? )；二者必居其一，也只居其一 。 [證 ].（采用邏輯法） (1)對(duì)任何元素 a，有 a?A ?aRa (R是 等價(jià)關(guān)系，故 R自反 ) 66 離散數(shù)學(xué) ?a??a?R ??a?R ≠? ； (2) ?先證： aRb??a?R = ?b?R 為證 ?a?R = ?b?R ，須 證 (a) ?a?R ??b?R 對(duì)任何元素 x? A ，有 x??a?R ? xRa ?xRa?aRb (已知條件： aRb) ?xRb (R是 等價(jià)關(guān)系，故 R傳遞 ) ?x??b?R 所以 ?a?R ? ?b?R 67 離散數(shù)學(xué) (b) ?b?R ? ?a?R 對(duì)任何元素 x? A ，有 x??b?R ? xRb ?xRb?aRb (已知條件： aRb) ?xRb?bRa (R是 等價(jià)關(guān)系，故 R對(duì)稱 ) ?xRa (R是 等價(jià)關(guān)系，故 R傳遞 ) ? x??a?R 所以 ?b?R ? ?a?R 綜合 (a)和 (b)，即得 ?b?R = ?a?R ； ?次證： ?a?R = ?b?R ? aRb ?a?R ≠? (本定理的 (1)) ?(?x0?A)(x0??a?R ) 68 離散數(shù)學(xué) ?(?x0?A)(x0??a?R ? x0??b?R ) (已知條件： ?a?R = ?b?R ) ?(?x0?A)(x0Ra?x0Rb ) ?(?x0?A)(aRx0?x0Rb ) (R是 等價(jià)關(guān)系，故 R對(duì)稱 ) ?aRb (R是 等價(jià)關(guān)系，故 R傳遞 且 ?xp?p ) (3)() ?a?R∩?b?R≠? ?(?x0?A)(x0??a?R ∩?b?R) ?(?x0?A)(x0??a?R ? x0??b?R ) ?(?x0?A)(x0Ra?x0Rb ) ?(?x0?A)(aRx0?x0Rb ) (R是 等價(jià)關(guān)系，故 R對(duì)稱 ) ?aRb (即 (a,b)?R) (R是 等價(jià)關(guān)系，故 R傳遞 且 ?xp?p ) 69 離散數(shù)學(xué) ? ?a?R = ?b?R (本定理的 (2)) ； () (整體采用反證法 ) 若 (a,b)?R ，則 ?a?R∩ ?b?R = ? 。否則若 ?a?R∩?b?R≠? ? ?a?R = ?b?R (本定理的 ()) ?aRb (本定理的 (2)) ?(a,b)?R 這就與已知條件： (a,b)?R 矛盾； (4)對(duì)任何序偶 (a,b) (a,b)?A A ?(a,b)?R?(a,b)?R (二分法，互斥 ) ?(?a?R = ?b?R)?(?a?R∩ ?b?R = ?) (本定理的 ()和 ()，互斥 ) 。 70 離散數(shù)學(xué) 定義 4. 設(shè) R和 S是非空集合 A上的兩個(gè)等價(jià)關(guān)系。若R?S ，則我們稱 R細(xì)于 S ， 或 S粗于 R 。 例 A是 一 非空集 。 則 (1)A上最細(xì)的 等價(jià) 關(guān)系是幺關(guān)系；即 R細(xì) =IA ， A/R細(xì) ={{a} : a?A} ； (2)A上最粗的 等價(jià) 關(guān)系是全關(guān)系；即， R粗 =A A ， A/R粗 ={A} 。 定理 R和 S是非空集合 A上的兩個(gè)等價(jià)關(guān)系。則 R?S?(?a?A)(?a?R? ?a?S) 。 [證 ].（采用邏輯法） ?先證： R?S? (?a?A)(?a?R? ?a?S) 對(duì)任何元素 a?A ，有 71 離散數(shù)學(xué) 對(duì)任何元素 x?A ，有 x? ?a?R ? xRa ? xSa (已知條件： R?S) ? x??a?S 所以 ?a?R? ?a?S 所以 (?a?A)(?a?R? ?a?S) ； ?次證： (?a?A)(?a?R? ?a?S)?R?S 對(duì)任何序偶 (a,b)?A A (a,b)?R ?aRb ?bRa (R是 等價(jià)關(guān)系，故 R對(duì)稱 ) ?b??a?R 72 離散數(shù)學(xué) ?b??a?S (已知條件： (?a?A)(?a?R? ?a?S) ) ?bSa ?aSb (S是 等價(jià)關(guān)系，故 S對(duì)稱 ) ? (a,b)?S 所以 R ?S 。 定理 R和 S是非空集合 A上的兩個(gè)等價(jià)關(guān)系。則 R=S?(?a?A)(?a?R = ?a?S) 。 [證 ].(采用邏輯法 ) R=S ?R?S?S?R ? (?a?A)(?a?R ? ?a?S)?(?a?A)(?a?S ? ?a?R) (定理 2) ? (?a?A)(?a?R ? ?a?S??a?S ? ?a?R) (?量詞 對(duì) ?的分配律 ： 73 離散數(shù)學(xué) ?x(A(x)??xB(x) ? ?x(A(x)?B(x)) ) ?(?a?A)(?a?R = ?a?S) 。 注： ?由定理 2知，若兩個(gè)等價(jià)關(guān)系相等，則每個(gè)元素所對(duì)應(yīng)的等價(jià)類也相同；若兩個(gè)等價(jià)關(guān)系的等價(jià)類集合相等，則兩個(gè)等價(jià)關(guān)系相同。 ?由 定理 3知，等價(jià)關(guān)系與等價(jià)類集合一一對(duì)應(yīng)。即相同的等價(jià)關(guān)系對(duì)應(yīng)著相同的等價(jià)類集合，不同的等價(jià)關(guān)系對(duì)應(yīng)著不同的等價(jià)類集合。 2176。 劃分與等價(jià)關(guān)系 定義 劃分 (covering partition) 設(shè) A是一非空集合 。則 A的 (1)覆蓋是一集合之集 ?={A? : ????A?≠?}，滿足條件： 74 離散數(shù)學(xué) A ? ； (2)劃分是一集合之集 ?={A? : ????A?≠?}，滿足條件： (a) A = ； (b)?1≠?2?A?1∩A?2 = ? ； 其中 A?稱為 劃分 ?的劃分塊 (block of partition)。 注： ?由劃分和覆蓋的定義可知， A上的劃分一定是 A上的覆蓋；反之則未必 。 定理 4 。 設(shè) R是非空集合 A上的等價(jià)關(guān)系。則 R的 等價(jià)類之 集 ?R = { ?a?R : a?A } 是 A上的一個(gè)劃分；等價(jià)類就是 劃分塊 。 [證 ].定理 1的 (1)不但直接給出 等價(jià)類的非空性，而且 A????A????75 離散數(shù)學(xué) 由它可得等價(jià)類滿足 劃分的 條件 (a)