Σχέση ισοδυναμίας

Η σχέση ισοδυναμίας είναι μια διμελής σχέση σε σύνολο που είναι ανακλαστική, συμμετρική και μεταβατική.

Κίνητρο

Η σχέση ισοδυναμίας είναι ένα είδος εκλέπτυνσης της σχέσης ισότητας. Πάντα μπορούμε να αποφασίσουμε αν δύο στοιχεία ενός συνόλου είναι ίδια, δηλαδή αν a = b. Μερικές φορές όμως μας βολεύει να εξετάσουμε αν δύο στοιχεία είναι απλώς όμοια, όχι απαραίτητα ίδια. Δηλαδή – αν έχουν κοινή κάποια ουσιώδη ιδιότητα. Για παράδειγμα δύο βιβλία μπορούμε να τα θεωρήσουμε όμοια αν έχουν το ίδιο είδος – ή με τη βοήθεια της ισοδυναμίας: δύο βιβλία είναι ισοδύναμα αν έχουν το ίδιο είδος.

Τι θα περιμέναμε από μια τέτοια ισοδυναμία; Ας πάρουμε ένα άλλο παράδειγμα. Δύο λέξεις είναι όμοιες/ισοδύναμες αν έχουν το ίδιο μήκος.

Μάλλον θα περιμέναμε ότι αν μετρήσουμε την ομοιότητα δύο ίδιων λέξεων, θα προκύψει ότι είναι όμοιες. Δηλαδή για όλες τις λέξεις πρέπει να ισχύει ότι είναι όμοιες/ισοδύναμες με τον εαυτό τους. Στη γλώσσα των σχέσεων: η σχέση ισοδυναμίας πρέπει να είναι ανακλαστική.

Επιπλέον, αν η λέξη «ρυάκι» είναι όμοια/ισοδύναμη με τη λέξη «Ελένη», τότε σίγουρα περιμένουμε ότι και η λέξη «Ελένη» θα είναι ισοδύναμη με τη λέξη «ρυάκι». Με άλλα λόγια, η σειρά δεν παίζει ρόλο. Στη γλώσσα των σχέσεων: η σχέση ισοδυναμίας πρέπει να είναι συμμετρική.

Και τέλος, αν η λέξη «γάτα» είναι όμοια/ισοδύναμη με τη λέξη «ψάρι» και η λέξη «ψάρι» είναι ισοδύναμη με τη λέξη «πόδι», τότε περιμένουμε ότι και οι λέξεις «γάτα» και «πόδι» θα είναι ισοδύναμες. Άρα η σχέση ισοδυναμίας πρέπει να είναι και μεταβατική.

Τίποτε άλλο δεν περιμένουμε από την ισοδυναμία.

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

Άλλα παραδείγματα ισοδυναμιών:

