Ανακλαστική σχέση

Στην θεωρία συνόλων, μία ανακλαστική σχέση είναι μία σχέση στην οποία κάθε στοιχείο σχετίζεται με τον εαυτό του.^[1]^:23^[2]^:5^[3]^:16 Πιο αυστηρά, μία σχέση $R$ σε ένα σύνολο $S$ είναι ανακλαστική αν για κάθε $x\in S$ ισχύει ότι $xRx$ .

Μία σχέση στην οποία κανένα στοιχείο δεν σχετίζεται με τον εαυτό του (δηλαδή $x\not Rx$ ), λέγεται μη-ανακλαστική.

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

Κάποια παραδείγματα ανακλαστικών σχέσεων είναι τα εξής:

Στους φυσικούς αριθμούς η σχέση «διαιρεί» είναι ανακλαστική καθώς κάθε φυσικός αριθμός διαιρεί τον εαυτό του.
Η σχέση «έχει την ίδια ηλικία» είναι ανακλαστική καθώς κάθε άνθρωπος έχει την ίδια ηλία με τον εαυτό του.
Η σχέση σύγκρισης $\leq$ μεταξύ πραγματικών αριθμών είναι ανακλαστική καθώς, εξ'ορισμού $x\leq x$ για κάθε $x\in \mathbb {R}$ .
Η σχέση $xRy\Leftrightarrow |x|_{a}=|y|_{a}$ μεταξύ των συμβολοσειρών που έχουν το ίδιο πλήθος από «a» (π.χ. η «babbabbba» και η «abaab» έχουν και οι δύο τρία «a») είναι ανακλαστική.

Και κάποιες σχέσεις που δεν είναι ανακλαστικές είναι οι εξής:

Η σχέση σύγκρισης $<$ μεταξύ πραγματικών αριθμών, καθώς δεν ισχύει ότι $x<x$ .
Η σχέση «είναι παντρεμμένος/η με» δεν είναι ανακλαστική, καθώς κάποιος δεν μπορεί να παντρευτεί τον εαυτό του.
Η σχέση «έχει ψηφίσει τον/την» στο σύνολο όλων των ανθρώπων του κόσμου δεν είναι ανακλαστική, καθώς υπάρχουν άνθρωποι που δεν έχουν ψηφίσει τον εαυτό τους. Στο σύνολο όμως των πολιτικών (μάλλον) είναι ανακλαστική, καθώς (μάλλον) κάθε πολιτικός έχει ψηφίσει τον εαυτό του.

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

Στον πίνακα αναπαράστασης μίας ανακλαστικής σχέσης, όλα τα στοιχεία της κύριας διαγωνίου του πίνακα είναι $1$ .
Στον γράφο που αναπαριστά μία ανακλαστική σχέση, όλοι οι κόμβοι έχουν έναν βρόγχο.
Μία σχέση $R$ είναι ανακλαστική αν και μόνο αν η αντίστροφή $R^{-1}$ της είναι ανακλαστική.

Πλήθος ανακλαστικών σχέσεων[Επεξεργασία | επεξεργασία κώδικα]

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

1,1,4,64,4096,\ldots \quad

(ακολουθία A053763 στην OEIS)

Απόδειξη

Αυτό προκύπτει ως εξής. Έστω $M(R)$ ο πίνακας της σχέσης $R$ , τότε για να είναι η σχέση ανακλαστική πρέπει όλα τα στοιχεία της διαγωνίου να είναι $1$ . Όλα τα υπόλοιπα $n^{2}-n=n\cdot (n-1)$ στοιχεία μπορούν να οριστούν ανεξάρτητα. Από την βασική αρχή απαρίθμησης προκύπτει ότι συνολικά υπάρχουν

\underbrace {2\cdot \ldots \cdot 2} _{n\cdot (n-1)}=2^{n\cdot (n-1)}

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

Σχετικές έννοιες[Επεξεργασία | επεξεργασία κώδικα]

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

Ανακλαστική κλειστότητα[Επεξεργασία | επεξεργασία κώδικα]

Η ανακλαστική κλειστότητα της σχέσης $R\subseteq S\times S$ είναι η σχέση

R'=R\cup \{(x,x):x\in S\}

.

Αυτή είναι η ελάχιστη (ως προς την σχέση υποσυνόλου) που συμπεριλαμβάνει την $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]