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

'教材习题解答第一章集合及其运算习题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个集合且，试证：证明：由，可得且，故。同理可得：因此45 6.设，试求？解：7.设S恰有n个元素，证明有个元素。证明：（1）当n＝0时，，命题成立。（2）假设当时命题成立，即（时）。那么对于（），中的元素可分为两类，一类为不包含中某一元素的集合，另一类为包含的集合。显然，这两类元素个数均为。因而，亦即命题在时也成立。由（1）、（2），可证得命题在时均成立。习题1.设A、B是集合，证明:证：当时，显然，得证。假设，则必存在，使得但，故与题设矛盾。所以假设不成立，故。2.设A、B是集合，试证证：显然。反证法：假设，则，若，则左，但右，矛盾。若，则左，但右，矛盾。故假设不成立，即。3.设A，B，C是集合，证明：证：45 由上式可以看出此展开式与A、B、C的运算顺序无关，因此，4.设A，B，C为集合，证明证：因为==。5.设A，B，C为集合，证明：证：＝。6.设A，B，C为集合，证明：证明：=7.设A，B，C都是集合，若且，试证B=C。证：证1：，则若，则。由于，故，即；若，则，由于，故。又，只能有。因此，，总有，故。同理可证，。因此。证2：8.设A，B，C为集合，试证：证：证Ⅰ，有，因此，，45 。故，即。反之，，有，。因此。故，即。所以＝。证Ⅱ：9.设，证明证：证1：，有且或。则若且，则，于是。若且，则，从而。反之，，则或。若，则由有，故，因此。若，则但，故，因此。从而。由集合相等的定义，。证2：，因为，所以。10.下列命题是否成立？(1)；(2)；(3)。解：（1），（2），（3）都不成立。反例如下：（1）任意，则。45 （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），则若，则。因而且，故；若，则，同理可得。故。反之，因为，故＝。，有。若，则，故；若，则，故。因此。45 所以＝。（2）证：，有且。则若，则且，故，。若，则且。故，因此。于是。（3）证：，有且。则若，则，故，因此；若，则，故，。于是反之，，则若，则，故，因而。即；若，则，故或。因此或，从而。综上可得：。于是证：，则若，则，因而。故，于是；若，则，与上同理可得。综上可得：。14．设A为任一集，为任一集族（），证明：45 证：，则若，则，因而；若，则，因而，故。于是。反之，设，则。若，显然；若，则，因而，即。所以，。综上可得，＝。15．填空：设A,B是两个集合。(a)__________________；(b)__________________；(c)___________________；(d)___________________；解：(a)且；(b)或(c)或；(d)（且）或（且）16．设A，B，C为三个集合，下列集合表达式哪一个等于？（a）；（b）（c）；（d）（e）答案：c。习题45 1．设A,B,C为集合，并且，则下列断言哪个成立？(1)；(2)；(3)；(4)。答案：d。在两边同时并上A即得。2．设A,B,C为任意集合，化简证：证1：原式＝证2：令原式＝T，全集为S，则且，故。3．证明：（1）；（2）；（3）证：（1）（2）证：〔根据（1）〕（3）证：〔根据（2）〕4．设和是集合S的子集的两个序列，对，有。令。试证：。45 证：当n＝1时，，故当n≥2时，设有或。则1.若，则但，因此有。于是（1）若且，有；（2）若且，由，有且，于是。2.若，则但。于是。综上可得：5．设X是一个非空集合，试证：，有。证明：由于，故。因为，故，显然有。对于，假设存在，使得，必可找到其中最小的值，使得，故；45 假如不存在p，则，故。综上可得：。所以＝。6．设V是任一集合，证明：有当且仅且且。证：因为，故。先证。设，则若，则，故且，矛盾。所以，即。其次，证明。设，则有两种情况：若。则，故。若。由，知。总之，，有，故。7．设为一集序列，记为这样的元素的全体形成的集合：当且仅当在序列中有无穷多项含有。集合称为集序列的上极限，记为，即。又记为这样的元素全体形成的集合；序列中只有有限项不含有这样的元素。称为序列的下极限，并记。证明；（1）；（2）。证：（1），在序列中只有有限项不含x，在不含x的项中必可找到下标最大的一项（若各项均含x，则令p＝0），有，故45 ，即。反之，，必使得，即时，。而集合中即使都不含有x，但也仅有有限项不含x，故。因此。综上可得：＝。（2），因为中有无穷多项含有x，故，当时，，因此，从而，即反之，，则，即中有无穷多项多含x，所以，即综上可得：。8．证明：证：，由定义可知：序列中只有有限项不含x，故必可找到不含x的下标最大的一项，可见此时均含x，即有无限项含x，故。因此。45 习题1．设。求。解：2．设A,B为集合，试证：A×B＝B×A的充要条件是下列三个条件至少一个成立：（1）；（2）；（3）。证：若（1）成立，。若（2）成立，同上。若（3）成立，A×B=B×B=B×A。假设必要性不成立，即。故不妨设使得。设，则，矛盾。于是，假设不成立。因而必要性成立。必要性也可以如下证明：1.若，则或。2.若，则，有。于是，因此且，故A=B。3．设A,B,C,D为任四个集合，证明：证：，有，即。所以，因此45 ，从而。反之，，有。即，从而。因此，＝。4．设为任意集合，试证：证：，有且或。则若，则，故，即。若，同理可证。从而。反之，，则或，即，但或，但。从而有，但，即，从而。综上可得：＝。5．设，试证：证：，则，故或。于是1.若，则。因此(1)若，则。45 (2)若，则，即。2.若，则必有，故。综上可得：。反之，，则或或，于是，(1)若，则且，即，于是。(2)若，则且，即，于是。(3)若，则且，即，于是。综上可得：。于是。7．设是三个任意集合，证明：证：8．设A,B为集合，下列命题哪些为真？（1）且（2）或（3）（4）若，则。（5）若，则。45 答案：（2），（5）为真。9．设A有m个元素，B有n个元素，则A×B是多少个序对组成的？A×B有多少个不同的子集？答：A×B有mn个序对；A×B有个不同子集。10．设是两个集合，，试证：若，则。证：，因为，故在B中任取一元素y，必有，因而，故。从而。反之，，因为，故在中任取一元素y，必有，因而，故。从而。于是。习题1.某班学生中有45％正在学德文，65％正在学法文。问此班中至少有百分之几的学生正同时学德文和法文？解：设A,B分别为正在学德文和法文的学生的集合，班级总人数为n，则，于是同时学习德文和法文的人数为，故。于是全班至少百分之十的学生同时学德文和法文。2．求1到250之间不能被2，3，5，7中任一数整除的数的个数。解：设，在S上的定义性质，n具有性质（相应地）当且仅当。令为S中具有性质之集，，则45 所求为：3．设A,B是两个有限集，试求解：4．马大哈写n封信，n个信封，把n封信放入到n个信封中，求全部装错的概率是多少？解：，令表示所有信都装错的集合，即。令表示第个信封恰好装对的集合，则。所以全部装错的集合为：。于是，易得。对于，有。又45 〔答案：0.3679，当n≥10时，概率都近似等于0.3679〕。5．毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子至少与一个姑娘跳过舞，但未能与所有姑娘跳过。同样地，每个姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子跳过舞。证明：在所有参加舞会的小伙与姑娘中，必可找到两个小伙子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞，而这两个姑娘中的每一个也只与这两个小伙中的一个跳过舞。证：设是小伙的集合，是姑娘的集合。与跳舞的姑娘的集合用表示；与跳舞的姑娘的集合用表示；与跳舞的姑娘的集合用表示；于是，由题意：且且，。若存在，使得且，则结论成立。反证法：假设不存在和满足且。于是应满足：或必有一个成立。因此把重新排列有：。从而与所有的姑娘都跳过舞，矛盾。因此假设不成立，本题得证。45 第二章映射习题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的个数为当A中有n个元素时，f的个数为因此f的总个数为+++++＝＝即从X到X的部分映射共有个。4.设是一个两两不相交的整数构成的数列，则必有长至少为的递增子序列或有长至少为的递减子序列。证：令，则。设以为首项的最长递增子序列的长度为，设以为首项的最长递减子序列的长度为。45 反证法：假设题中结论不成立，则。令，，则是单射。实际上，且，则若，则，所以；即。若，则，所以；即。故为单射，从而就有矛盾。习题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.已知个整数，试证：存在两个整数，使得能被整除。证：考察下式：45 若第式能被整除，则显然成立，此时；若任一式都不能被整除，则考察各式被整除后的余数，如下式：由于每一个都不能被整除，故共有个余数—相当于个物体。而任意整数被除后，只有－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整除。5.设为的任一排列，若n是奇数且，则乘积为偶数。解：反证法：若为奇数，则中的与45 必是一个为奇数，一个为偶数。而n为奇数，故奇数个数为比偶数多一个，这是不可能的。习题1.设，，证明证1：，则，即但。于是但，因此，故反之，设，有因此，即从而故因而证2：2.设，证明（1）（2）（3）证：（1）设，则使得。于是，。因此，，所以，故45 反之，设，则。于是或，使得。因此不论何种情况都，使得。因此，故因此，（2）设，则，使得。于是，且。从而，且，所以，故（3）设，则但。于是使得，且，从而，使得。故，即。3.设，，证明：证：设，则，使得。于是且，即，因此且，即，从而。反之，设，则且。于是且，使得。从而，使得，因此。从而因此，。4.设45 。以下四个小题中，每个小题均有四个命题，这四个命题有且仅有一个正确，请找出正确的那个。（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）1o2o3ooaobocXY7.设则成立吗？解：不成立。反例：设。。令，则。，。8.设X是一个无穷集合，。证明：存在X的一个真子集E使得。证：取，令。若到某一位与前面有重复项，设为第k项，即。令，则且。若互不相同，令，则。45 [不去掉可能就会有]9.设，证明，都有证；若，则,因而。若，设，则，使得且，于是且，因此。故反之，设，则且。于是且，使得。从而，，因此，而，所以，于是，故从而习题1.设，，，试求。解：因此。2.设X,Y,Z是三个非空集合，。证明：是满射当且仅当不存在从Y到Z的映射和，使得，但。证：因且为满射，故，使得。假设存在，但。因为，所以，使得。对于上面的，（是满射），使得45 ，即。故与，矛盾。所以假设不成立。也可以用如下方法：满射右可逆，使得假设得到，命题得证。，假设不是满射，则，使得。构造两个映射，当时，；当时，。因为，故此时，但即＝，与假设不存在，但矛盾，故一定是满射。3.设X,Y,Z是三个非空的集合，，证明：是单射当且仅当不存在从Z到X的映射，使得，但。证：是单射，则，有。假设存在和：，因为，于是，使得。而由于为单射，故，即，故矛盾。可以用：。逆否命题：。假设不是单射，则，但。构造两个映射和令，由于，故若，则有45 。但，于是有矛盾。习题1.设，试构造两个映射和g：，使得（1），但；（2），但。解：（1）但，故f是满射，但f不是单射。于是令：，，则但。事实上，当n＝1时，，故。（2）自己做。2.设则（1）若存在唯一的一个映射，使得，则是可逆的吗？（2）若存在唯一的一个映射，使得，则是可逆的吗？答案：（1）不一定可逆。当时，不一定可逆。当时，可逆。（2）一定可逆。证：由，得是单射。假设不是满射，则g不唯一，矛盾。3.设，则（1）若是左可逆的，则有多少个左逆映射？（2）若是右可逆的，则有多少个右逆映射？解：令，则（1）如图1(a)所示：有；（2）如图1(b)所示：有45 。（a）(b)图15.是否有一个从到的一一对应，使得，但？解：存在。为对换即可。习题1.设，求。解：2.将置换分解成对换的乘积。解：=(17)(13)(29)(28)(24)(26)3.设是任一n次置换，试证：与的奇偶性相同。证：假设与的奇偶性不同，不妨设为奇置换，为偶置换。因为（I为恒等置换），又，因而I是偶置换。而是奇置换与I是偶置换矛盾。45 因而假设不成立，故与奇偶性相同。5.任一偶置换均可被分解成3－循环置换（123），（124）…（12n）中若干之乘积。证：因为因此本题得证。6.证明下列置换等式（1）证：＝（2）8.在所有的n次置换中，有多少个n—循环置换？解：对，有n种选择对，有（n-1）种选择45 ……对有1种选择因此共有n!种排列对每个n－循环置换，均有n种排列，因此n－循环置换的个数为个习题3.找一个既不满足交换律又不满足结合律的二元运算解：n维向量空间中向量的叉积运算。4.给出一个三元运算的例子解：求三个正整数的最大公因数。5.设，A上的代数运算“”如表所示。代数运算“”是否满足交换律？结合律？“”有单位元吗？解：不满足交换律，因为运算表不对称。。也不满足结合律，单位为aoabcdaabcdbbaacccabdddcab6.设，。那么“”是N上的代数运算吗？为什么？解：当m=1时，，因此“”不是N上的代数运算。7.设“”是X上的代数运算，则应该怎样定义“”的逆运算？回忆一下，逆运算通常比原运算“难算”，这是为什么？例如，积分比微分难，减法比加法难，除法比乘法难，开方比幂方运算难。解：“”的逆运算可以这样定义：一个从X到的映射“”称为X上的n元运算的逆运算“”的逆运算的象集所在的集合的元素的个数是X的元素个数的倍（设），因而逆运算的个数很多，因此得到其中的一种就较困难，故逆运算较难算。45 第三章关系习题1.给出一个既不是自反的又不是反自反的二元关系？解：设R是X上的一个二元关系且即可。2.是否存在一个同时不满足自反性，对称性，反对称性，传递性和反自反性的二元关系？解：存在。设，R是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）若，则证：（1），则，即，因此。反之，，则，即，因此。45 从而（2），则，即或。于是或，即，因而。反之，，则或。于是或，即。从而，因此，。故（3），则。于是且，从而且，即因此反之，设，则且于是且，即。从而，因此故（4），则因为，所以，于是因而6.设R是X上的二元关系，证明：是对称的二元关系。证1：，故是对称的。证2：，则或，即或。于是，因此是对称的。45 9.有人说：“若R是X上的二元关系，只要R是对称的和传递的，则R必是自反的。”他的证明如下：若xRy，则由R的对称性便知有yRx。于是由xRy和yRx以及R的传递性即得xRx。所以，R是自反的。他的推论错在什么地方？这个结论是否对呢？解：若，则R是对称的，传递的，反自反的。若，只有使得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，R2和R3是B到C的二元关系，则一般情况下。但有人声称等号成立，他的证明如下：设，则，使得且。于是且。从而且，所以，即。同理可证相反的包含关系成立，故等式成立，这个证明错在什么地方？解：由且，只能得到。但45 不一定成立。例如时，故这步推理错误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均是对称的，所以，于是。因此Rk+1对称。综上，Rn对都是对称关系。7.设是X上的二元关系的一个无穷序列，则当每个Ri是对称关系时，45 还是对称的吗？证：，则的使得。因为Ri0对称，所以有，故。因此还是对称的。习题1.设R是X上的二元关系，试证（1）。证：（1）因为显然成立。其次，设，因为是一切包含的传递关系的交，而且是传递的，故，即。因此。（2）因为显然成立。其次，设，因为是一切包含的自反传递关系的交，而本身是自反的也是传递的且，故，即，因此。（3）（4）先证再证因为是包含的一切传递关系的交，又因为且是传递的，所以。45 因此。2.设X＝（a,b,c,d,e），R＝｛（a,b），（b,c），（c,d），（d,e）｝试求和。解：故3.设R,S为X上的二元关系，试证：（1）（2）。证：（1）因为所以因此（2）因为所以因此〔证毕〕6.举例说明与确定不相等。解：设，在N上定义小于关系“＜”，则“不等关系≠”。“全关系”。因此的确不相等。7.是否可以定义二元关系的反自反闭包与二元关系的反对称闭包？为什么？45 解：不可以。因为二元关系的反自反闭包和反对称闭包是空集，没有多少研究价值。因此不定义二元关系的反自反闭包和反对称闭包。8.是否存在X（X=n）上的一个二元关系R使得两两不相等。解：存在。设，则R是X上的二元关系且即可满足要求。9.证明：若R是对称的，则R＋也是对称的。证：，则，使得。因为若R是对称的，所以也是对称的，因此。即也是对称的。10.设是X上的二元关系，证明：（1）（2）（3）证：（1）因为都是A上的自反关系，所以也A上的自反关系。由，得，所以是包含的自反关系。由自反闭包的定义可知：又，故，，因此。从而（2）同（1）的证明。（3）因为，故，因此。例：设，A上的两个关系。于是，故，但45 。因此。习题1.设。是S上的二元关系：。证明（1）是S上的等价关系，（2）求等价类的集合。证：（1）等价关系显然。（2），共有8个，如图4所示。图4，，故，，。故等价类集合为。2.（1）等价关系显然。(2)如图4所示。，。故45 3.（1）是等价关系显然。（2），。故等价类集合为。4.由置换确定了上的一个关系当且仅当i与j在的循环分解式中的同一循环置换中，证明：是X上的等价关系，求。证；，i与i必在的循环分解式中的同一个循环置换中，即，则是自反的。，若，即i与j在的循环分解式中和同一个循环置换中，则j与i也在的循环分解式中的同一个循环置换中，故。因而是对称性的。，若，则i与j在的循环分解式中的同一个循环置换中，j与k在的循环分解式的同一个循环置换中，因而i与k也在的循环分解式中的同一个循环置换中，即。因而是传递性的。所以是X上的等价关系。5.给出X＝{1,2,3,4}上两个等价关系R与S，使得不是等价关系。解：如因为，但，所以不对称..因此不是等价关系。45 13.设X是一个集合，，试求：（1）X上自反二元关系的个数；（2）X上反自反二元关系的个数；（3）X上对称二元关系的个数；（4）X上自反或对称关系的个数；解：（1）X上自反二元关系的个数为（2）X上反自反二元关系的个数为（3）X上对称二元关系的个数为（4）X上自反或对称关系的个数为习题1.设是一个有限区间。令是区间上的有限划分的集合，的一个划分是形如的点的集合。在上定义二元关系如下：的每个分点也是的分点。证明：是上的偏序关系（注意，这里的划分与等价关系中的划分不同）。证：的每个分点也是的分点，故，因此是自反的；，若且，则的每个分点也是的分点且的每个分点也是的分点，故。因此是反对称的；，若且，则的每个分点是的分点，而且的每个分点也是的分点，因此的每个分点也是的分点，故。因此是传递的。综上可知：是上的偏序关系。2.设是偏序集。在上定义二元关系如下：，。证明：（1）是上的偏序关系；（2）若或，则是上的偏序关系吗？45 证：1.(1)，则。由于是偏序集，故有。从而是自反的；(2)，若且，则且。由是偏序集可知，且，故。因此“”是对称的。(3)，若且，有且。由是偏序集可知：与是传递的，所以且。故，因此是传递的。综上可知：是上的一个偏序关系。2.此题若改为：或，则不是偏序关系。因为不满足反对称性。例如：，则且，但。故不满足反对称性，因此不是偏序关系。3.存在一个偏序关系，使得中有唯一的极大元素，但没有最大元素？若有请给出一个具体例子；若没有，请证明之。解：存在。设，其中。在上定义的小于或等于关系“”，则就是一个没有最大元素，但却有唯一极大元的偏序集。5.令S＝｛1，2，…，12｝，画出偏序集（S,|）的Hass图，其中“|”是整除关系，它有几个极大（小）元素？列出这些极大（小）元素极大元素有6个，分别是7，8，9，10，11，12极小元素有1个是16.设是的自反且传递的二元关系，则（1）给出的一个实例；45 （2）在上定义二元关系是：。证明：是上的等价关系。（3）在商集上定义二元关系是：。证明：是上的偏序关系。证：（1）即可（2）自反、对称显然。下面看传递性因为若；由是传递的，有。由题意有，故是传递的。因此是上的等价关系。（3），因为是上的自反关系，故。而，所以是自反的；，若，则与在一个等类中，故，因此是反对称的；，若，则由的传递性有，即。因此是传递的。综上可知：是上的偏序关系。7.设是上的偏序关系，证明：是上的全序关系。证：，由于是上的全序关系，故或必有一个成立。所以，即；反之，因为是上的关系，故，，所以。因此。，有或，即与必有一个成立，故是上的全序关系。45 第四章无穷集合及其基数习题1.设为由序列的所有项组成的集合，则是否市可数的？为什么？解：因为序列是可以重复的，故若是由有限个数组成的集合，则是有限的集合；若是由无限个数组成的集合，则是可数的。故本题是至多可数的。2.证明：直线上互不相交的开区间的全体所构成的集合至多可数。证：在每个开区间中取一个有理数，则这些有理数构成的集合是整个有理数集合Q的子集，因此是至多可数的。3.证明：单调函数的不连续点的集合至多可数。证：设是所有不连续点的集合，是一个单调函数，则对应着一个区间，于是由上题便得到证明。4.任一可数集的所有有限子集构成的集族是可数集合。证：设则且。令，设，则是Ａ的子集的特征函数。｛0，1的有穷序列｝，即，若，则对应1；若则对应0。于是就对应着一个由0，1组成的有限序列0，1，1，0，…，0，1。此序列对应着一个二进制小数，而此小数是有理数。于是，可数集的所有有限子集对应着有理数的一个子集。又对应的小数也不同，故45 是单射。而可数集Ａ的所有有限子集是无穷的，故是可数的。5．判断下列命题之真伪：(1)若且是满射，则只要是可数的，那么是至多可数的；(2)若且是单射，那么只要是可数的，则也是可数的；(3)可数集在任一映射下的像也是可数的；答案：对，错，错。7．设Ａ是有限集，Ｂ是可数集，证明：是可数的。证：令，Ｂ可数。设。（中的每个f实际上就是Ｂ的一个有限子集，可数集的有限子集是可数的。于是由４题即可证明）（。用数学归纳法可以证明是可数的，但。8.设为一个有限字母表，上所有字（包括空字）之集记为。证明是可数集证１：设有限字母上所有字（包括空字）所形成的集，则是可数的。Ａ1＝{长度为1的字符串}Ａ2＝{长度为2的字符串}　　　Ａn＝{长度为n的字符串}　　　因为Ａi中每个长度都是有限的，而＝，故是至多可数的。又显然是无穷的，故是可数的。证2：不妨假设（令＝也是可以），则可按字典序排序为：45 。由于的全部元素可以排成无重复项的无穷序列，故是可数的。习题2.找一个初等可数，使得它是到实数的一一对应。解：,或，或3.试给出一个具体的函数，使得它是从到的一一对应。证：中包含一个可数子集可数。——可数的，故。令即为所求。4.证明：若可数，则不可数。（用对角线方法）。证：可数，则令。假设可数，则的子集（即的元素）是可数的，故中元素可排成一个无重复项的无穷序列：而，于是特征函可数，即可写成下列无穷序列形式：45 其中或。造一个特征函数。令则,但确实是到的一个映射，即是的子集的特征函数，矛盾。故不可数。5．令，利用康托对角线法证明S是不可数集。证:假设从N到{0,1}的所有映射之集可数，则可排成无重复项的无穷序列。每个函数确定了一个0,1序列。构造序列，若；否则。该序列对应的函数，，不为任一个，矛盾。45'