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

教材习题解答

第一章 集合及其运算
习题
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恰有n个元素，证明有个元素。
证明：（1）当n＝0时，，命题成立。
（2）假设当时命题成立，即（时）。那么对于（），中的元素可分为两类，一类为不包含中某一元素的集合，另一类为包含的集合。显然，这两类元素个数均为。因而，亦即命题在时也成立。
由（1）、（2），可证得命题在时均成立。

习题
1.设A、B是集合，证明:

证：当时，显然，得证。
假设，则必存在，使得但，故与题设矛盾。所以假设不成立，故。
2.设A、B是集合，试证
证：显然。
反证法：假设，则，若，则左，但右，矛盾。
若，则左，但右，矛盾。故假设不成立，即。
3. 设A，B，C是集合，证明：

证：

由上式可以看出此展开式与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为集合，试证：

证：证Ⅰ，有，因此，，。故，即。
反之，，有，。因此。故，即。
所以 ＝。
证Ⅱ：

9.设，证明
证：证1：，有且
或。则
若且，则，于是。
若且，则，从而
。
反之，，则或。
若，则由有，故，因此。
若，则但，故，因此。从而
。
由集合相等的定义，。
证2：，
因为，所以。
10.下列命题是否成立？
(1)；(2)；
(3)。
解：（1），（2），（3）都不成立。反例如下：
（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）证：，有且。则
若，则，故，因此；
若，则，故，。于是

反之，，则
若，则，故，因而。即
；
若，则，故或。因此或，从而。
综上可得：。于是

证：，则
若，则，因而。故，于是；
若，则，与上同理可得。
综上可得：。
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。
在两边同时并上A即得。
2．设A,B,C为任意集合，化简

证：证1：原式＝

证2：令原式＝T，全集为S，则
且，
故 。
3．证明：（1）；（2）；
（3）
证：（1）

（2）证： 〔根据（1）〕

（3）证：
〔根据（2）〕
4．设和是集合S的子集的两个序列，对，有。令。试证：
。
证：
当n＝1时，，故
当n≥2时，设有或。则
1.若，则但，因此有。于是
（1）若且，有；
（2）若且，由，有且，于是。
2.若，则但。于是
。
综上可得：
5．设X是一个非空集合，试证：，有
。
证明：由于，故。因为，故，显然有。
对于，假设存在，使得，必可找到其中最小的值，使得，故；
假如不存在p，则，故。
综上可得：。
所以＝。
6．设V是任一集合，证明：
有当且仅且且。
证：因为，故。
先证。设，则
若，则，故且，矛盾。
所以，即。
其次，证明。设，则有两种情况：
若。则，故。
若。由，知。
总之，，有，故。
7．设为一集序列，记为这样的元素的全体形成的集合：当且仅当在序列中有无穷多项含有。集合称为集序列的上极限，记为，即。又记为这样的元素全体形成的集合；序列中只有有限项不含有这样的元素。称为序列的下极限，并记。证明；
（1）；（2）。
证： （1），在序列中只有有限项不含x，在不含x的项中必可找到下标最大的一项（若各项均含x，则令p＝0），有，故，即
。
反之，，必使得，即时，。而集合中即使都不含有x，但也仅有有限项不含x，故。因此
。
综上可得：＝。
（2），因为中有无穷多项含有x，故，当时，，因此，从而，即

反之，，则，即中有无穷多项多含x，所以，即

综上可得：。
8．证明：
证：，由定义可知：序列中只有有限项不含x，故必可找
到不含x的下标最大的一项，可见此时均含x，即有无限项含x，故。因此
。

习题
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为任四个集合，证明：

证：，有，即
。所以，因此
，从而
。
反之，，有。即
，从而
。
因此，＝。
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个元素，则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中具有性质之集，，则

所求为：

3．设A,B是两个有限集，试求
解：
4．马大哈写n封信，n个信封，把n封信放入到n个信封中，求全部装错的概率是多少？
解：，令表示所有信都装错的集合，即
。
令表示第个信封恰好装对的集合，则。所以全部装错的集合为：
。
于是，易得
。
对于，有 。又

〔答案：0.3679，当n≥10时，概率都近似等于0.3679〕。
5．毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子至少与一个姑娘跳过舞，但未能与所有姑娘跳过。同样地，每个姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子跳过舞。证明：在所有参加舞会的小伙与姑娘中，必可找到两个小伙子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞，而这两个姑娘中的每一个也只与这两个小伙中的一个跳过舞。
证：设是小伙的集合，是姑娘的集合。
与跳舞的姑娘的集合用表示；
与跳舞的姑娘的集合用表示；

