哈工大《离散数学》教科书习题答案.doc

《哈工大《离散数学》教科书习题答案.doc》由会员分享，可在线阅读，更多相关《哈工大《离散数学》教科书习题答案.doc（45页珍藏版）》请在沃文网上搜索。

1、教材习题解答第一章 集合及其运算习题3. 写出方程的根所构成的集合。解：的根为，故所求集合为4.下列命题中哪些是真的，哪些为假a)对每个集A，；b)对每个集A，；c)对每个集A，；d)对每个集A，；e)对每个集A，；f)对每个集A，；g)对每个集A，；h)对每个集A，；i)对每个集A，；j)对每个集A，；k)对每个集A，；l)对每个集A，；m)对每个集A，；n)；o)中没有任何元素；p)若，则q)对任何集A，；r)对任何集A，；s)对任何集A，；t)对任何集A，；答案：假真真假真假真假真假真真假假假真真真真真5.设有n个集合且，试证：证明：由，可得且，故。同理可得：因此6.设，试求解：7.设S

2、恰有n个元素，证明有个元素。证明：（1）当n0时，命题成立。（2）假设当时命题成立，即（时）。那么对于（），中的元素可分为两类，一类为不包含中某一元素的集合，另一类为包含的集合。显然，这两类元素个数均为。因而，亦即命题在时也成立。由（1）、（2），可证得命题在时均成立。习题1.设A、B是集合，证明:证：当时，显然，得证。假设，则必存在，使得但，故与题设矛盾。所以假设不成立，故。2.设A、B是集合，试证证：显然。反证法：假设，则，若，则左，但右，矛盾。若，则左，但右，矛盾。故假设不成立，即。3. 设A，B，C是集合，证明：证：由上式可以看出此展开式与A、B、C的运算顺序无关，因此，4.设A，B，

3、C为集合，证明证：因为= = 。5.设A，B，C为集合，证明：证：。6.设A，B，C为集合，证明：证明： =7.设A，B，C都是集合，若且，试证B=C。证：证1： ，则若，则。由于，故，即；若，则，由于，故。又，只能有。因此，总有，故。同理可证，。因此。证2： 8.设A，B，C为集合，试证：证：证，有，因此，。故，即。反之，有，。因此。故，即。所以 。证： 9.设，证明证：证1：，有且或。则若且，则，于是。若且，则，从而。反之，则或。若，则由有，故，因此。若，则但，故，因此。从而。由集合相等的定义，。证2：，因为，所以。10.下列命题是否成立(1)；(2)；(3)。解：（1），（2），（3）都

4、不成立。反例如下：（1）任意，则。（2），则。（3），则。11下列命题哪个为真a)对任何集合A,B,C，若，则A=C。b)设A,B,C为任何集合，若，则B=C。c)对任何集合A,B，。d)对任何集合A,B，。e)对任何集合A,B，。f)对任何集合A,B，。答案：d是真命题。12设R,S,T是任何三个集合，试证：（1）；（2）；（3）；（4）证：（1），则若，则。因而且，故；若，则，同理可得。故。反之，因为，故。 ，有。若，则，故；若，则，故。因此。所以 。（2）证：，有且。则若，则且，故，。若，则且。故，因此。于是。（3）证：，有且。则若，则，故，因此；若，则，故，。于是反之，则若，则，故，因

5、而。即；若，则，故或。因此或，从而。综上可得：。于是证：，则若，则，因而。故，于是；若，则，与上同理可得。综上可得：。14设A为任一集，为任一集族（），证明：证：，则若，则，因而；若，则，因而，故。于是。反之，设，则。若，显然；若，则，因而，即。所以，。综上可得，。15填空：设A,B是两个集合。(a)_； (b)_； (c)_；(d)_； 解：(a) 且； (b) 或 (c) 或； (d) （且）或（且）16设A，B，C为三个集合，下列集合表达式哪一个等于（a）；（b）（c）；（d）（e）答案：c。习题1设A,B,C为集合，并且，则下列断言哪个成立(1)；(2)；(3)；(4)。答案：d。在两