• Κατοικία στην ίδια πόλη. Ο Γιώργος σίγουρα κατοικεί στην ίδια πόλη με τον Γιώργο (ανακλαστικότητα). Αν ο Γιώργος κατοικεί στην ίδια πόλη με τον Νίκο, τότε και ο Νίκος κατοικεί στην ίδια πόλη με τον Γιώργο (συμμετρία). Και αν ο Νίκος κατοικεί στην ίδια πόλη με τον Μιχάλη, τότε και ο Γιώργος κατοικεί στην ίδια πόλη με τον Μιχάλη (μεταβατικότητα).
• Τραγούδια με τον ίδιο δημιουργό. Το τραγούδι «Το τραγούδι της βροχής» έχει σίγουρα τον ίδιο δημιουργό με το τραγούδι «Το τραγούδι της βροχής» (ανακλαστικότητα). Αν τα τραγούδια «Το τραγούδι της βροχής» και «Ο δρόμος για το σπίτι» έχουν τον ίδιο δημιουργό, τότε και τα «Ο δρόμος για το σπίτι» και «Το τραγούδι της βροχής» έχουν τον ίδιο δημιουργό (συμμετρία). Και αν τα «Ο δρόμος για το σπίτι» και «Το φεγγάρι στη θάλασσα» έχουν τον ίδιο δημιουργό, τότε και τα «Το τραγούδι της βροχής» και «Το φεγγάρι στη θάλασσα» έχουν τον ίδιο δημιουργό (μεταβατικότητα).
• (a, b) ∈ R αν και μόνο αν το a − b είναι άρτιος αριθμός· τα a, b είναι ακέραιοι αριθμοί. Ανακλαστικότητα: a − a = 0, το μηδέν είναι άρτιος αριθμός. Συμμετρία: έστω c = a − b. Τότε b − a = −(a − b) = −c. Αν ο c είναι άρτιος, τότε πρέπει να είναι άρτιος και ο −c. Μεταβατικότητα: έστω p = a − b και q = b − c. Ξέρουμε ότι και ο p και ο q είναι άρτιοι αριθμοί. Τώρα πρέπει να αποδείξουμε ότι ο a − c είναι άρτιος αριθμός. Σε αυτή την εξίσωση αντικαθιστούμε το c με c = b − q: a − (b − q), που ισούται με a − b + q. Από τις υποθέσεις ξέρουμε ότι ο a − b είναι άρτιος αριθμός. Αν σε έναν άρτιο αριθμό προσθέσουμε έναν ακόμη άρτιο αριθμό q, παίρνουμε πάλι άρτιο αριθμό.
• Ισότητα. Η ισότητα είναι ισοδυναμία, και μάλιστα η μικρότερη ισοδυναμία σε οποιοδήποτε σύνολο M.

Τετριμμένη ισοδυναμία

Έχουμε ένα μη κενό σύνολο M. Ποια είναι η μικρότερη δυνατή ισοδυναμία R στο σύνολο M; Το μικρότερο δυνατό υποσύνολο του καρτεσιανού γινομένου M × M είναι το κενό σύνολο ∅. Ικανοποιεί το κενό σύνολο τις συνθήκες της ισοδυναμίας;

Σίγουρα είναι συμμετρικό, αφού η σχέση R δεν έχει κανένα στοιχείο, οπότε η συνθήκη της συμμετρίας ικανοποιείται αυτόματα και τετριμμένα. Παρόμοια η μεταβατικότητα. Το πρόβλημα είναι με την ανακλαστικότητα. Ο ορισμός λέει ότι για όλα τα στοιχεία x του συνόλου M ισχύει (x, x) ∈ R. Ικανοποιείται αυτό; Το σύνολο M είναι μη κενό, άρα περιέχει κάποιο στοιχείο, για παράδειγμα το q. Ανήκει το ζεύγος (q, q) στη σχέση R; Όχι. Η σχέση R λοιπόν δεν είναι ανακλαστική.

Ποια είναι η μικρότερη σχέση που ικανοποιεί την ανακλαστικότητα; Η σχέση ισότητας. Η σχέση R πρέπει να περιέχει τουλάχιστον τα ζεύγη (x, x) για όλα τα στοιχεία του M. Αυτή είναι ακριβώς η ταυτοτική σχέση. Είναι μια τέτοια σχέση συμμετρική; Εύκολα φαίνεται ότι ναι. Παρόμοια φαίνεται εύκολα ότι είναι και μεταβατική. Η μικρότερη σχέση ισοδυναμίας στο σύνολο M είναι λοιπόν η ταυτοτική σχέση, που τη συμβολίζουμε id_M και περιέχει τα ζεύγη (x, x) για όλα τα x ∈ M.

Ποια είναι η μεγαλύτερη δυνατή ισοδυναμία στο σύνολο M; Το μεγαλύτερο υποσύνολο είναι ολόκληρο το M × M. Ικανοποιεί τις συνθήκες της ισοδυναμίας; Φαίνεται μάλλον τετριμμένα ότι ναι.

Κλάση ισοδυναμίας

Κάθε ισοδυναμία χωρίζει το σύνολο M σε ένα σύστημα ξένων μεταξύ τους συνόλων, που τα ονομάζουμε κλάσεις ισοδυναμίας.

