偏序關係

偏序集合（英語：Partiallyordered set，簡寫poset）是數學中，特別是序理論中，指配備了部分排序關係的集合。 這個理論將排序、順序或排列這個集合的元素的直覺概念抽象化。這種排序不必然需要是全部的，就是說不必要保證此集合內的所有對象的相互可比較性。部分排序集合定義了部分排拓撲。

基本介紹

• 中文名：偏序關係
• 外文名：partial ordering relation
• 定義：R是集合A上的一個二元關係
• 解釋:：整除關係
• 概述：不要求每個元素之間都能比較大小
• 學科：數理科學

形式定義

設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上的二元關係，若“≤”滿足：

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}。這個偏序是全序。
• 自然數的集合配備了整除關係。
• 給定集合的子集的集合（它的冪集）按包含排序。
• 向量空間的子空間的集合按包含來排序。

一般的說偏序集合的兩個元素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中也成立。在計算機科學中，找到偏序的線性擴展的算法叫做拓撲排序。