6、边同时并上A即得。2设A,B,C为任意集合，化简证：证1：原式证2：令原式T，全集为S，则且，故 。3证明：（1）；（2）； （3）证：（1） （2）证： 根据（1）（3）证： 根据（2）4设和是集合S的子集的两个序列，对，有。令。试证：。证： 当n1时，故当n2时，设有或。则1.若，则但，因此有。于是（1）若且，有；（2）若且，由，有且，于是。2.若，则但。于是。综上可得：5设X是一个非空集合，试证：，有。证明：由于，故。因为，故，显然有。对于，假设存在，使得，必可找到其中最小的值，使得，故；假如不存在p，则，故。综上可得：。所以。6设V是任一集合，证明：有当且仅且且。证：因为，故。先证。设

7、，则若，则，故且，矛盾。所以，即。其次，证明。设，则有两种情况：若。则，故。若。由，知。总之，有，故。7设为一集序列，记为这样的元素的全体形成的集合：当且仅当在序列中有无穷多项含有。集合称为集序列的上极限，记为，即。又记为这样的元素全体形成的集合；序列中只有有限项不含有这样的元素。称为序列的下极限，并记。证明；（1）；（2）。证： （1），在序列中只有有限项不含x，在不含x的项中必可找到下标最大的一项（若各项均含x，则令p0），有，故，即。反之，必使得，即时，。而集合中即使都不含有x，但也仅有有限项不含x，故。因此。综上可得：。（2），因为中有无穷多项含有x，故，当时，因此，从而，即反之，则，

8、即中有无穷多项多含x，所以，即综上可得：。8证明：证：，由定义可知：序列中只有有限项不含x，故必可找到不含x的下标最大的一项，可见此时均含x，即有无限项含x，故。因此。习题1设。求。解： 2设A,B为集合，试证：ABBA的充要条件是下列三个条件至少一个成立：（1）；（2）；（3）。证：若（1）成立，。若（2）成立，同上。若（3）成立，AB=BB=BA。假设必要性不成立，即。故不妨设使得。设，则，矛盾。于是，假设不成立。因而必要性成立。必要性也可以如下证明：1.若，则或。2.若，则，有。于是，因此且，故A=B。3设A,B,C,D为任四个集合，证明：证：，有，即。所以，因此，从而。反之，有。即，从

9、而。因此，。4设为任意集合，试证：证：，有且或。则若，则，故，即。若，同理可证。从而。反之，则或，即，但或，但。从而有，但，即，从而。综上可得：。5设，试证：证：，则，故或。于是1. 若，则。因此(1)若，则。(2) 若，则，即。2.若，则必有，故。综上可得：。反之，则或或，于是，(1)若，则且，即，于是。(2)若，则且，即，于是。(3)若，则且，即，于是。综上可得：。于是。7设是三个任意集合，证明：证： 8设A,B为集合，下列命题哪些为真（1）且（2）或（3）（4）若，则。（5）若，则。答案：（2），（5）为真。9设A有m个元素，B有n个元素，则AB是多少个序对组成的AB有多少个不同的子集答

10、：AB有mn个序对；AB有个不同子集。10设是两个集合，试证：若，则。证：，因为，故在B中任取一元素y，必有，因而，故。从而。反之，因为，故在中任取一元素y，必有，因而，故。从而。于是。习题1.某班学生中有45正在学德文，65正在学法文。问此班中至少有百分之几的学生正同时学德文和法文解：设A,B分别为正在学德文和法文的学生的集合，班级总人数为n，则，于是同时学习德文和法文的人数为，故。于是全班至少百分之十的学生同时学德文和法文。2求1到250之间不能被2，3，5，7中任一数整除的数的个数。解：设，在S上的定义性质，n具有性质（相应地）当且仅当。令为S中具有性质之集，则所求为：3设A,B是两个有

11、限集，试求解：4马大哈写n封信，n个信封，把n封信放入到n个信封中，求全部装错的概率是多少解：，令表示所有信都装错的集合，即。令表示第个信封恰好装对的集合，则。所以全部装错的集合为：。于是，易得。 对于，有 。又答案：，当n10时，概率都近似等于。5毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子至少与一个姑娘跳过舞，但未能与所有姑娘跳过。同样地，每个姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子跳过舞。证明：在所有参加舞会的小伙与姑娘中，必可找到两个小伙子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞，而这两个姑娘中的每一个也只与这两个小伙中的一个跳过舞。证：设是小伙的集合，

