集合论小结.pptVIP

* * 习题课(集合论小结) 第五章 集合的基本概念及其运算 重点掌握： 集合的表示。 集合的运算： ρ(A) 、∩、∪、－、 ~ 、+ 、∪A、∩A、A×B 集合的运算性质 四个等价命题：（1）A?B （2）A?B=B （3）A?B=A （4）A-B=? 集合的“=”、“?”的定义及证明。 第六章 关系 重点掌握： 关系的定义全域关系、恒等关系 关系的表示 关系性质的判定及证明 关系运算：dom(R) 、ran(R) 、R·S、R-1 、 r（R）、 s（R）、t（R）。 偏序集合及哈斯图、偏序集合特殊元素的判定 等价关系、划分、等价关系与划分的关系 R是自反的??x(x?X ? x , x ? R) R是反自反的??x(x?X ? x , x ?R) R是对称的??x?y (x?X ? y ?X ? x , y ? R ? y , x ? R ) R是反对称的??x?y (x?X ? y?X ? x , y?R ? y, x?R ? x = y) R是传递的??x?y?z (x?X ? y?X ? z?X ? x , y?R ? y, z?R ? x , z?R ) 1. 设R是集合A上的关系，证明：R是自反的当且仅当IA ? R 。 证明 先证必要性。假设IA ? R 不成立，则必存在x∈A使得〈x,x〉∈IA且〈x,x〉?R ，这与R是自反的相矛盾，所以IA?R。 再证充分性。设IA?R 。对于任意x∈A，〈x,x〉∈IA，因为IA?R，所以〈x,x〉∈R。因此，R是自反的。 2. 设R是集合A上的关系，证明：R是反自反的当且仅当R∩IA＝?。 证明：证充分性，用反证法。 假设R不是反自反的，则存在x ?A ，使得x,x?R 。 又因为x,x? IA，因此x,x? R∩IA 。这与R∩IA＝?矛盾，所以R是反自反的。 证必要性，用反证法。 假设R∩IA??，则存在x,y ?A ，使得x,y?R ∩IA x,y?R ∩IA ? x,y?R? x,y? IA x,y?R? x=y x,x?R 这与R是反自反的矛盾，故R∩IA＝? 3. 设R是集合A上的关系，证明： R是对称的当且仅当R ＝ R－1 （已证明） 4. 设R是集合A上的关系，证明：R是反对称的当且仅当R∩R －1 ?IA 。 证明 设R是反对称的。若R∩R－1?IA不成立 ，则有x,y∈A，使得〈x,y〉∈R∩R－1,但〈x,y〉?IA ，即〈x,y〉∈R，〈y,x〉∈R，x≠y 。这与R是反对称的相矛盾。所以R∩R－1 ? IA 。 设R∩R－1?IA 。任取x,y∈A，如果〈x,y〉∈R且x≠y ，则〈x,y〉? IA ，故〈x,y〉? R∩R－1，因此〈x,y〉 ? R－1，即〈y,x〉? R 。这表明R是反对称的。 5. 设R是集合A上的关系，证明：R是传递的当且仅当R2?R 。 证明 设R是传递的。任取〈x,z〉∈R2 ，则有y∈A使得〈x,y〉,〈y,z〉∈R ，因为R是传递的，所以〈x,z〉∈R 。因此，R2 ? R 。 设R2?R 。任取〈x,y〉,〈y,z〉∈R ，则〈x,z〉∈R2 ，又因为R2?R ，故〈x,z〉∈R 。所以，R是传递的。 18．对于下列集合上的整除关系画出哈斯图。 （ 1） A={1，2，3，4，6，8，12，24} 2） B={1，2，3，?，12} 解： 1 2 4 3 8 6 24 12 1 2 3 4 5 6 7 8 9 10 12 11 26．设R是正整数的有序偶集合上的关系，并且?x，y?R?u，v?当且仅当xv=yu，证明R是等价关系。 证明：对于任意正整数x，y，因为xy=yx，根据R的定义，有?x，y?R?x，y?，故R有自反性。 对于任意正整数x，y，u，v，设?x，y?R?u，v?，根据R的定义，有xv=yu，即有uy=vx，?u，v?R?x，y?，因此R有对称性。 对于任意正整数x，y，u，v，s，t，设?x，y?R?u，v?，?u，v?R?s，t?根据R的定义，有xv=yu，ut=vs ,即 x/y=u/v, u/v=s/t 。因此x/y=s/t , 即xt=ys，根据R的定义，有?x，y?R?s，t?，故R有传递性。 综上所述，关系R是等价关系 第七章函数 重点：函数的定义、判定及证明，函数性质的判定及证明，函数的限制，函数下的象，函数的复合，反函数，函数运算的性质 函数：设F是关系，如果对于每