与跳舞的姑娘的集合用表示；
于是，由题意：且且，。
若存在，使得且，则结论成立。
反证法：假设不存在和满足且。于是
应满足：或必有一个成立。
因此把重新排列有：。从而与所有的姑娘都跳过舞，矛盾。
因此假设不成立，本题得证。
第二章 映 射
习题
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.设是一个两两不相交的整数构成的数列，则必有长至少为的递增子序列或有长至少为的递减子序列。
证：令，则。
设以为首项的最长递增子序列的长度为，
设以为首项的最长递减子序列的长度为。
反证法：假设题中结论不成立，则。
令，，则是单射。
实际上，且，则
若，则，所以；
即。
若，则，所以；
即。
故为单射，从而就有矛盾。
习题
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.已知个整数，试证：存在两个整数，使得能被整除。
证：考察下式：

若第式能被整除，则显然成立，此时；
若任一式都不能被整除，则考察各式被整除后的余数，如下式：

由于每一个都不能被整除，故共有个余数—相当于个物体。而任意整数被除后，只有－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是奇数且
，
则乘积为偶数。
解：反证法：若为奇数，则中的与必是一个为奇数，一个为偶数。而n为奇数，故奇数个数为比偶数多一个，这是不可能的。

习题
1.设，，证明
证1：，则，即但。于是
但，因此，
故
反之，设，有
因此，即
从而
故
因而
证2：

2. 设，证明
（1）
（2）
（3）
证：（1）设，则使得。于是，。因此，，所以，故

反之，设，则。于是或，使得。因此不论何种情况都，使得。因此，故

因此，
（2）设，则，使得。于是，且。
从而，且，所以，故

（3）设，则但。于是使得，且，从而，使得。
故，即
。
3.设，，证明：

证：设，则，使得。于是且，即，因此且，即，从而
。
反之，设，则且。于是且，使得。从而，使得，因此。从而

因此，。
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 o

2 o

3 o

o a

o b

o c

X
Y
7.设则成立吗？
解：不成立。
反例：设。
。
令，则。
，。
8.设X是一个无穷集合，。证明：存在X的一个真子集E使得。
证：取，令。若到某一位与前面有重复项，设为第k项，即。令，则
且。
若互不相同，令，则。
[不去掉可能就会有]
9.设，证明，都有
证；若，则,因而。
若，设，则，使得且，于是
且，因此。
故
反之，设，则且。于是且，使得。从而，，因此，而，所以，于是，故

从而
习题
1.设，
，，试求。
解：

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

即＝，与假设不存在，但矛盾，故一定是满射。
3.设X,Y,Z是三个非空的集合，，证明：是单射当且仅当不存在从Z到X的映射，使得，但。
证：是单射，则，有。假设存在和：，因为，于是，使得。
而由于为单射，故，即，故矛盾。
可以用：。
逆否命题：。
假设不是单射，则，但。构造两个映射和令，由于，故若，则有。但，于是有矛盾。

习题
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)所示：有
。

（a） (b)
图1
5. 是否有一个从到的一一对应，使得，但？
解：存在。为对换即可。
习题
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. 证明下列置换等式
（1）
证：
＝

（2）

8.在所有的n次置换中，有多少个n—循环置换？
解：
对，有n种选择
对，有（n-1）种选择
……
对有1种选择
因此共有n!种排列
对每个n－循环置换，均有n种排列，因此
n－循环置换的个数为个
习题
3. 找一个既不满足交换律又不满足结合律的二元运算
解：n维向量空间中向量的叉积运算。
4. 给出一个三元运算的例子
解：求三个正整数的最大公因数。
5. 设，A上的代数运算“”如表所示。代数运算“”是否满足交换律？结合律？“”有单位元吗？
解：不满足交换律，因为运算表不对称。。也不满足结合律，
单位为a
o
a
b
c
d
a
a
b
c
d
b
b
a
a
c
c
c
a
b
d
d
d
c
a
b
6.设，。
那么“”是N上的代数运算吗？为什么？
解：当m=1时，，
因此“”不是N上的代数运算。
7. 设“”是X上的代数运算，则应该怎样定义“”的逆运算？回忆一下，逆运算通常比原运算“难算”，这是为什么？例如，积分比微分难，减法比加法难，除法比乘法难，开方比幂方运算难。
解：“”的逆运算可以这样定义：一个从X到的映射
“”称为X上的n元运算的逆运算
“”的逆运算的象集所在的集合的元素的个数是X的元素个数的倍（设），因而逆运算的个数很多，因此得到其中的一种就较困难，故逆运算较难算。

