离散数学习题一,二参考答案

《离散数学》习题一参考答案

第一节 集合的基数

1. 证明两个可数集的并是可数集。

证明：设A ，B 是两可数集，A ={a 1, a 2, a 3, , a n , }，B ={b 1, b 2, b 3, , b n , } ⎧A B →N ⎪f :⎨a i 2i -1 ，f 是一一对应关系，所以|A∪B|=|N|=ℵ0。

⎪b 2j j ⎩

2．证明有限可数集的并是可数集

证：设A 1, A 2, A 3 A k 是有限个可数集，A i =(a i 1, a i 2, a i 3, a in , ), i =1, 2, 3, , k

k ⎧k ⎪A = A i →N ，f 是一一对应关系，所以|A|=| A i |=|N|=ℵ0。 f :⎨i =1

i =1⎪a ij j (k -1) +i ⎩

3. 证明可数个可数集的并是可数集。

证：设A 1, A 2, A 3 A k 是无限个可数集，A i =(a i 1, a i 2, a i 3, a in , ), i =1, 2, 3,

∞⎧A = A i →N ⎪⎪i =1f :⎨， 1⎪a ij (i +j -1)(i +j -2) +i ⎪2⎩

所以f 是一一对应关系，所以|A|=| A |=|N|=ℵ。 i ∞0

i =1

4. 证明整系数多项式所构成的集合是可数集。

证明：设整系数n 次多项式的全体记为

A n ={a 0x n +a 1x n -1+ +a n -1x +a n |a i ∈Z }

则整系数多项式所构成的集合A = A n ；

N =1∞

由于x k 的系数a k 是整数，那么所有x k 的系数的全体所构成的集合是可数集，由习题2“有限个可数集的并是可数集”可得A n 是可数集，再又习题4“可数个可数集的并是可数集”得出整系数多项式所构成的集合A = A n 也是可数集。

N =1∞

5. 证明不存在与自己的真子集等势的有限集合.

证明：设集合A 是有限集，则|A|=n，若B 是A 的真子集，则|B|≤|A|=n，A-B ≠φ，即|A-B|=|A|-|AB|＞0；又A=（A-B ）∪B ，（A-B ）B=φ，所以，，就是|A|＞|B|，即得结论。

6．证明正有理数集合是可数集，从而能证明有理数集是可数集。

m 证明：因为Q +={|m , n ∈N }，是正分数集， n

∞n +设A i ={|n ∈N },i =1, 2, 3, 4, , m }，A i 是可数集，并Q = A i i i =1

由可数集性质4“可数个可数集的并仍然是可数集”，所以正有理数集合是可数集。

有理数集Q=Q + {0} Q -，由可数集性质1，2，马上可得有理数集是可数集。

7．A 、B 为无限集，试说明下面的集合是否是无限集。

（1）A ∪B （2）A ∩B ；（3）A －B ；（4）A ×B

答：（1）A ∪B 是无限集，由可数集性质（2）可得。

（2）A ∩B 不一定是无限集，若A ∩B=φ，则|A∩B|=0；

（3）A －B 不一定是无限集，若A=B，则A －B=φ，

（4）A ×B 是无限集。相当于无限个无限集的并是无限集。

8．已知A ={n 7|n ∈N }，B ={n 109|n ∈N }，求

（1）A ，B 的基数；（2）A ∪B ，A ∩B 的基数。

⎧A =[n 7|n ∈N ) →N 解：（1）f :⎨，f 是一一对应关系，所以|A|=N|=ℵ0 7n n ⎩

⎧B =[n 109|n ∈N ) →N f :⎨，f 是一一对应关系，所以|B|=N|=ℵ0 109n n ⎩

（2）有可数集性质（2）可得A ∪B 是可数集，既| A∪B|=N|=ℵ0

因为(n 7) 109=(n 109) 7∈A B ，所以A ∩B ≠φ

⎧A B =[(n 109) 7|n ∈N ) →N ，f 是一一对应关系，所以| A∩B|=N|=ℵ0 f :⎨1097(n ) n ⎩

9. 设A 为任意集合，证明P （A ）与{0，1} A等势，其中{0，1} A为A 到{0，1}的全体函数。

⎧1x ∈A 解：若f A (x ) 是A 到{0，1}上的一个集函数，则f A (x ) =⎨ 0x ∉A ⎩

f ：ρ（A ）→{0, 1}

B →f B (x ) 所以f 是一一对应的，即ρ（A ）与{0, 1}等势。 A A

10. 集合A ，B 的笛卡尔乘积可表示为

A×B ＝｛〔a ，b 〕│a ∈A ，b ∈B ｝， 若A 1，A 2，„，A n 是可数集，证明A 1×A 2ׄ×A n 也是可数集。 解：．设A={a 1, a 2, a 3, , a n , }，B={b 1, b 2, b 3, , b n , }，并 C=A×B ={(a , b ) |a ∈A , b ∈B }= A

n =1∞n ，A n ={(a n , b i ) |b i ∈B }，

∞

因为A n 是可数集，n=1，2，3，„，所以C=A×B= A

n =1n 也是可数集，（可数个可数集是可

数集）。同理 A ×B ×C 也是可数集，由于A 1, A 2, A 3, , A n 是有限个可数集，所以A 1⨯A 2⨯A 3⨯ ⨯A n 也是可数集。