哈工大集合論習(xí)題課-第三章 關(guān)系習(xí)題課(學(xué)生)

1、習(xí) 題 課例1設(shè)，給出A上的一個二元關(guān)系，使其同時不滿足自反性、反自反性、對稱性、反對稱和傳遞性的二元關(guān)系，并畫出R的關(guān)系圖。解：，關(guān)系圖如圖所示。例2 設(shè)是一個集合，n，求：1.上的二元關(guān)系有多少？2. 上的自反的二元關(guān)系有多少？3. 上的反自反的二元關(guān)系有多少？解：因為把所有的反自反的二元關(guān)系的每個都加上對角線上的序?qū)?，就變成了自反的關(guān)系，因此，自反的與反自反的個數(shù)一樣多。即4. 上的對稱的二元關(guān)系有多少？，故共有個對稱的關(guān)系。5. 上的反對稱的二元關(guān)系有多少？6. 上既是自反的也是反自反的二元關(guān)系的個數(shù)；7.上既不是自反的也不是反自反的二元關(guān)系有多少？解：解：可用容斥原理來計算設(shè)B表示所

2、有自反關(guān)系構(gòu)成的集合，C表示所有反自反關(guān)系構(gòu)成的集合，則。而，故，從而于是，既不是自反的，也不是反自反關(guān)系共有個。8.自反的且對稱的關(guān)系有多少？此結(jié)果與“反自反的且對稱的關(guān)系有多少？”是一樣多即有（對角線上全去掉）9.自反的或?qū)ΨQ的關(guān)系有多少？解：設(shè)B表示自反關(guān)系的集合，C表示對稱關(guān)系的集合，則自反或?qū)ΨQ關(guān)系的集合為：。10.上既是反自反的也是反對稱的二元關(guān)系的個數(shù)為：；11.上既是對稱的也是反對稱的關(guān)系個數(shù)；解：上既是對稱的也是反對稱的關(guān)系，故有。12.上既不是對稱的也不是反對稱的關(guān)系個數(shù)；解：設(shè)A表示對稱、B表示反對稱，則既不是對稱的也不是反對稱的二元關(guān)系為：例3設(shè)有集合A，求A上具有反自

3、反且反對稱性的二元關(guān)系的數(shù)目，并寫出計算過程。解：不妨設(shè)，將，看作一個抽屜，看作一個抽屜，看作一個抽屜。若要獲得具有反對稱性且反自反性的關(guān)系，其中的元素只能在三個抽屜中取且每個抽屜中至多取一個元素，分幾種情況：（1）一個也不取，有種取法。（2）只取一個元素，有種取法。（3）取二個元素，有種取法。（4）取三個元素，有種取法。故具有反自反性且反對稱性的二元關(guān)系數(shù)目共有1612827個。若，結(jié)果又為多少？抽屜數(shù)：，每個抽屜有3種選擇，故共有個。例4 設(shè)，是A的冪集上的二元關(guān)系且，則不滿足下列哪些性質(zhì)？為什么？（1）自反性；（2）反自反性；（3）對稱性；（4）反對稱性；（5）傳遞性。等價于。解：(1)

4、自反性。因為，但，所以，故不是自反的。（2）反自反性。因為，故，故不是反自反的。（3）對稱性。，若，則，所以，故，從而是對稱的。（4）反對稱性。令，則，故且，但，所以，從而不是反對稱的。（5）傳遞性。令，則有且，故且，但，故，所以不是傳遞的。例5 設(shè)R是復(fù)數(shù)集合C上的一個二元關(guān)系且滿足，a，b為非負整數(shù)，試確定R的性質(zhì)。解：1.若ab0時，則，故為C上的恒等關(guān)系，顯然滿足：自反，對稱，反對稱和傳遞性質(zhì)。2.若不全為0，則滿足反對稱和反自反性質(zhì)，但不滿足自反、對稱和傳遞性。（1），所以，故R是反自反的，但不是自反的。（2）,若,則，而，因為不全不零，所以，故不可能有，即是反對稱的，但不是對稱的。

5、（3），若且，則且，而，因為不全為零，故，故不可能有，即不是傳遞的。習(xí)題課例1 證明：，其中證：；同理可證例2 書上做為定理出現(xiàn)設(shè)R、S是上的二元關(guān)系，則（1），是空關(guān)系。（2）證：因為是傳遞的，故。（3）證：因為且，故，且，從而例3 如圖5所示給出下圖中每個關(guān)系的自反、對稱和傳遞閉包。 （a） （b） （c）圖5（1）自反閉包（2）對稱閉包（3）傳遞閉包例4 設(shè)R是集合A上的反對稱關(guān)系，則t(R)一定是反對稱的嗎？證：t(R)在A上不一定是反對稱的。例：，則R的傳遞閉包為：t(R)是全關(guān)系，故t(R)不是反對稱的而是對稱的。例5 是否可以定義二元關(guān)系的反自反閉包與二元關(guān)系的反對稱閉包？為什么