12、是姑娘的集合。与跳舞的姑娘的集合用表示；与跳舞的姑娘的集合用表示； 与跳舞的姑娘的集合用表示；于是，由题意：且且，。若存在，使得且，则结论成立。反证法：假设不存在和满足且。于是应满足：或必有一个成立。因此把重新排列有：。从而与所有的姑娘都跳过舞，矛盾。因此假设不成立，本题得证。第二章 映 射习题1. 设A，B是有穷集，（1）计算；（2）从A到A有多少个双射解：（1）；（2）从A到A共有m!个双射。2. 设X是一个有穷集合，证明：从X到X的部分映射共有个。证：设，则f是X到X的一个部分映射。设当时，f的个数为当A是单元素集时，f的个数为当A中有2个元素时，f的个数为当A中有k个元素时，f的个数为

13、当A中有n个元素时，f的个数为因此f的总个数为+即从X到X的部分映射共有个。4.设是一个两两不相交的整数构成的数列，则必有长至少为的递增子序列或有长至少为的递减子序列。证：令，则。设以为首项的最长递增子序列的长度为，设以为首项的最长递减子序列的长度为。反证法：假设题中结论不成立，则。令，则是单射。实际上，且，则若，则，所以；即。若，则，所以；即。故为单射，从而就有矛盾。习题1. 证明：从一个边长为1的等边三角形中任意选5个点，那么这5个点中必有2个点，它们之间的距离至多为1/2，而任意10个点中必有2个点其距离至多是1/3。证：(1) 将边长为1的等边三角形4等分，得到4个边长为1/2的小等边

14、三角形。任给5个点，由鸽巢原理可知必有一个小等边三角形里面至少有2个点，又因为小等边三角形中任意两个点之间的距离至多为1/2，因此5个点中必有2个点，它们之间的距离至多为1/2。(2) 连接各边的三等分点，则可得到9个边长都为1/3的小等边小角形，每个小等边三角形中任意两个点之间的距离至多为1/3。将10个点放入该大等边三角形中，则由鸽洞原理，必有一个小等边三角形中至少有2个点，因此任意10个点中必有2个点其距离至多为1/3。2.已知个整数，试证：存在两个整数，使得能被整除。证：考察下式：若第式能被整除，则显然成立，此时；若任一式都不能被整除，则考察各式被整除后的余数，如下式：由于每一个都不能

15、被整除，故共有个余数相当于个物体。而任意整数被除后，只有1个余数相当于1抽屉，于是由鸽巢原理可知必有两个余数相等。设这两个余数为，对应两式相减便有：可被整除，此时。3. 证明在52个整数中，必有两个整数，使这两个整数之和或差能被100整除。证：设是52个整数，令为被100除后所得的余数，即相当于52个物体。任意一个整数被100除以后的余数为0，1，2，99，把它们分成51个类，即0,1,99,2,98,49,51,50相当于51个盒子。把52个余数放入到51个类中，必在两个余数放在一个类里。设在一个类中的两个余数分别为与，。则有（1） 若，则，即能被100整除。（2） ，则，即能被100整除。

16、5.设为的任一排列，若n是奇数且，则乘积为偶数。解：反证法：若为奇数，则中的与必是一个为奇数，一个为偶数。而n为奇数，故奇数个数为比偶数多一个，这是不可能的。习题1.设，证明证1：，则，即但。于是但，因此，故反之，设，有因此，即从而故因而证2：2. 设，证明（1）（2）（3）证：（1）设，则使得。于是，。因此，所以，故反之，设，则。于是或，使得。因此不论何种情况都，使得。因此，故因此，（2）设，则，使得。于是，且。从而，且，所以，故（3）设，则但。于是使得，且，从而，使得。故，即。3.设，证明：证：设，则，使得。于是且，即，因此且，即，从而。反之，设，则且。于是且，使得。从而，使得，因此。从而