Έστω το σύνολο όλων των λέξεων M και η ισοδυναμία R «λέξεις με το ίδιο μήκος». Δηλαδή (a, b) ∈ R αν και μόνο αν οι λέξεις a και b έχουν το ίδιο μήκος. Αυτή η ισοδυναμία χωρίζει το σύνολο των λέξεων σε μερικά μικρότερα σύνολα, που θα περιέχουν πάντα λέξεις ίδιου μήκους. Τις επιμέρους κλάσεις ισοδυναμίας μπορούμε να τις ξεχωρίσουμε με τη βοήθεια κάτω δείκτη, που θα δείχνει ταυτόχρονα το μήκος των λέξεων στο συγκεκριμένο σύνολο:

• M₁ = {ο, η, ω, …}
• M₂ = {να, με, σε, το, …}
• M₃ = {και, για, από, δεν, …}
• M₄ = {γάτα, ψάρι, πόδι, χέρι, …}
• …

Πρόσεξε δύο πράγματα: 1) τα επιμέρους σύνολα είναι ξένα μεταξύ τους, δεν έχουν κανένα κοινό στοιχείο. 2) όλα τα στοιχεία κάθε επιμέρους συνόλου είναι μεταξύ τους ισοδύναμα. Όλες οι λέξεις του συνόλου M₃ είναι μεταξύ τους ισοδύναμες, επειδή όλες οι λέξεις έχουν μήκος τρία, δηλαδή το ίδιο μήκος, που είναι η συνθήκη της ισοδυναμίας.

Κάθε στοιχείο ορίζει μονοσήμαντα την κλάση ισοδυναμίας του. Αυτό το γράφουμε συνήθως με τον συμβολισμό M[x], όπου x ∈ M. Αν γράψουμε M[και], ορίζουμε μονοσήμαντα την κλάση ισοδυναμίας που την έχουμε ήδη ονομάσει M₃.

Πώς βρίσκουμε την κλάση ισοδυναμίας, αν ξέρουμε κάποιο x ∈ M; Περνάμε από όλα τα στοιχεία του M και βρίσκουμε ποια από αυτά είναι ισοδύναμα με το στοιχείο x. Αυτά θα είναι όλα τα στοιχεία που θα ανήκουν στην κλάση ισοδυναμίας M[x].

Για το M[και] θα περνούσαμε από όλες τις λέξεις του M και θα κρατούσαμε στο M₃ τις λέξεις που έχουν μήκος τρία.

Ορισμός και ιδιότητες της κλάσης ισοδυναμίας

Την κλάση ισοδυναμίας θα μπορούσαμε να την ορίσουμε ως εξής. Έστω ένα σύνολο M και σε αυτό ορισμένη ισοδυναμία R. Τότε κλάση της διαμέρισης που περιέχει το στοιχείο x ∈ M ονομάζουμε:

$$M[x]=\{y\in M;(x,y)\in R\}$$

Ο ορισμός λέει ότι αυτά είναι όλα τα y που είναι ισοδύναμα με το δοσμένο στοιχείο x. Επειδή η σχέση ισοδυναμίας είναι ανακλαστική, με αυτόν τον τρόπο μπαίνει εκεί και το ίδιο το στοιχείο x – επειδή το x είναι ισοδύναμο με τον εαυτό του.

Διαμέριση της ισοδυναμίας λέμε το σύνολο όλων των κλάσεων ισοδυναμίας. Έτσι διαμέριση του συνόλου όλων των λέξεων θα ήταν το σύνολο {M₁, M₂, M₃, …}.

Βασικές ιδιότητες των κλάσεων ισοδυναμίας:

