偏序集合

偏序集合（英語：Partially ordered set，簡寫 poset）在數學中，特別是序理論中，是指配備了偏序關係的集合。這個關係形式化了排序、順序或排列這個集合的元素的直覺概念。這種排序不必然需要是全部的，就是說不需要但也可以保證在這個集合內的所有對象的相互可比較性。(在數學用法中，全序是一種偏序)。偏序集合定義了偏序拓撲。

基本介紹

• 中文名：偏序集合
• 外文名：Partially ordered set
• 簡寫： poset
• 數學中：配備了偏序關係的集合

定義

設R是非空集合A上的一個二元關係，若R滿足： 自反性、反對稱性、傳遞性，則稱R為A上的偏序關係。

以下為定義：

非嚴格偏序，自反偏序

給定集合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)有直接的對應關係。一個集合上的嚴格偏序的關係圖就是一個有向無環圖。其傳遞閉包是它自己。

下面是一些主要的例子:

自然數的集合配備了它的自然次序(小於等於關係)。這個偏序是全序。

整數的集合配備了它的自然次序。這個偏序是全序。

自然數的集合的有限子集 {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 有相同的絕對大小但卻不相等，違反了反對稱性。

Dilworth 定理

對於一個偏序集，其最少鏈劃分數等於其最長反鏈的長度。