非対称関係

数学において、非対称関係とは、集合上の2項関係 であり、すべての がと関係している場合、 はと関係しない関係である^[1]${\displaystyle R}$ ${\displaystyle X}$${\displaystyle a,b\in X,}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$${\displaystyle a.}$

上の二項関係はの任意の部分集合である。 と書くと、 はの省略形であることを意味する。この式は「 はによってと関連している」 と読むことができる。${\displaystyle X}$${\displaystyle R}$${\displaystyle X\times X.}$${\displaystyle a,b\in X,}$${\displaystyle aRb}$${\displaystyle (a,b)\in R,}$${\displaystyle aRb}$${\displaystyle (a,b)\in R.}$${\displaystyle aRb}$${\displaystyle a}$${\displaystyle b}$${\displaystyle R.}$

二項関係は、すべてに対してが真であればが偽である場合に非対称と呼ばれます。つまり、であれば、これは一階述語論理の表記法で次のように 記述できます。 論理的に同等の 定義は次のとおりです。${\displaystyle R}$${\displaystyle a,b\in X,}$${\displaystyle aRb}$${\displaystyle bRa}$${\displaystyle (a,b)\in R}$${\displaystyle (b,a)\not \in R.}$$${\displaystyle \forall a,b\in X:aRb\implies \lnot (bRa).}$$

および の少なくとも 1 つが偽である場合、${\displaystyle a,b\in X,}$${\displaystyle aRb}$${\displaystyle bRa}$

これは一階述語論理では次のように書くことができる。 関係が非対称であるためには、それが反対称かつ非反射的である必要がある。^[2]したがって、これは定義としてもとらえることができる。 $${\displaystyle \forall a,b\in X:\lnot (aRb\wedge bRa).}$$

非対称関係の例としては、実数間の「より小さい」関係が挙げられます。が である場合、 は必ずより小さくありません。より一般的には、任意の厳密な半順序は非対称関係です。すべての非対称関係が厳密な半順序であるわけではありません。非対称の非推移的、さらには反推移的な関係の例としては、じゃんけん関係が挙げられます。がに勝る場合、は に勝たず、 がに勝ってに勝つ場合、 は に勝たず${\displaystyle \,<\,}$${\displaystyle x<y}$${\displaystyle y}$${\displaystyle x.}$${\displaystyle X}$${\displaystyle Y,}$${\displaystyle Y}$${\displaystyle X;}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle Z,}$${\displaystyle X}$${\displaystyle Z.}$

非対称関係の制限と逆も非対称です。たとえば、実数から整数への制限は依然として非対称であり、の逆または双対も非対称です。 ${\displaystyle \,<\,}$${\displaystyle \,>\,}$${\displaystyle \,<\,}$

非対称関係は連結特性を持つ必要はありません。たとえば、厳密な部分集合関係は非対称であり、集合 と のどちらも他方の厳密な部分集合ではありません。関係が連結となるのは、その補集合が非対称である場合のみです。 ${\displaystyle \,\subsetneq \,}$${\displaystyle \{1,2\}}$${\displaystyle \{3,4\}}$

非例として、「以下」の関係があります。これは非対称ではありません。たとえば、 を逆にするととなり、両方とも真となるからです。以下関係は、対称でも非対称でもない関係の例であり、非対称は「非対称」と同じではないことを示しています。 ${\displaystyle \leq }$${\displaystyle x\leq x}$${\displaystyle x\leq x}$

空の関係は、（空に）対称かつ非対称 である唯一の関係です。

関係が非対称であるためには、以下の条件を満たす必要がある: ^[3]${\displaystyle R}$

• ${\displaystyle R}$非反射的かつ反対称的である（これも必要である）
• ${\displaystyle R}$は非反射的かつ推移的である。推移関係が非対称となるのは、それが非反射的である場合に限ります。 ^[4]と推移性は矛盾する非反射性を与える。このような関係は厳密な半順序である。${\displaystyle aRb}$${\displaystyle bRa,}$${\displaystyle aRa,}$
• ${\displaystyle R}$は非反射的であり、半順序性1を満たす（互いに比較できない2点線形順序は存在しない）
• ${\displaystyle R}$非推移的かつ非対称的である
• ${\displaystyle R}$反推移的であり推移的である
• ${\displaystyle R}$は反推移的であり、半順序性1を満たす。

• タルスキの実数の公理化- この一部は、実数に対して非対称であるという要件です。${\displaystyle \,<\,}$