偏序集合(英語:Partially ordered set,簡寫Poset)是數學中,特別是序理論中,指配備了偏序關係的集合。
這個理論將對集合的元素進行排序、順序或排列等直覺概念抽象化。這種排序不必是全部的,就是說不需要保證此集合內的所有物件的相互可比較性。偏序空間是具有閉偏序的拓撲空間。
{x,y,z}的子集的集合按包含排序的哈斯圖。
給定集合 , 設「 」是 上的二元關係,若「 」滿足:
- 自反性:對所有 ,有 ;
- 反對稱性:對所有 ,若 且 ,則 ;
- 遞移性:對所有 ,若 且 ,則 ;
則稱「 」是 上的非嚴格偏序或自反偏序。
給定集合 ,設「 」是 上的二元關係,若「 」滿足:
- 反自反性:對所有 ,有 ;
- 非對稱性:對所有 ,若 ,則 ;
- 遞移性:對所有 ,若 且 ,則 ;
則稱「 」是 上的嚴格偏序或反自反偏序。
嚴格偏序與有向無環圖(DAG)有直接的對應關係。一個集合上的嚴格偏序的關係圖就是一個有向無環圖。其遞移閉包是它自己。
容易證明以下結論:
- 給定集合 上的一個(非嚴格,自反)偏序「 」,則可自然地誘導出 上的一個(嚴格,反自反)偏序「 」,只需如此定義:
- 若且唯若 且 。
- 給定集合 上的一個(嚴格,反自反)偏序「 」,則可自然地誘導出 上的一個(非嚴格,自反)偏序「 」,只需如此定義:
- 若且唯若 或 。
- 給定集合 上的一個(非嚴格,自反)偏序「 」,其逆關係「 」也是 上的一個(非嚴格,自反)偏序;
- 給定集合 上的一個(嚴格,反自反)偏序「 」,其逆關係「 」也是 上的一個(嚴格,反自反)偏序;
由上述可知,只要定義了「 」、「 」、「 」、「 」中的任何一個,其餘三個關係的定義可以自然誘導而出,這四種關係實際上可以看成一體。故此在不嚴格區分的情況下,只需定義其一即可(通常是「 」),稱之為集合 上的偏序關係。(「偏序關係」通常被用來稱呼非嚴格偏序關係。)
- (非嚴格,自反)偏序和(嚴格,反自反)偏序之間的對應關係不同於在(非嚴格)弱序和嚴格弱序直接的對應(逆關係的補集)。只有對於全序這些對應才是相同的。
若集合 上定義了一個偏序,則 稱為偏序集(poset);若將其上的偏序關係改為其逆關係,得到的新偏序集 稱為 的序對偶。
雖然通常術語「有序集」用來稱呼全序集,但當上下文中不涉及其他序關係時,「有序集」也可用於稱呼偏序集。
下面是一些主要的例子:
- 自然數的集合的有限子集{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有相同的絕對大小但卻不相等,違反了反對稱性。
全序T是偏序P的線性擴展,只要x ≤ y在P中成立則x ≤ y在T中也成立。在計算機科學中,找到偏序的線性擴展的算法叫做拓撲排序。
- J. V. Deshpande, On Continuity of a Partial Order, Proceedings of the American Mathematical Society, Vol. 19, No. 2, 1968, pp. 383-386