Skip to main content

5. 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.

Equivalence Class

Consider an equivalence relation R on a set A. The equivalence class of an element a ∈ A, is the set of elements of A to which element a is related. It is denoted by [a].

Example :

Let R be an equivalence relation on the set A = {4, 5, 6, 7} defined by R = {(4, 4), (5, 5), (6, 6), (7, 7), (4, 6), (6, 4)}. Determine its equivalence classes.

The equivalence classes are as follows :

[4] = [6] = {4, 6} ,                                          [5] = {5} ,                                                      [7] = {7}

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.
The set A together with a partial order relation R on the set A is called a partial ordered set or POSET and is denoted by (A, 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.

    n-Ary Relations

    A set of ordered n-tuples is called an n-ary relation. For a set A, a subset of the product set An is called an n-ary relation on A. In particular, a subset of A3 is called a ternary relation on A.

    Total Order Relation

    Consider a relation R on the set A. If it is also called the case that for all, a, b ∈ A, we have either (a, b) ∈ R or (b, a) ∈ R or a = b, then the relation R is known as a total order relation on set A.

    Circular Relation

    Consider a relation R on the set A. Relation R is called circular if (a, b) ∈ R and (b, c) ∈ R ⇒ (c, a) ∈ R. If a relation is symmetric for and transitive both, then the relation is a circular relation.


Previous                                  Next

Comments

Post a Comment