6、？解：不可以。設(shè)A=a,b,c,R=(a,a)(a,b),(b,a),(a,c),則反自反閉包與反對稱閉包不存在。例6 舉例說明與確實不相等。解：設(shè)，在上定義小于關(guān)系“”，則“不等關(guān)系”；而“全關(guān)系”。因此的確不相等。例7（）是否存在（）上的一個二元關(guān)系R，使得兩兩不相等。解：存在。令，即可。例8 證明：如果R是對稱的，則R也是對稱的。證：證1 ，則，使得。于是存在m1個元素，使得。由R的對稱性有：。于是，從而，即是對稱的。習(xí) 題 課例1 設(shè)是整數(shù)集上的關(guān)系，定義為，則（1）證明：是等價關(guān)系；（2）確定的等價類。證：（1）因為，有，故，即R是自反的。，若，即，則，因此，即R是對稱的。，若，即且

7、，故，即，所以R是傳遞的。由此可知：是上的等價關(guān)系。（2）因為，所以R的等價類有：。例2設(shè)是上的一個自反關(guān)系，證明：是等價關(guān)系若且，則。書上習(xí)題證：是上的等價關(guān)系。若且，由的對稱性有：且，再由的傳遞性有：R是自反的，故有。若，由，有，所以是對稱的。若且，由的對稱性有：且，故由題意得，所以是傳遞。因此，是上的等價關(guān)系。例3.令，上的兩個關(guān)系如圖3所示，它們是否是等價關(guān)系？不是等價關(guān)系（因為不傳遞）是等價關(guān)系圖3例4 設(shè)，是上的等價關(guān)系，則也是上的等價關(guān)系嗎？解：不一定是的等價關(guān)系。因為不一定具有傳遞性。舉例：設(shè)，則因為且，但，故不滿足傳遞性，即不一定是上的等價關(guān)系。例5設(shè)是上如下的二元關(guān)系：，當(dāng)

8、且僅當(dāng)。證明：(1) 等價關(guān)系；(2)求等價類數(shù)。證：(1)等價關(guān)系顯然；(2)等價類數(shù)為：。只能取2，3，2n，故等價類數(shù)有個。例6 設(shè)R是A上的對稱和傳遞的關(guān)系。若對A中每個a，使得，證明：R是A上的等價關(guān)系。證：，使得。由R的對稱性有：。再由R的傳遞性有：。由a的任意性可知，R是A上的自反關(guān)系，故R是A上的等價關(guān)系。例7 設(shè)R是集合A上的一個自反的和傳遞的關(guān)系；T是A上的一個關(guān)系，使得且。證明：T是A上的等價關(guān)系。證：（1）因為R是上的自反關(guān)系，所以，有，故由T的定義有：，即T是上的自反關(guān)系。（2）若，由題設(shè)：且。顯然，即T是上的對稱關(guān)系。（3）若且，由題設(shè)可知：，且，。由R傳遞性得：且

9、，故，所以T是上的傳遞關(guān)系。由（1），（2），（3）即得T是上的等價關(guān)系。例8設(shè)是上的一個二元關(guān)系，設(shè)，使得且。證明：（1）若是上的等價關(guān)系，則也是上的等價關(guān)系；（2）證明：。分析：根據(jù)等價關(guān)系的定義，即關(guān)系應(yīng)滿足自反性、對稱性和傳遞性，分三步證明。證：1. 證明若是等價關(guān)系，則也是等價關(guān)系。（1）自反性因為是自反的，所以，有。根據(jù)的定義，有，所以是自反的；（2）對稱性：若，則，使得且。因為是對稱的，所以且，根據(jù)的定義有，所以是對稱的；(3) 傳遞性：若，則，使得且。因為是傳遞的，所以。且，使得且。因為是傳遞的，所以。根據(jù)的定義有。所以是傳遞的。由（1），（2），（3）可知：是等價關(guān)系。2.

