集合論習題選講 (2)

1、 1第二部分第二部分 集合論集合論 例題選講例題選講1.1. 設設A A，B B為任意集合，為任意集合，A=B A=B 充分必要條件是充分必要條件是 A-B =B-A A-B =B-A ? ?2.2. A A為實數集，為實數集， x x，yAyA，xRyxRy x-yx-y=2=2；則；則R R為等價關系為等價關系? ?3.3. 若若A=P(X)A=P(X)，|X|X| 2 2， x x，y Ay A，xRyxRy x x y y y y x x，則，則R R為等價關系為等價關系 ? ?4.4. 設設A=aA=a，則，則, P(P(AP(P(A) ) ？5.5. 設設f f：N NNN,fNN

2、,f()=)=xyxy, ,則則f f是滿射的是滿射的 ? ? 26.6. 若集合若集合A=B=CA=B=C，則，則A A （B B C C）= =（A A B B） C ?C ?7.7. 設設R R為為A A上的關系，則上的關系，則R R在在A A上自反當且僅當上自反當且僅當RIRIA A= ?= ?8.8. 設設R R為非空集合為非空集合A A上的等價關系，則上的等價關系，則R R一定是偏序關系一定是偏序關系? ?9.9. 兩個可數集的笛卡兒積是可數集兩個可數集的笛卡兒積是可數集? ? 10.10.集合的冪集集合的冪集P P（B B）關于集合的對稱差運算和并運算構）關于集合的對稱差運算和并

3、運算構成環(huán)成環(huán) ? ? 311.11.設設A A、B B、C C為任意集合，證明：為任意集合，證明：（1 1）（）（A-BA-B）- C = A - (BC)- C = A - (BC)（2 2）(A-B)-C=(A-C)- (B-C)(A-B)-C=(A-C)- (B-C)證明：（證明：（1 1）(A-B)-C = (A(A-B)-C = (AB)B)C C = A(= A(BBC) = AC) = A(BC)(BC) = A - (BC) = A - (BC) （2 2） (A-C)- (B-C)= (A(A-C)- (B-C)= (AC)C)(B(BC)C) =(A =(AC)(C)(B

4、C)BC) = (A = (AC)C)B)(AB)(AC)C)C)C) =(A =(AC)C)B =(AB =(AB)B)C C =(A-B) =(A-B)C =(A-B)-C C =(A-B)-C 412.12.設設A A、B B為任意集合，證明：為任意集合，證明： q (1) P(A)P(B) = P(AB) (1) P(A)P(B) = P(AB) q (2) P(A)P(B) (2) P(A)P(B) P(AB)P(AB)q 針對（針對（2 2）舉一反例，說明）舉一反例，說明P(A)P(B) = P(AB)P(A)P(B) = P(AB)對對某些集合某些集合A A和和B B是不成立的是

5、不成立的q 證明：證明：(1) (1) 先證先證 P(A)P(B)P(A)P(B) P(AB) P(AB)q xP(A)P(BxP(A)P(B), ), 則則 xP(AxP(A) ) xP(BxP(B) )q 所以所以 x x A A x x B Bq 所以所以 x x AB, AB, 即即 xP(ABxP(AB) )q 因此因此 P(A)P(B)P(A)P(B) P(AB) P(AB) 5q 再證再證 P(AB) P(AB) P(A)P(B) P(A)P(B)q xP(ABxP(AB) )q 則則 x x AB AB q 所以所以 x x A A x x B Bq 所以所以 xP(AxP(A

6、) ) xP(BxP(B) )q 所以所以 xP(A)P(BxP(A)P(B) )q 因此因此 P(AB)P(AB) P(A)P(B) P(A)P(B)q 綜上所述綜上所述 P(AB) = P(A)P(B) P(AB) = P(A)P(B) 6q (2)(2) P(A)P(B)P(A)P(B) P(AB) P(AB) q xP(A)P(BxP(A)P(B) )q 則則 xP(AxP(A) ) xP(BxP(B) )q 所以所以 x x A A x x B Bq 若若x x A A, ,則則 x x AB ABq 所以所以 xP(ABxP(AB) )q 若若x x B B, ,則則 x x AB

7、 ABq 所以所以 xP(ABxP(AB) )q 因此因此 P(A)P(B)P(A)P(B) P(AB) P(AB) 7q (3)(3) 舉例：舉例：q 令令A=1,B=2A=1,B=2q 則則 AB=1AB=1，22q 則則P(A)=P(A)=，11，P(B)=P(B)=，22q 而而P(AB)=P(AB)=，1,2,1,21,2,1,2q 顯然顯然P(A)P(B)= P(AB)P(A)P(B)= P(AB)不成立不成立. . 813.13.設設R R是是A A上的自反和傳遞關系，如下定義上的自反和傳遞關系，如下定義A A上的關系上的關系T T，使得，使得q x, x, yAyA T T R