第三章 关 系

习题
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是传递的，则R\S是传递的
答案：真真真假真真假
4.实数集合上的“小于”关系是否市反自反的？集合X的幂集上的“真包含”关系是否是反自反的？为什么？
证：实数集合上的“小于”关系是反自反的；
集合X的幂集上的“真包含”关系也是反自反的。
5.设R、S是X上的二元关系。证明：
（1）；（2）
（3）；（4）若，则
证：（1），则，即，因此。
反之，，则，即，因此。
从而
（2），则，
即或。于是或，
即，因而。
反之，，则或。
于是或，即。
从而，因此，。
故
（3），则。于是且，
从而且，即
因此
反之，设，则且
于是且，即。
从而，因此
故
（4），则
因为，所以，于是
因而
6.设R是X上的二元关系，证明：是对称的二元关系。
证1：，故是对称的。
证2：，则或，即或。
于是，因此是对称的。
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的二元关系，则一般情况下
。但有人声称等号成立，他的证明如下：设，则，使得且。于是且。从而且，所以，即。同理可证相反的包含关系成立，故等式成立，这个证明错在什么地方？
解：由且，只能得到。但不一定成立。
例如时，
故这步推理错误
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是对称关系时，还是对称的吗？
证：，则的使得。因为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）｝试求和。
解：

故

3.设R,S为X上的二元关系，试证：
（1）
（2）。
证：（1）因为
所以
因此
（2）因为
所以
因此 〔证毕〕
6.举例说明与确定不相等。
解：设，在N上定义小于关系“＜”，则
“不等关系≠”。
“全关系”。
因此的确不相等。
7.是否可以定义二元关系的反自反闭包与二元关系的反对称闭包？为什么？
解：不可以。
因为二元关系的反自反闭包和反对称闭包是空集，没有多少研究价值。因此不定义二元关系的反自反闭包和反对称闭包。
8.是否存在X（X=n）上的一个二元关系R使得两两不相等。
解：存在。
设，则R是X上的二元关系且即可满足要求。
9.证明：若R是对称的，则R＋也是对称的。
证：
，则，使得。因为若R是对称的，所以也是对称的，因此。即也是对称的。
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在的循环分解式中的同一循环置换中，证明：是X上的等价关系，求。
证；
，i与i必在的循环分解式中的同一个循环置换中，即，则是自反的。
，若，即i与j在的循环分解式中和同一个循环置换中，则j与i也在的循环分解式中的同一个循环置换中，故。因而是对称性的。
，若，则i与j在的循环分解式中的同一个循环置换中，j与k在的循环分解式的同一个循环置换中，因而i与k也在的循环分解式中的同一个循环置换中，即。因而是传递性的。
所以是X上的等价关系。
5.给出X＝{1,2,3,4}上两个等价关系R与S，使得不是等价关系。
解：如

因为，但，所以不对称..
因此不是等价关系。
13.设X是一个集合，，试求：
（1）X上自反二元关系的个数；
（2）X上反自反二元关系的个数；
（3）X上对称二元关系的个数；
（4）X上自反或对称关系的个数；
解：（1）X上自反二元关系的个数为
（2）X上反自反二元关系的个数为
（3）X上对称二元关系的个数为
（4）X上自反或对称关系的个数为
习题
1.设是一个有限区间。令是区间上的有限划分的集合，的一个划分是形如的点的集合。在上定义二元关系如下：
的每个分点也是的分点。
证明：是上的偏序关系（注意，这里的划分与等价关系中的划分不同）。
证：的每个分点也是的分点，故，因此是自反的；
，若且，则的每个分点也是的分点且的每个分点也是的分点，故。因此是反对称的；
，若且，则的每个分点是的分点，而且的每个分点也是的分点，因此的每个分点也是的分点，故。因此是传递的。
综上可知：是上的偏序关系。
2.设是偏序集。在上定义二元关系如下：
，。
证明：（1）是上的偏序关系；
（2）若或，则是上的偏序关系吗？
证：1.(1)，则。由于是偏序集，故有
。
从而是自反的；
(2)，若且，则
且。
由是偏序集可知，且，故。
因此“”是对称的。
(3)，若且，有且。由是偏序集可知：与是传递的，所以且。故，因此是传递的。
综上可知：是上的一个偏序关系。
2.此题若改为：或，则不是偏序关系。因为不满足反对称性。
例如：，则且，但。故不满足反对称性，因此不是偏序关系。
3.存在一个偏序关系，使得中有唯一的极大元素，但没有最大元素？若有请给出一个具体例子；若没有，请证明之。
解：存在。
设，其中。在上定义的小于或等于关系“”，则就是一个没有最大元素，但却有唯一极大元的偏序集。
5.令S＝｛1，2，…，12｝，画出偏序集（S,|）的Hass图，其中“|”是整除关系，它有几个极大（小）元素？列出这些极大（小）元素
极大元素有6个，分别是7，8，9，10，11，12
极小元素有1个是1
6.设是的自反且传递的二元关系，则
（1）给出的一个实例；
（2）在上定义二元关系是：。
证明：是上的等价关系。
（3）在商集上定义二元关系是：。
证明：是上的偏序关系。
证：（1）即可
（2）自反、对称显然。下面看传递性
因为若；由是传递的，有。由题意有，故是传递的。
因此是上的等价关系。
（3），因为是上的自反关系，故。而，所以是自反的；
，若，则与在一个等类中，故，因此是反对称的；
，若，则由的传递性有，即。因此是传递的。
综上可知：是上的偏序关系。
7.设是上的偏序关系，证明：
是上的全序关系。
证：，由于是上的全序关系，故或必有一个成立。所以，即；
反之，因为是上的关系，故，，所以
。
因此。
，有或，即与必有一个成立，故是上的全序关系。
第四章 无穷集合及其基数
习题
1.设为由序列

