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(BC)=(AB) ( AC) （假） A={2, 3}，B={1, 4, 7}，C={3,5} 3．设 A, B 是集合，若存在 A 到 B 的满射，则|B||A|。 （ 真 ） 设存在 A 到 B 的满射 f，对任意 bB，存在 xA，f(a)=b。 而由函数的定义，f(a1)=b1，f(a2)=b2，若 b1b2，则 a1a2。则|B||A|。 三、综合题（52 分） 1．设 R 是 A 上的二元关系。证明 R 的自反闭包的对称闭包的传递闭包，是包含 R 的最小 的等价关系。（15 分） 2．R 是集合 A 上的等价关系，|A|=n，|R|=s。对于 A 关于 R 的商集 A/R，|A/R|=r。 证明：rsn 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