通译百科：偏序

含光混世贵无名,孤高何用比云月

偏序

查询结果如下：

详细条目英文搜索 <<快速查询：

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

>形式定义

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

Ⅰ 自反性：对任意x∈A，有xRx；

Ⅱ 反对称性（即反对称关系）：对任意x,y∈A，若xRy，且yRx，则x=y；

Ⅲ 传递性：对任意x, y,z∈A，若xRy，且yRz，则xRz。

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

若然有x≼y，我们也说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}。这个偏序是全序。
自然数的集合配备了整除关系。
给定集合的子集的集合（它的幂集）按包含排序。
向量空间的子空间的集合按包含来排序。

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