当前位置:首页 科普知识 偏序关系

偏序关系

发布时间:2023-09-06 03:07:44

偏序集合(英语:Partial order set,简写poset)是数学中,特别是序理论中,指配备了部分排序关系的集合。 这个理论将排序、顺序或排列这个集合的元素的直觉概念抽象化。这种排序不必然需要是全部的,就是说不必要保证此集合内的所有对象的相互可比较性。部分排序集合定义了部分排拓扑。

偏序关系详细介绍

偏序集合(英语:Partial order set,简写poset)是数学中,特别是序理论中,指配备了部分排序关系的集合。 这个理论将排序、顺序或排列这个集合的元素的直觉概念抽象化。这种排序不必然需要是全部的,就是说不必要保证此集合内的所有对象的相互可比较性。部分排序集合定义了部分排拓扑。

偏序关系

偏序关系形式定义

设R是集合A上的一个二元关系,若R满足:

Ⅰ 自反性:对任意xA,有xRx

Ⅱ 反对称性(即反对称关系):对任意x,yA,若xRy,且yRx,则x=y

Ⅲ 传递性:对任意x, y,zA,若xRy,且yRz,则xRz

则称R为A上的偏序关系,通常记作≼。注意这里的≼不必是指一般意义上的“小于或等于”。

若然有xy,我们也说x排在y前面(x precedes y)。

偏序关系偏序分类

偏序关系非严格偏序,自反偏序

给定集合S,“≤”是S上的二元关系,若“≤”满足:

    自反性:∀a∈S,有a≤a;

    反对称性:∀a,b∈S,a≤b且b≤a,则a=b;

    传递性:∀a,b,c∈S,a≤b且b≤c,则a≤c;

则称“≤”是S上的非严格偏序或自反偏序。

偏序关系严格偏序,反自反偏序

给定集合S,“<”是S上的二元关系,若“<”满足:

    反自反性:∀a∈S,有a≮a;

    非对称性:∀a,b∈S,a<b ⇒ b≮a;

    传递性:∀a,b,c∈S,a<b且b<c,则a<c;

    偏序关系

则称“<”是S上的严格偏序或反自反偏序。

严格偏序与有向无环图(dag)有直接的对应关系。一个集合上的严格偏序的关系图就是一个有向无环图。其传递闭包是它自己。

偏序关系偏序相关结论

容易证明以下结论:

给定集合S上的一个(非严格,自反)偏序“≤”,则可自然地诱导出S上的一个(严格,反自反)偏序“<”,只需如此定义:a < b,如果 a ≤ b 且 a ≠ b。

给定集合S上的一个(严格,反自反)偏序“<”,则可自然地诱导出S上的一个(非严格,自反)偏序“≤”,只需如此定义:a ≤ b,如果 a < b 或 a = b。

给定集合S上的一个(非严格,自反)偏序“≤”,其逆关系“≥”也是S上的一个(非严格,自反)偏序;

给定集合S上的一个(严格,反自反)偏序“<”,其逆关系“>”也是S上的一个(严格,反自反)偏序;

由上述可知,只要定义了“≤”、“<”、“≥”、“>”中的任何一个,其余三个关系的定义可以自然诱导而出,这四种关系实际上可以看成一体。故此在不严格区分的情况下,只需定义其一即可(通常是“≤”),称之为集合S上的偏序关系。(“偏序关系”通常被用来称呼非严格偏序关系。)

(非严格,自反)偏序和(严格,反自反)偏序之间的对应关系不同于在(非严格)弱序和严格弱序直接的对应(逆关系的补集)。只有对于全序这些对应才是相同的。

偏序关系偏序集与序对偶关系

若集合S上定义了一个偏序,则S称为偏序集(poset);若将其上的偏序关系改为其逆关系,得到的新偏序集S'称为S的序对偶。

虽然通常术语“有序集”用来称呼全序集,但当上下文中不涉及其他序关系时,“有序集”也可用于称呼偏序集。

偏序关系例子

下面是一些主要的例子:

自然数的集合配备了它的自然次序(小于等于关系)。这个偏序是全序。

整数的集合配备了它的自然次序。这个偏序是全序。

自然数的集合的有限子集{1, 2, ...,n}。这个偏序是全序。

自然数的集合配备了整除关系。

偏序关系

给定集合的子集的集合(它的幂集)按包含排序。

向量空间的子空间的集合按包含来排序。

一般的说偏序集合的两个元素xy可以处于四个相互排斥的关联中任何一个:要么x<y,要么x=y,要么x>y,要么xy是“不可比较”的(三个都不是)。全序集合是用规则排除第四种可能的集合:所有元素对都是可比较的,并且声称三分法成立。自然数、整数、有理数和实数都关于它们代数(有符号)大小是全序的,而复数不是。这不是说复数不能全序排序;比如我们可以按词典次序排序它们,通过x+iy<u+iv当且仅当x<u或(x=uy<v),但是这种排序没有合理的大小意义因为它使得1大于100i。按绝对大小排序它们产生在其中所有对都是可比较的预序,但这不是偏序因为1和i有相同的绝对大小但却不相等,违反了反对称性。

偏序关系偏序的线性扩展

全序T是偏序P的线性扩展,只要xyP中成立则xyT中也成立。在计算机科学中,找到偏序的线性扩展的算法叫做拓扑排序。

温馨提示:
本文【偏序关系】由作者 爱百科 转载提供。 该文观点仅代表作者本人, 自学教育网 信息发布平台,仅提供信息存储空间服务, 若存在侵权问题,请及时联系管理员或作者进行删除。
(c)2008-2025 自学教育网 All Rights Reserved 汕头市灵创科技有限公司
粤ICP备2024240640号-6