8、 R R Rq 證明：證明：T T是是A A上的等價關系。上的等價關系。q 證明：證明： 先證先證T T具有自反性具有自反性q xAxA, , 由于由于R R是是A A上自反關系上自反關系, , 所以所以 RRq 即即 R R RRq 由由T T的定義知：的定義知： TTq 所以所以T T具有自反性具有自反性 9q 再證再證T T具有對稱性具有對稱性q x,yAx,yA , ,若若 TTq 由由T T的定義知：的定義知： R RR Rq 即即 R R R R q 再由再由T T的定義知：的定義知： TTq 所以所以T T具有對稱性具有對稱性q 10q 再證再證T T具有傳遞性具有傳遞性q x,

9、 yx, y，zAzA , ,若若 T TT Tq 由由T T的定義知：的定義知：R RR Rq 并且并且R RR Rq 再由再由R R具有傳遞性知具有傳遞性知: R R: R Rq 再根據再根據T T的定義知的定義知: T: Tq 所以所以T T具有傳遞性。具有傳遞性。q 綜上所述知綜上所述知T T為為A A上的等價關系。上的等價關系。 1114.14.設設為偏序集，在為偏序集，在A A上定義新的關系上定義新的關系S S如下：如下： x, x, yAyA xSyxSy yRxyRx 稱稱S S為為R R的對偶關系的對偶關系q (1) (1) 證明證明S S也是也是A A上的偏序關系。上的偏序

10、關系。q (2) (2) 如果如果R R是整數集合上的小于或等于關系，那么是整數集合上的小于或等于關系，那么S S是是什么關系？如果什么關系？如果R R是正整數集合上的整除關系，那么是正整數集合上的整除關系，那么S S是什么關系是什么關系? ?q (3) (3) 偏序集偏序集和和AS中的極大元、極小元、最中的極大元、極小元、最大元、最小元等之間有什么關系？大元、最小元等之間有什么關系？ 12q 證明：證明：(1)(1)證明證明S S也是也是A A上的偏序關系上的偏序關系。q 先證先證S S具有自反性具有自反性q xAxA 由于由于R R具有自反性，所以具有自反性，所以 RRq 由由S S的定義

11、知：的定義知：S , S , 所以所以S S具有自反性。具有自反性。q 再證再證S S具有反對稱性具有反對稱性q x x，y A,y A,若若S S 并且并且SSq 那么由那么由S S的定義知：的定義知：RR并且并且RRq 由于由于R R是偏序關系，所以是偏序關系，所以R R具有反對稱性具有反對稱性, , 所以所以 x=yx=yq 所以所以S S具有反對稱性。具有反對稱性。 13q 再證再證S S具有傳遞性具有傳遞性q x x，y y，zAzA, ,若若S S 并且并且SSq 由由S S的定義知：的定義知：R R 并且并且RRq 又因又因R R為偏序關系，所以為偏序關系，所以R R具有傳遞性具

12、有傳遞性q 所以所以 RRq 再由再由S S的定義知：的定義知：SSq 所以所以S S具有傳遞性。具有傳遞性。q 綜上所述綜上所述S S為為A A上的偏序關系。上的偏序關系。 14q (2)(2)如果如果R R是整數集合上的小于或等于關系，那么是整數集合上的小于或等于關系，那么S S是是什么關系？如果什么關系？如果R R是正整數集合上的整除關系，那么是正整數集合上的整除關系，那么S S是什么關系是什么關系? ?q 如果如果R R是整數集合上的小于或等于關系，那么是整數集合上的小于或等于關系，那么S S是是A A上的上的大于或等于關系。大于或等于關系。q 如果如果R R是正整數集合上的整除關系，

13、那么是正整數集合上的整除關系，那么S S是正整數集是正整數集合上的倍數關系。合上的倍數關系。 15q (3)(3)偏序集偏序集和和AS中的極大元、極小元、最大元、中的極大元、極小元、最大元、最小元等之間有什么關系？最小元等之間有什么關系？q 偏序集偏序集極大元是極大元是AS中的極小元，偏序集中的極小元，偏序集q 極小元是極小元是AS中的極大元、偏序集中的極大元、偏序集最大元是最大元是ASq 中的最小元，偏序集中的最小元，偏序集最小元是最小元是AS中的最大元。中的最大元。 1615.15.設設R R為為A A上的關系，則上的關系，則R R在在A A上傳遞當且僅當（上傳遞當且僅當（R R R R） R R證明：必證明：必要性：若要性：若 R R在在A A上具有傳遞性上具有傳遞性 R R R R t ( R R ) t ( R R ) R ( R (因為因為R R在在A A上傳遞上傳遞) ) 所以所以 R R R R R R 充分性：若充分性：若（R R R R） R R ， R R R R R R R ( R ( 因為因為R R R R) R R) 所以所以R R在在A A上傳遞。上傳遞。 17練習：練習：1 設設A, B，C為為集合，集合，若若A B=A C，則，則B=C？2 設設A, B，C為為集合，集合，若若A B=A C，