基本介紹
- 中文名:擬序
- 外文名:quasi-order
- 所屬領域:數學(組合學)
- 屬性:一種特殊的二元關係
- 特點:反自反性、可傳遞性
定義,舉例分析,相關定理,定理1,定理2,
定義
設R是集合A上的一個關係,如果R是反自反的和傳遞的,則稱R是A上的一個擬序關係。一般用符號“”表示擬序關係。若可記作,讀作“a小於b”。
舉例分析
例1 實數集上的小於關係R是擬序關係。
證明:對任何一個實數x都不存在x<x,所以R是反自反的。
對於任何實數x,y,如果x<y,則必然不存在y<x,所以R是反對稱的。
對於任何實數x,y,z,如果x<y,y<z,則必然x<z,所以R是傳遞的。
例2 整數集Z上的“<”(小於關係)是擬序關係。
例3 證明集合A的冪集P(A)上的關係“”是擬序關係。
證明: (1)對,有X不真包含X,所以具有反自反性。
(2)設X,Y,Z∈P(A),若,則有,因此具有傳遞性。
故是P(A)上的擬序關係。
相關定理
對於擬序有下面的定理。
定理1
集合X上的關係R是擬序的,則其必是反對稱的。
證明:用反證法。設R不是反對稱的,則必至少存在兩個元素a,b∈X,它們有<a,b>∈R且<b,a>∈R,由於R是擬序的,故它是傳遞的,由此必有<a,a>∈R,但R又是反自反的,故矛盾。由此定理得證。
由擬序關係、偏序關係以及閉包的定義可知,擬序關係的自反閉包是一個偏序關係,由此可得下面的定理。
定理2
設R是集合上的關係,則:
(1) 如果R是一個擬序關係,則是一個偏序關係;
(2) 如果R是一個偏序關係,則是一個擬序關係。
其中。根據定義很容易得到定理的證明。