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

Στην θεωρία συνόλων, μία συμμετρική σχέση είναι μία σχέση, στην οποία αν το $x$ σχετίζεται με το $y$ τότε και το $y$ σχετίζεται με το $x$ .^[1]^:23^[2]^:5^[3]^:16 Ένα παράδειγμα τέτοιας σχέσης είναι αυτή των «συγχωριανών», αν ο Γιώργος είναι συγχωριανός της Άννας, τότε και η Άννα είναι συγχωριανή του Γιώργου.

Πιο αυστηρά, έστω μία σχέση $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$ .

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ Κολουντζάκης, Χ.· Παπαχριστόδουλος (2015). Διακριτά μαθηματικά (PDF). Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. doi:10.57713/kallipos-517.
↑ Φωτάκης, Δ.· Σούλιου, Δ. «Σχέσεις» (PDF). Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Εθνικό Μετσόβιο Πολυτεχνείο. Ανακτήθηκε στις 27 Απριλίου 2024.
↑ Ζάχος, Ε.· Παγουρτζής, Α.· Σούλιου, Θ. (2015). Θεμελίωση επιστήμης υπολογιστών. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις.

[1] Κολουντζάκης, Χ.· Παπαχριστόδουλος (2015). Διακριτά μαθηματικά (PDF). Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. doi:10.57713/kallipos-517.

[2] Φωτάκης, Δ.· Σούλιου, Δ. «Σχέσεις» (PDF). Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Εθνικό Μετσόβιο Πολυτεχνείο. Ανακτήθηκε στις 27 Απριλίου 2024.

[3] Ζάχος, Ε.· Παγουρτζής, Α.· Σούλιου, Θ. (2015). Θεμελίωση επιστήμης υπολογιστών. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις.

[1]

[2]

[3]