Skip to main content

4. Types of Relations

 

Types of Relations

Consider a given set A such that A = {1, 2, 3} on which the following types of relations are defined.

Reflexive Relation

A relation R on set A is said to be a reflexive if (a, a) ∈ R or aRa for every a ∈ A. reflexive relation is also known as diagonal relation denoted as ΔA.

If cardinality of a set B is n i.e. |B| = n, then total number of reflexive relations = 1 x 2n2-n = 2n2-n.
Total number of elements in B x B = n2 i.e. |B2| = n2 and total number of diagonal elements is n, then total number of non-diagonal elements is (n2-n). For reflexive, the diagonal elements should be necessarily included in the set B x B i.e. the diagonal elements have only one choice but other elements may or may not be in the set B x B i.e. they have two choices. So the total diagonal elements can be selected in 1n ways and the total non-diagonal elements can be selected in 2n2-n ways.

Irreflexive Relation

A relation R on set A is said to be irreflexive if (a, a) ∉ R for every a ∈ A.

If cardinality of a set B is n i.e. |B| = n, then total number of irreflexive relations = 1 x 2n2-n = 2n2-n.
Total number of elements in B x B = n2 i.e. |B2| = n2 and total number of diagonal elements is n, then total number of non-diagonal elements is (n2-n). For irreflexive, the diagonal elements should not be necessarily included in the set B x B i.e. the diagonal elements have only one choice but other elements may or may not be in the set B x B i.e. they have two choices. So the total diagonal elements can be selected in 1n ways and the total non-diagonal elements can be selected in 2n2-n ways.

Examples

R = ∅ is an irreflexive relation.
R = A x A is a reflexive relation.
R = {(1, 1), (2, 2), (3, 3)} is a reflexive relation.
R = {(1, 2), (2, 1), (1, 1), (2, 2)} is neither a reflexive nor an irreflexive relation.
R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)} is a reflexive relation.
R = {1, 2), (2, 3), (1, 3)} is an irreflexive relation.

Symmetric Relation

A relation R on a set A is said to be symmetric if and only if whenever aRb then bRa, that is, whenever (a, b) ∈ R then (b, a) ∈ R.

If cardinality of a set B is n i.e. |B| = n, then total number of symmetric relations = 2n x 2(n2-n)/2 = 2n(n+1)/2.
Total number of elements in B x B = n2 i.e. |B2| = n2 and total number of diagonal elements is n, then total number of non-diagonal elements is (n2-n). For symmetric, the diagonal elements may or may not be included in the set B x B i.e. the diagonal elements have two choices. But for non-diagonal elements, let's take an example, if (a, b) ∈ R then (b, a) must be included for symmetric relation, and if (a, b) ∉ R then (b, a) should not be included in the relation i.e. we need to choose from only half of non-diagonal elements and we can do that by two choices. So the total diagonal elements can be selected in 2n ways and the total non-diagonal elements can be selected in 2(n2-n)/2 ways.

Anti-symmetric Relation

A relation R on a set A is said to be anti-symmetric if and only if whenever aRb and bRa then a = b, that is, whenever (a, b) ∈ R and (b, a) ∈ R then a = b. In other words, if (a, b) ∈ R then (b, a) ∉ R, but if (b, a) ∈ R then a must be equal to b (i.e. a = b), then only the relation R will be an anti-symmetric relation.

If cardinality of a set B is n i.e. |B| = n, then total number of anti-symmetric relations = 2n x 3(n2-n)/2.
Total number of elements in B x B = n2 i.e. |B2| = n2 and total number of diagonal elements is n, then total number of non-diagonal elements is (n2-n). For anti-symmetric, the diagonal elements may or may not be included in the set B x B i.e. the diagonal elements have two choices. But for non-diagonal elements, let's take an example, if (a, b) ∈ R then (b, a) ∉ R or (b, a) ∈ R then (a, b) ∉ R for anti-symmetric relation, and if (a, b) ∉ R then (b, a) should not be included in the relation i.e. we need to choose from only half of non-diagonal elements and we can do that by three choices. So the total diagonal elements can be selected in 2n ways and the total non-diagonal elements can be selected in 3(n2-n)/2 ways.

Asymmetric Relation

A relation R on a set A is said to be asymmetric if for every aRb, (b, a) does not belong to R i.e. (a, b) ∈ R implies that (b, a) ∉ R.

Note: A relation is asymmetric if and only if it is both anti-symmetric and irreflexive.

