Μεταβατική σχέση

δυαδική σχέση R με την ιδιότητα ότι αν xRy και yRz τότε και xRz

Στην θεωρία συνόλων μεταβατική σχέση είναι μία σχέση σε ένα σύνολο που ικανοποιεί την εξής ιδιότητα[1]:23[2]:18[3]:5[4]:16

Σε μία μεταβατική σχέση , αν και , τότε ισχύει ότι . Δηλαδή αν στον γράφο της σχέσης υπάρχει μονοπάτι (με μαύρο χρώμα), τότε υπάρχι και η ακμή (με κόκκινο χρώμα).
αν και , τότε ,

για κάθε στοιχεία . Στην γραφική αναπαράσταση της αυτό σημαίνει ότι αν υπάρχει μονοπάτι από το στο και από το στο , τότε τo συνδέεται με το .

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

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

Επεξεργασία
 
Παράδειγμα μεταβατικής σχέσης.

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

  • Η σχέση "είναι απόγονος του/τη" είναι μεταβατική.
  • Η σχέση της ισότητας είναι μεταβατική, καθώς αν   και  , τότε  .
  • Η σχέση του "διαιρεί" στους φυσικούς είναι μεταβατική, καθώς αν   και  , τότε  .
  • Κάθε σχέση διάταξης είναι μεταβατική σχέση. Για παράδειγμα, η σύγκριση μεταξύ φυσικών (ή ρητών ή πραγματικών) αριθμών είναι μεταβατική, καθώς αν   και  , τότε  .
  • Στην θεωρία γράφων, η σχέση της προσβασιμότητας είναι μεταβατική, όπου   αν και μόνο αν υπάρχει μονοπάτι από το   στο  .
  • Η σχέση
 ,
είναι μεταβατική (δείτε το σχήμα).
 
Παράδειγμα μη μεταβατικής σχέσης. Με κόκκινο τα ελάχιστα ζεύγη που πρέπει να προστεθούν ώστε να γίνει η σχέση μεταβατική.

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

  • Η σχέση είναι «πατέρας του/της» δεν είναι
  • Λέμε ότι η πόλη   "είναι κοντά" στην πόλη  , αν η απόσταση τους είναι μικρότερη από 10km. Η σχέση αυτή δεν είναι κατά ανάγκη μεταβατική, γιατί μπορεί η   να είναι κοντά στην   και η   να είναι κοντά στην  , αλλά η   μπορεί να μην είναι κοντά στην   (γιατί αν είναι και οι τρεις σε μία ευθεία μπορεί να απέχουν έως και 20km).
  • Η σχέση
 ,
δεν είναι μεταβατική (λείπουν οι ακμές που δίνονται με κόκκινο στο σχήμα).

Ιδιότητες

Επεξεργασία
  • Μία σχέση   είναι μεταβατική ανν  , όπου   είναι η σύνθεση σχέσεων.
  • Αν μία σχέση   είναι μεταβατική, τότε και η αντίστροφή της είναι μεταβατική.
  • Η τομή δύο μεταβατικών σχέσεων είναι μεταβατική. (Η ένωση δύο μεταβατικών σχέσεων δεν είναι κατά ανάγκη μεταβατική).
  • Σε μία μεταβατική σχέση   αν υπάρχουν στοιχεία   τέτοια ώστε
 ,
τότε η σχέση   περιορισμένη στο υποσύνολο   είναι σχέση ισοδυναμίας.[Σημείωση 1]

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

Επεξεργασία

Δεν υπάρχει γενικός κλειστός τύπος για το πλήθος των δυνατών μεταβατικών σχέσεων σε ένα πεπερασμένο σύνολο. Τα πλήθη δύνονται από την ακολουθία:

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

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

Επεξεργασία

Δείτε επίσης

Επεξεργασία


Παραπομπές

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

Σημειώσεις

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