【正文】 環(huán)置換中，故。因而是對稱性的。，若，則i與j在的循環(huán)分解式中的同一個循環(huán)置換中，j與k在的循環(huán)分解式的同一個循環(huán)置換中，因而i與k也在的循環(huán)分解式中的同一個循環(huán)置換中，即。因而是傳遞性的。所以是X上的等價關系。＝{1,2,3,4}上兩個等價關系R與S，使得不是等價關系。解：如因為，但，所以不對稱..因此不是等價關系。，試求：（1）X上自反二元關系的個數；（2）X上反自反二元關系的個數；（3）X上對稱二元關系的個數；（4）X上自反或對稱關系的個數；解：（1）X上自反二元關系的個數為（2）X上反自反二元關系的個數為（3）X上對稱二元關系的個數為（4）X上自反或對稱關系的個數為習題。令是區(qū)間上的有限劃分的集合，的一個劃分是形如的點的集合。在上定義二元關系如下：的每個分點也是的分點。證明：是上的偏序關系（注意，這里的劃分與等價關系中的劃分不同）。證：的每個分點也是的分點，故，因此是自反的；，若且，則的每個分點也是的分點且的每個分點也是的分點，故。因此是反對稱的；，若且，則的每個分點是的分點，而且的每個分點也是的分點，因此的每個分點也是的分點，故。因此是傳遞的。綜上可知：是上的偏序關系。在上定義二元關系如下： 。證明：（1）是上的偏序關系；（2）若或，則是上的偏序關系嗎？證：1.(1)，則。由于是偏序集，故有。從而是自反的；(2)，若且，則且。由是偏序集可知，且，故。因此“”是對稱的。(3)，若且，有且。由是偏序集可知：與是傳遞的，所以且。故，因此是傳遞的。綜上可知：是上的一個偏序關系。：或，則不是偏序關系。因為不滿足反對稱性。例如：，則且，但。故不滿足反對稱性，因此不是偏序關系。，使得中有唯一的極大元素，但沒有最大元素？若有請給出一個具體例子；若沒有，請證明之。解：存在。設，其中。在上定義的小于或等于關系“”，則就是一個沒有最大元素，但卻有唯一極大元的偏序集。＝｛1，2，…，12｝，畫出偏序集（S,|）的Hass圖，其中“|”是整除關系，它有幾個極大（小）元素？列出這些極大（小）元素極大元素有6個，分別是7，8，9，10，11，12極小元素有1個是1，則（1）給出的一個實例；（2）在上定義二元關系是：。證明：是上的等價關系。（3）在商集上定義二元關系是：。證明：是上的偏序關系。證：（1）即可（2）自反、對稱顯然。下面看傳遞性因為若；由是傳遞的，有。由題意有，故是傳遞的。因此是上的等價關系。（3），因為是上的自反關系，故。而，所以是自反的；，若，則與在一個等類中，故，因此是反對稱的；，若，則由的傳遞性有，即。因此是傳遞的。綜上可知：是上的偏序關系。，證明：是上的全序關系。證：，由于是上的全序關系，故或必有一個成立。所以，即；反之，因為是上的關系，故，所以。因此。 ，有或，即與必有一個成立，故是上的全序關系。第四章 無窮集合及其基數習題的所有項組成的集合，則是否市可數的？為什么？解：因為序列是可以重復的，故若是由有限個數組成的集合，則是有限的集合；若是由無限個數組成的集合，則是可數的。故本題是至多可數的。：直線上互不相交的開區(qū)間的全體所構成的集合至多可數。證：在每個開區(qū)間中取一個有理數，則這些有理數構成的集合是整個有理數集合Q的子集，因此是至多可數的。：單調函數的不連續(xù)點的集合至多可數。證：設是所有不連續(xù)點的集合，是一個單調函數，則對應著一個區(qū)間，于是由上題便得到證明。證：設則且。令，設，則是Ａ的子集的特征函數。｛0，1的有窮序列｝，即，若，則對應1；若則對應0。于是就對應著一個由0，1組成的有限序列0，1，1，0，…，0，1。此序列對應著一個二進制小數，而此小數是有理數。于是，可數集的所有有限子集對應著有理數的一個子集。又對應的小數也不同，故是單射。而可數集Ａ的所有有限子集是無窮的，故是可數的。5．判斷下列命題之真?zhèn)危?1)若且是滿射，則只要是可數的，那么是至多可數的；(2)若且是單射，那么只要是可數的，則也是可數的；(3)可數集在任一映射下的像也是可數的；答案：對，錯，錯。7．設Ａ是有限集，Ｂ是可數集，證明：是可數的。證：令，Ｂ可數。設。（中的每個f實際上就是Ｂ的一個有限子集，可數集的有限子集是可數的。于是由４題即可證明）（。用數學歸納法可以證明是可數的，但。8. 設為一個有限字母表，上所有字（包括空字）之集記為。證明是可數集證１：設有限字母上所有字（包括空字）所形成的集，則是可數的。Ａ1＝{長度為1的字符串}Ａ2＝{長度為2的字符串}　 　　 Ａn＝{長度為n的字符串}　　　 因為Ａi 中每個長度都是有限的，而＝，故是至多可數的。又顯然是無窮的，故是可數的。證2：不妨假設（令＝也是可以），則可按字典序排序為：。由于的全部元素可以排成無重復項的無窮序列，故是可數的。習題，使得它是到實數的一一對應。解：,或，或，使得它是從到的一一對應。證：中包含一個可數子集可數。——可數的，故。令即為所求。：若可數，則不可數。（用對角線方法）。證：可數，則令。假設可數，則的子集（即的元素）是可數的，故中元素可排成一個無重復項的無窮序列：而，于是特征函可數，即可寫成下列無窮序列形式： 其中或。造一個特征函數。令則,但確實是到的一個映射，即是的子集的特征函數，矛盾。故不可數。5．令，利用康托對角線法證明S是不可數集。證:假設從N到{0, 1}的所有映射之集可數，則可排成無重復項的無窮序列。每個函數確定了一個0,1序列。構造序列，若；否則。該序列對應的函數，不為任一個，矛盾。46