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

Αρχείο:Transitivity property example.svg

Σε μία μεταβατική σχέση $R$, αν $xRy$ και $yRz$, τότε ισχύει ότι $xRz$. Δηλαδή αν στον γράφο της σχέσης υπάρχει μονοπάτι $x\to y\to z$ (με μαύρο χρώμα), τότε υπάρχι και η ακμή $x\to z$ (με κόκκινο χρώμα).

Στην θεωρία συνόλων μεταβατική σχέση είναι μία σχέση $R$ σε ένα σύνολο $X$ που ικανοποιεί την εξής ιδιότηταΠρότυπο:RpΠρότυπο:RpΠρότυπο:RpΠρότυπο:Rp

αν $xRy$ και $yRz$, τότε $xRz$,

για κάθε στοιχεία $x,y,z\in X$. Στην γραφική αναπαράσταση της $R$ αυτό σημαίνει ότι αν υπάρχει μονοπάτι από το $x$ στο $y$ και από το $y$ στο $z$, τότε τo $x$ συνδέεται με το $z$.

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

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

Αρχείο:Transitive relation example graph and matrix.svg

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

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

• Η σχέση "είναι απόγονος του/τη" είναι μεταβατική.
• Η σχέση της ισότητας είναι μεταβατική, καθώς αν $x=y$ και $y=z$, τότε $x=z$.
• Η σχέση του "διαιρεί" στους φυσικούς είναι μεταβατική, καθώς αν $d|x$ και $x|y$, τότε $d|y$.
• Κάθε σχέση διάταξης είναι μεταβατική σχέση. Για παράδειγμα, η σύγκριση μεταξύ φυσικών (ή ρητών ή πραγματικών) αριθμών είναι μεταβατική, καθώς αν $x=y$ και $y=z$, τότε $x=z$.
• Στην θεωρία γράφων, η σχέση της προσβασιμότητας είναι μεταβατική, όπου $xRy$ αν και μόνο αν υπάρχει μονοπάτι από το $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)\}$,

είναι μεταβατική (δείτε το σχήμα).

Αρχείο:Non transitive relation example graph and matrix.svg

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

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

• Η σχέση είναι «πατέρας του/της» δεν είναι
• Λέμε ότι η πόλη $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,\dots ,x_n$ τέτοια ώστε

$x_{1}R{x}_2,x_{2}R{x}_3,\dots ,x_{n-1}R{x}_n,x_{n}R{x}_1$,

τότε η σχέση $R$ περιορισμένη στο υποσύνολο $\{x_1,\dots ,x_n\}$ είναι σχέση ισοδυναμίας.

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

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

$1,2,13,171,3994,\dots$ Πρότυπο:Oeis

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

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

Δείτε επίσης

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