預序關係

b)的預序為偏序。 說明作為特例,空集上的空關係為一預序。 反過來說,每個預序都可理解為一個有向圖上的可到達關係。

定義

考慮集合 P 及其上的二元關係\lesssim。若具有自反性和傳遞性,則稱為預序。具體來說,對 P 的任意元素 a,b 和 c,下列性質成立:
自反性:a\lesssima
傳遞性:若a\lesssimb且b\lesssimc,則a\lesssimc
帶預序的集合稱為預序集合(preordered set,或者proset)。
同時滿足反對稱性(若 a\lesssimb 且 b\lesssima,則 a = b)的預序為偏序
另一方面,如果一個預序滿足對稱性(若a\lesssimb,則b\lesssima),則為等價關係

說明

作為特例,空集上的空關係為一預序。空集加上空關係構成一預序集。

導出偏序

將預序集的等價元素等同起來,可得到由該預序集所導出的偏序集。具體過程如下:定義預序集 X 上的等價關係\sim,使得 a\simb 若且唯若 a\lesssimb 且 b\lesssima。定義所得商集X/\sim(所有\sim等價類構成的集合)上的序關係\leq,使得[x]\leq[y] 若且唯若 x\lesssimy。由\sim的構造可知,\leq的定義與所選等價類的代表元素無關,故上述定義明確。易證該關係為一偏序。

舉例

  • 有向圖(可以包括圈)上的可到達關係給出了一個預序≤,對於有向圖中的任意兩點x, y,x≤y若且唯若存在一條由x到y的路徑。反過來說,每個預序都可理解為一個有向圖上的可到達關係。(比如,如果x≤y的話,就規定這個圖包含由x到y的有向邊。)不過,這種對應關係不是唯一的。不同的圖也可以給出相同的可到達關係。而同樣地,有向無環圖上的可到達關係也誘導出一個偏序。
  • 拓撲中網的收斂定義使用預序比使用偏序可避免重要特徵的丟失。
  • 可數全序間的嵌入(embedding)關係。
  • 圖論中的graph-minor關係。

全預序的例子:
  • 一般模型中的偏好概念。

相關詞條

相關搜尋

熱門詞條

聯絡我們