17、因此，。4.设。以下四个小题中，每个小题均有四个命题，这四个命题有且仅有一个正确，请找出正确的那个。（1）（a）若，则未必在A中 （b）若，则 （c）若，则（d）若，则（2）（a） （b）（c） （d）（3）（a） （b）（c） （d）上面三个均不对（4）（a） （b）（c）若 （d）若答案：（a）（b）（c）（d）1 o2 o3 oo ao bo cXY7.设则成立吗解：不成立。反例：设。令，则。，。8.设X是一个无穷集合，。证明：存在X的一个真子集E使得。证：取，令。若到某一位与前面有重复项，设为第k项，即。令，则且。若互不相同，令，则。不去掉可能就会有9.设，证明，都有证；若，则,因而。

18、若，设，则，使得且，于是且，因此。故反之，设，则且。于是且，使得。从而，因此，而，所以，于是，故从而习题1.设，试求。解：因此。2.设X,Y,Z是三个非空集合，。证明：是满射当且仅当不存在从Y到Z的映射和，使得，但。证：因且为满射，故，使得。假设存在，但。因为，所以，使得。对于上面的，（是满射），使得，即。故与，矛盾。所以假设不成立。也可以用如下方法：满射右可逆，使得假设得到，命题得证。，假设不是满射，则，使得。构造两个映射，当时，；当时，。因为，故此时，但即，与假设不存在，但矛盾，故一定是满射。3.设X,Y,Z是三个非空的集合，证明：是单射当且仅当不存在从Z到X的映射，使得，但。证：是单射，

19、则，有。假设存在和：，因为，于是，使得。而由于为单射，故，即，故矛盾。可以用：。逆否命题：。假设不是单射，则，但。构造两个映射和令，由于，故若，则有。但，于是有矛盾。习题1. 设，试构造两个映射和g：，使得（1），但；（2），但。解：（1）但，故f是满射，但f不是单射。于是令：，则但。事实上，当n1时，故。（2）自己做。2.设则（1）若存在唯一的一个映射，使得，则是可逆的吗（2）若存在唯一的一个映射，使得，则是可逆的吗答案：（1）不一定可逆。当时，不一定可逆。当时，可逆。（2）一定可逆。证：由，得是单射。假设不是满射，则g不唯一，矛盾。3.设，则（1）若是左可逆的，则有多少个左逆映射（2）若是

20、右可逆的，则有多少个右逆映射解：令，则（1）如图1(a)所示：有；（2）如图1(b)所示：有。（a） (b)图15. 是否有一个从到的一一对应，使得，但 解：存在。为对换即可。习题1.设，求。解：2.将置换分解成对换的乘积。解： =(1 7)(1 3)(2 9)(2 8)(2 4)(2 6)3.设是任一n次置换，试证：与的奇偶性相同。证：假设与的奇偶性不同，不妨设为奇置换，为偶置换。因为（I为恒等置换），又，因而I是偶置换。而是奇置换与I是偶置换矛盾。因而假设不成立，故与奇偶性相同。 5.任一偶置换均可被分解成3循环置换（123），（124）（12n）中若干之乘积。证：因为因此本题得证。6.

21、证明下列置换等式（1）证：（2）8.在所有的n次置换中，有多少个n循环置换解：对，有n种选择对，有（n-1）种选择对有1种选择因此共有n!种排列对每个n循环置换，均有n种排列，因此n循环置换的个数为个习题3. 找一个既不满足交换律又不满足结合律的二元运算解：n维向量空间中向量的叉积运算。4. 给出一个三元运算的例子解：求三个正整数的最大公因数。5. 设，A上的代数运算“”如表所示。代数运算“”是否满足交换律结合律“”有单位元吗解：不满足交换律，因为运算表不对称。也不满足结合律， 单位为aoabcdaabcdbbaacccabdddcab6.设，。那么“”是N上的代数运算吗为什么解：当m=1时，

