定義
設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+ i y < u+ i v 若且唯若 x < u 或 ( x = u 且 y < v),但是這種排序沒有合理的大小意義因為它使得 1 大於 100 i。按絕對大小排序它們產生在其中所有對都是可比較的預序,但這不是偏序因為 1 和 i 有相同的絕對大小但卻不相等,違反了反對稱性。
Dilworth 定理
對於一個偏序集,其最少鏈劃分數等於其最長反鏈的長度。