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

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

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

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

ή ισοδύναμα

για κάθε $a,b\in S$, αν $aRb$ και $a\neq b$, τότε $a\not Rb$.

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

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

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

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

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

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

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

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

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

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

$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,\ldots$ (ακολουθία A083667 στην OEIS).

Απόδειξη  

Κάθε ένα από τα στοιχεία της διαγωνίου μπορεί να είναι είτε $0$ είτε $1$ ανεξάρτητα από τα υπόλοιπα στοιχεία του πίνακα.

Το στοιχεία στην θέση $M(R)_{ij}$ εξαρτάται μόνο από το στοιχείο $M(R)_{ji}$. Για αυτά, λόγω του περιορισμού της αντισυμμετρικής σχέσης, είτε πρέπει να είναι και τα δύο $0$, είτε το ένα $0$ και το άλλο $1$. Συνεπώς, υπάρχουν τρεις διαφορετικές περιπτώσεις.

Υπάρχουν $n$ στοιχεία στην διαγώνιο και $n\cdot (n-1)/2$ από τα ζεύγη σχέσεων $((i,j),(j,i))$. Από την βασική αρχή απαρίθμησης προκύπτει ότι συνολικά υπάρχουν

$\underbrace {2\cdot \ldots \cdot 2} _{n}\cdot \underbrace {3\cdot \ldots \cdot 3} _{n\cdot (n-1)}$,

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

Δείτε επίσης

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