Αντισυμμετρική σχέση

Αρχείο:Antisymmetric relation graph and matrix.svg

Παράδειγμα αντισυμμετρικής σχέσης και η αναπαράστασή της με γράφο και με πίνακα.

Στην θεωρία συνόλων, μία αντισυμμετρική σχέση είναι μία σχέση $R$ στο σύνολο $S$, για την οποία ισχύει ότι

για κάθε $a,b\in S$, αν $aRb$ και $bRa$ τότε $a=b$,

ή ισοδύναμα

για κάθε $a,b\in S$, αν $aRb$ και $a\ne b$, τότε $aRb$.Πρότυπο:Rp

Το πιο σύνηθες παράδειγμα τέτοιας σχέσης είναι η διάταξη $\le$, για παράδειγμα στους φυσικούς αριθμούς για την οποία δεν μπορούμε να έχουμε ότι $a\le b$ και $b\le a$ εκτός αν $a=b$.

Παραδείγματα

Οι εξής σχέσεις είναι αντισυμμετρικές:

• Η διάταξη $<$των φυσικών αριθμών (και των πραγματικών αριθμών).
• Η διάταξη $\le$των φυσικών αριθμών (και των πραγματικών αριθμών).
• Η σχέση του «είναι απόγονος του/της» μεταξύ ανθρώπων είναι αντισυμμετρική, καθώς δεν μπορούμε να έχουμε ότι ο Γιώργος είναι απόγονος της Άννας, και ότι η Άννα είναι απόγονος του Γιώργου.
• Αντίστοιχα και με τις σχέσεις «είναι γονιός του/της», «είναι προϋστάμενος/η του/της», κ.ο.κ.
• Η σχέση «διαιρεί» στους θετικούς αριθμούς είναι αντισυμμετρική καθώς για $a\ne b$ δεν μπορεί να έχουμε και $a\mid b$ αλλά και $b\mid a$.
• Η σχέση

$R=\{(1,1),(2,1),(2,3),(3,4),(4,4),(4,5),(5,2)\}$,

είναι αντισυμμετρική (δείτε το πρώτο σχήμα).

• Η ταυτοτική σχέση είναι αντισυμμετρική.

Αρχείο:Non antisymmetric relation graph and matrix.svg

Παράδειγμα μη αντισυμμετρικής σχέσης και με κόκκινο χρώμα οι σχέσεις που δεν ικανοποιούν την συνθήκη.

Οι εξής σχέσεις δεν είναι αντισυμμετρικές:

• Η σχέση του «είναι συγχωριανός/ή του», «είναι συμφοιτητής/τρια του/της».
• Η σχέση

$R=\{(1,1),(2,1),(3,2),(3,5),(4,4),(4,5),(5,3)\}$,

δεν είναι αντισυμμετρική (δείτε το δεύτερο σχήμα).

Πλήθος αντισυμμετρικών σχέσεων

Σε ένα πεπερασμένο σύνολο $S$ αποτελούμενο από $n$ στοιχεία, υπάρχουν το πολύ

$2^n\cdot 3^{n\cdot (n-1)/2}$

σχέσεις που είναι αντισυμμετρικές. Τα πλήθη δίνονται από την ακολουθία:

$1,2,12,216,11664,\dots$ Πρότυπο:Oeis.

Δείτε επίσης

• Συμμετρική σχέση
• Ανακλαστική σχέση
• Μεταβατική σχέση