【正文】 個(gè)類里。于是使得，且，從而，使得。證明：存在X的一個(gè)真子集E使得。對(duì)于上面的，（是滿射），使得，即。習(xí)題1. 設(shè)，試構(gòu)造兩個(gè)映射和g：，使得（1），但；（2），但。解： =(1 7)(1 3)(2 9)(2 8)(2 4)(2 6)，試證：與的奇偶性相同。，對(duì)稱性，反對(duì)稱性，傳遞性和反自反性的二元關(guān)系？解：存在。證1：，故是對(duì)稱的。 e）若R,S都是傳遞的，則也是傳遞的。，則，使得。解：故,S為X上的二元關(guān)系，試證：（1）（2）。由，得，所以是包含的自反關(guān)系。證明：是上的偏序關(guān)系（注意，這里的劃分與等價(jià)關(guān)系中的劃分不同）。：或，則不是偏序關(guān)系。（3），因?yàn)槭巧系淖苑搓P(guān)系，故。證：設(shè)則且。證明是可數(shù)集證１：設(shè)有限字母上所有字（包括空字）所形成的集，則是可數(shù)的。故不可數(shù)。證：可數(shù)，則令。（中的每個(gè)f實(shí)際上就是Ｂ的一個(gè)有限子集，可數(shù)集的有限子集是可數(shù)的。證：在每個(gè)開區(qū)間中取一個(gè)有理數(shù)，則這些有理數(shù)構(gòu)成的集合是整個(gè)有理數(shù)集合Q的子集，因此是至多可數(shù)的。證：（1）即可（2）自反、對(duì)稱顯然。(3)，若且，有且。解：如因?yàn)?，但，所以不?duì)稱..因此不是等價(jià)關(guān)系。圖4，故。證：，則，使得。 其次，設(shè)，因?yàn)槭且磺邪淖苑磦鬟f關(guān)系的交，而本身是自反的也是傳遞的且，故，即，因此。證3用數(shù)學(xué)歸納法對(duì)n進(jìn)行歸納。解：，下列命題哪些為真？a）若R,S都是自反的，則也是自反的。從而，因此。那么“”是N上的代數(shù)運(yùn)算嗎？為什么？解：當(dāng)m=1時(shí)，因此“”不是N上的代數(shù)運(yùn)算。（a） (b)圖15. 是否有一個(gè)從到的一一對(duì)應(yīng)，使得，但？ 解：存在。逆否命題：。證明：是滿射當(dāng)且僅當(dāng)不存在從Y到Z的映射和，使得，但。因此不論何種情況都，使得。設(shè)這兩個(gè)余數(shù)為，對(duì)應(yīng)兩式相減便有：可被整除，此時(shí)。，則必有長(zhǎng)至少為的遞增子序列或有長(zhǎng)至少為的遞減子序列。又〔答案：，當(dāng)n≥10時(shí)，〕。10．設(shè)是兩個(gè)集合，試證：若，則。綜上可得：＝。于是，假設(shè)不成立。反之，必使得，即時(shí)。證：因?yàn)?，故?．設(shè)A,B,C為任意集合，化簡(jiǎn)證：證1：原式＝證2：令原式＝T，全集為S，則且，故 。因此或，從而。因而且，故；若，則，同理可得。從而。又，只能有。那么對(duì)于（），中的元素可分為兩類，一類為不包含中某一元素的集合，另一類為包含的集合。假設(shè)，則必存在，使得但，故與題設(shè)矛盾。故，即。反例如下：（1）任意，則。因此。14．設(shè)A為任一集，為任一集族（），證明：證：，則若，則，因而；若，則，因而，故。則，則但，因此有。設(shè)，則有兩種情況：若。8．證明：證：，由定義可知：序列中只有有限項(xiàng)不含x，故必可找到不含x的下標(biāo)最大的一項(xiàng)，可見此時(shí)均含x，即有無限項(xiàng)含x，故。3．設(shè)A,B,C,D為任四個(gè)集合，證明：證：，有，即。，則必有，故。于是。與跳舞的姑娘的集合用表示；與跳舞的姑娘的集合用表示； 與跳舞的姑娘的集合用表示；于是，由題意：且且。實(shí)際上，且，則若，則，所以；即。設(shè)在一個(gè)類中的兩個(gè)余數(shù)分別為與。故，即。證：取，令。故與，矛盾。解：（1）但，故f是滿射，但f不是單射。證：假設(shè)與的奇偶性不同，不妨設(shè)為奇置換，為偶置換。設(shè)，R是X上的二元關(guān)系。證2：，則或，即或。 答案：真假假假假，R2和R3是B到C的二元關(guān)系，則一般情況下。因?yàn)镽k，R均是對(duì)稱的，所以，于是。證：（1）因?yàn)樗砸虼耍?）因?yàn)樗砸虼? 〔證畢〕。由自反閉包的定義可知：又，故，因此。故3. （1）是等價(jià)關(guān)系顯然。證：的每個(gè)分點(diǎn)也是的分點(diǎn)，故，因此是自反的；，若且，則的每個(gè)分點(diǎn)也是的分點(diǎn)且的每個(gè)分點(diǎn)也是的分點(diǎn)，故。因?yàn)椴粷M足反對(duì)稱性。而，所以是自反的；，若，則與在一個(gè)等類中，故，因此是反對(duì)稱的；，若，則由的傳遞性有，即。令，設(shè)，則是Ａ的子集的特征函數(shù)。Ａ1＝{長(zhǎng)度為1的字符串}Ａ2＝{長(zhǎng)度為2的字符串}　 　　 Ａn＝{長(zhǎng)度為n的字符串}　　　 因?yàn)椋羒 中每個(gè)長(zhǎng)度都是有限的，而＝，故是至多可數(shù)的。5．令，利用康托對(duì)角線法證明S是不可數(shù)集。（用對(duì)角線方法）。設(shè)。：直線上互不相交的開區(qū)間的全體所構(gòu)成的集合至多可數(shù)。證明：是上的偏序關(guān)系。因此“”是對(duì)稱的。＝{1,2,3,4}上兩個(gè)等價(jià)關(guān)系R與S，使得不是等價(jià)關(guān)系。（2），共有8個(gè)，如圖4所示。：若R是對(duì)稱的，則R＋也是對(duì)稱的。（2）因?yàn)轱@然成立。因?yàn)镽對(duì)稱，所以，因此，故R對(duì)稱。習(xí)題1.“父子“關(guān)系的平方是什么關(guān)系？解：“父子“關(guān)系的平方是”祖孫“關(guān)系={1,2,3,4},R={(1,2),(2,2),(3,4)},S={(2,3),(3,1),(4,2)}試求：。于是或，即。也不滿足結(jié)合律， 單位為aoabcdaabcdbbaacccabdddcab。，則（1）若是左可逆的，則有多少個(gè)左逆映射？（2）若是右可逆的，則有多少個(gè)右逆映射？解：令，則（1）如圖1(a)所示：有；（2）如圖1(b)所示：有?？梢杂茫?。,Y,Z是三個(gè)非空集合。反例：設(shè)。于是或，使得。而任意整數(shù)被除后，只有－1個(gè)余數(shù)——相當(dāng)于－1抽屜，