• (a, b) ∈ R αν και μόνο αν M[a] = M[b]. Αν έχουμε δύο στοιχεία a, b που είναι ισοδύναμα, τότε οι κλάσεις ισοδυναμίας τους πρέπει να είναι ίσες.
• Αντίστροφα, αν δεν ισχύει (a, b) ∈ R, τότε ισχύει επίσης M[a] ≠ M[b], ακριβέστερα M[a] ∩ M[b] = ∅. Αν έχουμε δύο στοιχεία που δεν είναι ισοδύναμα, τότε οι κλάσεις της διαμέρισής τους είναι ξένες.
• Η ένωση όλων των κλάσεων ισοδυναμίας πρέπει να δίνει το αρχικό σύνολο M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Η προηγούμενη γραφή είναι μόνο για πεπερασμένο πλήθος κλάσεων ισοδυναμίας, αλλά γενικά μπορεί να είναι άπειρες.)

Παραδείγματα διαμερίσεων ισοδυναμίας

Πρώτο παράδειγμα, περιττοί και άρτιοι αριθμοί:

Έστω μια απλή ισοδυναμία R ορισμένη στους φυσικούς αριθμούς N. (a, b) ∈ R αν και μόνο αν και το a και το b είναι περιττοί ή και το a και το b είναι άρτιοι. Παραδείγματα στοιχείων: (1, 7), (13, 9), (4, 6), (8, 136). Θα προσδιορίσουμε τώρα τη διαμέριση αυτής της ισοδυναμίας σε κλάσεις ισοδυναμίας.

Θα ξεκινήσουμε σταδιακά. Με τι θα ισούται η κλάση N[1]; Πρέπει να βρούμε όλους τους αριθμούς που είναι ισοδύναμοι με τον αριθμό ένα. Σύμφωνα με τη συνθήκη της ισοδυναμίας είναι όλοι οι περιττοί αριθμοί, άρα N[1] = {1, 3, 5, 7, 9, …}.

Με τι θα ισούται η κλάση N[2]; Βρίσκουμε όλους τους αριθμούς που είναι ισοδύναμοι με το δύο. Αυτοί είναι όλοι οι άρτιοι αριθμοί: N[2] = {2, 4, 6, 8, 10, …}.

Τώρα το N[3]. Ποιοι αριθμοί είναι ισοδύναμοι με το τρία; Όλοι οι περιττοί αριθμοί. Έτσι όμως παίρνουμε το σύνολο N[1], που το υπολογίσαμε στην προπροηγούμενη παράγραφο. Παρόμοια για το N[4], εκεί πάλι το σύνολο των άρτιων αριθμών.

Βλέπουμε ότι στη συνέχεια θα επαναλαμβάνονταν συνεχώς τα ίδια σύνολα. Φαίνεται και από το ότι όποιον άλλο φυσικό αριθμό n κι αν πάρουμε, θα ισχύει ότι n ∈ N[1] ή n ∈ N[2]. Άλλους φυσικούς αριθμούς εκτός από περιττούς και άρτιους δεν έχουμε, άρα αυτά τα δύο σύνολα αποτελούν τη διαμέριση της ισοδυναμίας.

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

Δεύτερο παράδειγμα, απόλυτη τιμή:

Έστω η ισοδυναμία R στο σύνολο των ακέραιων αριθμών Z που ορίζεται ως εξής: (a, b) ∈ R αν και μόνο αν |a| = |b|. (Οι κατακόρυφες γραμμές είναι η απόλυτη τιμή.) Πάλι θα προχωρήσουμε σταδιακά:

• Z[0] = {0}. Το μηδέν σχετίζεται μόνο με το μηδέν.
• Z[1] = {−1, 1}. Το ένα σχετίζεται με το ένα και με το μείον ένα, επειδή |1| = |−1|.
• Z[2] = {−2, 2}. Το δύο σχετίζεται με το δύο και με το μείον δύο.
• Z[3] = {−3, 3}.
• …

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

$$\{\{a,-a\};a\in {\mathbb{Z}}_0^{+}\}$$

(Δηλαδή όλα τα ζεύγη a, −a, όπου a είναι ακέραιος μη αρνητικός αριθμός.) Βλέπεις ότι οι κλάσεις είναι άπειρες.