22、因此“”不是N上的代数运算。7. 设“”是X上的代数运算，则应该怎样定义“”的逆运算回忆一下，逆运算通常比原运算“难算”，这是为什么例如，积分比微分难，减法比加法难，除法比乘法难，开方比幂方运算难。解：“”的逆运算可以这样定义：一个从X到的映射“”称为X上的n元运算的逆运算“”的逆运算的象集所在的集合的元素的个数是X的元素个数的倍（设），因而逆运算的个数很多，因此得到其中的一种就较困难，故逆运算较难算。第三章 关 系习题1.给出一个既不是自反的又不是反自反的二元关系解：设R是X上的一个二元关系且即可。2.是否存在一个同时不满足自反性，对称性，反对称性，传递性和反自反性的二元关系解：存在。设，R

23、是X上的二元关系。3.设R，S是X上的二元关系，下列命题哪些成立：a)若R与S是自反的，则分别也是自反的。b) 若R与S是对称的，则分别对称的c) 若R与S是传递的，则也是传递的d) 若R与S不是自反的，则也不是自反的e) 若R与S是反自反的，则也是反自反的f) 若R是自反的，则也是反自反的。g) 若R与S是传递的，则RS是传递的答案：真真真假真真假4.实数集合上的“小于”关系是否市反自反的集合X的幂集上的“真包含”关系是否是反自反的为什么证：实数集合上的“小于”关系是反自反的；集合X的幂集上的“真包含”关系也是反自反的。5.设R、S是X上的二元关系。证明：（1）；（2）（3）；（4）若，则证

24、：（1），则，即，因此。反之，则，即，因此。从而（2），则，即或。于是或，即，因而。反之，则或。于是或，即。从而，因此，。故（3），则。于是且，从而且，即因此反之，设，则且于是且，即。从而，因此故（4），则因为，所以，于是因而6.设R是X上的二元关系，证明：是对称的二元关系。证1：，故是对称的。证2：，则或，即或。于是，因此是对称的。9.有人说：“若R是X上的二元关系，只要R是对称的和传递的，则R必是自反的。”他的证明如下：若xRy，则由R的对称性便知有yRx。于是由xRy和yRx以及R的传递性即得xRx。所以，R是自反的。他的推论错在什么地方这个结论是否对呢解：若，则R是对称的，传递的，反自

25、反的。若，只有使得xRx，才能说R是自反的。此人只是说明了X中的部分元素满足了xRx，因而是错误的。所以这个结论不对。习题1.“父子“关系的平方是什么关系解：“父子“关系的平方是”祖孙“关系2.设X=1,2,3,4,R=(1,2),(2,2),(3,4),S=(2,3),(3,1),(4,2)试求：。解：3.设R与S为X上的任两个集合，下列命题哪些为真a）若R,S都是自反的，则也是自反的。 b）若R,S都是对称的，则也是对称的。 c）若R,S都是反自反的，则也是反自反的。 d）若R,S都是反对称的，则也是反对称的。 e）若R,S都是传递的，则也是传递的。 答案：真假假假假4.设R1是A到B，R

26、2和R3是B到C的二元关系，则一般情况下。但有人声称等号成立，他的证明如下：设，则，使得且。于是且。从而且，所以，即。同理可证相反的包含关系成立，故等式成立，这个证明错在什么地方解：由且，只能得到。但不一定成立。例如时，故这步推理错误5.设R，S是X上的满足的对称关系，证明.证1：设，则使得且。因为R，S均对称，所以于是从而因此故证2，故，于是6.设R为X上的对称关系，证明：是对称关系。证1，故R对称。证2，则，使得。因为R对称，所以，因此，故R对称。证3用数学归纳法对n进行归纳。当n=1时，Rn=R显然是对称的。假设当n=k时，Rk对称。当n=k+1时，。，则，使得。因为Rk，R均是对称的，

27、所以，于是。因此Rk+1对称。综上，Rn对都是对称关系。7.设是X上的二元关系的一个无穷序列，则当每个Ri是对称关系时，还是对称的吗证：，则的使得。因为Ri0对称，所以有，故。因此还是对称的。习题1.设R是X上的二元关系，试证（1）。证：（1）因为显然成立。其次，设，因为是一切包含的传递关系的交，而且是传递的，故，即。因此。（2）因为显然成立。 其次，设，因为是一切包含的自反传递关系的交，而本身是自反的也是传递的且，故，即，因此。（3）（4）先证再证因为是包含的一切传递关系的交，又因为且是传递的，所以。因此。2.设X（a,b,c,d,e），R（a,b），（b,c），（c,d），（d,e）试求和