If cardinality of a set B is n i.e. |B| = n, then total number of asymmetric relations = 1n x 3(n2-n)/2 = 3(n2-n)/2
Total number of elements in B x B = n2 i.e. |B2| = n2 and total number of diagonal elements is n, then total number of non-diagonal elements is (n2-n). For asymmetric, the diagonal elements should not be included in the set B x B i.e. the diagonal elements have only one choice. But for non-diagonal elements, let's take an example, if (a, b) ∈ R then (b, a) ∉ R or (b, a) ∈ R then (a, b) ∉ R for asymmetric relation, and if (a, b) ∉ R then (b, a) should not be included in the relation i.e. we need to choose from only half of non-diagonal elements and we can do that by three choices. So the total diagonal elements can be selected in 1n ways and the total non-diagonal elements can be selected in 3(n2-n)/2 ways.

Examples

R = {(1, 2), (2, 1)} is a symmetric relation.
R = {(2, 3), (3, 2), (1, 1), (3, 3)} is a symmetric relation.
R = {(1, 1), (2, 2), (3, 3)} is a symmetric and an anti-symmetric relation.
R = ∅ is a symmetric, an anti-symmetric and an asymmetric relation.
R = A x A is a symmetric relation.
R = {(1, 2), (2, 3), (1, 3)} is an anti-symmetric and an asymmetric relation.
R = {(1, 2), (2, 1), (2, 3), (3, 3)} is neither symmetric, nor anti-symmetric and nor asymmetric.
R = {(1, 2), (2, 2), (3, 3)} is an anti-symmetric relation.

Transitive Relation

A relation R on a set A is said to be transitive if and only if whenever aRb and bRc then aRc, that is whenever (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R. Thus R is not transitive if there exists a, b, c ∈ A such that (a, b), (b, c) ∈ R but (a, c) ∉ R.

Examples

R = {(1, 2), (2, 1), (1, 1), (2, 2)} is transitive relation.
R = {(1, 1), (2, 2), (3, 3)} is transitive relation.
R = {(1, 2)} is transitive relation as there does not exist (b, c).
R = {(1, 2), (1, 3)} is transitive relation as there does not exists (a, b) and (b, c).
R = {(1, 2), (3, 2)} is transitive relation as there does not exists (a, b) and (b, c).
R = {(1, 2), (2, 3), (1, 3), (1, 1)} is transitive relation.
R = {(3, 1), (2, 3)} is not a transitive relation as (a, b) and (b, c) exists but (a, c) i.e. (2, 1) does not exist.

Closure Properties of Relations

The closure property means that the a set is closed for some mathematical operation.

Reflexive Closure

To obtain the reflexive closure of a relation, append all other diagonal elements (a, a) of cross product of a set (A x A) in the relation that are initially not in the relation.

Let R be a relation on a set A, then
R ⋃ ΔA is the reflexive closure of R.

Example: Let A = {1, 2, 3}. Let R is a relation on A defined by R = {(1, 1), (1, 3), (2, 3)}, then
Reflexive closure of R is
RF = R ⋃ ΔA = {(1, 1), (1, 3), (2, 2), (2, 3), (3, 3)}

Symmetric Closure

To obtain the symmetric closure of a relation, append all pairs (b, a) in the relation that are initially not in the relation whenever (a, b) belongs to relation.

Let R be a relation on a set A, then
R ⋃ R-1 is the symmetric closure of R.

Example: Let A = {1, 2, 3}. Let R is a relation on A defined by R = {(1, 1), (1, 3), (2, 3)}, then
Symmetric closure of R is
RS = R ⋃ R-1 = {(1, 1), (1, 3), (3, 1), (2, 3), (3, 2)}

Transitive Closure (Warshall's Algorithm)

To obtain the transitive closure of a relation, follow the following steps with an example of a set A = {1, 2, 3} defined by a relation R = {(1, 1), (1, 3), (2, 2), (3, 1), (3, 2)}:

  1. Representation in matrix form: Firstly, represent the cross product of the set in matrix form such that mark '1' in the position of ordered pair that are present in the relation and mark '0' to the position of ordered pair that are not present in the relation.

                 1           2           3
            1       1           0           1
            2   0           1           0
            3   1           1           0

  2. Make 2 rows and columns equal to the number of elements in the given set. In the first column of first row, write a set including the row elements of first column of matrix that has been marked as '1'. Similarly, write in the other columns of the first row.
    In the first column of second row, write a set including the column elements of first row of matrix that has been marked as '1'. Similarly, write in the other columns of second row.

                     I                  II              III
          C         {1, 3}           {2, 3}           {1}
          R     {1, 3}             {2}           {1, 2}

  3. Write all the ordered pairs obtained by the cross product as first row by second row of two sets of each column. Append the ordered pairs in the relation that are initially not in the relation.

    R = {(1, 1), (1, 3), (3, 1), (3, 3), (2, 2), (3, 2), (1, 1), (1, 2)}

  4. Repeat the steps till all the ordered pairs obtained by the cross product belongs to the relation.

Note: We can also check from this theorem whether the given relation is transitive or not. If any ordered pair is found such that it does not belongs to the relation initially, then the relation is not a transitive relation.


Previous                                  Next

Comments

Post a Comment