擬序關係

擬序關係亦稱偽序關係或前序關係，是一種重要的二元關係，指集合A上的自反的與傳遞的二元關係R，A稱為擬序集。擬序關係有下列特點： 1. 對角集EA⊆R，且當〈a，b〉∈R，〈b，c〉∈R時，〈a,c〉∈R；2. R 的矩陣(rij)λ主對角線上的元素全是1，且當rij=rjk=1時,rik=1；3. R的箭頭圖上，每個元素有一個從自己出發又指向自身的箭頭，且在有a到b的箭頭，b到c的箭頭時，就有a到c的箭頭。擬序關係的逆關係一定是擬序的，反對稱的擬序關係是偏序關係，但擬序關係可以不是偏序關係。

定義

擬序關係是一種次序關係，比偏序關係的限制更嚴格一些。它是一種滿足反自反、反對稱與傳遞的關係。

擬序關係

擬序關係

設R是非空集合A上的關係，若R具有反自反性、傳遞性，則稱R是A上的 擬序關係(Quasi-ordering relation)，記該關係R為<。若，可記作，讀作“a小於b”。

注意：這裡的“小於”不是指普通數的大小關係的<，而是指擬序的“小於”。x“小於”y的含義是：依照這個順序，x排在y的前邊。

例題解析

例1 A={1，2，3}，R是A上的整除關係，R={<1，1>，<1，2>，<1，3>，<2，2>，<3，3>}，顯然R是偏序關係，A中元素有以下關係：1<2，1<3；1=1，2=2，3=3；2和3不可比。

例2實數集上的小於關係R是擬序關係。

證明：對任何一個實數x都不存在x<x，所以R是反自反的。

對於任何實數x，y，如果x<y，則必然不存在y<x，所以R是反對稱的。

對於任何實數x，y，z，如果x<y，y<z，則必然x<z，所以R是傳遞的。

性質定理

定理1設尺是集合A上的擬序關係，則R是反對稱性。

擬序關係

擬序關係

擬序關係

證明: 設R不是反對稱的，則至少存在兩個元素，且因為R是傳遞的，所以這與R是反自反的特性相矛盾，因此R具有反對稱性。

從該定理，很容易得出以下結論：

(1) 由反自反性和傳遞性可以推出反對稱性。

(2) 擬序關係具有反自反性、反對稱性和傳遞性。

(3) 擬序和偏序的區別在於反自反性和自反性上，它們均具有反對稱性和傳遞性。

擬序關係

擬序關係

(4) 若R是偏序關係，則是擬序關係；若R是擬序關係，則是偏序關係。即偏序是擬序的擴充，擬序是偏序的縮減。

(5) 擬序集合與偏序集合具有相同的哈斯圖。