偏序集
数学概念
设R是集合A上的一个关系,如果R是自反的、反对称的和可传递的,则称R是集合A的偏序关系,简称偏序,记作“≤”。对于(a,b)∈R,就把它表示成a≤b。
偏序集与偏序关系的概念
定义1,设P是集合,P上的二元关系“≤”满足以下三个条件,则称“≤”是P上的偏序关系(或部分序关系):
(1)自反性:a≤a,∀a∈P;
(2)反对称性:∀a,b∈P,若a≤b且b≤a,则a=b;
(3)传递性:∀a,b,c∈P,若a≤b且b≤c,则a≤c;
具有偏序关系的集合P为偏序集(或称半序集),记为(P,≤)。a≤b读作“a小于或等于b”或“a含于b”,a
定义2,设(P,≤)是偏序集,对于P中任意二元x,y有x≤y yRx,则称R是≤的逆关系,记作≤-1。≤-1称为≤的逆。
定理1,设(P,≤)是偏序集,则(P,≤-1)也是偏序集,偏序集(P,≤-1)称为偏序集(P,≤)的对偶,简记作P-1。
定义3,设(P,≤)是偏序集,NP,由于关系≤是P×P的子集,令≤N=≤∩(N×N)是≤与N×N的交集,则称≤N是关系≤在N上的限制。
定理2,设(P,≤)是偏序集,关系≤N是≤在N上的限制,则(N,≤N)是偏序集,称为(P,≤)的子偏序集。
偏序集的哈塞图
刻画偏序关系的一种示意图。即有限集A的偏序结构的直观图示。图中用小圆圈表示集合A的元素。在a,b∈A,aRb时,从a有一条连续上升的不必笔直的线段或折线到达b。下面各图都可以看成集合的哈塞图。设R是集合A的偏序关系,则在偏序结构的哈塞图中:
1、aRb,当且仅当a到b有一条或几条严格上升的线段或折线连结。a与b间无线连结,或虽有折线连结但在上下起伏的时候,且。如图1中,,,等(为R的补关系)。
2、无水平的线段。
3、当R是全序时,哈塞图可画成一个上升的链状图,如图4。
4、同一个集合,当偏序关系不同时,有不同的哈塞图。例如,当A={2,3,4,6,8}时,关系R=“x不大于y”,G=“x整除y”时,R与G的哈塞图分别为图5与图6。
5、集合A的两个哈塞图相同,当且仅当通过变形可以把一个变成另一个,但是必须不改变图的连接并保持线段的上升方向。例如,图6、图7是同一个哈塞图。
6、把一个关系的哈塞图上下反转,得到它的逆关系的哈塞图,但左右翻转还是原关系的哈塞图。
哈塞(Hasse,H.)是第一个使用这种通俗的图来表示偏序。
参考资料
最新修订时间:2024-08-06 22:05
目录
概述
偏序集与偏序关系的概念
参考资料