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

right|300px|thumb|Σε μία μεταβατική σχέση <math>R</math>, αν <math>x R y</math> και <math>y R z</math>, τότε ισχύει ότι <math>x R z</math>. Δηλαδή αν στον γράφο της σχέσης υπάρχει μονοπάτι <math>x \to y \to z</math> (με μαύρο χρώμα), τότε υπάρχι και η ακμή <math>x \to z</math> (με κόκκινο χρώμα).
Στην θεωρία συνόλων **μεταβατική σχέση** είναι μία σχέση R σε ένα σύνολο X που ικανοποιεί την εξής ιδιότητα
:αν x R y και y R z, τότε x R z,
για κάθε στοιχεία x, y, z \in X. Στην γραφική αναπαράσταση της R αυτό σημαίνει ότι αν υπάρχει μονοπάτι από το x στο y και από το y στο z, τότε τo x συνδέεται με το z.

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

## Παραδείγματα
300px|thumb|right|Παράδειγμα μεταβατικής σχέσης.
Οι παρακάτω σχέσεις είναι μεταβατικες:
* Η σχέση "είναι απόγονος του/τη" είναι μεταβατική.
* Η σχέση της ισότητας είναι μεταβατική, καθώς αν x = y και y = z, τότε x = z.
* Η σχέση του "διαιρεί" στους φυσικούς είναι μεταβατική, καθώς αν d |x και x | y, τότε d | y.
* Κάθε σχέση διάταξης είναι μεταβατική σχέση. Για παράδειγμα, η σύγκριση μεταξύ φυσικών (ή ρητών ή πραγματικών) αριθμών είναι μεταβατική, καθώς αν x = y και y = z, τότε x = z.
* Στην θεωρία γράφων, η σχέση της προσβασιμότητας είναι μεταβατική, όπου x R y αν και μόνο αν υπάρχει μονοπάτι από το x στο y. 
* Η σχέση 
::R = \{ (1, 2), (1, 3), (1,4), (1,5), (2,3), (2, 4), (2, 5), (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (6, 5) \},
:είναι μεταβατική (δείτε το σχήμα).

300px|right|thumb|Παράδειγμα μη μεταβατικής σχέσης. Με κόκκινο τα ελάχιστα ζεύγη που πρέπει να προστεθούν ώστε να γίνει η σχέση μεταβατική.
Μερικές σχέσεις που δεν είναι μεταβατικές είναι οι εξής:
* Η σχέση είναι «πατέρας του/της» δεν είναι 
* Λέμε ότι η πόλη A "είναι κοντά" στην πόλη B, αν η απόσταση τους είναι μικρότερη από 10km. Η σχέση αυτή δεν είναι κατά ανάγκη μεταβατική, γιατί μπορεί η A να είναι κοντά στην B και η B να είναι κοντά στην C, αλλά η A μπορεί να μην είναι κοντά στην C (γιατί αν είναι και οι τρεις σε μία ευθεία μπορεί να απέχουν έως και 20km).
* Η σχέση 
::R = \{ (1, 4), (2, 3), (3, 4), (4,3), (3,5) \},
:δεν είναι μεταβατική (λείπουν οι ακμές που δίνονται με κόκκινο στο σχήμα). 

## Ιδιότητες
* Μία σχέση R είναι μεταβατική ανν R \circ R \subseteq R, όπου \circ είναι η σύνθεση σχέσεων.
* Αν μία σχέση R είναι μεταβατική, τότε και η αντίστροφή της είναι μεταβατική.
* Η τομή δύο μεταβατικών σχέσεων είναι μεταβατική. (Η ένωση δύο μεταβατικών σχέσεων δεν είναι κατά ανάγκη μεταβατική).
* Σε μία μεταβατική σχέση R αν υπάρχουν στοιχεία x_1, \ldots, x_n τέτοια ώστε 
::x_1 R x_2, x_2 R x_3, \ldots, x_{n-1} R x_{n}, x_n R x_1,
:τότε η σχέση R περιορισμένη στο υποσύνολο \{ x_1, \ldots, x_n \} είναι σχέση ισοδυναμίας.

## Πλήθος μεταβατικών σχέσεων
Δεν υπάρχει γενικός κλειστός τύπος για το πλήθος των δυνατών μεταβατικών σχέσεων σε ένα πεπερασμένο σύνολο. Τα πλήθη δύνονται από την ακολουθία:
:1, 2, 13, 171, 3994, \ldots 

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

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

## Παραπομπές


## Σημειώσεις


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