教材习题解答
第一章 集合及其运算
P8习题
3. 写出方程x2?2x?1?0的根所构成的集合。
解：x2?2x?1?0的根为x??1，故所求集合为{?1} 4.下列命题中哪些是真的，哪些为假
a)对每个集A，??A；b)对每个集A，??A； c)对每个集A，A?{A}；d)对每个集A，A?A； e)对每个集A，A?A；f)对每个集A，A?{A}； g)对每个集A，A?2A；h)对每个集A，A?2A； i)对每个集A，{A}?2A；j)对每个集A，{A}?2A； k)对每个集A，??2A；l)对每个集A，??2A； m)对每个集A，A?{A}；n)??{?}；
o){?}中没有任何元素；p)若A?B，则2A?2B
q)对任何集A，A?{x|x?A}；r)对任何集A，{x|x?A}?{y|y?A}；
{x|x?A}?{A|A?A}；s)对任何集A，y?A?y?{x|x?A}；t)对任何集A，
答案：假真真假真假真假真假真真假假假真真真真真 5.设有n个集合A1,A2,?,An且A1?A2???An?A1，试证：
A1?A2???An
证明：由A1?A2?A4???An?A1，可得A1?A2且A2?A1，故A1?A2。 同理可得：A1?A3?A4???An 因此A1?A2?A3???An 6.设S?{?,{?}}，试求2S？
1
解：2S?{?,{?},{{?}},{?,{?}}}
7.设S恰有n个元素，证明2S有2n个元素。
证明：（1）当n＝0时，S??,2S?{?},2S?1?20，命题成立。
（2）假设当n?k(k?0,k?N)时命题成立，即2S?2k（S?k时）。那么对于?S1（S1?k?1），2S1中的元素可分为两类，一类为不包含S1中某一元素x的集合，另一类为包含x的集合。显然，这两类元素个数均为2k。因而2S1?2k?1，亦即命题在n?k?1时也成立。 由（1）、（2），可证得命题在n?N时均成立。
P16习题
1.设A、B是集合，证明:
(A\\B)?B?(A?B)\\B?B??
证：?当B??时，显然(A\\B)?B?(A?B)\\B，得证。
?假设B??，则必存在x?B，使得x?(A\\B)?B但x?(A?B)\\B，故
(A\\B)?B?(A?B)\\B与题设矛盾。所以假设不成立，故B??。
2.设A、B是集合，试证A???B?A?B
证：?显然。
?反证法：假设A??，则?x0?A，若x0?B，则x0?左，但x0?右，矛盾。若x0?B，则x0?左，但x0?右，矛盾。故假设不成立，即A??。 3. 设A，B，C是集合，证明：
(A?B)?C?A?(B?C)
证：(A?B)?C?[(A\\B)?(B\\A)]?C?[(A?BC)?(B?AC)]?C
?[(A?BC)?(B?AC)\\C]?(C\\((A?BC)?(B?AC)))?(A?B?C)?(B?A?C)?(C?((A?B)?(B?A)))CCCCCC
?(A?BC?CC)?(B?AC?CC)?(C?((AC?BC)?(A?B)))
2
?(A?BC?CC)?(AC?B?CC)?(AC?BC?C)?(A?B?C)
由上式可以看出此展开式与A、B、C的运算顺序无关，因此，
(A?B)?C?A?(B?C)
4.设A，B，C为集合，证明A\\(B?C)?(A\\B)\\C
证：因为A\\(B?C)?A?(B?C)C?A?BC?CC= (A?BC)\\C= (A\\B)\\C。 5.设A，B，C为集合，证明：
(A?B)\\C?(A\\C)?(B\\C)
证：(A?B)\\C?(A?B)?CC?(A?CC)?(B?CC)＝(A\\C)?(B\\C)。 6.设A，B，C为集合，证明：
(A?B)\\C?(A\\C)?(B\\C)
证明：(A?B)\\C?(A?B)?CC?A?B?CC?(A?CC)?(B?CC) =(A\\C)?(B\\C)
7.设A，B，C都是集合，若A?B?A?C且A?B?B?C，试证B=C。
证：证1： ?x?B，则
若x?A，则x?(A?B)。由于A?B?A?C，故x?(A?C)，即x?C；
若x?A，则x?(A?B)，由于A?B?A?C，故x?A?C。又x?A，只能有x?C。因此，?x?B，总有x?C，故B?C。
同理可证，C?B。 因此B?C。
证2： B?B?(A?B)?B?(A?C)?(B?A)?(B?C) ?(C?A)?(B?C)?C?(A?B)?C?(A?C)?C 8.设A，B，C为集合，试证：
(A\\B)\\C?(A\\B)\\(C\\B)
证：证Ⅰ?x?(A\\B)\\C，有x?A,x?B,x?C，因此，x?(A\\B)，x?(C\\B)。故x?(A\\B)\\(C\\B)，即(A\\B)\\C?(A\\B)\\(C\\B)。
3
?x?(A\\B)\\(C\\B)，A\\B)，x?(C\\B)。反之，有x?(因此x?A,x?B,x?C。
故x?(A\\B)\\C，即(A\\B)\\(C\\B)?(A\\B)\\C。
所以 (A\\B)\\C＝(A\\B)\\(C\\B)。
证Ⅱ：(A\\B)\\(C\\B)?(A?BC)?(C?BC)C?(A?BC)?(CC?B) ?(A?BC)?CC?(A\\B)\\C 9.设X?Y?Z，证明Z\\(Y\\X)?X?(Z\\Y)
证：证1：?x?Z\\(Y\\X)?Z?(Y?XC)C?Z?(YC?X)，有x?Z且x?Y 或x?X。则
若x?Z且x?Y，则x?Z\\Y，于是x?X?(Z\\Y)。 若x?Z且x?X，则x?X?(Z\\Y)，从而
Z\\(Y\\X)?X?(Z\\Y)。
反之，?x?X?(Z\\Y)，则x?X或x?Z\\Y。
若x?X，则由X?Y?Z有x?Y,x?Z，故x?Y\\X，因此x?Z\\(Y\\X)。 若x?Z\\Y，则x?Z但x?Y，故x?Y\\X，因此x?Z\\(Y\\X)。从而
X?(Z\\Y)?Z\\(Y\\X)。
由集合相等的定义，Z\\(Y\\X)?X?(Z\\Y)。
证2：Z\\(Y\\X)?Z?(Y?XC)?Z?(YC?X)?(Z?YC)?(Z?X)， 因为X?Z，所以Z\\(Y\\X)?(Z?YC)?X?X?(Z\\Y)。 10.下列命题是否成立？
(1)(A\\B)?C?A\\(B\\C)；(2)A?(B\\C)?(A?B)\\C； (3)A\\(B?C)?(A?B)\\B。
解：（1），（2），（3）都不成立。反例如下：
（1）A??,C?{1},B任意，则(A\\B)?C?C?{1};A\\(B\\C)??。 （2）A?{1},B??,C?{1}，则A?(B\\C)?{1};(A?B)\\C??。
4
（3）A??,B?{1},C?{1,2}，则A\\(B?C)??;(A?C)\\B?{2}。 11．下列命题哪个为真？
a)对任何集合A,B,C，若A?B?B?C，则A=C。 b)设A,B,C为任何集合，若A?B?A?C，则B=C。 c)对任何集合A,B，2A?B?2A?2B。 d)对任何集合A,B，2A?B?2A?2B。 e)对任何集合A,B，2A\\B?2A\\2B。 f)对任何集合A,B，2A?B?2A?2B。 答案：d是真命题。
12．设R,S,T是任何三个集合，试证：
（1）S?T?(S?T)?(S?T)； （2）R?(S?T)?(R?S)?(R?T)；
（3）(R?S)?(R?T)?R?(S?T)?(R?S)?(R?T)； （4）R?(S?T)?(R?S)?(R?T) 证：（1）?x?S?T?(S\\T)?(T\\S)，则
若x?S，则x?T。因而x?(S?T)且x?(S?T)，故x?(S?T)?(S?T)； 若x?S，则x?T，同理可得x?(S?T)?(S?T)。故
S?T?(S?T)?(S?T)。
反之，因为(S?T)?(S?T)，故
(S?T)?(S?T)＝(S?T)\\(S?T)[?(S?T)\\(T?S)??]。
?x?(S?T)?(S?T)?(S?T)\\(S?T)，有x?(S?T),x?(S?T)。 若x?S，则x?T，故x?S?T； 若x?S，则x?T，故x?S?T。因此
(S?T)?(S?T)?S?T。
所以 S?T＝(S?T)?(S?T)。
5
（2）证：?x?(R?S)?(R?T)，有x?(R?S)且x?(R?T)。则 若x?R，则x?S且x?T，故x?(S?T)，x?R?(S?T)。
若x?R，则x?S且x?T。故x?(S?T)，因此x?R?(S?T)。于是
(R?S)?(R?T)?R?(S?T)。
（3）证：?x?(R?S)?(R?T)，有x?(R?S)且x?(R?T)。则 若x?R，则x?S,x?T，故x?(S?T)，因此x?R?(S?T)； 若x?R，则x?S,x?T，故x?(S?T)，x?R?(S?T)。于是
(R?S)?(R?T)?R?(S?T)
反之，?x?R?(S?T)，则
若x?R，则x?(S?T)，故x?S,x?T，因而x?(R?S),x?(R?T)。即
x?(R?S)?(R?T)；
若x?R，则x?(S?T)，故x?S或x?T。因此x?(R?S)或x?(R?T)，从而x?(R?S)?(R?T)。
综上可得：R?(S?T)?(R?S)?(R?T)。于是
(R?S)?(R?T)?R?(S?T)?(R?S)?(R?T)
证：?x?(R?S)?(R?T)，则
若x?(R?S)，则x?(R?T)，因而x?R,x?T,x?S。故x?S?T，于是
x?R?(S?T)；
若x?(R?S)，则y?(R?T)，与上同理可得x?R?(S?T)。 综上可得：R?(S?T)?(R?S)?(R?T)。
14．设A为任一集，{B?}??I为任一集族（I??），证明：
A?(?B?)??(A?B?)
??I??I 6
证：?x?A?(?B?)，则
??I若x?A，则x?A?B?(??I)，因而x??(A?B?)；
??I若x?A，则???I,x?B?，因而???I,x?A?B?，故x??(A?B?)。于
??I是
A?(?B?)??(A?B?)。
??I??I反之，设x??(A?B?)，则???I,x?A?B?。
??I若x?A，显然x?A?(?B?)；
??I若x?A，则???I,x?B?，因而x??B?，即x?A?(?B?)。所以，
??I??I(A?B?)?A?(?B?)。 ????I?I综上可得，A?(?B?)＝?(A?B?)。
??I??I15．填空：设A,B是两个集合。
(a)x?A?B?__________________； (b)x?A?B?__________________；
(c)x?A\\B?___________________； (d)x?A?B?___________________；
解：(a) x?A且x?B； (b) x?A或x?B
(c) x?A或x?B； (d) （x?A且x?B）或（x?A且x?B） 16．设A，B，C为三个集合，下列集合表达式哪一个等于A\\(B?C)？
（a）(A\\B)?(A\\C)；（b）(A?B)\\(A?C) （c）(A\\B)?(A\\C)；（d）(A?B)\\(A?C) （e）(A?B)?(A?C) 答案：c。
(A\\B)?(A\\C)?(A?BC)?(A?CC)?A?(BC?CC)?A?(B?C)?A\\(B?C)P20习题
C
1．设A,B,C为集合，并且A?B?A?C，则下列断言哪个成立？
7
(1)B?C；(2)A?B?A?C；(3)A?BC?A?CC；(4)AC?B?AC?C。 答案：d。
在AC?B?AC?C两边同时并上A即得A?B?A?C。 2．设A,B,C为任意集合，化简
(A?B?C)?(AC?B?C)?(A?BC?C)?(A?B?CC)?(A?B?C)?(A?B?C)?(A?B?C)CCCCCC
证：证1：原式＝(B?C)?(A?BC)?(B?CC)?(AC?BC?C)
?B?(A?BC)?(AC?BC?C)?(A?B)?(AC?BC?C)?(A?B)?((A?B)?C)?A?B?C证2：令原式＝T，全集为S，则
C
S?T?(AC?BC?CC)且T?(AC?BC?CC)??， 故 T?(AC?BC?CC)C?A?B?C。
3．证明：（1）A?B?(A?B)?(AC?BC)；（2）(A?B)C?(A?B)?(AC?BC)；
（3）(A?B)C?(AC?B)?(A?BC)
证：（1）(A?B)?(AC?BC)?((A?B)?AC)?((A?B)?BC) ?(B?AC)?(A?BC)?(A\\B)?(B\\A)?(A?B)
（2）证：(A?B)C?((A?B)?(AC?BC))C 〔根据（1）〕
?(A?B)C?(AC?BC)C?(AC?BC)?(A?B)
（3）证：(AC?B)?(A?BC)?((AC?B)?A)?((AC?B)?BC) 〕 ?(A?B)?(AC?BC)?(A?B)C 〔根据（2）
4．设M1,M2,?和N1,N2,?是集合S的子集的两个序列，对i?j,i,j?1,2,?，有
Ni?Nj??。令Q1?M1,Qn?Mn?(?Mk)C,n?2,3,?。试证：
k?1n?1Nn?Qn??(Ni?Mi)。
i?1n证：?x?Nn?Qn?(Nn\\Qn)?(Qn\\Nn)
8
当n＝1时，x?N1?Q1?N1?M1??(Ni?Mi)，故Nn?Qn??(Ni?Mi)
i?1i?1nn当n≥2时，设x?N?Q?N(Q\\n)Q(nN?\\n)nnn则
有x?(Nn\\Qn)或x?(Qn\\Nn)。
1.若x?(Nn\\Qn)，则x?Nn但x?Qn?Mn?(?Mk),即x?Mn或x??Mk，
ci?1i?1n?1n?1因此有x?Mn或x?Mi(i?n?1)。于是
（1）若x?Nn且x?Mn，有x?Nn\\Mn?Nn?Mn??(Ni?Mi)；
i?1n（2）若x?Nn且x?Mi(i?n?1)，由Ni?Nj??(i?j)，有x?Ni(i?n?1)且
x?Mi，于是x?Mi\\Ni?Mi?Ni??(Ni?Mi)。
i?1n2.若x?Qn\\Nn，则x?Qn?Mn?(?Mk)c，即x?Mn但x?Nn。于是
i?1n?1x?Mn\\Nn?Mn?Nn??(Ni?Mi)。
i?1n综上可得：Nn?Qn??(Ni?Mi)
i?1n5．设X是一个非空集合，An?X,An?1?An,n?1,2,3,?试证：?n，有
An??(Am?Am?n? cm?1)??Am。
m?n? cm?n，故Am?An，显证明：由于Am?1?Am，故Am?Am?1?Am\\Am?1。因为
??然有?(Am?Am?n cm?1)??Am?An。
m?n对于?x?An，假设存在p(p?n)，使得x?Ap，必可找到其中最小的值p0，使得x?Ap0\\Ap0?1，故x??(Am?Am?n? cm?1)??Am；
m?n? 9
假如不存在p，则x??Am，故x??(Am?Am?nm?n?? cm?1)??Am。
m?n?综上可得：An?
?m?n?(A?m?A cm?1)??Am。
m?n?所以An＝?(Am?Am?n cm?1)??Am。
m?n?6．设V是任一集合，证明：
?S,T,W?2V有S?T?W当且仅且S?T?S?W且S?W。 证：?因为S?T?W，故S?T?T\\S?W\\S?S?W。
?先证S?T。设x?S，则
若x?T，则x?S\\T?S?T?S?W?W\\S，故x?W且x?S，矛盾。 所以x?T，即S?T。
其次，证明T?W。设x?T，则有两种情况： 若x?S。则x?T\\S?S?T?S?W?W\\S，故x?W。 若x?S。由S?W，知x?W。 总之，?x?T，有x?W，故T?W。
7．设A1,A2,?为一集序列，记A为这样的元素的全体形成的集合：x?A当且仅当在序列A1,A2,?中有无穷多项An含有x。集合A称为集序列A1,A2,?的上极限，记为limAn，即limAn?A。又记A为这样的元素全体形成的集合；序列A1,A2,?n??n??中只有有限项不含有这样的元素。称A为序列A1,A2,?的下极限，并记
limAn?A。证明；
n??（1）limAn???Ak；（2）limAn???Ak。
n??n?1k?nn??n?1k?n????证： （1）?x?limAn，在序列A1,A2,?中只有有限项不含x，在不含x的
n??项中必可找到下标最大的一项Ap?1（若各项均含x，则令p＝0），有x??Ak，
k?p? 10
故x???Ak，即
n?1k?n??limAn???Ak。
n??n?1k?n??反之，?x???Ak，必?p使得x??Ak，即?k?p时，x?Ak。而集合
n?1k?n???k?pA1,A2,?,AP?1中即使都不含有x，但也仅有有限项不含x，故x?limAn。因此
n??n?1k?n??Ak?limAn。
n????综上可得：limAn＝??Ak。
n??n?1k?n??（2）?x?limAn，因为A1,A2,?中有无穷多项含有x，故?N，当n?N时，
n??x?An，因此x??Ak，从而x???Ak，即
k?nn?1k?n???limAn???Ak
n??n?1k?n??反之，?x???Ak，则?n?1,x??Ak，即A1,A2,?中有无穷多项多含x，
n?1k?n???k?n所以x?limAn，即
n??n?1k?n??Ak?limAn
n????综上可得：limAn???Ak。
n??n?1k?n??8．证明：limAn?limAn
n??n??证：?x?limAn，由limAn定义可知：序列A1,A2,?中只有有限项不含x，故
n??n??必可找
到不含x的下标最大的一项AP，可见此时AP?1,AP?2,?均含x，即有无限项含x，故x?limAn。因此
n??limAn?limAn。
n??n??
11
P25习题
1．设A?{a,b,c},B?{e,f,g,h},C?{x,y,z}。求A?B,B?A,A?C,A2?B。
解：
A?B?{(a,e),(a,f),(a,g),(a,h),(b,e),(b,f),(b,g),(b,h),(c,e),(c,f),(c,g),(c,h)}B?A?{(e,a),(e,b),(e,c),(f,a),(f,b),(f,c),(g,a),(g,b),(g,c),(h,a),(h,b),(h,c)}A?C?{(a,x),(a,y),(a,z),(b,x),(b,y),(b,z),(c,x),(c,y),(c,z)} A2?B?{((a,a),e),((a,a),f),((a,a),g),
((a,a),h),((a,b),e),((a,b),f),((a,b),g),((a,b),h),((a,c),e),((a,c),f),((a,c),g),((a,c),h),((b,a),e),((b,a),f),((b,a),g),((b,a),h),((b,b),e),((b,b),f),((b,b),g),((b,b),h),((b,c),e),
((b,c),f),((b,c),g),((b,c),h),((c,a),e),((c,a),f),((c,a),g),((c,a),h),((c,b),e),((c,b),f),((c,b),g),((c,b),h),((c,c),e),((c,c),f),((c,c),g),((c,c),h)}2．设A,B为集合，试证：A×B＝B×A的充要条件是下列三个条件至少一个成立：
（1）A??；（2）B??；（3）A?B。
证：?若（1）成立，A?B???B?A。 若（2）成立，同上。
若（3）成立，A×B=B×B=B×A。
?假设必要性不成立，即A??,B??,A?B。故不妨设?x使得x?A,x?B。设y?B，则(x,y)?A?B,(x,y)?B?A，矛盾。 于是，假设不成立。因而必要性成立。
必要性也可以如下证明：
1.若A?B?B?A??，则A??或B??。
,y?B2.若A?B?B?A??，则?x?A，有(x,y)?A?B?B?A。于是x?B,y?A，因此A?B且B?A，故A=B。
3．设A,B,C,D为任四个集合，证明：
(A?B)?(C?D)?(A?C)?(B?D)
证：?(x,y)?(A?B)?(C?D)，有x?A?B,y?C?D，即
x?A,x?B,y?C,y?D。所以(x,y)?A?C,(x,y)?B?D，因此
12
(x,y)?(A?C)?(B?D)，从而
(A?B)?(C?D)?(A?C)?(B?D)。
反之，?(x,y)?(A?C)?(B?D)，有x?A,x?B,y?C,y?D。即
(x,y)?(A?B)?(C?D)，从而
(A?C)?(B?D)?(A?B)?(C?D)。
因此，(A?B)?(C?D)＝(A?C)?(B?D)。 4．设E1,E2,E3,E4为任意集合，试证：
(E1?E2)\\(E3?E4)?((E1\\E3)?E2)?(E1?(E2\\E4))
证：?(x,y)?(E1?E2)\\(E3?E4)，有x?E1,y?E2且x?E3或y?E4。则 若x?E3，则x?E1\\E3)，故(x,y)?(E1\\E3)?E2)，即
(x,y)?((E1\\E3)?E2)?(E1?(E2\\E4))。
若y?E4，同理可证(x,y)?((E1\\E3)?E2)?(E1?(E2\\E4))。从而
(E1?E2)\\(E3?E4)?((E1\\E3)?E2)?(E1?(E2\\E4))。
反之，?(x,y)?((E1\\E3?)E2?)(E1?(E2\\E4，))则(x,y)?(E1\\E3)?E2)或
(x,y)?E1?(E2\\E4)，即x?E1，y?E2但x?E3或x?E1，y?E2但y?E4。从而有(x,y)?E1?E2，但(x,y)?E3?E4，即(x,y)?(E1?E2)\\(E3?E4)，从而
((E1\\E3)?E2)?(E1?(E2\\E4))?(E1?E2)\\(E3?E4)。
综上可得：(E1?E2)\\(E3?E4)＝((E1\\E3)?E2)?(E1?(E2\\E4))。 5．设A?X,B?Y，试证：(A?B)C?(AC?B)?(A?BC)?(AC?BC)
证：?(x,y)?(A?B)C，则(x,y)?(A?B)，故x?A或y?B。于是 1. 若x?A，则x?AC。因此
(1)若y?B，则(x,y)?AC?B?(AC?B)?(A?BC)?(AC?BC)。
13
(2) 若y?B，则y?BC，即(xy,)?ACB?2.若x?A，则必有y?B，故(x,y)?A?BCC?(ACB?)(A?B?)C(AB??)CCC?(AC?B)(A?B?)C(A?B?)C。 。
综上可得：(A?B)C?(AC?B)?(A?BC)?(AC?BC)。 反之，?(x,y)?(AC?B)?(A?BC)?(AC?BC)，则
(x,y)?AC?B或(x,y)?A?BC或(x,y)?AC?BC，于是，
(1)若(x,y)?AC?B，则x?A且x?B，即(xy于是(x,y)?(A?B)C。 ,)?AB?，
,)?AB?，(2)若(x,y)?A?BC，则x?A且x?B，即(xy于是(x,y)?(A?B)C。 ,)?AB?，(3)若(x,y)?AC?BC，则x?A且x?B，即(xy于是(x,y)?(A?B)C。
综上可得：(AC?B)?(A?BC)?(AC?BC)?(A?B)C。 于是(A?B)C?(AC?B)?(A?BC)?(AC?BC)。 7．设A,B,C是三个任意集合，证明：
A?(B?C)?(A?B)?(A?C)
证：A?(B?C)?A?((B\\C)?(C\\B))?A?(B\\C)?A?(C\\B)
?((A?B)\\(A?C))?((A?C)\\(A?B))?(A?B)?(A?C)
8．设A,B为集合，下列命题哪些为真？
（1）(x,y)?A?B?x?A且y?B （2）(x,y)?A?B?x?A或y?B （3）2A?B?2A?2B
（4）若A?C?B?C，则A?B。 （5）若A?C?B?C,C??，则A?B。
答案：（2），（5）为真。
9．设A有m个元素，B有n个元素，则A×B是多少个序对组成的？A×B有多少个不同的子集？
答：A×B有mn个序对；A×B有2mn个不同子集。
10．设A,B是两个集合，B??，试证：若A?B?B?A，则A?B。
14
证：?x?A，因为B??，故在B中任取一元素y，必有(x,y)?A?B，因而
(x,y)?B?B，故x?B。从而A?B。
反之，?x?B，因为B??，故在B中任取一元素y，必有(x,y)?B?B，因而(x,y)?A?B，故x?A。从而B?A。
于是A?B。
P33习题
1.某班学生中有45％正在学德文，65％正在学法文。问此班中至少有百分之几的学生正同时学德文和法文？
解：设A,B分别为正在学德文和法文的学生的集合，班级总人数为n，则
A?n?45%,B?n?65%，于是同时学习德文和法文的人数为A?B，故 A?B?A?B?n?n?10%。
于是全班至少百分之十的学生同时学德文和法文。
2．求1到250之间不能被2，3，5，7中任一数整除的数的个数。
解：设S?{1,2,?,250}，在S上的定义性质Pn具有性质P11,P2,P3,P4,?n?S，（相应地P2,P3,P4）当且仅当2|n(3|n,5|n,7|n)。
令Ai为S中具有性质Pi之集，i?1,2,3,4，则
??250??A1??2k|k?1,2,?,???2??????250??A2??3k|k?1,2,?,???3????
??250??A3??5k|k?1,2,?,???5??????250??A4??7k|k?1,2,?,???7????所求为：
S?A1?A2?A3?A4?250?((125?83?50?35)?(41?25?17?16?11?7)?(8?5?3?2)?1)
?250?(293?117?18?1)?57 15
3．设A,B是两个有限集，试求22解：22A?BA?B??
?22A?B?22A?B?22A?B
4．马大哈写n封信，n个信封，把n封信放入到n个信封中，求全部装错的概率是多少？
解：Sn?n!，令A表示所有信都装错的集合，即
A?{i1,i2,?,in|i1?1,i2?2,?,in?n}。
令Ai表示第i个信封恰好装对的集合，则AiC?A。所以全部装错的集合为：
CC。 A?A1C?A2???An于是，易得
Ai?(n?1)!,Ai?Aj?(n?2)!,i?j。
对于1?i1?i2???ik?n，有 Ai1?Ai2???Aik?(n?k)!。又
A?A?A???A?S??Ai?n!??Ai?C1C2Cni?1i?1nn1?i?j?n?Ai?Aj???(?1)?n!(1?n?Ai?1ni12n?n!?Cn(n?1)!?Cn(n?2)!???(?1)nCn(0)!1111?????(?1)n)，故1!2!3!n!AA?1111?P????1??????(?1)n??e?1?0.3678Snn!?1!2!3!n!?
〔答案：0.3679，当n≥10时，概率都近似等于0.3679〕。
5．毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子至少与一个姑娘跳过舞，
但未能与所有姑娘跳过。同样地，每个姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子跳过舞。证明：在所有参加舞会的小伙与姑娘中，必可找到两个小伙子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞，而这两个姑娘中的每一个也只与这两个小伙中的一个跳过舞。
证：设F?{f1,f2,?,fn}是小伙的集合，G?{g1,g2,?,gm}是姑娘的集合。 与f1跳舞的姑娘的集合用Gf1表示； 与f2跳舞的姑娘的集合用Gf2表示；
? ? ?
与fn跳舞的姑娘的集合用Gfn表示；
16
于是，由题意：Gf1?Gf2???Gfn?G且Gfi??且Gfi?G，i?1,2,3,?,n。 若存在Gfi,Gfj(i?j)，使得Gfi?Gfj且Gfj?Gfi，则结论成立。 反证法：假设不存在Gfi和Gfj满足Gfi?Gfj且Gfj?Gfi。于是
?i,j(i?j),Gfi与Gfj应满足：Gfi?Gfj或Gfj?Gfi必有一个成立。 因此把Gf1，Gf2，?，Gfn重新排列有：Gf i1?Gfi2???Gfin。从而fin与所有的姑娘都跳过舞，矛盾。
因此假设不成立，本题得证。
17
第二章 映 射
P39习题
1. 设A，B是有穷集，A?m,B?n
（1）计算AB；（2）从A到A有多少个双射？ 解：（1）AB?mn；（2）从A到A共有m!个双射。
2. 设X是一个有穷集合，证明：从X到X的部分映射共有(X?1)X个。
证：设f:A?X,A?X，则f是X到X的一个部分映射。 设X?n
00当A??时，f的个数为Cnn?1 11当A是单元素集时，f的个数为Cnn?n 22当A中有2个元素时，f的个数为Cnn
?
kk当A中有k个元素时，f的个数为Cnn
?
nn当A中有n个元素时，f的个数为Cnn
0011kknn因此f的总个数为Cnn+Cnn+?+Cnn+?+Cnn＝(1?n)n
＝(X?1)X
即从X到X的部分映射共有(X?1)X个。
4.设u1,u2,?,umn?1是一个两两不相交的整数构成的数列，则必有长至少为n?1的递增子序列或有长至少为m?1的递减子序列。
证：令A?{u1,u2,?umn?1}，则A?mn?1。 设以ui为首项的最长递增子序列的长度为??i， 设以ui为首项的最长递减子序列的长度为??i。
18
反证法：假设题中结论不成立，则??,2,3,?,mn?1。 i?n,?i?m,i?1??是单射。 令?:A?{1,2,?,n}?{1,2,?,m},?ui?A，?(ui)?(??,?ii)，则
实际上，?ui,uj?A且ui?uj(i＜j)，则
?????若ui＞uj，则??i＞?j，所以(?i,?i)?(?j,?j)；
即?(ui)??(uj)。
?????若ui＜uj，则??i＞?j，所以(?i,?i)?(?j,?j)；
即?(ui)??(uj)。
故?为单射，从而就有mn?1?mn矛盾。
P43习题
1. 证明：从一个边长为1的等边三角形中任意选5个点，那么这5个点中必有2个点，它们之间的距离至多为1/2，而任意10个点中必有2个点其距离至多是1/3。
证：(1) 将边长为1的等边三角形4等分，得到4个边长为1/2的小等边三角形。
任给5个点，由鸽巢原理可知必有一个小等边三角形里面至少有2个点，又因为小等边三角形中任意两个点之间的距离至多为1/2，因此5个点中必有2个点，它们之间的距离至多为1/2。
(2) 连接各边的三等分点，则可得到9个边长都为1/3的小等边小角形，每个小等边三角形中任意两个点之间的距离至多为1/3。将10个点放入该大等边三角形中，则由鸽洞原理，必有一个小等边三角形中至少有2个点，因此任意10个点中必有2个点其距离至多为1/3。
2.已知m个整数a1,a2,?am，试证：存在两个整数k,?,0?k＜??m，使得
ak?1?ak?2???a?能被m整除。
证：考察下式：
19
a1a1?a2a1?a2?a3?a1?a2???am
若第i式能被m整除，则显然成立，此时k?0,??i；
若任一式都不能被m整除，则考察各式被m整除后的余数，如下式：
a1?q1m?r1a1?a2?q2m?r2a1?a2?a3?q3m?r3?a1?a2???am?qmm?rm
由于每一个都不能被m整除，故共有m个余数—相当于m个物体。而任意整数被m除后，只有m－1个余数——相当于m－1抽屉，于是由鸽巢原理可知必有两个余数相等。设这两个余数为ri,rj,i?j(i＜j)，对应两式相减便有：
ai?1?ai?2???aj可被m整除，此时k?i,??j。
3. 证明在52个整数中，必有两个整数，使这两个整数之和或差能被100整除。
证：设a1,a2,?,a52是52个整数，令?i为ai被100除后所得的余数，即
ai?100qi??i,0??i?99,i?1,2,?,52[相当于52个物体]。
任意一个整数被100除以后的余数为0，1，2，…，99，把它们分成51个类，即{0},{1,99},{2,98},…{49,51},{50}[相当于51个盒子]。
把52个余数?i,i?1,2,?,52放入到51个类中，必在两个余数放在一个类里。 设在一个类中的两个余数分别为?i与?j，i?j。则有
（1） 若?i??j，则?i??j?0，即ai?aj能被100整除。 （2） ?i??j，则?i??j?0，即ai?aj能被100整除。
5.设a1,a2,?,an为1,2,3,?,n的任一排列，若n是奇数且
(a1?1)(a2?2)?(an?n)?0，
则乘积为偶数。
解：反证法：若(a1?1)(a2?2)?(an?n)为奇数，则(ai?i)中的ai与i必是一
20
?n??n?个为奇数，一个为偶数。而n为奇数，故奇数个数为???1比偶数??多一个，
?2??2?这是不可能的。
P46习题
1.设f:X?Y，C,D?Y，证明f?1(C\\D)?f?1(C)\\f?1(D)
证1：?x?f?1(C\\D)，则f(x)?C\\D，即f(x)?C但f(x)?D。于是
x?f?1(C)但x?f?1(D)，因此x?f?1(C)\\f?1(D)， 故f?1(C\\D)?f?1(C)\\f?1(D)
反之，设x?f?1(C)\\f?1(D)，有x?f?1(C)且x?f?1(D) 因此f(x)?C且f(x)?D，即f(x)?C\\D 从而x?f?1(C\\D)
故f?1(C)\\f?1(D)?f?1(C\\D)
因而f?1(C\\D)?f?1(C)\\f?1(D)
证2：f?1(C\\D)?f?1(C?Dc)?f?1(C)?f?1(DC)
?f?1(C)?(f?1(D))C?f?1(C)\\f?1(D)
2. 设f:X?Y, A,B?X，证明
（1）f(A?B)?f(A)?f(B) （2）f(A?B)?f(A)?f(B) （3）f(A)\\f(B)?f(A\\B)
证：（1）设y?f(A?B)，则?x?A?B使得y?f(x)。于是，x?A或x?B。因此，y?f(A)或y?f(B)，所以y?f(A)?f(B)，故
f(A?B)?f(A)?f(B)
21
反之，设y?f(A)?f(B)，则y?f(A)或y?f(B)。于是?x?A或x?B，使得f(x)?y。因此不论何种情况都?x?A?B，使得f(x)?y。因此y?f(A?B)，故
f(A)?f(B)?f(A?B)
因此，f(A)?f(B)?f(A)?(B)
（2）设y?f(A?B)，则?x?A?B，使得y?f(x)。于是，x?A且x?B。 从而，y?f(A)且y?f(B)，所以y?f(A)?f(B)，故
f(A?B)?f(A)?f(B)
（3）设y?f(A)\\f(B)，则y?f(A)但y?f(B)。于是?x?A使得f(x)?y，且x?B，从而?x?A\\B，使得f(x)?y。
故y?f(x)?f(A\\B)，即
f(A)\\f(B)?f(A\\B)。
3.设f:X?Y，A?X,B?Y，证明：
f(f?1(B)?A)?B?f(A)
证：设y?f(f?1(B)?A)，则?x?f?1(B)?A，使得f(x)?y。于是x?f?1(B)且x?A，即f(x)?B且f(x)?f(A)，因此y?f(x)?B且y?f(A)，即
y?B?f(A)，从而
f(f?1(B)?A)?B?f(A)。
反之，设y?B?f(A)，则y?B且y?f(A)。于是?x?A且x?f?1(B)，使得f(x)?y。从而?x?f?1(B)?A，使得f(x)?y，因此y?f(f?1(B)?A)。从而
B?f(A)?f(f?1(B?A)) 因此，f(f?1(B?A))?B?f(A)。
4.设f:X?Y,A?X,B?Y。以下四个小题中，每个小题均有四个命题，这四个
22
命题有且仅有一个正确，请找出正确的那个。
（1）（a）若f(x)?f(A)，则x未必在A中 （b）若f(x)?f(A)，则x?A （c）若f(x)?f(A)，则x?A
（d）若f(x)?f(A)，则x?Ac
（2）（a）f(f?1(B))?B （b）f(f?1(B))?B
（c）f(f?1(B))?B （d）f(f?1(B))?Bc （3）（a）f?1(f(A))?A （b）f?1(f(A))?A
（c）f?1(f(A))?A （d）上面三个均不对 （4）（a）f(A)?? （b）f(B)??
（c）若y?Y,则f?1(y)?x （d）若y?Y,则f?1(y)?x 答案：（a）（b）（c）（d）
7.设f:X?Y,A?X,则(f(A))c?f(Ac)成立吗？
解：不成立。
反例：设X?{1,2,3},Y?{a,b,c}。
f:X?Y,f(1)?a,f(2)?a,f(3)?b。
1 o 2 o o a o b o c X Y 令A?{1,2}，则Ac?{3}。
f(A)?{a}，(f((A))?{b,c},但f(A)?b。
cc3 o 8.设X是一个无穷集合，f:X?Y。证明：存在X的一个真子集E使得f(E)?E。
证：取x0?X，令x1?f(x0),x2?f(x1),?,xn?f(xn?1),?。若到某一位与前面有重复项，设为第k项，即f(xk)?xi(i?k)。令E?{x0,x1,x2,?,xk}?X，则
f(E)?E且E?X。
若xi互不相同，令E1?X\\{x0}?X，则f(E1)?E1。 [不去掉x0可能就会有E1?X]
23
9.设f:A?B，证明?T?2B，都有f(f?1(T))?T?f(A)
证；若T??，则f(f?1(T))??,T?f(A)??,因而f(f?1(T))?T?f(A)。 若T??，设y?f(f?1(T))，则?x?f?1(T)，使得f(x)?y且x?A，于是
y?f(x)?T且y?f(x)?f(A)，因此y?T?f(A)。
故f(f?1(T))?T?f(A)
反之，设y?T?f(A)，则y?T且y?f(A)。于是?x?f?1(T)且x?A，使得f(x)?y。从而，f(x)?f(f?(T)且f(x)?f(A)，因此y?f(x)?f(f?1(T)?A))，而f?1(T)?A，所以f(f?1(T)?f(A)，于是y?f(f?1(T))，故
T?f(A)?f(f?1(T))
从而T?f(A)?f(f?1(T))
P50习题
1.设X?{a,b,c},Y?{0,1},Z?{2,3},f:X?Y,f(a)?f(b)?0，
f(c)?1;g:Y??，g(0)?2,g(1)?3，试求g?f。
解：
g?f(a)?g(0)?2g?f(b)?g(0)?2 g?f(c)?g(1)?3因此g?f:X?Z,g?f(a)?2,g?f(b)?2,g?f(c)?3。
2.设X,Y,Z是三个非空集合，Z?2。证明：f:X?Y是满射当且仅当不存在从Y到Z的映射g1和g2，使得g1?g2，但g1?f?g2?f。
证：?因f:X?Y且f为满射，故?y?Y,?x?X，使得f(x)?y。 假设存在g1,g2,g1?g2，但g1?f?g2?f。因为g1?g2，所以?y0?Y，使得对于上面的y0，?x0?X（f是满射），使得g1(f(x0))?g2(f(x0)) g1(y0)?g2(y0)。
[g1(y0)?g2(y0)]，即g1f(x0)?g2f(x0)。故g1?f?g2?f与g1?f?g2?f，矛盾。
24
所以假设不成立。 也可以用如下方法：
f满射?f右可逆??h:Y?X，使得f?h?IY?假设g1?f?g2?f得到
g1?g2，命题得证。
?f:X?Y，假设f不是满射，则?y0?Y，使得?x?X,f(x)?y0。构造两个映射g1,g2:Y?Z，
当y?y0时，g1(y0)?g2(y0)； 当y?y0时，g1(y)?g2(y)。 因为Z?2，故此时g1?g2，但
?x?X,g1?f(x)?g1(y?y0)?g2(y?y0)?g2?f(x)
即g1?f＝g2?f，与假设不存在g1?g2，但g1?f?g2?f矛盾，故f一定是满射。 3.设X,Y,Z是三个非空的集合，X?2，证明：f:X?Y是单射当且仅当不存在从Z到X的映射g1,g2，使得g1?g2，但f?g1?f?g2。
证：?f是单射，则?x1,x2,x1?x2，有f(x1)?f(x2)。假设存在g1和g2：
Z?X,g1?g2，因为X?2，于是?z0?Z，使得g1(z0)?g2(z0)。
而由于f为单射，故f(g，，故?f(g)即f?g?g1(z0))2(z0)1(z0)?f2(z0)f?g1?f?g2矛盾。
可以用：f单射?f左可逆的??h使得hf?IX?由f?g1?f?g2?g1?g2得证。
逆否命题：g1?g2?fg1?fg2。
则?x1,x2?X,x1?x2，但f(x1)?f(x2)。构造两个映射g1?假设f不是单射，
和g2:Z?X,?z?Z,令g1(z)?x1,g2(z)?x2，由于X?2，故若x1?x2，则有
g1?g2。但?z?Z,f?g1(z)?f(x1)?f(x2)?f?g2(z)，于是有f?g1?f?g2矛盾。
25
P55习题
1. 设N?{1,2,3,?}，试构造两个映射f和g：N?N，使得
（1）fg?IN，但gf?IN； （2）gf?IN，但fg?IN。
解：（1）fg?IN但gf?IN，故f是满射，但f不是单射。于是令：
f:N?N,f(1)?1,f(n)?n?1,n?2，g:N?N,?n?N,g(n)?n?1，则
fg?IN但gf?IN。事实上，当n＝1时，gf(1)?g(f(1))?g(1)?2，故gf?IN。
（2）自己做。 2.设f:X?Y则
（1）若存在唯一的一个映射g:Y?X，使得gf?IX，则f是可逆的吗？ （2）若存在唯一的一个映射g:Y?X，使得fg?IY，则f是可逆的吗？ 答案：（1）f不一定可逆。 当X?1时，f不一定可逆。 当X?2时，f可逆。 （2）f一定可逆。
证：由fg?IY，得f是单射。假设f不是满射，则g不唯一，矛盾。 3.设f:X?Y,X?m,Y?n，则
（1）若f是左可逆的，则f有多少个左逆映射？ （2）若f是右可逆的，则f有多少个右逆映射？ 解：令X?(x1,x2,?,xm),Y?(y1,y2,?,yn)，则 （1）如图1(a)所示：有mn?m；（2）如图1(b)所示：有
f?1(y1)?f?1(y2)???f?1(yn)。
26
x1x2x3xmy1y2y3ymn-m个y1y2y3yn（a） (b)
图1
5. 是否有一个从X到X的一一对应f，使得f?f?1，但f?IX？ 解：存在。f为对换即可。
P63习题
?12345??12345??1?11.设?1???，?2＝??，求?1?2,?2?1,?1,?2。
?43215??32514?解：
?12345??12345??1?2???,?2?1???15234???23541??1?1???12345??1?12345??,?2???43215???42153?
?123456789?2.将置换??分解成对换的乘积。
?791652348??123456789?解： ????173??29846?
791652348??=(1 7)(1 3)(2 9)(2 8)(2 4)(2 6)
3.设?是任一n次置换，试证：?与??1的奇偶性相同。
证：假设?与??1的奇偶性不同，不妨设?为奇置换，??1为偶置换。因为
???1?I（I为恒等置换），又I?(ij)(ij)，因而I是偶置换。
??1是奇置换与I是偶置换矛盾。 而??因而假设不成立，故?与??1奇偶性相同。
27
5.任一偶置换均可被分解成3－循环置换（123），（124）…（12n）中若干之乘积。
证：?i,j,s,t?{1,2,?,n}, i?j,s?t
(ij)(st)?(1i)(1j)(1i)(2s)(2t)(2s)?(1i)(1j)(2s)(1j)(2t)(2s)
?(1i)(2s)(1j)(2t)(1i)(2s)
?(12s)(12i)(12t)(12j)(1 2 s)(1 2 i)
?12s??12i??12si?因为(12s)(12i)?????????(1i)(2s)
2s12i1is21???????12t??12(12t)(12j)?????2t1??2j因此本题得证。 6. 证明下列置换等式
（1）(ac1?chbd1?dk)(ab)?(ac1?ch)(bd1?dk)
j??12tj??????(1j)(2t) 1??jt21??ac1c2?chbd1?dk?证：(ac1?chbd1?dk)(ab)???(ab)
?c1c2c3?bd1d2?a??ac1c2?chbd1?dk?＝??
ccc?add?b12?123??(ac1?ch)(bd1?dk)
?ac1?chbd1?dk?（2）(ac1?ch)(bd1?dk)(ab)???(ab)
?c1c2?ad1d2?b??ac1?chbd1?dk?????(ac1?chbd1?dk) cc?bdd?a?1212?8.在所有的n次置换中，有多少个n—循环置换？
?ii?in?解：(i1,i2,?,in)??12?
?i2i3?i1?对i1，有n种选择 对i2，有（n-1）种选择 ??
对in有1种选择
28
因此共有n!种排列
对每个n－循环置换，均有n种排列，因此
n!n－循环置换的个数为?(n?1)!个
nP70习题
3. 找一个既不满足交换律又不满足结合律的二元运算
解：n维向量空间中向量的叉积运算。 4. 给出一个三元运算的例子
解：求三个正整数的最大公因数。
5. 设A?{a,b,c,d}，A上的代数运算“?”如表所示。代数运算“?”是否满足交换律？结合律？“?”有单位元吗？
解：不满足交换律，因为运算表不对称。d?c?a,c?d?d,d?c?c?d。也不
(b?b)?c?a?c?c满足结合律，b?(b?c)?b?a?b
(b?b)?c?b?(b?c)单位为a o a b c d a a b c d b b a a c c c a b a d d c d b 6.设N?{1,2,3,?}，?m,n?N,m?n?nlog10m。
那么“?”是N上的代数运算吗？为什么？ 解：当m=1时，log10m?0，nlog10m?0,0?N
因此“?”不是N上的代数运算。
7. 设“?”是X上的代数运算，则应该怎样定义“?”的逆运算？回忆一下，逆运算通常比原运算“难算”，这是为什么？例如，积分比微分难，减法比加法难，除法比乘法难，开方比幂方运算难。
解：“?”的逆运算可以这样定义：一个从X到X?X?X???X?Xn的映射 “?”称为X上的n元运算的逆运算
“?”的逆运算的象集所在的集合X?X?X???X的元素的个数是X的元素个数的mn?1倍（设X?m），因而逆运算的个数很多，因此得到其中的一种就较困难，故逆运算较难算。
29
第三章 关 系
P86习题
1.给出一个既不是自反的又不是反自反的二元关系？
解：设X?(a,b,c),R是X上的一个二元关系且R?{(a,a),(a,b)}即可。 2.是否存在一个同时不满足自反性，对称性，反对称性，传递性和反自反性的二元关系？
解：存在。
设X?{a,b,c}，R是X上的二元关系R?{(a,a),(a,c),(a,b),(c,a)}。 3.设R，S是X上的二元关系，下列命题哪些成立：
a)若R与S是自反的，则R?S,R?S分别也是自反的。 b) 若R与S是对称的，则R?S,R?S分别对称的 c) 若R与S是传递的，则R?S也是传递的 d) 若R与S不是自反的，则R?S也不是自反的 e) 若R与S是反自反的，则R?S,R?S也是反自反的 f) 若R是自反的，则Rc也是反自反的。
g) 若R与S是传递的，则R\\S是传递的 答案：真真真假真真假
4.实数集合上的“小于”关系?是否市反自反的？集合X的幂集上的“真包含”关系?是否是反自反的？为什么？
证：实数集合上的“小于”关系?是反自反的；
集合X的幂集上的“真包含”关系?也是反自反的。
5.设R、S是X上的二元关系。证明：
（1）(R?1)?1?R；（2）(R?S)?1?R?1?S?1
（3）(R?S)?1?R?1?S?1；（4）若R?S，则R?1?S?1
证：（1）?(x,y)?(R?1)?1，则(y,x)?R?1，即(x,y)?R，因此(R?1)?1?R。 反之，?(x,y)?R，则(y,x)?R?1，即(x,y)?(R?1)?1，因此R?(R?1)?1。 从而(R?1)?1?R
（2）?(x,y)?(R?S)?1，则(y,x)?R?S，
30
即(y,x)?R或(y,x)?S。于是(x,y)?R?1或(x,y)?S?1， 即(x,y)?R?1?S?1，因而(R?S)?1?R?1?S?1。 反之，?(x,y)?R?1?S?1，则(x,y)?R?1或(x,y)?R?1。 于是(y,x)?R或(y,x)?S，即(y,x)?R?S。 从而(x,y)?(R?S)?1，因此，R?1?S?1?(R?S)?1。 故(R?S)?1?R?1?S?1
（3）?(x,y)?(R?S)?1，则(y,x)?R?S。于是(y,x)?R且(y,x)?S， 从而(x,y)?R?1且(x,y)?S?1，即(x,y)?R?1?S?1 因此(R?S)?1?R?1?S?1
反之，设(x,y)?R?1?S?1，则(x,y)?R?1且(x,y)?S?1 于是(y,x)?R且(y,x)?S，即(y,x)?R?S。 从而(x,y)?(R?S)?1，因此R?1?S?1?(R?S)?1 故R?1?S?1?(R?S)?1
（4）?(x,y)?R?1，则(y,x)?R
因为R?S，所以(y,x)?S，于是(x,y)?S?1 因而R?1?S?1
6.设R是X上的二元关系，证明：R?R?1是对称的二元关系。
证1：(R?R?1)?1?R?1?(R?1)?1，故R?R?1是对称的。
证2：则(x,y)?R或(x,y)?R?1，即(y,x)?R?1或(y,x)?R。 ?(x,y)?R?R?1，于是(y,x)?R?R?1，因此R?R?1是对称的。
9.有人说：“若R是X上的二元关系，只要R是对称的和传递的，则R必是自反的。”他的证明如下：若xRy，则由R的对称性便知有yRx。于是由xRy和yRx以及R的传递性即得xRx。所以，R是自反的。他的推论错在什么地方？这个结论是否对呢？
31
解：若R??，则R是对称的，传递的，反自反的。
若R??，只有?x?X使得xRx，才能说R是自反的。此人只是说明了X中的部分元素满足了xRx，因而是错误的。
所以这个结论不对。
P92习题
1.“父子“关系的平方是什么关系？
解：“父子“关系的平方是”祖孙“关系
2.设X={1,2,3,4},R={(1,2),(2,2),(3,4)},S={(2,3),(3,1),(4,2)}
试求：R?S,S?R,R2,S2,R?(S?R),(R?S)?R。 解：
R?S?{(1,3),(2,3),(3,2)}S?R?{(2,4),(3,2),(4,2)} R?{(1,2),(2,2)} S2?{(2,1),(4,3)}2
R?(S?R)?R?{((2,4),(3,2),(4,2)} ?{(1,4),(2,4),(3,2)}(R?S)?R={(1,3),(2,3),(3,2)}?R ={(1,4),(2,4),(3,2)}
3.设R与S为X上的任两个集合，下列命题哪些为真？
a）若R,S都是自反的，则R?S也是自反的。 b）若R,S都是对称的，则R?S也是对称的。 c）若R,S都是反自反的，则R?S也是反自反的。 d）若R,S都是反对称的，则R?S也是反对称的。 e）若R,S都是传递的，则R?S也是传递的。 答案：真假假假假
4.设R1是A到B，R2和R3是B到C的二元关系，则一般情况下
R1?(R2\\R3)?(R1?R2)\\(R1?R3)。但有人声称等号成立，他的证明如下：设则?b?X，使得(a,b)?R1且(b,c)?R2\\R3。于是(b,c)?R2且(a,c)?R1?(R2\\R3)，
(b,c)?R3。从而(a,c)?R1?R2且(b,c)?R1?R3，所以(a,c)?(R1?R2)\\(R1?R3)，即R1?(R2\\R3)?(R1?R2)\\(R1?R3)。同理可证相反的包含关系成立，故等式成立，这个证明错在什么地方？
解：由(a,c)?R1,(b,c)?R2且(b,c)?R3，只能得到(a,b)?R1?R2。但(a,c)?R1?R3不一定成立。
例如(a,a)?R1,(a,c)?R3时，(a,c)?(R1?R3)
32
故这步推理错误
5.设R，S是X上的满足R?S?S?R的对称关系，证明R?S?S?R.
证1：设(x,z)?S?R，则?y?X,使得(x,y)?S且(y,z)?R。 因为R，S均对称，所以R?R?1,S?S?1 于是(y,x)?S?1?S,(z,y)?R?1?R
从而(z,x)?R?S,(x,z)?(R?S)?1?(S?R)?1?R?1?S?1?R?S 因此S?R?R?S 故S?R?R?S
证2S?R?S?1?R?1?(R?S)?1?(S?R)?1?R?1?S?1?R?S，故S?R?R?S，于是R?S?S?R
6.设R为X上的对称关系，证明：?n?N,Rn是对称关系。
证1(Rn)?1?(R?R???R)?1?R?1?R?1???R?1?R?R??R?Rn，故R对称。 证2?(x,y)?Rn，则?y1,y2,?,yn?1?X，使得
(x,y1)?R,(y1,y2)?R,?,(yn?1,y)?R。因为
R对称，所以
(y,yn?1)?R,(yn?1,yn?2)?R,?,(y2,y1)?R,(y1,x?R)，因此(y,x)?Rn，故R对称。
证3用数学归纳法对n进行归纳。 当n=1时，Rn=R显然是对称的。 假设当n=k时，Rk对称。
当n=k+1时，Rk?1?Rk?R?R?Rk。
?(x,y)?Rk?1，则?z?X，使得(x,z)?Rk,(z,y)?R。
因为Rk，R均是对称的，所以(y,z)?R,(z,x)?Rk，于是(y,x)?R?Rk?Rk?1。 因此Rk+1对称。
综上，Rn对n?N都是对称关系。
7.设R1,R2,R3,?是X上的二元关系的一个无穷序列，则当每个Ri是对称关系时，
?Ri还是对称的吗？
i?1? 33
证：则?i0的使得(x,y)?Rio。因为Ri0对称，所以有(y,x)?Rio，?(x,y)??Ri，
i?1?故(y,x)??Ri。因此?Ri还是对称的。
i?1i?1??P98习题
1.设R是X上的二元关系，试证（1）
(R?)??R?,(2)(R*)*?R*,(3)R?R*?R*?R?R?,(4)(R?)*?(R*)??R?。 证：（1）因为R??(R?)?显然成立。
其次，设(a,b)?(R?)?，因为(R?)?是一切包含R?的传递关系的交，而
R??(R?)?且R?是传递的，故(a,b)?R?，即(R?)??R?。
因此(R?)??R?。
（2）因为R??(R?)?显然成立。
其次，设(a,b)?(R?)?，因为(R?)?是一切包含R?的自反传递关系的交，而R?
本身是自反的也是传递的且R??(R?)?，故(a,b)?R?，即(R?)??R?，因此
(R?)??R?。
（3）R?R??R?(R0?R?R2??)?R?R2?R3???R?
R??R?(R0?R?R2??)?R?R?R2?R3???R? （4）先证(R?)??R?
(R?)??(R?)0?(R?)??IX?R??R? 再证(R?)??R?
因为(R?)?是包含R?的一切传递关系的交，又因为R??(R?)?且R?是传递的，所以(R?)??R?。
因此(R?)??(R?)??R?。
2.设X＝（a,b,c,d,e），R＝｛（a,b），（b,c），（c,d），（d,e）｝试求R?和R?。
34
解：R2?{(a,c),(b,d),(c,e)}
R3?{(a,d),(b,e)}R4?{(a,e)}R5??
故R??R?R1?R2?R3?R4?R5?{(a,b),(b,c),(c,d),(d,e),(a,c),
(b,d),(c,e),(a,d),(b,e),(a,e)}
R??IX?R??{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(b,c),(c,d),(d,e),(a,c),(b,d),(c,e),(a,d),(b,e),(a,e)}3.设R,S为X上的二元关系，试证：
（1）(R?S)??R??S? （2）(R?S)??R??S?。 证：（1）因为R?R?S,S?R?S 所以R??(R?S)?,S??(R?S)? 因此R??S??(R?S)? （2）因为R?R?S,S?R?S 所以R??(R?S)?,S??(R?S)?
因此R??S??(R?S)? 〔证毕〕 6.举例说明s(t(R))与t(s(R))确定不相等。
解：设N?{1,2,3,?}，在N上定义小于关系“＜”，则
s(t(?))?s(?)?“不等关系≠”。 t(s(?))?t(?)?“全关系”。
因此的确不相等。
7.是否可以定义二元关系的反自反闭包与二元关系的反对称闭包？为什么？
解：不可以。
因为二元关系的反自反闭包和反对称闭包是空集，没有多少研究价值。因此不定义二元关系的反自反闭包和反对称闭包。
8.是否存在X（X=n）上的一个二元关系R使得R,R2,?,Rn两两不相等。
35
解：存在。
设X?{1,2,3,?,n}，则R是X上的二元关系且R?{(1,2),(2,3),?,(n?1,n)}即可满足要求。
9.证明：若R是对称的，则R＋也是对称的。
证：
?(x,y)?R??Ri，则?m?N，使得(x,y)?Rm。因为若R是对称的，所
?i?1?以R也是对称的，因此(y,x)?R??Ri。即R?也是对称的。
mm?i?110.设R1,R2是X上的二元关系，证明：
（1）r(R1?R2)?r(R1)?r(R2) （2）S(R1?R2)?s(R1)?s(R2) （3）t(R1?R2)?t(R1)?t(R2)
证：（1）因为r(R1)和r(R2)都是A上的自反关系，所以r(R1)?r(R2)也A上的自反关系。
由R1?r(R1),R2?r(R2)，得R1?R2?r(R1)?r(R2)，所以r(R1)?r(R2)是包含
R1?R2的自反关系。由自反闭包的定义可知：r(R1?R2)?r(R1)?r(R2)
又R1?R1?R2,R2?R1?R2，故r(R1)?r(R1?R2)，r(R2)?r(R1?R2)，因此
r(R1)?r(R2)?r(R1?R2)。从而r(R1?R2)?r(R1)?r(R2) （2）同（1）的证明。
（3）因为R1?R1?R2,R2?R1?R2，故t(R1)?t(R1?R2),t(R2)?t(R1?R2)，因此t(R1)?t(R2)?t(R1?R2)。
例：设X?{a,b,c}，A上的两个关系R1?{(a,b)},R2?{(b,c)}。于是
t(R1)?{(a,b)},t(R2)?{(b,c)}，故t(R1)?t(R2)?{(a,b),(b,c)}，但 R1?R2?{(a,b),(b,c)},t(R1?R2)?{(a,b),(b,c),(a,c)}。 因此t(R1?R2)?t(R1)?t(R2)。
36
P113习题
1.设X?{1,2,3},Y?{1,2},S?{f|f:X?Y}。?是S上的二元关系：
（2）求等价类f,g?S,f?g?Im(f)?Im(g)。证明（1）?是S上的等价关系，的集合。
证：（1）等价关系显然。
（2）f:X?Y，共有8个，如图4所示。
123f112123f2112112123f323f42
123f521123f621123f721123f821图4
?f?S，[f]R?{g|Im(f)?Im(g)}，故
[f1]R?{f1}，[f2]R?{f2,f3,f4,f5,f6,f7}，[f3]R?{f3}。 故等价类集合为{[f1]R,[f2]R,[f3]R}。
22.?P113?（1）等价关系显然。
(2)如图4所示。
?f?S，[f]R?{g|f(1)?f(2)?f(3)?g(1)?g(2)?g(3)}。故
[f1]R?{f1}?{g|g(1)?g(2)?g(3)?3},[f2]R?{f2,f3,f5}?{g|g(1)?g(2)?g(3)?4},[f4]R?{f4,f6,f7}?{g|g(1)?g(2)?g(3)?5},[f8]R?{f8}?{g|g(1)?g(2)?g(3)?6}.33. ?P113?（1）?是等价关系显然。
37
（2）?f?S，[f]R?{g|{f?1(y)|y?Y}?{g?1(y)|y?Y}}。
[f1]R?{f1,f8}?{{1,2,3},?}[f2]R?{f2,f7}?{{1,2},{3}}[f3]R?{f3,f6}?{{1,3},{2}}[f4]R?{f4,f5}?{{1},{2,3}}故等价类集合为{[f1]R,[f2]R,[f3]R,[f4]R}。
?124.由置换????36354856127?8上的一个关系?,,8}?确定了X?{1,27?4?:i,j?X,i?当且仅当ji与j在?的循环分解式中的同一循环置换中，证明：?是X上的等价关系，求X/?。
证；???135??26??48??7?
?i?X，i与i必在?的循环分解式中的同一个循环置换中，即i?i，则?是自反的。
?i,j?X，若i?j，即i与j在?的循环分解式中和同一个循环置换中，则
j与i也在?的循环分解式中的同一个循环置换中，故j?i。因而?是对称性的。
?i,j,k?X，若i?j,j?k，则i与j在?的循环分解式中的同一个循环置换
中，j与k在?的循环分解式的同一个循环置换中，因而i与k也在?的循环分解式中的同一个循环置换中，即i?k。因而?是传递性的。
所以?是X上的等价关系。
5.给出X＝{1,2,3,4}上两个等价关系R与S，使得R?S不是等价关系。
解：如R?{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)}
S?{(1,1),(2,2),(3,3),(4,4),(2,3),(3,2)}
R?S?{(1,1),(2,2),(3,3),(4,4),(2,3),(3,2),(1,2),(1,3),(2,1)}因为(1,3)?R?S，但(1,3)?R?S，所以R?S不对称.. 因此R?S不是等价关系。 13.设X是一个集合，X?n，试求：
（1）X上自反二元关系的个数； （2）X上反自反二元关系的个数； （3）X上对称二元关系的个数； （4）X上自反或对称关系的个数； 解：（1）X上自反二元关系的个数为2n
38
2?n
（2）X上反自反二元关系的个数为2（3）X上对称二元关系的个数为2n2?n
n2?n2
?n（4）X上自反或对称关系的个数为2n2?2n2?n2?2n2?n2
P125习题
1.设[a,b]是一个有限区间。令S是区间[a,b]上的有限划分的集合，[a,b]的一个划分?是形如a?x1?x2???xn?b,n?N的点的集合。在S上定义二元关系R如下：
??1,?2?S,?1R?2??2的每个分点也是?1的分点。
证明：R是S上的偏序关系（注意，这里的划分与等价关系中的划分不同）。
证：???S,?的每个分点也是?的分点，故?R?，因此R是自反的；
??1,?2?S，若?1R?2且?2R?1，则?2的每个分点也是?1的分点且?1的每个分点也是?2的分点，故?1??2。因此R是反对称的；
??1,?2,?3?S，若?1R?2且?2R?3，则?2的每个分点是?1的分点，而且?3的每个分点也是?2的分点，因此?3的每个分点也是?1的分点，故?1R?3。因此R是传递的。
综上可知：R是S上的偏序关系。
2.设(S,?1),(T,?2)是偏序集。在S?T上定义二元关系T,?3如下：
?(s,t),(s?,t?)?S?T，(s,t)?3(s?,t?)?(s?1s?,t?2t?)。 证明：（1）?3是S?T上的偏序关系；
（2）若(s,t)?3(s?,t?)?s?1s?或t?2t?，则?3是S?T上的偏序关系吗？ 证：1.(1)?(s,t)?S?T，则s?S,t?T。由于(S,?1),(T,?2)是偏序集，故有
s?1s,t?2t?(s,t)?3(s,t)。
从而?3是自反的；
(2)?(s1,t1),(s2,t2)?S?T，若(s1,t1)?3(s2,t2)且(s2,t2)?3(s1,t1)，则
39
(s1?1s2且s2?1s1)且(t1?2t2且t2?2t1)。
由(S,?1),(T,?2)是偏序集可知，s1?s2且t1?t2，故(s1,t1)?(s2,t2)。 因此“?3”是对称的。
(3)?(s1,t1),(s2,t2),(s3,t3)?S?T，若(s1,t1)?3(s2,t2)且(s2,t2)?3(s1,t1)，有由(S,?1),(T,?2)是偏序集可知：?1与?2是传(s1?1s2,s2?1s3)且(t1?2t2,t2?2t3)。
递的，所以s1?1s3且t1?2t3。故(s1,t1)?3(s3,t3)，因此?3是传递的。
综上可知：?3是S?T上的一个偏序关系。
2.此题若改为：(s,t)?3(s?,t?)?s?1t或s??2t?，则?3不是偏序关系。因为?3不满足反对称性。
例如：(I,?3)，则(1,2)?3(2,1)且(2,1)?3(1,2)，但(1,2)?(2,1)。故?3不满足反对称性，因此?3不是S?T偏序关系。
3.存在一个偏序关系?，使得(X,?)中有唯一的极大元素，但没有最大元素？若有请给出一个具体例子；若没有，请证明之。
解：存在。
设X?{i,1,2,3,?}，其中i??1。在X上定义的小于或等于关系“?”，则
(X,?)就是一个没有最大元素，但却有唯一极大元i的偏序集。
5.令S＝｛1，2，…，12｝，画出偏序集（S,|）的Hass图，其中“|”是整除关系，它有几个极大（小）元素？列出这些极大（小）元素
极大元素有6个，分别是7，8，9，10，11，12 极小元素有1个是1
6.设R是X的自反且传递的二元关系，则
（1）给出R的一个实例；
（2）在X上定义二元关系~是：x~y?xRy,yRx。
证明：~是X上的等价关系。
（3）在商集X~上定义二元关系?是：[a]?[b]?aRb。
证明：?是X~上的偏序关系。 证：（1）(I,?)即可
40
（2）自反、对称显然。下面看传递性
因为若x~y且y~z?xRy,yRx且yRz,zRy；由R是传递的，有xRz，zRx。由题意有x~z，故~是传递的。
因此~是X上的等价关系。
（3）?[a]?X所以?是自反的；
?[a],[b]?X~~，因为R是X上的自反关系，故aRa。而aRa?a[]?a[]，
，若[a]?[b],[b]?[a]?aRb,bRa，则a与b在一个等类中，故
[a]?[b]，因此?是反对称的；
?[a],[b],[c]?X~]?[b],[]b[]?c?aRbbR,c，若[a，则由R的传递性有aRc，
即[a]?[c]。因此?是传递的。
综上可知：?是X~上的偏序关系。
7.设R是X上的偏序关系，证明：
R是X上的全序关系?X?X?R?R?1。
证：由于R是X上的全序关系，故(x,y)?R或(y,x)?R?1??(x,y)?X?X，必有一个成立。所以(x,y)?R?R?1，即X?X?R?R?1；
反之，因为R是X上的关系，故R?X?X，R?1?X?X，所以
R?R?1?X?X。
因此X?X?R?R?1。
? ?(x,y)?X?X?R?R?1，有(x,y)?R或(x,y)?R?1，即xRy与yRx必有一个成立，故R是X上的全序关系。
41
第四章 无穷集合及其基数
P136习题 1.设A为由序列
a1,a2,?,an,?
的所有项组成的集合，则是否市可数的？为什么？
解：因为序列是可以重复的，故
若A是由有限个数组成的集合，则A是有限的集合； 若A是由无限个数组成的集合，则A是可数的。 故本题A是至多可数的。
2.证明：直线上互不相交的开区间的全体所构成的集合至多可数。
证：在每个开区间中取一个有理数，则这些有理数构成的集合是整个有理数集合Q的子集，因此是至多可数的。
3.证明：单调函数的不连续点的集合至多可数。
证：设A是所有不连续点的集合，f是一个单调函数，则?x0?A,x0对应着一个区间(f(x0?0),f(x?0))，于是由上题便得到证明。 4.任一可数集A的所有有限子集构成的集族是可数集合。
证：设A?{a1,a2,?,an,?},B?{ai1,ai2,?,aik},则B?A且B?k??。 令??{BB?A,B??}，
设?:A?{0,1}，则?是Ａ的子集的特征函数。
?B??,?(B)?｛0，1的有穷序列｝，即?ai?A，
若ai?B，则对应1；若ai?B则对应0。于是
?B??,?(B)就对应着一个由0，1组成的有限序列0，1，1，0，?，0，1。
此序列对应着一个二进制小数，而此小数是有理数。于是，可数集A的所有有限子集?对应着有理数的一个子集。
又?B1,B2??,B1?B2,B1,B2对应的小数也不同，故?是单射。而可数集Ａ的
42
所有有限子集?是无穷的，故?是可数的。 5．判断下列命题之真伪：
(1)若f:X?Y且f是满射，则只要X是可数的，那么Y是至多可数的； (2)若f:X?Y且f是单射，那么只要Y是可数的，则X也是可数的； (3)可数集在任一映射下的像也是可数的； 答案：对，错，错。
7．设Ａ是有限集，Ｂ是可数集，证明：BA?{f|f:A?B}是可数的。
证：令A?{1,2,?,n},B?{b1,b2,?,bn,?}，Ｂ可数。 设f:A?B,?i?A,f(i)?B。
（BA中的每个f实际上就是Ｂ的一个有限子集，可数集的有限子集是可数的。于是由４题即可证明）
（f(k1),f(k2),?,f(kn))?B?B???B?Bn。 用数学归纳法可以证明BA是可数的，但Bn?BA。
8. 设?为一个有限字母表，?上所有字（包括空字）之集记为??。证明??是可数集
证１：设有限字母?上所有字（包括空字?）所形成的集??，则??是可数的。
Ａ1＝{长度为1的字符串} Ａ2＝{长度为2的字符串}
? ?
Ａn＝{长度为n的字符串}
? ?
因为Ａi 中每个长度都是有限的，而?＝?Ai，故??是至多可数的。又????i?1显然是无穷的，故??是可数的。
证2：不妨假设??{a,b,c}（令?＝{0,1}也是可以），则可按字典序排序为：
43
由于?*的全部元素可以排成无重?,a,b,c,aa,ab,ac,ba,bb,bc,?,aaa,aab,?。复项的无穷序列，故?*是可数的。
P142习题
2.找一个初等可数f(x)，使得它是(0,1)到实数R的一一对应。
?解：Ctgx,或tgx，或tg(x?)
23.试给出一个具体的函数，使得它是从(0,1)到[0,1]的一一对应。
111证：(0,1)中包含一个可数子集A?{,2,3,?}可数。
222111A1?A?{0,1}?{0,1,,2,3,?}——可数的，故A?A1。
222令?:(0,1)?[0,1],?x?(0,1)
当x?A?x?01?当x?2???(x)??11
当x??4??1当x?1,i?3??2i?22i?(x)即为所求。
4.证明：若A可数，则2A不可数。（用对角线方法）。
证：A可数，则令A?{1,2,3,?}。
假设2A可数，则A的子集（即2A的元素）是可数的，故2A中元素可排成一个无重复项的无穷序列：
A1,A2,?,An?
而2A~Ch(A)?{ff:A?{0,1}}，于是特征函Ch(A)可数，即Ch(A)可写成下列无穷序列形式：
f1,f2,?,fn?
44
f1:a11a12a13?f2:a21a22a23?f3:a31a32a33? ? ? ?fn:an1an2an3?? ? ??造一个特征函数?。令??{bi}1
其中aij?0或1,j?1,2,3,?。
?1 若a11?0b1??；0 若a?1?11?1 若a22?0b2??；?0 若a22?1 ? ?1 若ann?0bn???0 若ann?1 ? 则??f1,f2,f3,?,fn,?,但?确实是A到{0,1}的一个映射，即?是A的子集的特征函数，矛盾。故2A不可数。
5．令N?{1,2,3,?}，S?{ff:N?{0,1}},利用康托对角线法证明S是不可数集。
证:假设从N到{0, 1}的所有映射之集可数，则可排成无重复项的无穷序列
f1,f2,f3,?。每个函数fi确定了一个0,1序列ai1,ai2,ai3,?。构造序列若aii?0；否则bi?0。该序列对应的函数f(i)?bi，i?N， b1,b2,b3,?,bi?1，
不为f1,f2,?任一个，矛盾。
45