Equivalence relations

Equivalence Relations :

Let R be a relation on set A. If R is reflexive, symmetric, and transitive then it is said to be a equivalence relation.
Consequently, two elements a and b related by an equivalence relation are said to be equivalent.

Example – Show that the relation
R = \{(a,b)\:|\: a\equiv b (mod\:m)\} is an equivalence relation. a\equiv b (mod\:m) is the congruence modulo m function. It is true if and only if m divides a-b.

Solution – To show that the relation is an equivalence relation we must prove that the relation is reflexive, symmetric and transitive.

    1. Reflexive – For any element aa - a = 0 is divisible by m.
      \therefore a \equiv a (mod\:m). So, congruence modulo m is reflexive.
    2. Symmetric – For any two elements a and b, if (a,b)\in R or a\equiv b (mod\:m) i.e. a - b is divisible by m, then b - a is also divisible by m.
      \therefore b\equiv a (mod\:m). So Congruence Modulo m is symmetric.
    3. Transitive – For any three elements ab, and c if (a,b), (b,c) \in R then-
      (a-b) mod\:m = 0
      (b-c) mod\:m = 0
      Adding both equations,

         \begin{flalign*} &\Rightarrow (a-b) mod\:m + (b-c) mod\:m = 0\\ &\Rightarrow (a-b+b-c) mod\:m = 0\\ &\Rightarrow (a-c) mod\:m = 0 \end{flalign}

      \therefore a \equiv c (mod\:m). So, R is transitive.

Since the relation R is reflexive, symmetric, and transitive, we conclude that R is an equivalence relation.

Author: Deepak Chahar

Leave a Reply

Your email address will not be published. Required fields are marked *