318698614-Equivalence-Relations-a-ppt (2) (1).ppt

discrete math

1. EQUIVALENCE
RELATIONS

2. DEFINITION
An equivalence relationon a set S is a set Rof ordered pairs of
elements of S such that
(a,a)R for all a in S. 
(a,b)R implies (b,a) R 
(a,b)R and (b,c)R imply (a,c)R
Reflexive
Symmetric
Transitive

3. PROPERTIES OF EQUIVALENCE
RELATIONS
a
Reflexive
a b
Symmetric
a b c
Transitive

4. WHICH OF THESE RELATIONS ON {0, 1, 2, 3} ARE
EQUIVALENCE RELATIONS? DETERMINE THE
PROPERTIES OF AN EQUIVALENCE RELATION THAT THE
OTHERS LACK
a){ (0,0), (1,1), (2,2), (3,3) }
Has all the properties, thus, is an equivalence relation
b){ (0,0), (0,2), (2,0), (2,2), (2,3), (3,2), (3,3) }
Not reflexive: (1,1) is missing
Not transitive: (0,2) and (2,3) are in the relation, but not (0,3)
c){ (0,0), (1,1), (1,2), (2,1), (2,2), (3,3) }
Has all the properties, thus, is an equivalence relation
4

5. WHICH OF THESE RELATIONS ON {0, 1, 2, 3} ARE
EQUIVALENCE RELATIONS? DETERMINE THE
PROPERTIES OF AN EQUIVALENCE RELATION THAT THE
OTHERS LACK
a){ (0,0), (1,1), (1,3), (2,2), (2,3), (3,1), (3,2) (3,3) }
Not transitive: (1,3) and (3,2) are in the relation, but not (1,2)
b){ (0,0), (0,1) (0,2), (1,0), (1,1), (1,2), (2,0), (2,2), (3,3) }
Not symmetric: (1,2) is present, but not (2,1)
Not transitive: (2,0) and (0,1) are in the relation, but not (2,1)

6. NOTATION
Given a relation R, we usually write
a R b instead of
For example:
x = 1 instead of
instead of 
(a,b)R 
(x,1)  
(p,q)  
pq

7. PROPERTIES REVISITED
R is an equivalence relation on S if R is:
Reflexive:
aR afor all ain S
Symmetric:
aR b implies bR afor all a, bin S
Transitive:
aR band bR cimplies aR cfor all a,b,c in S

8. SUPPOSE THAT ZIS A NON-EMPTY SET, AND FIS A FUNCTION
THAT HAS Z AS ITS DOMAIN. LET RBE THE RELATION ON Z
CONSISTING OF ALL ORDERED PAIRS (X,Y) WHERE F(X) = F(Y),
MEANING THAT XAND YARE RELATED IF AND ONLY IF F(X) =
F(Y)
Show that Ris an equivalence relation on Z
a= afor all ain Z
a= bimplies b= afor all a,bin Z
a= band b= cimplies a= cfor all a,b,c, in Z.
= is reflexive, symmetric, and transitive
So = is an equivalence relation on Z!

9. IS ≤ AN EQUIVALENCE RELATION
ON THE INTEGERS?
1 ≤ 2, but 2 ≤ 1, so ≤ is not symmetric
Hence, ≤ is notan equivalence relation on Z.
(Note that ≤ isreflexive and transitive.)