For faster navigation, this Iframe is preloading the Wikiwand page for 偏序关系.

偏序关系

维基百科,自由的百科全书

本条目存在以下问题,请协助改善本条目或在讨论页针对议题发表看法。 此条目需要精通或熟悉数学的编者参与及协助编辑。 (2020年8月8日)请邀请适合的人士改善本条目。更多的细节与详情请参见讨论页。另见其他需要数学专家关注的页面。 此条目已列出参考文献,但因为没有文内引注而使来源仍然不明。 (2020年8月8日)请加上合适的文内引注来改善这篇条目。 此条目需要补充更多来源。 (2020年8月8日)请协助补充多方面可靠来源改善这篇条目无法查证的内容可能会因为异议提出而移除。致使用者:请搜索一下条目的标题(来源搜索:"偏序关系"网页新闻书籍学术图像),以检查网络上是否存在该主题的更多可靠来源(判定指引)。 此条目的引用需要进行清理,使其符合格式。 (2020年8月8日)参考文献应符合正确的引用脚注外部链接格式。
{x,y,z}的子集的集合按包含排序的哈斯图。
{x,y,z}的子集的集合按包含排序的哈斯图

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

定义

非严格偏序,自反偏序

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

  1. 自反性:∀a∈S,有a≤a;
  2. 反对称性:∀a,b∈S,a≤b且b≤a,则a=b;
  3. 传递性:∀a,b,c∈S,a≤b且b≤c,则a≤c;

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

严格偏序,反自反偏序

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

  1. 反自反性:∀a∈S,有a≮a;
  2. 反对称性:∀a,b∈S,a<b ⇒ b≮a;
  3. 传递性:∀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中也成立。在计算机科学中,找到偏序的线性扩展的算法叫做拓扑排序

参见

引用

  • J. V. Deshpande, On Continuity of a Partial Order, Proceedings of the American Mathematical Society, Vol. 19, No. 2, 1968, pp. 383-386
{{bottomLinkPreText}} {{bottomLinkText}}
偏序关系
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.