28、。解：故3.设R,S为X上的二元关系，试证：（1）（2）。证：（1）因为所以因此（2）因为所以因此 证毕6.举例说明与确定不相等。解：设，在N上定义小于关系“”，则“不等关系”。“全关系”。因此的确不相等。7.是否可以定义二元关系的反自反闭包与二元关系的反对称闭包为什么解：不可以。因为二元关系的反自反闭包和反对称闭包是空集，没有多少研究价值。因此不定义二元关系的反自反闭包和反对称闭包。8.是否存在X（X=n）上的一个二元关系R使得两两不相等。解：存在。设，则R是X上的二元关系且即可满足要求。9.证明：若R是对称的，则R也是对称的。证：，则，使得。因为若R是对称的，所以也是对称的，因此。即也是对

29、称的。10.设是X上的二元关系，证明：（1）（2）（3）证：（1）因为都是A上的自反关系，所以也A上的自反关系。由，得，所以是包含的自反关系。由自反闭包的定义可知：又，故，因此。从而（2）同（1）的证明。（3）因为，故，因此。例：设，A上的两个关系。于是，故，但。因此。习题1.设。是S上的二元关系：。证明（1）是S上的等价关系，（2）求等价类的集合。证：（1）等价关系显然。（2），共有8个，如图4所示。图4，故，。故等价类集合为。2.（1）等价关系显然。(2)如图4所示。，。故3. （1）是等价关系显然。（2），。故等价类集合为。4.由置换确定了上的一个关系当且仅当i与j在的循环分解式中的同一

30、循环置换中，证明：是X上的等价关系，求。证；，i与i必在的循环分解式中的同一个循环置换中，即，则是自反的。，若，即i与j在的循环分解式中和同一个循环置换中，则j与i也在的循环分解式中的同一个循环置换中，故。因而是对称性的。，若，则i与j在的循环分解式中的同一个循环置换中，j与k在的循环分解式的同一个循环置换中，因而i与k也在的循环分解式中的同一个循环置换中，即。因而是传递性的。所以是X上的等价关系。5.给出X1,2,3,4上两个等价关系R与S，使得不是等价关系。解：如因为，但，所以不对称.因此不是等价关系。13.设X是一个集合，试求：（1）X上自反二元关系的个数；（2）X上反自反二元关系的个数

31、；（3）X上对称二元关系的个数；（4）X上自反或对称关系的个数；解：（1）X上自反二元关系的个数为（2）X上反自反二元关系的个数为（3）X上对称二元关系的个数为（4）X上自反或对称关系的个数为习题1.设是一个有限区间。令是区间上的有限划分的集合，的一个划分是形如的点的集合。在上定义二元关系如下：的每个分点也是的分点。证明：是上的偏序关系（注意，这里的划分与等价关系中的划分不同）。证：的每个分点也是的分点，故，因此是自反的；，若且，则的每个分点也是的分点且的每个分点也是的分点，故。因此是反对称的；，若且，则的每个分点是的分点，而且的每个分点也是的分点，因此的每个分点也是的分点，故。因此是传递的。

32、综上可知：是上的偏序关系。2.设是偏序集。在上定义二元关系如下： ，。证明：（1）是上的偏序关系；（2）若或，则是上的偏序关系吗证：1.(1)，则。由于是偏序集，故有。从而是自反的；(2)，若且，则且。由是偏序集可知，且，故。因此“”是对称的。(3)，若且，有且。由是偏序集可知：与是传递的，所以且。故，因此是传递的。综上可知：是上的一个偏序关系。2.此题若改为：或，则不是偏序关系。因为不满足反对称性。例如：，则且，但。故不满足反对称性，因此不是偏序关系。3.存在一个偏序关系，使得中有唯一的极大元素，但没有最大元素若有请给出一个具体例子；若没有，请证明之。解：存在。设，其中。在上定义的小于或等于

