=
{ y 
S : x ~ y }
Καρτεσιανά γινόμενα. Μια σχέση σε συνολο
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. Δείξτε ότι η ~ είναι σχέση ισοδυναμίας και βρείτε όλες τις κλάσεις ισοδυναμίας.
στα περιεχόμενα