Home » Equivalence Relations

Equivalence Relations

A relation R on a set A is called an equivalence relation if it satisfies following three properties:

  1. Relation R is Reflexive, i.e. aRa ∀ a∈A.
  2. Relation R is Symmetric, i.e., aRb ⟹ bRa
  3. Relation R is transitive, i.e., aRb and bRc ⟹ aRc.

Example: Let A = {1, 2, 3, 4} and R = {(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)}.

Show that R is an Equivalence Relation.

Solution:

Reflexive: Relation R is reflexive as (1, 1), (2, 2), (3, 3) and (4, 4) ∈ R.

Symmetric: Relation R is symmetric because whenever (a, b) ∈ R, (b, a) also belongs to R.

Example: (2, 4) ∈ R ⟹ (4, 2) ∈ R.

Transitive: Relation R is transitive because whenever (a, b) and (b, c) belongs to R, (a, c) also belongs to R.

Example: (3, 1) ∈ R and (1, 3) ∈ R ⟹ (3, 3) ∈ R.

So, as R is reflexive, symmetric and transitive, hence, R is an Equivalence Relation.

Note1: If R1and R2 are equivalence relation then R1∩ R2 is also an equivalence relation.

Example: A = {1, 2, 3}
                 R1 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
                 R2 = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}
                 R1∩ R2 = {(1, 1), (2, 2), (3, 3)}

Note2: If R1and R2 are equivalence relation then R1∪ R2 may or may not be an equivalence relation.

Example: A = {1, 2, 3}
                 R1 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
                 R2 = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}
                 R1∪ R2= {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2)}

Hence, Reflexive or Symmetric are Equivalence Relation but transitive may or may not be an equivalence relation.

Inverse Relation

Let R be any relation from set A to set B. The inverse of R denoted by R-1 is the relations from B to A which consist of those ordered pairs which when reversed belong to R that is:

R-1 = {(b, a): (a, b) ∈ R}  

Example1: A = {1, 2, 3}
                   B = {x, y, z}

Solution: R = {(1, y), (1, z), (3, y)
               R-1 = {(y, 1), (z, 1), (y, 3)}
                  Clearly (R-1)-1 = R

Note1: Domain and Range of R-1 is equal to range and domain of R.

Example2: R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (3, 2)}
                R-1 = {(1, 1), (2, 2), (3, 3), (2, 1), (3, 2), (2, 3)}

Note2: If R is an Equivalence Relation then R-1 is always an Equivalence Relation.

Example: Let A = {1, 2, 3}
                    R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
                    R-1 = {(1, 1), (2, 2), (3, 3), (2, 1), (1, 2)}
                    R-1 is a Equivalence Relation.

Note3: If R is a Symmetric Relation then R-1=R and vice-versa.

Example: Let A = {1, 2, 3}
                    R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3), (3, 2)}
                    R-1 = {(1, 1), (2, 2), (2, 1), (1, 2), (3, 2), (2, 3)}

Note4: Reverse Order of Law
     (SOT)-1 = T-1 or S-1
     (ROSOT)-1 = T-1 or S-1 or R-1.


You may also like