设R是集合A上的一个关系,如果R是自反的、反对称的和可传递的,则称R是集合A的偏序关系,简称
偏序,记作“≤”。对于(a,b)∈R,就把它表示成a≤b。
定义1,设P是集合,P上的二元关系“≤”满足以下三个条件,则称“≤”是P上的
偏序关系(或部分序关系):
具有
偏序关系的集合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,≤)的子偏序集。
偏序集的哈塞图
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.)是第一个使用这种通俗的图来表示偏序。