33、关系“”，则就是一个没有最大元素，但却有唯一极大元的偏序集。5.令S1，2，12，画出偏序集（S,|）的Hass图，其中“|”是整除关系，它有几个极大（小）元素列出这些极大（小）元素极大元素有6个，分别是7，8，9，10，11，12极小元素有1个是16.设是的自反且传递的二元关系，则（1）给出的一个实例；（2）在上定义二元关系是：。证明：是上的等价关系。（3）在商集上定义二元关系是：。证明：是上的偏序关系。证：（1）即可（2）自反、对称显然。下面看传递性因为若；由是传递的，有。由题意有，故是传递的。因此是上的等价关系。（3），因为是上的自反关系，故。而，所以是自反的；，若，则与在一个等类中，故

34、，因此是反对称的；，若，则由的传递性有，即。因此是传递的。综上可知：是上的偏序关系。7.设是上的偏序关系，证明：是上的全序关系。证：，由于是上的全序关系，故或必有一个成立。所以，即；反之，因为是上的关系，故，所以。因此。 ，有或，即与必有一个成立，故是上的全序关系。第四章 无穷集合及其基数习题1.设为由序列的所有项组成的集合，则是否市可数的为什么解：因为序列是可以重复的，故若是由有限个数组成的集合，则是有限的集合；若是由无限个数组成的集合，则是可数的。故本题是至多可数的。2.证明：直线上互不相交的开区间的全体所构成的集合至多可数。证：在每个开区间中取一个有理数，则这些有理数构成的集合是整个有理

35、数集合Q的子集，因此是至多可数的。3.证明：单调函数的不连续点的集合至多可数。证：设是所有不连续点的集合，是一个单调函数，则对应着一个区间，于是由上题便得到证明。4.任一可数集的所有有限子集构成的集族是可数集合。证：设则且。令，设，则是的子集的特征函数。0，1的有穷序列，即，若，则对应1；若则对应0。于是就对应着一个由0，1组成的有限序列0，1，1，0，0，1。此序列对应着一个二进制小数，而此小数是有理数。于是，可数集的所有有限子集对应着有理数的一个子集。又对应的小数也不同，故是单射。而可数集的所有有限子集是无穷的，故是可数的。5判断下列命题之真伪：(1)若且是满射，则只要是可数的，那么是至多

36、可数的；(2)若且是单射，那么只要是可数的，则也是可数的；(3)可数集在任一映射下的像也是可数的；答案：对，错，错。7设是有限集，是可数集，证明：是可数的。证：令，可数。设。（中的每个f实际上就是的一个有限子集，可数集的有限子集是可数的。于是由题即可证明）（。用数学归纳法可以证明是可数的，但。8. 设为一个有限字母表，上所有字（包括空字）之集记为。证明是可数集证：设有限字母上所有字（包括空字）所形成的集，则是可数的。1长度为1的字符串2长度为2的字符串 n长度为n的字符串 因为i 中每个长度都是有限的，而，故是至多可数的。又显然是无穷的，故是可数的。证2：不妨假设（令也是可以），则可按字典序排

37、序为：。由于的全部元素可以排成无重复项的无穷序列，故是可数的。习题2.找一个初等可数，使得它是到实数的一一对应。解：,或，或3.试给出一个具体的函数，使得它是从到的一一对应。证：中包含一个可数子集可数。可数的，故。令即为所求。4.证明：若可数，则不可数。（用对角线方法）。证：可数，则令。假设可数，则的子集（即的元素）是可数的，故中元素可排成一个无重复项的无穷序列：而，于是特征函可数，即可写成下列无穷序列形式： 其中或。造一个特征函数。令则,但确实是到的一个映射，即是的子集的特征函数，矛盾。故不可数。5令，利用康托对角线法证明S是不可数集。证:假设从N到0, 1的所有映射之集可数，则可排成无重复项的无穷序列。每个函数确定了一个0,1序列。构造序列，若；否则。该序列对应的函数，不为任一个，矛盾。