el.wikipedia.org

Ανακλαστική σχέση - Βικιπαίδεια

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

(Ανακατεύθυνση από Μη-ανακλαστική σχέση)

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

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

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

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

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

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

{\displaystyle 1,1,4,64,4096,\ldots \quad } (ακολουθία A053763 στην OEIS)

Απόδειξη  

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

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

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

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

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

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

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

Αυτή είναι η ελάχιστη (ως προς την σχέση υποσυνόλου) που συμπεριλαμβάνει την {\displaystyle R} και είναι ανακλαστική.

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