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

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

Στην θεωρία συνόλων, μία συμμετρική σχέση είναι μία σχέση, στην οποία αν το $x$ σχετίζεται με το $y$ τότε και το $y$ σχετίζεται με το $x$. Ένα παράδειγμα τέτοιας σχέσης είναι αυτή των «συγχωριανών», αν ο Γιώργος είναι συγχωριανός της Άννας, τότε και η Άννα είναι συγχωριανή του Γιώργου.

Πιο αυστηρά, έστω μία σχέση $R$ στο σύνολο $S$, δηλαδή $R\subseteq S\times S$, τότε για κάθε $x,y\in S$ έχουμε ότι

$xRy\Leftrightarrow yRx$.

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

Οι παρακάτω σχέσεις είναι συμμετρικές:

• Οι σχέσεις "είναι συμφοιτητής/τρια", "είναι συναπόφοιτος/η", "είναι συνάδελφος", "είναι αδελφός/ή".
• Η σχέση "είναι παντρεμμένος/η".
• Η σχέση της ισότητας είναι συμμετρική, καθώς αν $x=y$ τότε και $y=x$.
• Η σχέση $R_{n}$ στους ακεραίους, ώστε $xR_{n}y\Leftrightarrow x\equiv y{\pmod {n}}$, δηλαδή η σχέση μεταξύ υσοϋπόλοιπων αριθμών (για κάθε $n\geq 1$).
• Η σχέση

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

της οποίας οι αναπαραστάσεις δίνονται και στην πρώτη εικόνα.

Αναπαράσταση μίας μη συμμετρικής σχέσης σαν γράφο και σαν πίνακα. Τα κόκκινα στοιχεία είναι αυτά που χαλάνε την συμμετρία.

Οι παρακάτω σχέσεις δεν είναι συμμετρικές:

• Στο σύνολο $S$ των μαθητών μίας τάξης, η σχέση "είναι ψηλότερος/η" δεν είναι συμμετρική, καθώς αν η Άννα είναι ψηλότερη από τον Γιώργο, τότε δεν μπορεί να είναι και ο Γιώργος ψηλότερος από την Άννα.
• Στο σύνολο $S$ των αθρώπων της γης, η σχέση "είναι γονιός", δεν είναι συμμετρική, καθώς αν η Άννα είναι η μητέρα του Γιώργου, τότε δεν μπορεί και ο Γιώργος να είναι ο πατέρας της Άννας.
• Η σχέση

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

δεν είναι συμμετρική

Ιδιότητες

• Μία σχέση είναι συμμετρική αν και μόνο αν η σχέση είναι ίση με την αντίστροφή της.

Απόδειξη  

Έστω $R$ μία σχέση στο σύνολο $S$, και $R^{T}$ η αντίστροφή της. Από τον ορισμό της αντίστροφης σχέσης, έχουμε ότι

$\forall x,y\in S.xR^{T}y\Leftrightarrow yRx$.

Η σχέση $R$ είναι συμμετρική ανν

$\forall x,y\in S.xRy\Leftrightarrow yRx$,

ή ισοδύναμα

$\forall x,y\in S.yR^{T}x\Leftrightarrow xRy\Leftrightarrow yRx$,

δηλαδή

$\forall x,y\in S.yR^{T}x\Leftrightarrow yRx$.

• Έστω ο δυαδικός πίνακας $M(R)$ που αντιστοιχεί στην σχέση $R$. Τότε, ο πίνακας είναι συμμετρικός αν και μόνο αν η συνάρτηση είναι συμμετρική.

Απόδειξη  

Ο πίνακας $M(R)$ είναι συμμετρικός ανν $M(R)=M(R)^{T}$, δηλαδή είναι ίσος με τον ανάστροφό του. Ο ανάστροφος πίνακας αντιστοιχή στον πίνακα της αντίστροφης σχέσης $R^{T}$, δηλαδή $M(R^{T})=M(R)^{T}$. Επομένως, το συμπέρασμα προκύπτει από την προηγούμενη ιδιότητα.

• Έστω ο κατευθυνόμενος γράφος $G(R)$ που αντιστοιχεί στην σχέση $R$. Τότε, αν ο κόμβος $y$ είναι προσβάσιμος από τον $x$, τότε και ο $y$ είναι προσβάσιμος από τον $x$.

Απόδειξη  

Για να είναι ο κόμβος $y$ προσβάσιμος από τον κόμβο $x$, σημαίνει ότι υπάρχει μονοπάτι $P=(p_{1},\ldots ,p_{\ell })$ μήκους $\ell$ με $p_{1}=x$ και $p_{\ell }=y$. Επισης για κάθε ακμή $(p_{i},p_{i+1})$ στο μονοπάτι ξέρουμε ότι $p_{i}Rp_{i+1}$. Επομένως, αφού η σχέση είναι συμμετρική ισχύει επίσης ότι $p_{i+1}Rp_{i}$ και $(p_{i+1},p_{i})$. Άρα έχουμε ότι $P'=(p_{\ell },\ldots ,p_{1})$ είναι επίσης μονοπάτι στον γράφο και συνδέει το $y$ με το $x$. Συνεπώς, και ο $y$ είναι προσβάσιμος από τον $x$.

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

Το πλήθος των συμμετρικών σχέσεων σε ένα πεπερασμένο σύνολο $X$ αποτελούμενο από $n$ στοιχεία είναι $2^{n\cdot (n+1)/2}$. Τα πλήθη δίνονται από την ακολουθια:

$1,2,8,64,1024,\ldots \qquad$(ακολουθία A006125 στην OEIS)

Απόδειξη  

Τα στοιχεία του πίνακα με μπεζ χρώμα αρκούν για να καθορίσουν πλήρως μία συμμετρική σχέση.

Αυτό προκύπτει ως εξής. Έστω $M(R)$ ο πίνακας της σχέσης $R$, τότε αν προσδιορίσουμε τα στοιχεία του πίνακα που βρίσκονται στην κύρια διαγώνιό του ή πάνω από αυτή, τότε αυτομάτως προσδιόριζουμε τα στοιχεία ολόκληρου του πίνακα. Στην πρώτη γραμμή υπάρχουν $n$ τέτοια στοιχεία, στην δεύτερη γραμμή υπάρχουν $n-1$, κ.ο.κ. Συνολικά υπάρχουν

$\sum _{i=1}^{n}i={\frac {n\cdot (n+1)}{2}}$ στοιχεία.

Κάθε τέτοιο στοιχείο παίρνει δύο τιμές (είτε $0$ είτε $1$) και μπορεί να οριστεί ανεξάρτητα από τα υπόλοιπα. Από την βασική αρχή απαρίθμησης προκύπτει ότι συνολικά υπάρχουν

$\underbrace {2\cdot \ldots \cdot 2} _{n\cdot (n+1)/2}=2^{n\cdot (n+1)/2}$

δυνατές συμμετρικές σχέσεις.

Σχετικές έννοιες

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

Μία αντισυμμετρική σχέση είναι μία σχέση $R$ για την οποία για κάθε $x\neq y$ αν $(x,y)\in R$, τότε $(y,x)\notin R$.

Δείτε επίσης

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