Διαμερίσεις και Κλάσεις Ισοδυναμίας

Ορισμός Διαμέρισης

Μια Διαμέριση ενός συνόλου Α είναι ο χωρισμός του σε υποσύνολα $S_i$ με τις εξής δύο ιδιότητες:

α) Κάθε στοιχείο του συνόλου Α ανήκει σε κάποιο $S_i$.

β) Τα υποσύνολα $S_i$ είναι ξένα μεταξύ τους. Δεν έχουν δηλαδή κανένα κοινό στοιχείο.

Δηλαδή κάθε στοιχείο του Α ανήκει σε ένα και μόνο ένα $S_i$.

Ορισμός Σχέσης

Μια Σχέση ή διμελής σχέση σε ένα σύνολο Α είναι μια συλλογή από διατεταγμένα ζεύγη στοιχείων του Α. Δηλαδή είναι ένα υποσύνολο του καρτεσιανού γινόμενου $A^2 = A \times A$.  

Ορισμός Σχέσης Ισοδυναμίας

Σχέση Ισοδυναμίας $\sim$ είναι μια σχέση που έχει τις εξής τρεις ιδιότητες:

α) Είναι Αυτοπαθής, δηλαδή κάθε στοιχείο είναι ισοδύναμο με τον εαυτό του, $\alpha \sim \alpha$. Αυτό σημαίνει ότι το διατεταγμένο ζεύγος (α,α) ανήκει στη σχέση, για κάθε α.

β) Είναι Συμμετρική, δηλαδή αν $\alpha \sim \beta$ τότε και $\beta \sim \alpha$. Αν δηλαδή το (α,β) ανήκει στην σχέση τότε και το (β,α) ανήκει στην σχέση.

γ) Είναι Μεταβατική, δηλαδή αν $\alpha \sim \beta$ και $\beta \sim \gamma$ τότε και $\alpha \sim \gamma$. Αν δηλαδή το (α,β) και το (β,γ) ανήκουν στη σχέση τότε και το (α,γ) ανήκει στην σχέση.

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

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

Απόδειξη

α) Πρώτα θα αποδείξουμε ότι κάθε διαμέριση ορίζει μια σχέση ισοδυναμίας.
Έστω διαμέριση του συνόλου Α. Η διαμέριση αυτή αποτελείται από υποσύνολα $S_i$ του Α με τις ιδιότητες $\cup_{i \in I} S_i = A$ και $S_i \cap S_j = \emptyset$.
Ορίζουμε τη σχέση $\alpha \sim \beta$ αν και μόνο αν $a \in S_i$ και $\beta \in S_i$.
Αυτή η σχέση είναι σχέση ισοδυναμίας διότι:
1. Είναι αυτοπαθής (δηλαδή $\alpha \sim \alpha$) γιατί $\alpha \in S_i \Rightarrow \alpha \in S_i$.
2. Είναι συμμετρική (δηλαδή $\alpha \sim \beta \Rightarrow \beta \sim \alpha$) γιατί αν $\alpha \sim \beta$ τότε $\alpha \in S_i$ και $\beta \in S_i$ άρα ανήκουν και τα δύο στο υποσύνολο $S_i$ άρα και $\beta \sim \alpha$.
3. Είναι μεταβατική (δηλαδή $\alpha \sim \beta$ και $\beta \sim \gamma \Rightarrow \alpha \sim \gamma$) γιατί από το $\alpha \sim \beta$ το $\alpha \in  S_i$ και το $\beta \in S_i$. Από το $\beta \sim \gamma$ έχουμε ότι $\beta \in S_i$ και άρα $\gamma \in S_i$. Άρα το $\alpha$ και το $\gamma$ ανήκουν στο $S_i$ και άρα $\alpha \sim \gamma$.

β) Τώρα θα αποδείξουμε ότι κάθε σχέση ισοδυναμίας σε ένα σύνολο Α έχει κλάσεις ισοδυναμίας που είναι διαμέριση του Α.
Έστω η σχέση ισοδυναμίας $\sim$. Αυτή ορίζει κλάσεις ισοδυναμίας $S_{\alpha}$ στο Α με την ιδιότητα $x \in S_{\alpha}$ αν $x \sim \alpha$.
1. Κάθε στοιχείο του Α ανήκει σε κάποια κλάση ισοδυναμίας γιατί για κάθε $x \in A$ το $x \in S_x$.
2. Οι κλάσεις ισοδυναμίας δεν έχουν κανένα κοινό στοιχείο μεταξύ τους.
Έστω $x \in S_{\alpha}$ και $x \in S_{\beta}$. Τότε $x \sim \alpha$ και $x \sim \beta$.
Το $x \sim \alpha \Rightarrow \alpha \sim x$ και με την $x \sim \beta$ και την μεταβατική ιδιότητα έχουμε ότι $\alpha \sim \beta$ δηλαδή $\alpha \in S_{\beta}$ και άρα $S_{\alpha} \subseteq S_{\beta}$(1). Με τον ίδιο τρόπο δείχνουμε ότι το $S_{\beta} \subseteq S_{\alpha}$.
Το $x \sim \beta \Rightarrow \beta \sim x$ και με την $x \sim \alpha$ και την μεταβατική ιδιότητα έχουμε ότι $\beta \sim \alpha$ δηλαδή $\beta \in S_{\alpha}$ και άρα $S_{\beta} \subseteq S_{\alpha}$(2).
Έτσι από την (1) και (2) έχουμε ότι $S_{\alpha} = S_{\beta}$ και δεν υπάρχουν κοινά στοιχεία μεταξύ διαφορετικών κλάσεων ισοδυναμίας.
Άρα οι κλάσεις ισοδυναμίας είναι διαμέριση του Α. $\square$

Βιβλιογραφία

• John B. Fraleigh: Εισαγωγή στην Άλγεβρα. σελ. 11-14