跳至內容

非對稱關係

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

數學中,非對稱關係(英語:Asymmetric relation)是二元關係的一種。若集合 上的二元關係 為非對稱關係,則對於所有 。換句話說,如果 存在關係,則 不存在關係[1]

正式定義

[編輯]

一個定義於 上的二元關係 的任何子集。給定 ,我們將 簡寫為 ,讀作「 存在關係 is related to by )」。

如果對於所有 ,若 ,則 (也就是 ),則我們稱 非對稱的。以一階邏輯的形式可以寫成:

一個邏輯等價的定義如下:對於所有 中至少有一為假。以一階邏輯的形式可以寫成:

非對稱關係的一個例子是定義於實數上的「小於關係」,亦即 。由於當 小於 時, 一定不小於 ,因此 是非對稱的。另一方面,「小於等於關係」則不是非對稱的,因為當 時, 會同時成立,不符合非對稱關係的定義。

非對稱關係不代表對稱關係的相反,上述的「小於等於關係」既不是非對稱關係,也不是對稱關係;而「空關係()」是唯一同時是非對稱關係,也是對稱關係的關係。

非對稱關係(Asymmetric)與反對稱關係(Antisymmetric)的差異在於:反對稱關係容許自反性 可以屬於 ,而非對稱關係不允許。如上述的「小於等於關係」即是反對稱關係的一例。

特性

[編輯]
  • 一個關係為非對稱的,若且唯若該關係為反對稱非自反[2]
  • 對於一個非對稱關係 ,對其施加限制或求其逆關係後,該關係同樣是非對稱的。例如,由「」定義的關係是非對稱關係(若 ),若將集合從實數限縮至整數,該關係同樣是非對稱的;求該關係的逆關係「」,該逆關係同樣是非對稱的。
  • 一個遞移關係為非對稱的,若且唯若該關係為非自反[3]:若存在 使得該關係不是非對稱,則由遞移性可得到 ,使得該關係同樣不是非自反關係。
  • 一個關係為遞移性的且非對稱的,若且唯若該關係為嚴格偏序的。
  • 一個非對稱關係不一定是全關係。例如,由「嚴格子集」定義的關係是非對稱關係(若 ),但不是全關係()。

參見

[編輯]

參考資料

[編輯]
  1. ^ Gries, David; Schneider, Fred B., A Logical Approach to Discrete Math, Springer-Verlag: 273, 1993 .
  2. ^ Nievergelt, Yves, Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography, Springer-Verlag: 158, 2002 .
  3. ^ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. Transitive Closures of Binary Relations I (PDF). Prague: School of Mathematics - Physics Charles University. 2007: 1 [2013-08-20]. (原始內容 (PDF)存檔於2013-11-02).  Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".