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

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

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

 Παραδείγματα 
300px|thumb|right|Παράδειγμα μεταβατικής σχέσης.
Οι παρακάτω σχέσεις είναι μεταβατικες:
 Η σχέση "είναι απόγονος του/τη" είναι μεταβατική.
 Η σχέση της ισότητας είναι μεταβατική, καθώς αν  και , τότε .
 Η σχέση του "διαιρεί" στους φυσικούς είναι μεταβατική, καθώς αν  και , τότε .
 Κάθε σχέση διάταξης είναι μεταβατική σχέση. Για παράδειγμα, η σύγκριση μεταξύ φυσικών (ή ρητών ή πραγματικών) αριθμών είναι μεταβατική, καθώς αν  και , τότε .
 Στην θεωρία γράφων, η σχέση της προσβασιμότητας είναι μεταβατική, όπου  αν και μόνο αν υπάρχει μονοπάτι από το  στο . 
 Η σχέση 
,
είναι μεταβατική (δείτε το σχήμα).

300px|right|thumb|Παράδειγμα μη μεταβατικής σχέσης. Με κόκκινο τα ελάχιστα ζεύγη που πρέπει να προστεθούν ώστε να γίνει η σχέση μεταβατική.
Μερικές σχέσεις που δεν είναι μεταβατικές είναι οι εξής:
 Η σχέση είναι «πατέρας του/της» δεν είναι 
 Λέμε ότι η πόλη  "είναι κοντά" στην πόλη , αν η απόσταση τους είναι μικρότερη από 10km. Η σχέση αυτή δεν είναι κατά ανάγκη μεταβατική, γιατί μπορεί η  να είναι κοντά στην  και η  να είναι κοντά στην , αλλά η  μπορεί να μην είναι κοντά στην  (γιατί αν είναι και οι τρεις σε μία ευθεία μπορεί να απέχουν έως και 20km).
 Η σχέση 
,
δεν είναι μεταβατική (λείπουν οι ακμές που δίνονται με κόκκινο στο σχήμα). 

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

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


 Σχετικές έννοιες 
 Μία μεταβατική σχέση που είναι επίσης ανακλαστική και συμμετρική λέγεται σχέση ισοδυναμίας.
 Μια μεταβατική σχέση που είναι επίσης ανακλαστική και αντισυμμετρική λέγεται μερική διάταξη.
 Μεταβατική κλεισότητα μίας σχέσης  είναι η μεταβατική σχέση  ώστε  και είναι η ελάχιστη ως προς την σχέση του υποσυνόλου.

 Δείτε επίσης 
 Ανακλαστική σχέση
 Συμμετρική σχέση
 Μεταβατική κλειστότητα

 Παραπομπές 

 Σημειώσεις 

Κατηγορία:Θεωρία συνόλων
Κατηγορία:Δυαδικές σχέσεις