Προβολή πηγαίου κώδικα για τη σελίδα Μεταβατική σχέση

[[Αρχείο:Transitivity property example.svg|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> (με κόκκινο χρώμα).]]
Στην [[θεωρία συνόλων]] '''μεταβατική σχέση''' είναι μία [[μαθηματική σχέση|σχέση]] <math>R</math> σε ένα [[σύνολο]] <math>X</math> που ικανοποιεί την εξής ιδιότητα<ref>{{cite book |url=https://repository.kallipos.gr/bitstream/11419/5187/3/discr-pdf-%CE%9A%CE%9F%CE%A5.pdf |last1=Κολουντζάκης |first1=Μ. |last2=Παπαχριστόδουλος |first2=Χ. |year=2015 |title=Διακριτά μαθηματικά |publisher=Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις |doi=10.57713/kallipos-517 }}{{Dead link|date=Σεπτεμβρίου 2024 }}</ref>{{rp|23}}<ref name="D21">{{cite web |url=http://web-server.math.uoc.gr:1080/Members/ddais/Algebra_I_XE_20_21/EAL.pdf |title=Εισαγωγική άλγεβρα: Σημειώσεις παραδόσεων |location=Ηράκλειον, Κρήτης |last=Νταής |first=Δημήτριος Ι.  |year=2021 }}</ref>{{rp|18}}<ref>{{cite web |url=http://www.softlab.ntua.gr/~fotakis/discrete_math/data/06_Relations.pdf |last1=Φωτάκης |first1=Δ. |last2=Σούλιου |first2=Δ. |title=Σχέσεις |publisher=Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Εθνικό Μετσόβιο Πολυτεχνείο |access-date=27 April 2024}}</ref>{{rp|5}}<ref>{{cite book |last1=Ζάχος |first1=Ε. |last2=Παγουρτζής |first2=Α. |last3=Σούλιου |first3=Θ. |year=2015 |title=Θεμελίωση επιστήμης υπολογιστών |publisher=Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις |url=https://hdl.handle.net/11419/5454 }}</ref>{{rp|16}}
:αν <math>x R y</math> και <math>y R z</math>, τότε <math>x R z</math>,
για κάθε στοιχεία <math>x, y, z \in X</math>. Στην γραφική αναπαράσταση της <math>R</math> αυτό σημαίνει ότι αν υπάρχει μονοπάτι από το <math>x</math> στο <math>y</math> και από το <math>y</math> στο <math>z</math>, τότε τo <math>x</math> συνδέεται με το <math>z</math>.

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

== Παραδείγματα ==
[[Αρχείο:Transitive relation example graph and matrix.svg|300px|thumb|right|Παράδειγμα μεταβατικής σχέσης.]]
Οι παρακάτω σχέσεις είναι μεταβατικες:
* Η σχέση "είναι απόγονος του/τη" είναι μεταβατική.
* Η σχέση της [[ισότητα|ισότητας]] είναι μεταβατική, καθώς αν <math>x = y</math> και <math>y = z</math>, τότε <math>x = z</math>.
* Η σχέση του "διαιρεί" στους φυσικούς είναι μεταβατική, καθώς αν <math>d |x</math> και <math>x | y</math>, τότε <math>d | y</math>.
* Κάθε σχέση διάταξης είναι μεταβατική σχέση. Για παράδειγμα, η σύγκριση μεταξύ φυσικών (ή ρητών ή πραγματικών) αριθμών είναι μεταβατική, καθώς αν <math>x = y</math> και <math>y = z</math>, τότε <math>x = z</math>.
* Στην [[θεωρία γράφων]], η σχέση της προσβασιμότητας είναι μεταβατική, όπου <math>x R y</math> αν και μόνο αν υπάρχει μονοπάτι από το <math>x</math> στο <math>y</math>. 
* Η σχέση 
::<math>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) \}</math>,
:είναι μεταβατική (δείτε το σχήμα).

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

== Ιδιότητες ==
* Μία σχέση <math>R</math> είναι μεταβατική ανν <math>R \circ R \subseteq R</math>, όπου <math>\circ</math> είναι η [[σύνθεση σχέσεων]].
* Αν μία σχέση <math>R</math> είναι μεταβατική, τότε και η [[αντίστροφη σχέση|αντίστροφή]] της είναι μεταβατική.
* Η [[τομή συνόλων|τομή]] δύο μεταβατικών σχέσεων είναι μεταβατική. (Η [[ένωση συνόλων|ένωση]] δύο μεταβατικών σχέσεων δεν είναι κατά ανάγκη μεταβατική).
* Σε μία μεταβατική σχέση <math>R</math> αν υπάρχουν στοιχεία <math>x_1, \ldots, x_n</math> τέτοια ώστε 
::<math>x_1 R x_2, x_2 R x_3, \ldots, x_{n-1} R x_{n}, x_n R x_1</math>,
:τότε η σχέση <math>R</math> περιορισμένη στο υποσύνολο <math>\{ x_1, \ldots, x_n \}</math> είναι [[σχέση ισοδυναμίας]].<ref group="Σημείωση">Αυτή η παρατήρηση επιτρέπει την αποσύνθεση του γράφου της σχέσης σε επιμέρους σχέσεις ισοδυναμίας (ή απομονομένα στοιχεία) που συνδέονται μεταξύ τους με έναν  [[Κατευθυνόμενος άκυκλος γράφος|κατευθυνόμενο ακυκλικό γράφο]].</ref>

== Πλήθος μεταβατικών σχέσεων ==
Δεν υπάρχει γενικός κλειστός τύπος για το πλήθος των δυνατών μεταβατικών σχέσεων σε ένα [[πεπερασμένο σύνολο]]. Τα πλήθη δύνονται από την ακολουθία:
:<math>1, 2, 13, 171, 3994, \ldots</math> {{oeis|A006905}}

== Σχετικές έννοιες ==
* Μία μεταβατική σχέση που είναι επίσης [[ανακλαστική σχέση|ανακλαστική]] και [[συμμετρική σχέση|συμμετρική]] λέγεται [[σχέση ισοδυναμίας]].
* Μια μεταβατική σχέση που είναι επίσης ανακλαστική και [[αντισυμμετρική σχέση|αντισυμμετρική]] λέγεται [[μερική διάταξη]].
* [[Μεταβατική κλεισότητα]] μίας σχέσης <math>R</math> είναι η μεταβατική σχέση <math>R^*</math> ώστε <math>R \subseteq R^*</math> και είναι η ελάχιστη ως προς την σχέση του [[υποσύνολο|υποσυνόλου]].

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


== Παραπομπές ==
<references/>

== Σημειώσεις ==
<references group="Σημείωση"/>


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