複製鏈接
請複製以下鏈接發送給好友

偏序關係

鎖定
偏序集合(英語:Partial order set,簡寫poset)是數學中,特別是序理論中,指配備了部分排序關係的集合。 這個理論將排序、順序或排列這個集合的元素的直覺概念抽象化。這種排序不必然需要是全部的,就是説不必要保證此集合內的所有對象的相互可比較性。部分排序集合定義了部分排拓撲。
中文名
偏序關係
外文名
Partial ordering relation
定    義
R是集合A上的一個二元關係
解釋:
整除關係
概    述
不要求每個元素之間都能比較大小
學    科
數理科學

偏序關係形式定義

設R是集合A上的一個二元關係,若R滿足:
Ⅰ 自反性:對任意xA,有xRx
Ⅱ 反對稱性(即反對稱關係):對任意x,yA,若xRy,且yRx,則x=y
Ⅲ 傳遞性:對任意x, y,zA,若xRy,且yRz,則xRz [1] 
則稱R為A上的偏序關係,通常記作≼。注意這裏的≼不必是指一般意義上的“小於或等於”。
若然有xy,我們也説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)有直接的對應關係。一個集合上的嚴格偏序的關係圖就是一個有向無環圖。其傳遞閉包是它自己 [2] 

偏序關係偏序相關結論

容易證明以下結論:
  • 給定集合S上的一個(非嚴格,自反)偏序“≤”,則可自然地誘導出S上的一個(嚴格,反自反)偏序“<”,只需如此定義:a < b,如果 a ≤ b 且 a ≠ b。
  • 給定集合S上的一個(嚴格,反自反)偏序“<”,則可自然地誘導出S上的一個(非嚴格,自反)偏序“≤”,只需如此定義:a ≤ b,如果 a < b 或 a = b。
  • 給定集合S上的一個(非嚴格,自反)偏序“≤”,其逆關係“≥”也是S上的一個(非嚴格,自反)偏序;
  • 給定集合S上的一個(嚴格,反自反)偏序“<”,其逆關係“>”也是S上的一個(嚴格,反自反)偏序;
由上述可知,只要定義了“≤”、“<”、“≥”、“>”中的任何一個,其餘三個關係的定義可以自然誘導而出,這四種關係實際上可以看成一體。故此在不嚴格區分的情況下,只需定義其一即可(通常是“≤”),稱之為集合S上的偏序關係。(“偏序關係”通常被用來稱呼非嚴格偏序關係。)
  • (非嚴格,自反)偏序和(嚴格,反自反)偏序之間的對應關係不同於在(非嚴格)弱序和嚴格弱序直接的對應(逆關係補集)。只有對於全序這些對應才是相同的 [3] 

偏序關係偏序集與序對偶關係

若集合S上定義了一個偏序,則S稱為偏序集poset);若將其上的偏序關係改為其逆關係,得到的新偏序集S'稱為S的序對偶
雖然通常術語“有序集”用來稱呼全序集,但當上下文中不涉及其他序關係時,“有序集”也可用於稱呼偏序集 [1] 

偏序關係例子

下面是一些主要的例子:
  • 自然數的集合配備了它的自然次序(小於等於關係)。這個偏序是全序
  • 整數的集合配備了它的自然次序。這個偏序是全序。
  • 自然數的集合的有限子集{1, 2, ...,n}。這個偏序是全序。
  • 自然數的集合配備了整除關係。
  • 給定集合的子集的集合(它的冪集)按包含排序。
  • 向量空間的子空間的集合按包含來排序。
一般的説偏序集合的兩個元素xy可以處於四個相互排斥的關聯中任何一個:要麼x<y,要麼x=y,要麼x>y,要麼xy是“不可比較”的(三個都不是)。全序集合是用規則排除第四種可能的集合:所有元素對都是可比較的,並且聲稱三分法成立。自然數整數有理數和實數都關於它們代數(有符號)大小是全序的,而複數不是。這不是説複數不能全序排序;比如我們可以按詞典次序排序它們,通過x+iy<u+iv當且僅當x<u或(x=uy<v),但是這種排序沒有合理的大小意義因為它使得1大於100i。按絕對大小排序它們產生在其中所有對都是可比較的預序,但這不是偏序因為1和i有相同的絕對大小但卻不相等,違反了反對稱性 [4] 

偏序關係偏序的線性擴展

全序T是偏序P線性擴展,只要xyP中成立則xyT中也成立。在計算機科學中,找到偏序的線性擴展的算法叫做拓撲排序
參考資料
  • 1.    胡冠章, ‎王殿軍.應用近世代數:清華大學出版社,2006:22
  • 2.    毛徐新,徐羅山. S-超連續偏序集的幾個特徵[J]. 模糊系統與數學,2017,(05):147-151.
  • 3.    張濤,魏昕宇,楊爽. 屬性拓撲與屬性偏序雙向轉化[J]. 燕山大學學報,2017,(05):428-437.
  • 4.    J. V. Deshpande, On Continuity of a Partial Order, Proceedings of the American Mathematical Society, Vol. 19, No. 2, 1968, pp. 383-386