Asymmetrische relatie

In de wiskunde is een asymmetrische relatie een tweeplaatsige relatie $R$ van verzameling $X$ waar voor elke $a,b\in X$ geldt dat als $(a,b)\in R$ dan $(b,a)\notin R$.

Formele definitie

Voorafgaand

Een tweeplaatsige relatie op $X$ is elke deelverzameling $R$ van $X\times X$. Als gegeven is dat $a,b\in X$, schrijft men $aRb$ dan en slechts dan als $(a,b)\in R$. De uitdrukking $aRb$ wordt gelezen als "$a$ is gerelateerd aan $b$ via $R$."

Definitie

Een tweeplaatsige relatie $R$ is asymmetrisch wanneer voor alle $a,b\in X$ geldt: als $aRb$ waar is, dan is $bRa$ onwaar. Dat wil zeggen, als $(a,b)\in R$, dan $(b,a)\notin R$.

Dit kan in de taal van de eerste-orde-predicatenlogica geschreven worden als $$\mathrm{\forall }a,b\in X:aRb⟹\mathrm{\neg }(bRa).$$Een logisch equivalente definitie is:

voor alle $a,b\in X,$ is óf $aRb$ onwaar, óf $bRa$ onwaar, óf ze zijn allebei onwaar.

In de taal van de eerste-orde-predicatenlogica kan dat als volgt worden geschreven:$$\mathrm{\forall }a,b\in X:\mathrm{\neg }(aRb\wedge bRa).$$Een relatie is asymmetrisch dan en slechts dan als zij zowel antisymmetrisch als irreflexief is.

Voorbeelden

Een voorbeeld van een asymmetrische relatie is de "is kleiner dan" relatie $<$ tussen reële getallen: als $x<y$ dan is $y$ uitsluitend groter dan $x$. Elke strikte partiële orde is een asymmetrische relatie, maar niet elke asymmetrische relatie is een strikte partiële orde. Een voorbeeld van een asymmetrische, intransitieve relatie relatie is de steen-papier-schaar relatie. Stel, $X$ verslaat $Y,$ dan verslaat $Y$ niet $X;$ en stel, $X$ verslaat $Y$ en $Y$ verslaat $Z,$ dan verslaat $X$ niet $Z.$

Eigenschappen

Het is voldoende als er aan één van de volgende voorwaarden gedaan wordt, wil relatie $R$ asymmetrisch zijn.

• $R$ is irreflexief en antisymmetrisch (dit is ook nodig)
• $R$ is irreflexief en transitief. Een transitieve relatie is asymmetrisch dan en slechts dan als zij irreflexief is: als $aRb$ en $bRa,$ volgt uit transitiviteit $aRa,$ wat in tegenspraak is met irreflexiviteit. Deze relatie is een strikte partiele orde.
• $R$ is antitransitief en antisymmetrisch
• $R$ is antitransitief en transitief