跳至內容

預序關係

維基百科,自由的百科全書

預序關係(簡稱預序,又稱先序preorder)、在數學中,是一類接近於偏序關係的二元關係,但僅滿足自反性傳遞性而不滿足反對稱性。偏序的大多數理論均可擴展到預序。

定義

[編輯]

考慮集合 P 及其上的二元關係 。若 具有自反性傳遞性,則稱 預序。具體來說,對任意 P 的元素 abc,下列性質成立:

a a (自反性)
a bb c,則 a c (傳遞性)

帶預序的集合稱為預序集合。同時滿足反對稱性(若 a bb a,則 a = b)的預序為偏序

說明

[編輯]

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

導出偏序

[編輯]

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

舉例

[編輯]

參見

[編輯]

參考文獻

[編輯]
  • Schröder, Bernd S. W., Ordered Sets: An Introduction, Boston: Birkhäuser, 2002, ISBN 0-8176-4128-9