拟序关系
二元关系
拟序关系亦称伪序关系或前序关系,是一种重要的二元关系。满足反自反性和传递性的二元关系R,称A为拟序集。拟序关系有下列特点: 1. 对角集EA⊆R,且当〈a,b〉∈R,〈b,c〉∈R时,〈a,c〉∈R;2. R 的矩阵(rij)λ主对角线上的元素全是1,且当rij=rjk=1时,rik=1;3. R的箭头图上,每个元素有一个从自己出发又指向自身的箭头,且在有a到b的箭头,b到c的箭头时,就有a到c的箭头。拟序关系的逆关系一定是拟序的,反对称的拟序关系是偏序关系,但拟序关系可以不是偏序关系。
定义
拟序关系是一种次序关系,比偏序关系的限制更严格一些。它是一种满足反自反、反对称与传递的关系。
设R是非空集合A上的关系,若R具有反自反性、传递性,则称R是A上的拟序关系(Quasi-ordering relation),记该关系R为<。若,可记作,读作“a小于b”。
注意:这里的“小于”不是指普通数的大小关系的<,而是指拟序的“小于”。x“小于”y的含义是:依照这个顺序,x排在y的前边。
例题解析
例1 A={1,2,3},R是A上的整除关系,R={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>},显然R是偏序关系,A中元素有以下关系:1<2,1<3;1=1,2=2,3=3;2和3不可比。
例2实数集上的小于关系R是拟序关系。
证明:对任何一个实数x都不存在x
对于任何实数x,y,如果x
对于任何实数x,y,z,如果x
性质定理
定理1设R是集合A上的拟序关系,则R是反对称性。
证明: 设R不是反对称的,则至少存在两个元素,且因为R是传递的,所以这与R是反自反的特性相矛盾,因此R具有反对称性。
从该定理,很容易得出以下结论:
(1) 由反自反性和传递性可以推出反对称性。
(2) 拟序关系具有反自反性、反对称性和传递性。
(3) 拟序和偏序的区别在于反自反性和自反性上,它们均具有反对称性和传递性。
(4) 若R是偏序关系,则是拟序关系;若R是拟序关系,则是偏序关系。即偏序是拟序的扩充,拟序是偏序的缩减。
(5) 拟序集合与偏序集合具有相同的哈斯图
参考资料
最新修订时间:2023-01-03 18:15
目录
概述
定义
例题解析
参考资料