10、證明。，因為是上的等價關(guān)系，故是自反的，即。由的定義知，故。反之，由的定義知：，使得且。因為是等價關(guān)系，故是傳遞的，因此，于是。從而。例9 給定上的相容關(guān)系R，證明為上的等價關(guān)系。證：R是自反的，對稱的顯然。故只要證明傳遞即可。但，故是傳遞的。例10 設(shè)是集合A的劃分，若，1in，證明：是集合的劃分。證：因為是集合A的劃分，故，ij。但，當(dāng)ij時，。當(dāng)ij時，。所以是的劃分。例11設(shè)和是集合上的等價關(guān)系，和是由和所誘導(dǎo)產(chǎn)生的劃分，證明：當(dāng)且僅當(dāng)?shù)拿總€劃分塊都包含在的某個劃分塊中，。 分析：只要理解等價關(guān)系和劃分的概念以及它們之間的一一對應(yīng)關(guān)系，就很容易證明。證：令劃分, 。充分性。若，則的每個

11、劃分塊都包含在的某個劃分塊中。于是，即為中任一劃分塊，所以。在中任取一個元素。因為是的劃分且，所以存在，使得。于是，有，又因為，所以。根據(jù)劃分的定義有，所以。由的任意性知，的每一劃分塊都包含在的某一劃分塊中。必要性若的每個劃分塊都包含在的某個劃分塊中，則。，則在的同一劃分塊中。根據(jù)題設(shè)，必有在的同一劃分塊中，故。因此。例12設(shè)。是S上的二元關(guān)系，則（1）若，證明：是上的等價關(guān)系；求等價類的集合。（2）若，證明：是上的等價關(guān)系；求等價類的集合。（3）若，證明：是上的等價關(guān)系；求等價類的集合。證：因為，所以到的映射共有8個，如圖2所示。圖21（1）等價關(guān)系顯然。（2），故，。所以等價類集合為。2（

12、1）等價關(guān)系顯然（2），。故 所以等價類集合為。3（1）是等價關(guān)系顯然。（2），。故故等價類集合為。例13由置換確定了上的一個關(guān)系當(dāng)且僅當(dāng)與在的循環(huán)分解式中的同一循環(huán)置換中，證明：（1）是上的等價關(guān)系；（2）求。證：（1）因為，則，與必在的循環(huán)分解式中的同一個循環(huán)置換中，即，故是自反的；，若，即與在的循環(huán)分解式中的同一個循環(huán)置換中，則與也在的循環(huán)分解式中的同一個循環(huán)置換中，即。故是對稱性的；，若，則與在的循環(huán)分解式中的同一個循環(huán)置換中，與在的循環(huán)分解式的同一個循環(huán)置換中，因而與也在的循環(huán)分解式中的同一個循環(huán)置換中，即。故是傳遞性的。綜上可知：是上的等價關(guān)系。（2）。例14 設(shè)，并設(shè)，在上定義關(guān)

13、系為：。證明：(1)R是等價關(guān)系；(2)計算出A/R。證：I(1)自反性。，有，所以，即R是A上的自反關(guān)系。(2)對稱性。，若，則，故，所以，即R是A上的對稱關(guān)系。(3)傳遞性。，若且，則且，即，所以，故R是A上的傳遞關(guān)系。由(1)，(2)，(3)可知，R是A上的等價關(guān)系。II首先求出A=SS的全部元素，然后找出所有元素對應(yīng)的等價類即可。在求等價類時，記住以下幾條性質(zhì)：(1)；(2)若，則。因為所以，例15設(shè)是上的等價關(guān)系，是上的等價關(guān)系。關(guān)系滿足：證明：是上的等價關(guān)系。解：（1）自反性：，有，；因為和分別為和上的自反關(guān)系，所以，故，因此是自反性的；（2）對稱性：，若，則，；因為和分別為和上的

14、對稱關(guān)系，所以有，從而，因此是對稱性的；(3) 傳遞性：，若且，則有 ，；因為和分別為和上的傳遞關(guān)系，所以有，從而，因此是傳遞性的。綜上可知：是上的等價關(guān)系。例15設(shè)是自然數(shù)集合，定義上的二元關(guān)系：，則 （1）證明是一個等價關(guān)系；（2）求關(guān)系的等價類；證：（1）自反性：，是偶數(shù)，所以有。因此是自反的；對稱性：若，即是偶數(shù)，則是偶數(shù)，所以有。因此是對稱的；傳遞性：若，即是偶數(shù)，是偶數(shù)，則是偶數(shù)，所以有。因此是傳遞的。 綜上可知：是等價關(guān)系。（2）關(guān)系的等價類有：。（3）設(shè)， 則所誘導(dǎo)的等價關(guān)系就是。例17 設(shè)，A上的二元關(guān)系R定義為：，證明：1.R是A上的等價關(guān)系；2.確定由R對集合A的劃分。證

