等价关系与偏序关系1.ppt

1
等价关系
设R为非空集合上的关系. 如果R是自反的、对称的和传递的, 则称R为A上的等价关系. 设 R 是一个等价关系, 若<x,y>∈R, 称 x等价于y, 记做x~y.
由定义知:
(1)关系R是等价关系当且仅当R同时具备自反性、对称性和传递性;
(2)关系R不是等价关系当且仅当R不具备自反性或对称性或传递性。
2
实例
设 A={1, 2, …, 8}, R={ <x,y>| x,y∈A∧x≡y (mod 3)}
R 的关系图如:
例1 设 A={1, 2, …, 8}, 如下定义 A上的关系R: R={<x,y>| x,y∈A∧x≡y (mod 3)}其中 x≡y (mod 3) 叫做 x与y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等. 不难验证R为A上的等价关系, 因为
x∈A, 有x≡x(mod 3)x,y∈A, 若x≡y(mod 3), 则有y≡x(mod 3)x,y,z∈A, 若x≡y(mod 3), y≡z(mod 3), 则有x≡z(mod 3)
3
设R是非空集合A上的等价关系,则有下面的结论成立:
1)对xA,[x]R≠Φ;
2)对x,y∈A,如果y∈[x]R,则有[x]R=[y]R
3)对x,y∈A,如果y [x]R,则有[x]R∩[y]R=Φ
4) =A;
设R是非空集合A上的等价关系,对任意x∈A,称集合[x]R={y|y∈A∧<x,y>∈R}(也即A中与x等价的全体元素构成的子集)为x关于R的等价类.
等价类
4
集合的划分
设A为非空集合, 若A的子集族(P(A)) 满足下面条件:
(1) 
(2) xy (x,y∈∧x≠y→x∩y=) (3) ∪=A 则称是A的一个划分, 称中的元素为A的划分块.
5
商集
设R 为非空集合A 上的等价关系, 以R 的
所有等价类作为元素的集合称为A关于R
的商集, 记做 A/R,
 A/R = { [x]R | x∈A }
6
等价关系与划分的一一对应
(1) 商集 A/R 就是A 的一个划分,不同的商集对应于不同的划分
(2) 任给A 的一个划分, 如下定义A 上的关系 R:R ={<x,y> | x,y∈A∧x 与 y 在的同一划分块中}则R 为A上的等价关系, 且该等价关系确定的商集就是.
7
总结
1、熟记等价关系的定义;
2、利用等价关系的定义证明一个关系是等价关系;
3、给定A上的等价关系R,会求所有的等价类和商集A/R;并求出对应的集合的划分;
4、给定集合A上的划分,会求对应的等价类。
8
判定下列关系具有哪些性质
1、对任何非空集合A,A上的恒等关系;
2、多边形的“相似关系”、“全等关系”;
3、集合A的幂集P(A)上定义的“包含关系”;
4、集合A的幂集P(A)上定义的“真包含关系”。
解:1,2都具有自反性,对称性和传递性,是等价关系;
3 具有自反性,反对称性和传递性;
4 具有反自反性,反对称性,传递性。
偏序关系
拟序关系
9
偏序关系
非空集合A上的自反、反对称和传递的关系,称为A上的偏序关系,记作≼. 设≼为偏序关系, 如果<x, y>∈≼, 则记作 x≼y, 读作 x“小于或等于”y.
并将集合A与偏序关系R一起叫做偏序集, 用序偶<A,R>或者<A,≼>表示。
不指数的大小,
而指在偏序关
系中的顺序性
【实例】试判断下列关系是否为偏序关系:
(1)集合A的幂集P(A)上的包含关系“”
(2)实数集合R上的小于等于关系“≤”
(3)自然数集合N上的模m同余关系;
(4)自然数集合N上的整除关系“|”;
根据偏序关系的定义知(1),(2),(4),所对应的关系同时具有自反性,反对称性和传递性,所以都是偏序集;(3)所对应的关系不具有反对称性,
所以不是偏序集。