的所有项组成的集合，则是否市可数的？为什么？
解：因为序列是可以重复的，故
若是由有限个数组成的集合，则是有限的集合；
若是由无限个数组成的集合，则是可数的。
故本题是至多可数的。
2.证明：直线上互不相交的开区间的全体所构成的集合至多可数。
证：在每个开区间中取一个有理数，则这些有理数构成的集合是整个有理数集合Q的子集，因此是至多可数的。
3.证明：单调函数的不连续点的集合至多可数。
证：设是所有不连续点的集合，是一个单调函数，则对应着一个区间，于是由上题便得到证明。
4.任一可数集的所有有限子集构成的集族是可数集合。
证：设则且。
令，
设，则是Ａ的子集的特征函数。
｛0，1的有穷序列｝，即，
若，则对应1；若则对应0。于是
就对应着一个由0，1组成的有限序列0，1，1，0，…，0，1。此序列对应着一个二进制小数，而此小数是有理数。于是，可数集的所有有限子集对应着有理数的一个子集。
又对应的小数也不同，故是单射。而可数集Ａ的所有有限子集是无穷的，故是可数的。
5．判断下列命题之真伪：
(1)若且是满射，则只要是可数的，那么是至多可数的；
(2)若且是单射，那么只要是可数的，则也是可数的；
(3)可数集在任一映射下的像也是可数的；
答案：对，错，错。
7．设Ａ是有限集，Ｂ是可数集，证明：是可数的。
证：令，Ｂ可数。
设。
（中的每个f实际上就是Ｂ的一个有限子集，可数集的有限子集是可数的。于是由４题即可证明）
（。
用数学归纳法可以证明是可数的，但。
8. 设为一个有限字母表，上所有字（包括空字）之集记为。证明是可数集
证１：设有限字母上所有字（包括空字）所形成的集，则是可数的。
Ａ1＝{长度为1的字符串}
Ａ2＝{长度为2的字符串}

Ａn＝{长度为n的字符串}

因为Ａi 中每个长度都是有限的，而＝，故是至多可数的。又显然是无穷的，故是可数的。
证2：不妨假设（令＝也是可以），则可按字典序排序为：
。由于的全部元素可以排成无重复项的无穷序列，故是可数的。

习题
2.找一个初等可数，使得它是到实数的一一对应。
解：,或，或
3.试给出一个具体的函数，使得它是从到的一一对应。
证：中包含一个可数子集可数。
——可数的，故。
令

即为所求。
4.证明：若可数，则不可数。（用对角线方法）。
证：可数，则令。
假设可数，则的子集（即的元素）是可数的，故中元素可排成一个无重复项的无穷序列：

而，于是特征函可数，即可写成下列无穷序列形式：

其中或。
造一个特征函数。令

则,但确实是到的一个映射，即是的子集的特征函数，矛盾。故不可数。
5．令，利用康托对角线法证明S是不可数集。
证:假设从N到{0, 1}的所有映射之集可数，则可排成无重复项的无穷序列。每个函数确定了一个0,1序列。构造序列，若；否则。该序列对应的函数，，
不为任一个，矛盾。

45