4.设A,B是集合,若存在A到B的满射,则Bl。 (真) 设存在A到B的满射,对任意b∈B,存在x∈A,fu)=b。 而由函数的定义,间=b,1y)=b2,若b马,则a。则B≤4l 证明:任何平面图是5-可着色的。(10分) 证明:定理9.10证明,112页。 三、如果在一个地图上任何两个地区都相邻,问在该地图上最多有几个地区?(10分) 四、R是集合A上的等价关系,4=n,|R=s。对于A关于R的商集A/R,MR=r。证明: rS22。(14分) 习题解析: R、A和AR三者的基数之间存在什么关系? 1)R是集合A上的等价关系→R对A形成的一个划分,这个划分就是商集A/R。 2)取划分的一个块,若块中元素k个,则该块产生的有序对为k2个。 线 3)r个块的有序对相加,和等于。r个块中所含元素的个数相加,和等于n 内 证明思路和过程 不 设AR的r个等价类集合的元素个数分别是m1,m2,…,mr。则m+m+ +mr =I 要 m+mr +m2=s。因此,问题转换为证明(mr2+m2+….….+mr)h=(m1+m2+ 答 m))2,即证明rm12+mx2+ m2。(可以用数学归纳法进行 题 证明)。 数学归纳法证明:rⅧmr2+m2+……+m)≥(m+m2+,…+m)2 归纳基础 当r=1时,左式=m2,右式=mr2,左式≥右式,命题成立。 归纳步骤: 设当r=k时,命题成立。即,kmr2+m2+…+mk2)2(m+m2+……+m)2。 则当r=k+1时,左式= k+1)m12+m2+……+mk+12) +m =km2+m2+.….+mk2)+kmk+12+m2+m2+…..+mk2)+mk+2 =km12+m2+……+mk2)+(m2+mk+1)+(m2+mk+r2)+……+(m2+m+12)+mk+ 右式=(m1+m2+…+mk+1)2 =(m+m2 =(m1+m2+……+mk)2+2mk+1m1+2mk+1m2+…….+2mk+1mk+mk+r 由归纳假设km2+m2+…+mx)(m+m+……+my2,以及基本不等式,左式≥右式 命题成立。 所以r2n2。 五、如果有一群人,其中有k个人彼此认识或者有l个人彼此不认识。我们用rkD表示这群人至少 第2页第 2 页 （ 装 订 线 内 不 要 答 题 ） 4．设 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|。 二、证明：任何平面图是 5-可着色的。 （10 分） 证明：定理 9.10 证明，112 页。 三、如果在一个地图上任何两个地区都相邻，问在该地图上最多有几个地区？（10 分） 4 四、R 是集合 A 上的等价关系，|A|=n，|R|=s。对于 A 关于 R 的商集 A/R，|A/R|=r。证明： rsn 2。（14 分） 习题解析： • 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+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，以及基本不等式，左式右式， 命题成立。 所以 rsn 2。 五、如果有一群人，其中有 k 个人彼此认识或者有 l 个人彼此不认识。我们用 r(k, l)表示这群人至少