复旦大学《集合论与图论》课堂练习1(2017年11月6日)(参考答案)

《集合论与图论》课堂练习1

（2017年11月6日 13:30-15:10 复旦大学计算机学院）

学号姓名成绩

一、填空题（30分，每格2分）

1．设A为一个集合，若A为空集或与集合{0,1,2,…,n-1}的基数相同，则A为有限集。若存在从N到A的双射，则称A为可列集。

2．设R是A上的二元关系，定义R的自反（对称，传递）闭包记为R’，满足下列三个条件：

（1）R’是自反的（对称的，传递的）；

（2）R’?R；

（3）对任一自反（对称，传递关系）R”，R?R”，则R’?R”。

3．集合A的递归（归纳）定义由三部分组成：

（1）_基础: 某些元素属于我们正在定义的集合A中,说明集合A是非空的

_ _;

（2）_递归（归纳）: 使用当前集合A中的现有元素来产生含在此集合中的更多元素, 即建立产生集合A中新元素的一种方法

_ ;

（3）_闭合: 只有在集合A中的元素是通过有限次应用(1)和(2)得到的

_ _。

4．设A和B是两个任意集合，f 是从A到B的二元关系。若f 具有性质：（1）f 的定义域Dom f=A；

（2）如果(a, b)，(a, b’)∈f，则b=b’。

则称关系f 是从A到B的函数，记为f:A?→B。

5．函数f:R?R→ R?R，f((x, y))=(x+y, x-y)。f的逆函数f-1是f-1((x, y))=((x+y)/2, (x-y)/2) 。

6. 设集合A={ x | (x∈R) and (x3-2x2-x+2=0) },则集合A的幂集P(A)= {?, {1},{-1}, {2}, {-1, 1}, {-1, 2}, {1. 2}, {-1, 1, 2} } 。

7. 设R是从A到B的二元关系，则从B到A的二元关系记为R-1，定义为R-1 ={(b, a)|(a, b)∈R}，称为R的逆关系。

8. 设g: A?→B, f: B?→C，定义复合函数f o g为：f o g ={(a, c) | a∈A, c∈C，且存在b∈B，使b=g(a), c=f(b) }，称f o g是从A到C的复合函数。

二、是非判断题（24分，每题6分，其中判断3分，论述3分）

1．设A, B, C是任意集合，A?(B⊕C)=( A?B) ⊕( A?C)；

（真）

2．设A, B, C是任意集合，则A?B?B=A?(B-A)。

（真）

3．设f: N→N?N, f(n)=(n, n+1)，则f是满射。

（假）

4．设R 是A 上的二元关系，则ts (R ) = st (R )。

（ 假 ）

三、综合题（46分）

1．试证明下面结论：

(1) 设A 1与A 2为可列集，则A 1与A 2的直积21A A ?也是可列集。

(2) 任意有限个可列集的直积也是可列的。即设n 为任意正整数，n A A A ,,,21Λ为可列集，则n A A A ???Λ21也是可列的。

(3) 可列个可列集的直积也是可列的吗？（要求先判断，再说明理由） 解：(1)是作业；(2)利用数学归纳法可由(1)直接得到。

（3）可列个可列集的直积不是可列的，它的基是?。即若ΛΛn A A A ,,,21为可列集，则ΛΛn A A A ???21的基为?。现证明如下：

我们只要证明|)1,0(|||=???ΛΛN N N ，其中N 为自然数集。

先证|||)1.0(|ΛΛN N N ???≤：设)1,0(∈?x ，把x 写成十进制的无限小数x=0.x 1x 2x 3….，定义函数Λ???→N N N f )1,0(:为),,,()(321Λx x x x f =，其中x=0.x 1x 2x 3….为x 的十进制无限表示。易知f 是单射，所以|||)1.0(|ΛΛN N N ???≤。

再证|)1.0(|||≤???ΛΛN N N 。我们把每个自然数用二进制表示。定义函数 )1,0(:→???ΛN N N g ：对任意ΛΛ222.0)),,,((321321x x x x x x g =，这里等式右边的x i 是x i 的二进制表示。易知g 是单射，注意这里必须用2把各个x i 隔开，

否则不是单射。

所以|)1.0(|||≤???ΛΛN N N 。故|)1.0(|||=???ΛΛN N N

2．求不超过100的质数的个数

（15分，方法正确5分，公式正确5分，结果正确5分）

因为102=100，所以，不超过100的合数，其质因子只有可能是2、3、5、7。 设S ={x | x ∈N , 1≤x ≤100}, A 1, A 2, A 3, A 4分别是能被2、3、5、7整除的集合。 则求不超过100的质数的个数N=1234A A A A ???+3

2、3、5、7这4个数不属于集合1234A A A A ???，但它们是不超过100的质数。此外1属于1234A A A A ???，但1不是质数，所以上述公式+3

| A 1|=50，| A 2|=33，| A 3|=20，| A 4|=14；

| A 1? A 2|=16，| A 1? A 3|=10，| A 1? A 4|=7，| A 2? A 3|=6，| A 2? A 4|=4，| A 3? A 4|=2； | A 1? A 2? A 3|=3, | A 1? A 2? A 4|=2，| A 1? A 3? A 4|=1，| A 2? A 3? A 4|=0；

| A 1? A 2? A 3? A 4|=0

由容斥原理 N=1234A A A A ???+3=100-(50+33+20+14)+(16+10+7+6+4+2)-(3+2+1+0)+0+3=25

3．R 是集合A 上的二元关系，用R 定义关系T ，满足：任意a , b ∈A ，有aTb ?aRb 并且bRa 。关系R 至少要具备哪些性质，使得T 是等价关系，证明你的结论。 （16分）

解题分析：

求使得T 是等价关系R 至少要具备哪些性质，就是求使得T 是自反、对称和传递关系的所有必要条件。

分别从T 是自反的、对称的和传递的出发，来讨论R 至少要具备哪些性质，求得T 是等价关系的必要条件。

解：

（1）对称性。

因为对于任意a, b∈A，有aTb?aRb并且bRa，因此T是对称的，与R的性质无关。

（2）自反性。

若T是自反的，则对于任意a∈A，有aTa?aRa，因此R是自反的。

（3）传递性。

若T是传递的，则对于任意a, b, c∈A，如果aTb并且bTc，则aTc。aTb?aRb并且bRa，bTc?bRc并且cRb，aTc?aRc并且cRa，所以(aRb并且bRa), (bRc并且cRb)? aRc并且cRa 就是为使T具有传递性，R应该具有的性质。

所以，使得T是等价关系，R要具备的性质是：自反，如果(aRb并且bRa), (bRc并且cRb)，则aRc并且cRa。

可以证明：求得的R具备的性质，同时分别也是使T是自反、传递的充分条件。