《集合论与图论》课堂练习1 (2013年10月23日13:30-15:00复旦大学计算机科学技术学院2012级) 学号 姓名 成绩 、填空题(30分,每格3分) 1.设A为一个集合,若 A为有限集。 则称A为可列集。 2.设R是A上的二元关系,R的自反(对称,传递)闭包,记为R',满足下列 3个条件 (3) 3.集合A的递归(归纳)定义由三部分组成: (2) 4.设R1是从A到B的二元关系,R2是从B到C的二元关系,则从A到C的 R1和R2的复合关系定义为 5.设f1是从A到B的函数,f是从B到C的函数,则从A到C的f和f的复 合函数定义为 是非判断题(18分,每题6分,其中判断3分,论述3分)
1 《集合论与图论》课堂练习 1 （2013 年 10 月 23 日 13:30-15:00 复旦大学计算机科学技术学院 2012 级） 学号 姓名 成绩 一、 填空题（30 分，每格 3 分） 1．设 A 为一个集合，若 A 为有限集。 若 ，则称 A 为可列集。 2．设 R 是 A 上的二元关系，R 的自反（对称，传递）闭包，记为 R’，满足下列 3 个条件： （1）_ _ _; （2）_ _ ; （3）_ _ _。 3．集合 A 的递归（归纳）定义由三部分组成： （1）_ _ _; （2）_ _ ; （3）_ _ _。 4．设 R1 是从 A 到 B 的二元关系，R2 是从 B 到 C 的二元关系，则从 A 到 C 的 R1 和 R2 的复合关系定义为_ _ _ 。 5. 设 f1 是从 A 到 B 的函数，f2 是从 B 到 C 的函数，则从 A 到 C 的 f1 和 f2的复 合函数定义为_ _ _ 。 二、是非判断题（18 分，每题 6 分，其中判断 3 分，论述 3 分）
1.自然数集合的幂集是不可列集。 (真) 2. AU(BECF()E(AUC) (假) A={2,3},B={1,4,7},C={3,5} 3.设A,B是集合,若存在A到B的满射,则B (真) 设存在A到B的满射f,对任意b∈B,存在x∈A,fa)=b。 而由函数的定义,=b,fay)=b2,若bb,则aa。则B≤ 综合题(52分) 1.设R是A上的二元关系。证明R的自反闭包的对称闭包的传递闭包,是包含R的最小 的等价关系。(15分) 2.R是集合A上的等价关系,|=n,R=s。对于A关于R的商集A/R,MA/R=r 证明:rs≌n2。(16分) *中国科学院计算所2000* 习题解析: ·R、A和A/R三者的基数之间存在什么关系? 1)R是集合A上的等价关系→R对A形成的一个划分,这个划分就是商集A/R。 2)取划分的一个块,若块中元素k个,则该块产生的有序对为k2个 3)r个块的有序对相加,和等于s。r个块中所含元素的个数相加,和等于n。 证明思路和过程 设AR的r个等价类集合的元素个数分别是m,m,…,mr。则m+m2+….+mr m2+m2+ +m2=s。因此,问题转换为证明m-2+m2+ +m2方xm+m+……,+m)m,即证明rm12+m2+……+mr2)2(m1+m+ m)2。(可以用数学归纳法进行证明)。 数学归纳法证明:r(mr2+m2+…….+m;2)2(m+m2+ 归纳基础 当r=1时,左式=m12,右式=m12,左式≥右式,命题成 归纳步骤: 设当r=k时,命题成立。即,k(m2+m2+….+mk)2(m1+m2+……+m2。 则当r=k+1时,左式= k+D)m2+m2+……+mk+12) +mk+r2)+mr2+m2+….+mk+r) km2+m2+……,+m2)+kmk+12+m2+m2+…..+mk2)+mk+12 km2+m2+.…,+mk2)+(m2+mk+12)+(m2+mk+r2)+…,+(mk2+mk+12)+mk+1 右式=(m+m2+….…,+mk+
2 1．自然数集合的幂集是不可列集。 （真） 2．A(BC)=(AB) ( AC) （假） A={2, 3}，B={1, 4, 7}，C={3,5} 3．设 A, B 是集合，若存在 A 到 B 的满射，则|B||A|。 （ 真 ） 设存在 A 到 B 的满射 f，对任意 bB，存在 xA，f(a)=b。 而由函数的定义，f(a1)=b1，f(a2)=b2，若 b1b2，则 a1a2。则|B||A|。 三、综合题（52 分） 1．设 R 是 A 上的二元关系。证明 R 的自反闭包的对称闭包的传递闭包，是包含 R 的最小 的等价关系。（15 分） 2．R 是集合 A 上的等价关系，|A|=n，|R|=s。对于 A 关于 R 的商集 A/R，|A/R|=r。 证明：rsn 2。（16 分） /*中国科学院计算所 2000*/ 习题解析： • R、A 和 A/R 三者的基数之间存在什么关系？ 1）R 是集合 A 上的等价关系 R 对 A 形成的一个划分，这个划分就是商集 A/R。 2）取划分的一个块，若块中元素 k 个，则该块产生的有序对为 k 2 个。 3）r 个块的有序对相加，和等于 s。r 个块中所含元素的个数相加，和等于 n。 证明思路和过程： 设 A/R 的 r 个等价类集合的元素个数分别是 m1, m2, …, mr。则 m1+m2+… … +mr =n ， m1 2+m2 2+… … +mr 2 =s 。 因 此 ， 问 题 转 换 为 证 明 (m1 2+m2 2+… … +mr 2 )/r(( m1+m2+… … +mr)/r)2，即证明 r (m1 2+m2 2+… … +mr 2 ) ( m1+m2+… … +mr) 2。（可以用数学归纳法进行证明）。 数学归纳法证明：r (m1 2+m2 2+… … +mr 2 ) ( m1+m2+… … +mr) 2。 归纳基础： 当 r=1 时，左式= m1 2，右式= m1 2，左式右式，命题成立。 归纳步骤： 设当 r=k 时，命题成立。即，k (m1 2+m2 2+… … +mk 2 ) ( m1+m2+… … +mk) 2。 则当 r=k+1 时，左式= (k+1) (m1 2+m2 2+… … +mk+12 ) =k(m1 2+m2 2+… … +mk+12 )+ (m1 2+m2 2+… … +mk+12 ) =k(m1 2+m2 2+… … +mk 2 )+kmk+12+(m1 2+m2 2+… … +mk 2 ) + mk+12 =k (m1 2+m2 2+… … +mk 2 )+( m1 2+mk+12 )+ ( m2 2+mk+12 )+……+( mk 2+mk+12 )+ mk+12 右式=( m1+m2+… … +mk+1) 2
=(m1+m2+……+mk)2+2mk+1(m1+m2+……,+mk)+mkx+12 =(m1+m2+…….+mk)2+2mk+1m1+2mk+1m2+….….+2mk+1mk+mk+2 由归纳假设km2+m2+….+mk)(m+m+……+mb2,以及基本不等式,左 式≥右式,命题成立。 所以rsn2 3.格是一个偏序集,其中每对元素都有一个最大下界和最小上界。 (1)证明一个集合上的所有划分的集合与关系≤构成一个格 (2)如果划分P1是P2的加细,则P1≤P2。(22分,每题11分) 设∏是集合S的所有划分的集合,如果划分P是P2的加细,即如果P1中的每个 集合都是P2中某个集合的子集,则P1≤P2 首先证明(∏,≤)是偏序集 由于P≤P,所以≤是自反的 假设P1≤P2,并且P≤P1。令T∈P,因为P1≤P2,存在集合T∈P2,使得TT 又因为P2≤P1,存在集合T"∈P1,使得T'cT;从而TcT。但是因为P1是划分, 由T=T和 TCTCT推出T=T,于是TeP2。反之,通过交换P1与P2同样得出 P2的每个子集也在P1中。因此P1=P2,并且≤是反对称的 假设P1≤P2并且P2≤P3。令T∈P1,存在集合T∈P2,使得TT;由于P2≤P3,存 在集合T'eP3,使得T'<T”;所以TT,因此P1≤P3。所以≤是传递的。 划分P1和P2的最大下界是划分P,P的子集都是形如TT2的非空集合,其中T∈P1,T2∈ P2,划分P1和P2的最小上界对应于等价关系的划分:x∈S等价于y∈S,如果对某个非负整 数n存在序列x=x0,x,x2,…,xn=y,使得从1到n的每个i,x1和x在P1或者P2的同一元 素中
3 =( m1+m2+… … +mk) 2+2 mk+1 ( m1+m2+… … +mk)+ mk+12 =( m1+m2+… … +mk) 2+2 mk+1 m1+2 mk+1 m2+… … +2 mk+1 mk+ mk+12 由归纳假设 k (m1 2+m2 2+… … +mk 2 ) ( m1+m2+… … +mk) 2，以及基本不等式，左 式右式，命题成立。 所以 rsn 2。 3．格是一个偏序集，其中每对元素都有一个最大下界和最小上界。 （1）证明一个集合上的所有划分的集合与关系≤构成一个格。 （2）如果划分 P1 是 P2 的加细，则 P1≤P2。（22 分，每题 11 分） 设是集合 S 的所有划分的集合，如果划分 P1 是 P2 的加细，即如果 P1 中的每个 集合都是 P2 中某个集合的子集，则 P1≤P2。 首先证明（，≤）是偏序集。 由于 P≤P，所以≤是自反的。 假设 P1≤P2，并且 P2≤P1。令 T P1，因为 P1≤P2，存在集合 T’P2，使得 TT’； 又因为 P2≤P1，存在集合 T”P1，使得 T’T”；从而 TT”。但是因为 P1是划分， 由 T=T”和 TT’T”推出 T’=T”，于是 TP2。反之，通过交换 P1 与 P2同样得出 P2的每个子集也在 P1中。因此 P1=P2，并且≤是反对称的。 假设 P1≤P2 并且 P2≤P3。令 T P1，存在集合 T’P2，使得 TT’；由于 P2≤P3，存 在集合 T”P3，使得 T’T”；所以 TT”，因此 P1≤P3。所以≤是传递的。 划分 P1 和 P2 的最大下界是划分 P，P 的子集都是形如 T1T2 的非空集合，其中 T1 P1，T2 P2，划分 P1 和 P2 的最小上界对应于等价关系的划分：xS 等价于 yS，如果对某个非负整 数 n 存在序列 x=x0, x1, x2, …, xn=y，使得从 1 到 n 的每个 i，xi-1和 xi 在 P1 或者 P2 的同一元 素中