Skip to main content

9. Equivalence and Partial Order Relations

 

Equivalence Relation

A relation R on a non-empty set A is an equivalence relation if it satisfies the following three properties :

  1. Relation R is reflexive i.e. if a ∈ A then every (a, a) ∈ R.
  2. Relation R is symmetric i.e. if a, b ∈ A and (a, b) ∈ R, then every (b, a) ∈ R.
  3. Relation R is transitive i.e. if a, b, c ∈ A, (a, b) ∈ R and (b, c)∈ R, then every (a, c) ∈ R.

Note: i. If R1 and R2 are equivalence relations then R1 ⋂ R2 is also an equivalence relation.
         ii. If R1 and R2 are equivalence relations then R1 ⋃ R2 may or may not be an equivalence relation.
        iii. If R is an equivalence relation, then R-1 is always an equivalence relation.

Examples :

Consider the following relations R on a set A = {1, 2, 3} such that

  1. R = {(1, 1), (2, 2), (3, 1), (1, 2), (1, 3), (2, 1), (3, 3)}
  2. R = {(1, 1), (1, 2), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)}
    1. Reflexive: Relation R is reflexive as 1, 2, 3 ∈ A, and (1, 1), (2, 2) and (3, 3) ∈ R.
    2. Symmetric: Relation R is symmetric because whenever (a, b) ∈ R, (b, a) also belongs to R.
              (3, 1) ∈ R ⇒ (1, 3) ∈ R,              (1, 2) ∈ R ⇒ (2, 1) ∈ R.
    3. Transitive: Relation R is transitive because whenever (a, b) and (b, c) belongs to R, (a, c) also belongs to R.
                 (3, 1) ∈ R and (1, 3) ∈ R              ⇒ (3, 3) ∈ R
                 (1, 2) ∈ R and (2, 1) ∈ R              ⇒ (1, 1) ∈ R
    So, as R is reflexive, symmetric and transitive. Hence R is an equivalence relation.

    1. Reflexive: Relation R is irreflexive as 1, 2, 3 ∈ A, but (2, 2) ∉ R.
      2. Hence, the relation R is not an equivalence relation. But we proceed further to check whether relation is symmetric and transitive or not.
    2. Symmetric: Relation R is not symmetric as (3, 1) ∈ R but (1, 3) doesn't belongs to R.
    3. Transitive: Relation R is not transitive as (1, 2) and (2, 3) belongs to R but (1, 3) doesn't belongs to R. Also (2, 3) and (3, 2) belongs to R but (2, 2) doesn't belongs to R.
    Hence, R is neither reflexive, nor symmetric and not transitive relation.

Compatible Relation

A binary relation on a set that is reflexive and symmetric is called a compatible relation. Every equivalence relation is compatible relation but every compatible relation need not to be an equivalence relation.

Partial Order Relation

A relation R on a non-empty set A is called a partial order relation if it satisfies the following three conditions :

  1. Relation R is reflexive i.e. if a ∈ A then every (a, a) ∈ R.
  2. Relation R is anti-symmetric i.e. if a, b ∈ A, (a, b) ∈ R and (b, a) ∈ R then a = b.
  3. Relation R is transitive i.e. if a, b, c ∈ A, (a, b) ∈ R and (b, c)∈ R, then every (a, c) ∈ R.

Examples :

Consider the following relations R on a set A = {1, 2, 3} such that

  1. R = {(1, 1), (2, 2), (1, 3), (2, 3), (3, 3)}
  2. R = {(1, 1), (1, 2), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)}
    1. Reflexive: Relation R is reflexive as 1, 2, 3 ∈ A, and (1, 1), (2, 2) and (3, 3) ∈ R.
    2. Anti-Symmetric: Relation R is anti-symmetric because whenever (a, b) ∈ R and (b, a) ∈ R then a = b.
           (1, 1) ∈ R ⇒ 1 = 1,                         (2, 2) ∈ R ⇒ 2 = 2,                       (3, 3) ∈ R ⇒ 3 = 3.
    3. Transitive: Relation R is transitive because whenever (a, b) and (b, c) belongs to R, (a, c) also belongs to R.
                 (3, 1) ∈ R and (1, 3) ∈ R              ⇒ (3, 3) ∈ R
                 (1, 2) ∈ R and (2, 1) ∈ R              ⇒ (1, 1) ∈ R
    So, as R is reflexive, anti-symmetric and transitive. Hence R is a partial order relation.

    1. Reflexive: Relation R is irreflexive as 1, 2, 3 ∈ A, but (2, 2) ∉ R.
      2. Hence, the relation R is not a partial order relation. But we proceed further to check whether relation is anti-symmetric and transitive or not.
    2. Anti-Symmetric: Relation R is not anti-symmetric as (1, 2) ∈ R and (2, 1) also belongs to R but 1 ≠ 2. Also (2, 3) ∈ R and (3, 2) also belongs to R but 2 ≠ 3.
    3. Transitive: Relation R is not transitive as (1, 2) and (2, 3) belongs to R but (1, 3) doesn't belongs to R. Also (2, 3) and (3, 2) belongs to R but (2, 2) doesn't belongs to R.
    Hence, R is neither reflexive, nor anti-symmetric and not transitive relation.

Comments

Post a Comment