1、离散数学集合论1主要内容n 集合代数n 二元关系n 函数集合的基本概念集合的运算有穷集合的计数集合恒等式有序对与笛卡儿积二元关系关系的运算关系的性质 关系的闭包等价关系与划分偏序关系函数的定义与性质函数的复合与反函数双射函数与集合的基数27.6 等价关系与划分例 7.16 设 A=1,2,8, 定义 A 上的关系 R如下 :验证 R是 A上的等价关系 . 一 . 等价关系定义 7.15 设 R为非空集合 A上的关系 .如果 R是 自反的 , 对称的和 传递的 ,则称 R为 A上的等价关系 .对等价关系 R,若 R, 则称 x 等价于 y,记为 x y or xRy. 解 : xA,有 , 故
2、R是自反的 .x,yA, 若 , 则 , 故 R是对称的 .x,y,zA,若 , 则 , 故 R是传递的 . R是 A上的一个等价关系 .3等价类定义 7.16 设 R 为非空集合 A上的等价关系 ,xA, 令称 xR为 x在 R下的等价类 (简称为 x的等价类 ),有时简记为 x. x 称为该等价类的代表元 .注 :一个等价类是 A中在等价关系 R下彼此等价的所有元素的集合 ,等价类中各元素的地位是平等的 ,每个元素都可以作为其所在等价类的代表元 .例如 ,在上例中的等价关系 R下 ,A中元素形成了三个等价类 :1=4=7=1, 4, 7; 2=5=8=2, 5, 8;3=6=3, 6. ,
3、 , , , , , , , , , , , , , , 4等价类的性质定理 7.14 设 R 为非空集合 A上的等价关系 ,则（ 1） xA, x是 A的非空子集 .（ 2） x, yA,如果 xRy, 则 x=y（ 3） x, yA,如果 x与 y不具有关系 R, 则 x 与 y 不相交 .（ 4） x | xA = A证 ： (1) 显然 .(2) z x R R（ R是对称的） R R R R z y, 从而 x y同理可得 ,y x. 故 x = y5等价类的性质(3) 反证法 .假设 x y ,则存在 zx y.因而 z x 且 z y,即 R R. 根据 R的对称性和传递性 ,必
4、有 R.这与前提条件矛盾 .故原命题成立 .(4) 先证 再证 因此6商集与划分定义 7.17 设 R为非空集合 A上的等价关系 ,以 R的所有等价类作为元素 , 形成的集合称为 A关于 R的 商集 ,记为 A/R,即 :例如 :例 7.16中等价关系形成的商集为 : A/R 1, 4, 7, 2, 5, 8, 3, 6定义 7.18 设 A为非空集合 ,若 A的子集族 (P(A), 是由 A的一些子集形成的集合 ) 满足下列条件 :(1) (2) xy(x,y xyxy= )(3) 则称 是 A的一个 划分 ,而称 中的元素为 A的划分块或类 . 五 . 集合的划分7等价关系与划分例 7.1
5、7 设 A=a, b, c, d , 则 1=a,b,c ,d和 2=a,b,c,d都是 A的划分 ,而 3=a,a,b,c,d和 4= ,a,b,c都不是 A的划分 .注 :给定非空有限集 A上的一个等价关系 R,在 R下彼此等价的元素构成的子集便形成了 A的一个划分 ,它其实就是商集 A/R, 其每个类 (等价块 ) 就是 R的一个等价类 ;反之 ,任给 A的一个 划分 ,可定义 A上的关系 R如下 :R=x,yAx 与 y在 的同一个类中 可以验证 R是 A上的一个等价关系 .可见 A上的等价关系与 A的划分是一一对应的 .8例例 7.18 求 A=1, 2, 3上所有的等价关系 .解
6、先求出 A的所有划分 :1=1, 2, 3; 2=1, 2, 3；3=2, 1, 3; 4=3, 1, 2;5= 1, 2, 3.与这些划分一一对应的等价关系是 :1: 全域关系 EA2: R 2=, I A3: R 3=, I A4: R 4=, I A5: 恒等关系 IA97.7 偏序关系一. 偏序关系与偏序集定义 7.19 设 R为非空集合 A上的关系 .如果 R是 自反的 ,反对称的 和传递的 ,则称 R 为 A上的偏序关系 ,记为 .对一个偏序关系 ,如果 ,则记为 x y.注 :1. 集合 A上的恒等关系 IA和空关系都是 A上的偏序关系 ,但全域关系 EA 一般不是 A上的偏序关系 .2. 实数域上的小于等于关系（大于等于关系） ,自然数域上的整除关系 ,集合的包含关系等都是偏序关系 .10
