Equivalene relation


For the set of cities on a map, consider the relation x r y if and only if city x is connected by a road to city y. A city is considered to be connected to itself, and two cities are connected even though there are cities on the road between them. Is this an equivalence relation or a partial ordering? Explain.


Let R be a relation on set A . If R is reflexive, symmetric, and transitive then it is said to be equivalence relation. Consequently, two elements a and b related by an equivalence relation are said to be equivalent .
Example - Show that relation R ={(a,b)|a=b(mod m)} is an equivalence relation.
Solution -

  1. Reflexive - for element a-a=0 is divisible by m.
    a=a(mod m) . So congruence modulo m is reflexive.
  2. Symmetric - For any two elements a and b , if (a,b) €R i.e. Congruence Modulo m is Symmetric.
  3. Transitive - For any three elements a,b and c if (a,b), (b,c) € R then
    (a-b) mod m =0
    (b-c) mod m =0
    Adding both above equations (a-c)mod m =0
    So R is transitive
    Therefore R is an equivalence relation