4. Σχέσεις ισοδυναμίας.

 

Καρτεσιανά γινόμενα. Μια σχέση σε συνολο S είναι απλως ένα υποσύνολο του S S. Συνήθως οι σχέσεις συμβολίζονται με R ή ~, και γράφουμε x R y ή x ~ y ανν το διατεταγμένο ζεύγος είναι μέλος της σχέσης.

Μια σχέση ~ στο S λέγεται ανακλαστική αν: a ~ a για όλα τα μέλη a του S.

Λέγεται συμμετρική αν: a ~ b συνεπάγεται b ~ a, για όλα τα μέλη a, b του S.

Λέγεται μεταβατική αν: a ~ b και b ~ c συνεπάγoνται a~c, για όλα τα μέλη a, b, c του S.

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

Τάξεις ισοδυναμίας: Εστω ~ σχέση ισοδυναμίας στο S και x μέλος του S. Η κλάση ισοδυναμίας του x ως προς την ~ είναι το σύνολο = { y S : y ~ x }

 

Θεώρημα 4.1. Για μια σχεση ισοδυναμίας ~ σε σύνολο S ισχύουν τα εξής.

(1) = { y S : x ~ y }

(2)  x

(3)  x ~ y ανν =

(4) ανν =

(5) Αν , τότε .

 

Διαμερίσεις.

Δεδομένου φυσικού αριθμού n, στο Ζ ορίζεται μια σχέση ~ μέσω της a ~ b ανν n a - b. H ~ είναι σχέση   ισοδυναμίας. Λέγεται ισοτιμία modulo n. Συχνά αντι a ~ b γράφουμε a = b mod n. Yπάρχουν ακριβώς n κλάσεις ισοτιμίας mod n, και το σύνολο τους συμβολίζεται με Ζn. To Zn αποτελείται από τις κλάσεις των 0, 1, 2, , n-1.

 

Ασκήσεις

 

4.1. Βρείτε όλες τις σχέσεις στο σύνολο {1, 2}. Ποιες απ αυτές είναι ανακλαστικές, ποιες συμμετρικές, ποιες μεταβατικές και ποιες σχέσεις ισοδυναμίας;

Λύση

4.2. Από τις εξής τρείς σχέσεις στο Ν, ποιες είναι ανακλαστικές, ποιες συμμετρικές και ποιες μεταβατικές;

R1 = { (1, 1), (2, 2), (3, 3), (1, 2) }.

R2 = { (1, 1), (1, 2), (2, 1), (2, 2) }.

R3 = { (1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3) }

Λύση

4.3. Ποιες από τις R1, R2, R3 της 4.2. ως σχέσεις στο { 1, 2, 3 }, είναι ανακλαστικές, συμμετρικές ή μεταβατικές;

Λύση

4.4. Ποιες δύο από τις ιδιότητες ανακλαστικότητα, συμμετρία, μεταβατικότητα μαζί συνεπάγονται την τρίτη;

Λύση

4.5. "Συμμετρία + μεταβατικότητα ανακλαστικότητα.

Απόδειξη. Αν a ~ b, τότε και b ~ a, λόγω συμμετρίας. Αρα και a ~ a, λόγω μεταβατικότητας

Που είναι το σφάλμα;

Λύση

Εξετάστε αν η σχέση ~ στο Ζ που ορίζεται στις επόμενες 6 ασκήσεις είναι ανακλαστική, συμμετρική ή μεταβατική; Οπου η ~ είναι σχέση ισοδυναμίας, βρείτε την κλάση ισοδυναμίας κάθε ακεραίου.

4.6. x ~ y αν ο x y είναι περιττός.

Λύση

4.7. x ~ y αν ο x y είναι ζυγός.

Λύση

4.8. x ~ y αν ο x y θετικός.

Λύση

4.9. x ~ y αν ο x y 0.

Λύση

4.10. x ~ y αν .

Λύση

4.11. x ~ y αν xy 0.

Λύση

4.12. Στο Ζ* η ~ ορίζεται μέσω της x ~ y αν xy 0. Δείξτε ότι η ~ είναι σχέση ισοδυναμίας και βρείτε όλες τις κλάσεις ισοδυναμίας.

Λύση

4.13. Στο S = { - 4, - 3, - 2, - 1, 1, 2, ., 10 } η ~ ορίζεται μέσω της x ~ y αν xy 0 και 3 x - y. Δείξτε ότι η ~ είναι σχέση ισοδυναμίας και βρείτε όλες τις κλάσεις ισοδυναμίας.

Λύση

 

Επιστροφή στα περιεχόμενα