更新时间:2022-08-25 14:02
偏序集合(英语:Partial order set,简写poset)是数学中,特别是序理论中,指配备了部分排序关系的集合。 这个理论将排序、顺序或排列这个集合的元素的直觉概念抽象化。这种排序不必然需要是全部的,就是说不必要保证此集合内的所有对象的相互可比较性。部分排序集合定义了部分排拓扑。
则称“<”是S上的严格偏序或反自反偏序。
严格偏序与有向无环图(dag)有直接的对应关系。一个集合上的严格偏序的关系图就是一个有向无环图。其传递闭包是它自己。
容易证明以下结论:
由上述可知,只要定义了“≤”、“<”、“≥”、“>”中的任何一个,其余三个关系的定义可以自然诱导而出,这四种关系实际上可以看成一体。故此在不严格区分的情况下,只需定义其一即可(通常是“≤”),称之为集合S上的偏序关系。(“偏序关系”通常被用来称呼非严格偏序关系。)
若集合S上定义了一个偏序,则S称为偏序集(poset);若将其上的偏序关系改为其逆关系,得到的新偏序集S'称为S的序对偶。
虽然通常术语“有序集”用来称呼全序集,但当上下文中不涉及其他序关系时,“有序集”也可用于称呼偏序集。
下面是一些主要的例子:
一般的说偏序集合的两个元素x和y可以处于四个相互排斥的关联中任何一个:要么x 全序T是偏序P的线性扩展,只要x≤y在P中成立则x≤y在T中也成立。在计算机科学中,找到偏序的线性扩展的算法叫做拓扑排序。