偏序关系
来自维基百科,自由的百科全书
来自维基百科,自由的百科全书
偏序集合(英語:Partially ordered set,简写Poset)是数学中,特别是序理论中,指配备了偏序关系的集合。 这个理论将对集合的元素进行排序、顺序或排列等直觉概念抽象化。这种排序不必是全部的,就是说不需要保证此集合内的所有对象的相互可比较性。偏序空間是具有閉偏序的拓撲空間。
给定集合S,“≤”是S上的二元关系,若“≤”满足:
则称“≤”是S上的非严格偏序或自反偏序。
给定集合S,“<”是S上的二元关系,若“<”满足:
则称“<”是S上的严格偏序或反自反偏序。
容易证明以下结论:
由上述可知,只要定义了「≤」、「<」、「≥」、「>」中的任何一个,其余三个关系的定义可以自然诱导而出,这四种关系实际上可以看成一体。故此在不严格区分的情况下,只需定义其一即可(通常是「≤」),称之为集合S上的偏序关系。(“偏序关系”通常被用来称呼非严格偏序关系。)
若集合S上定义了一个偏序,则S称为偏序集(poset);若将其上的偏序关系改为其逆关系,得到的新偏序集S'称为S的序对偶。
虽然通常术语“有序集”用来称呼全序集,但当上下文中不涉及其他序关系时,“有序集”也可用于称呼偏序集。
下面是一些主要的例子:
一般的说偏序集合的两个元素x和y可以处于四个相互排斥的关联中任何一个:要么x < y,要么x = y,要么x > y,要么x和y是“不可比较”的(三个都不是)。全序集合是用规则排除第四种可能的集合:所有元素对都是可比较的,并且声称三分法成立。自然数、整数、有理数和实数都关于它们代数(有符号)大小是全序的,而复数不是。这不是说复数不能全序排序;比如我们可以按词典次序排序它们,通过x+iy < u+iv当且仅当x < u或(x = u且y < v),但是这种排序没有合理的大小意义因为它使得1大于100i。按绝对大小排序它们产生在其中所有对都是可比较的预序,但这不是偏序因为1和i有相同的绝对大小但却不相等,违反了反对称性。
全序T是偏序P的线性扩展,只要x ≤ y在P中成立则x ≤ y在T中也成立。在计算机科学中,找到偏序的线性扩展的算法叫做拓扑排序。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.