15、：1.首先證明R是A上的等價關(guān)系。(1)自反性。，因為，故，即R是自反的。(2)，若，有，則，從而，即R是對稱的。(3)，若即，得，從而，故R是傳遞的。由(1)、(2)、(3)可知，R是A上的等價關(guān)系。2.由定理知，由R的等價類可確定對集合A的劃分。劃分中的元素分別為元素的等價類，它們是：即集合A的劃分。習(xí) 題 課例1 非空集合A上存在二元關(guān)系R，使得R既是A上的等價關(guān)系又是A上的偏序關(guān)系嗎？解：存在。A上的恒等關(guān)系就滿足。例2 在A1,2,3,4,6,8,12,24和B2,3,4,8,9,10,11上定義的整除關(guān)系“|”，畫出Hasse圖，指出最大（?。┰?，極大（小）元。(a) (b)圖1解

16、：如圖1(a)所示最大元：24 最小元：1；極大元：24 極小元：1；如圖1(b)所示最大元：無 極大元：8，9，10，11；最小元：無 極大元：2，3，11（元素11既是極大元又是極小元）。例3 設(shè)偏序集的關(guān)系圖如圖2(a)所示。(1)畫出的Hasse圖。(2)設(shè)Bb,c，求B的上界集合C和上確界；下界集合D和下確界。(a) (b)圖2解：1. 的Hasse圖如圖8(b)所示。1. 設(shè)Bb,c，則A中無任意元素“大于”b，也同時“大于”c，故C，此時，無上確界，而Dd，下確界：d。例4 設(shè)集合上的偏序關(guān)系如圖9所示。則1.求出A的最大（?。┰瑯O大（?。┰?。2.求出的上界、下界、上確界和下確

17、界。x5x4x3x2x1圖2解：1.最大元：最小元：無極大元：極小元：，2.令，則上界：下界； 上確界：下確界：令，則上界：，下界：無； 上確界：，下確界：無；令，則上界：，下界：； 上確界：，下確界：。例5設(shè)集合，上的關(guān)系定義如下：。則 （1）寫出的關(guān)系矩陣；（2）驗證是偏序集；（3）并畫出Hasse圖。（4）若上的關(guān)系如下：，則又如何？cebad解：（1）所對應(yīng)的關(guān)系矩陣為為：（2）由關(guān)系矩陣可知：對角線上的所有元素全為1，故是自反的； 圖10，故是反對稱的； 對應(yīng)的關(guān)系矩陣為： 。因此是傳遞的。綜上可知：故是上的偏序關(guān)系，從而是偏序集。（3）對應(yīng)的Hasse圖如圖10所示。（4）的關(guān)系矩

18、陣為：因為，但，故不是傳遞的。因此，不是上的偏序關(guān)系。實際上，也可通過計算的關(guān)系矩陣來說明：，故不是傳遞的。因此不是上的偏序關(guān)系。例6 證明：每個由個實數(shù)組成的數(shù)列中必有一個長至少為的不減子序列，或有一個長至少為的不增子序列。證：不妨設(shè)個數(shù)是互不相同的。于是，這個數(shù)構(gòu)成的集合A，且。在A上定義二元關(guān)系“”如下：當(dāng)且僅當(dāng)且。其中是實數(shù)間的通常的小于或等于關(guān)系。顯然，二元關(guān)系是自反的，傳遞的。設(shè)且，則，且，從而，。所以，是反對稱的。因此是A上的偏序關(guān)系，是偏序集。由推論可知，A中或有長至少為的鏈或有長至少為的反鏈。A中長至少為的鏈，就是序列的長至少為的不減（在下）的子序列。而A的長至少為的反鏈，實際上就構(gòu)成了的不增子序列。設(shè)反鏈中元素按下標(biāo)遞增順序排列成因1，而，所以，故，。于是便有：。例7設(shè)是實數(shù)集，令為到的所有映射所構(gòu)成的集合。若，定義：，證明：（1）是偏序關(guān)系；（2）是全序關(guān)系嗎?分析：證明是偏序關(guān)系，首先搞清是定義在什么集合上，中的元素是什么形式；然后再按偏序關(guān)系的定義分別證明的自反性，反對稱性，傳遞性；證明這三個性質(zhì)，可以直接采用按定義方法證明。顯然是定義在以映