发布时间 : 星期六 文章吉林大学离散数学课后习题答案更新完毕开始阅读
证明：反证法：假设R是传递的，对于任意(a，b)?R，因为R是对称的，所以(a，b)? R，则有(a，a)? R，这与R是不反身的矛盾，故假设不成立，原结论成立。
7.集合A上的关系是对称的，反对称的，试指明关系R的结构。 解：R的结构是A 中元素只可能与自身有关系。
8.若集合A上的关系R具有传递性，则R+=R。
证明：R+是包含R的最小具有传递性的关系，则对任意包含R的且有传递性的关系都包含R+，又因为R?R ，且R具有传递性，所以R+?R，又R+?R，所以R+＝R
9.设R是集合A上的关系，如果 1）对任意a?A，都有a R a ； 2）若aRb，aRc，则bRc ； 证明：R是等价关系。
证明：根据已知，对任意a?A，都有a R a，故R具有反身性； 对任意a、b?A，若aRb，又有a R a，根据2），有bR a，故R具有对称性； 对任意a、b、c?A，若a R b，b R c，又R具有对称性，则有bRa，bRc，根据2），有 a R c，故R具有传递性
因此，R是等价关系。
10.有人说：“等价关系中的反身性可以不要，因为反身性可以从对称性和传递性推出：由对称性，从a ? b可得b ? a，再由传递性得a ? a”。你的意见呢？
解：这种说法是错误的。对于任意a?A，和一个A上的等价关系R，可能不存在a R b，也就推不出a R a了，而反身性则要求对于每一个a?A，都有a R a。
11.若集合A上的关系R，S具有对称性，证明：R?S具有对称性的充要条件为R?S= S?R。
证明：
充分性：若R?S= S?R，往证R?S具有对称性。
对于任意x，y?A，若(x，y)? R?S，则存在a?A，满足(x，a)?R，(a，y)? S，又R，S具有对称性，所以有(y，a)? S，(a，x)? R，所以(y，x)? S?R，又S?R= R?S，故(y，x)? R?S，因此R?S具有对称性；
必要性：若R?S具有对称性，往证R?S= S?R。
先证R?S? S?R：对于任意(x，y)? R?S，因R?S具有对称性，则有(y，x)? R?S，则存在a?A，满足(y，a)?R，(a，x)? S，又R，S具有对称性，所以有(x，a)? S，(a，y)? R，所以(x，y)? S?R，故R?S? S?R；
再证S?R? R?S：对于任意(x，y)?S?R，则存在a?A，满足(x，a)? S，(a，y)? R，又R，S具有对称性，所以有(y，a)?R，(a，x)? S，故(y，x)? R?S，因R?S具有对称性，所以(x，y)? R?S，故S?R? R?S； 因此，R?S= S?R得证。
-1
12.若R是等价关系，试证明R也是等价关系。
-1-1
证明：因为R是等价关系，所以R有对称性，所以有R= R，所以R也是等价关系。
13
13.对于实n阶方阵A，B，C，试证明下列关系是等价关系：
1）矩阵A，B等价，记以A?B，如果存在非奇异矩阵P，Q，使得B=P?A?Q；
-1
2）矩阵A，B相似，记以A ? B，如果存在非奇异矩阵P，使得B=P?A?P；
3）矩阵A，B合同，记以A ? B，如果存在非奇异矩阵P，使得B=P?A?P?，其中P?是P的转置矩阵。
1）证明：对于每一个实n阶方阵A，存在n阶单位矩阵I，满足A=I?A?I，故有A ? A，所以矩阵等价关系具有反身性；
对于任意的实n阶方阵A、B，若A ? B，则存在非奇异矩阵P、Q，满足B=P?A?Q，则
-1-1
A=P?B?Q，所以有B ? A，所以矩阵等价关系具有对称性；
对于任意的实n阶方阵A、B、C，若A ? B，B ?C，则存在非奇异矩阵P、Q、S 、T，满足B=P?A?Q，C=S?B?T，则C= (SP)?A?(QT)，所以有A ? C，所以矩阵等价关系具有传递性。
故矩阵的等价关系是等价关系。
-1
2）证明：对于每一个实n阶方阵A，存在n阶单位矩阵I，满足A=I?A?I，故有A ? A，所以矩阵相似关系具有反身性；
-1-1
对于任意的实n阶方阵A、B，若A ? B，则存在非奇异矩阵P，满足B=P?A?P，则A=P
-1-1-1
?B?P，即A=P?B?(P)，所以有B ? A，所以矩阵相似关系具有对称性；
对于任意的实n阶方阵A、B、C，若A ? B，B ? C，则存在非奇异矩阵P、Q，满足B=P
-1-1-1-1 -1
?A?P，C= Q?B?Q，则C= (QP)?A?(PQ)，即C= (QP)?A?(PQ)，所以有A ? C，所以矩阵相似关系具有传递性。
故矩阵的相似关系是等价关系。
3）证明：对于每一个实n阶方阵A，存在n阶单位矩阵I，满足A=I?A?I?，故有A ? A，所以矩阵合同关系具有反身性；
-1
对于任意的实n阶方阵A、B，若A ? B，则存在非奇异矩阵P，满足B=P?A?P?，则A=P
-1-1-1
?B?(P?)，即A=P?B?(P)?所以有B ? A，所以矩阵合同关系具有对称性；
对于任意的实n阶方阵A、B、C，若A ? B，B ? C，则存在非奇异矩阵P、Q，满足B=P?A?P?，C= Q?B?Q?，则C= (QP)?A?(P?Q?)，即C= (QP)?A?(PQ)?，所以有A ? C，所以矩阵合同关系具有传递性。
故矩阵的合同关系是等价关系。
14.试证明定理1.2.8。 证明：（1）由定理1.2.7和定义1.2.12知A/R为A的一个划分。
（2）由Rc的定义知，对任意的x?C有xRcx，即Rc满足自反性。对任意的x?C，y?C有xRcy且yRcx，即Rc满足对称性。对任意的x?C，y?C，z?C有xRcy，yRcz，并且xRcz也成立，故Rc满足传递性。综上Rc是A上的等价关系。
15.设R是集合A上的关系，A??A，定义A?上的关系R?如下：
R?=R?( A?? A?)
试确定下述断言的真假：
（1） 如果R传递，则R?传递。
（2） 如果R为部分序关系，则R?也是部分序关系。 （3） 如果（A,R）是全序集，则（A?, R?）也是全序集。
14
(4) 如果（A,R）是良序集，则（A?, R?）也是良序集。
解：（1）为真； （2）为真； （3）为真； （4）为真。
1.3.3习题1.3解答
1. 证明：映射的乘法满足结合律，举例说明：映射的乘法不满足交换律。
证明：设?是集合A到集合B内的映射，?是集合B到集合C内的映射，?是集合C到集合D内的映射，对于任意a?A，有
( (???)??)(a)= (???)(? (a) ) = ?(? (? (a) ) ) (??(???))(a)= ?((???) (a) ) = ?(? (? (a) ) )
可见( (???)??)(a)= (??(???))(a)，所以映射的乘法满足结合律。 举例：设映射?：a?b b?c c?a 映射?：a? c b?b c? a
则(???)(a)= ?(? (a) )= ?(b)=b (???)(a)= ? (? (a) )= ? (c)=a
可见(???)(a) ? (???)(a)，映射的乘法不满足交换律。
2.将集合M中元素映射到自身的变换称为同一变换，记为I。设?，?是集合M上的两
-1
个变换，如果???=???=I，则?，?是1–1变换，并且?=?。 证明：（1）先证?、?分别是单映射。
对任意x1，x2?M，如果?(x1)= ?(x2)，则有
x1=I(x1)= (???) (x1)= ?(?(x1) )= ?(?(x2) )= (???) (x2) =I(x2)= x2 所以?是单映射。
同理可证?是单映射。
（2）再证?、?分别是满射。
因为?和?都是M到M的单映射，所以有?(M) ? M，? (M) ? M，于是 M =I (M)= (???) (M)= ? (? (M) ) ??(M)，
同理A=I (M)= (???) (M)= ? (? (M) ) ?? (M)， 所以?(M) = M，? (M)= M，即?、?是满射。 （3）往证?=?-1。
由?是1–1映射，故存在?-1，对任意x ?M， ?-1(x)= I (?-1(x))= (???) (?-1(x))= ?(? (?-1(x))= ?(x) 故?=?-1。
3.设?是集合M到集合N内的映射，证明对M的任意子集A，B，有?( A∩B) ? ? (A)∩? (B)，举例说明：?( A∩B) = ? (A)∩? (B)不成立。
证明：对任意y??(A∩B) ?N，则存在y的原象x，使得?(x)=y，因y??( A∩B)，所以
15
x?A∩B，即x?A并且x?B，所以有y??(A)且y??(B)，即y?? (A)∩? (B)，故?( A∩B) ? ? (A)∩? (B)。
例：设M={1，2，3，4}，A={1，2，3}，B={2，3，4} ?：1?a 2?b 3?c 4?a
则?( A∩B)= ?( {2，3})={b，c}
? (A)∩? (B)= {a，b，c}∩{a，b，c}={a，b，c}
4.设?是集合M到集合N内的映射，A是N的子集，M中所有在?下映射到A中的元
-1-1-1
素集合称为A的逆象集，记为? (A)，若A，B是N的任意子集，求证：? ( A∩B) = ? (A)
-1
∩? (B)。
-1-1-1
证明：先证? ( A∩B) ? ? (A)∩? (B)。
-1-1
对任意x?? ( A∩B)，则?(x)?A∩B，所以?(x)?A且 ?(x)?B，那么 x?? (A)且
-1-1-1-1-1-1
x?? (B)，即x?? (A)∩? (B)，故? ( A∩B) ? ? (A)∩? (B)。
-1-1-1
再证? (A)∩? (B) ?? ( A∩B)。
-1-1-1-1
对任意x?? (A)∩? (B)，则x?? (A)且x?? (B)，所以?(x) ? A且?(x)? B，即?(x)
-1-1-1-1
? A∩B，所以x?? (A∩B)，故? (A)∩? (B) ?? ( A∩B)。
-1-1-1
因此，? ( A∩B) = ? (A)∩? (B)。
5.证明：若A1， A2， …，An是可数集合，则A1? A2? … ?An是可数集合。
证明：采用归纳法，当k=2时，由定理 1.3.5知A1? A2={(a1i, a2j)?a1i?A1, a2j?A2}是可数集合。
假设k=n-1时，A1? A2? … ?An-1={(a1i, a2j, …, a(n-1)k)?a1i?A1, a2j?A2,…, a(n-1)k ?An-1}是可数集合。则当k=n时，
A1? A2? … ?An={(a1i, a2j, …, a(n-1)k, ans)?a1i?A1, a2j?A2,…, a(n-1)k ?An-1,ans?An}。此集合相当于把A1? A2? … ?An-1中每个元素的小括号内符号序列作为一个元素与An中每一个元素构成的有序对为元素作成的集合。由假设知A1? A2? … ?An-1可数，An也是可数集合，故由归纳假设知这两个集合的直乘积构成的集合A1? A2? … ?An可数。归纳法完成。
6.证明：任意含有不可数子集的集合必是不可数集。
证明：假设含有不可数子集A1的集合A可数，则由定理1.3.2知A1可数，矛盾，故假设不成立。
7.证明：任何不可数集合均含有一可数无穷子集。
证明：设A为任一不可数集合，显然A??，可设a0?A。考虑A1=A-{ a0}，A1仍不可数。又有a1?A1。再考虑A2=A1-{ a1}，A2仍为不可数集合。同样有a2?A2，…，如此类推。令B={a0, a1, a2,…}，显然B?A，且对任一自然数n总有an?B，故B为一可数无穷子集。
8.证明：直线上互不相交的开区间为元素作成的集合是可数集。 证明：设互不相交的开区间可分别表示为
(a1, b1)，(a2, b2)，…，(an, bn)，…
于是，每个(ai, bi)中至少有一个有理数qi，从而上述所有开区间的集合与有理数集合的一个
16
子集存在1-1映射。由于有理数集是可数集合，所以由直线上互不相交的开区间为元素作成的集合是可数集。
9.所有系数为整数的多项式集合是否为可数集合？为什么？ 答：所有系数为整数的多项式集合是可数集合。
证明：对于任意给定的非负整数n，设所有n次整系数多项式的集合记为An，我们证明An是可数集合。注意An与n个整数集合的直乘积I?…?I存在1-1映射，故由习题5知，是可数集合。所以所有系数为整数的多项式集合可表示为
?A，由定理1.3.4知这些多项
i?0i?式构成的集合可数。
10.有理多项式的根称为代数数。证明所有有理系数多项式的集合是可数集合；其所有根的集合是可数集合。即所有代数数构成的集合是可数集合。
证明：仿上题证明可得所有有理系数多项式的集合是可数集合。设所有n次有理系数多项式的集合记为An，则An是可数集合。令f(x)∈An，则f(x)根的个数≤n，于是，所有n次有理系数多项式根的集合Bn是可数集合。从而所有代数数构成的集合
11.非代数数的实数称为超越数，证明超越数集合是不可数集合。
证明：实数集合是由代数数和非代数数构成的，因为代数数构成的集合为可数集合，若超越数集合也是可数集合，则由定理1.3.4知由它们构成的实数集合是可数集合，这与实数是不可数集合矛盾，即假设不成立，从而超越数集合不可数。
12.自然数的所有序列作成的集合是否为可数集合？为什么？ 答：不是可数集合。
证明：设I表示整数集合，则整数的所有序列作成的集合为I?…?I?…，且自然数的所有序列作成的集合与集合I?…?I?…等浓。所以我们只需证明I?…?I?…是不可数集合。设B={0，1，2，…，9}，则B?…?B?…是I?…?I?…的子集。采用类似定理1.3.6的证明方法，可证明B?…?B?…是不可数集合，因此自然数的所有序列作成的集合不是可数集合。
?B是可数集合。
i?1i? 17