Closure of Relations and Equivalence Relations

Closure of Relations :

Consider a relation R on set AR may or may not have a property P, such as reflexivity, symmetry, or transitivity.

if there is a relation S with property P containing R such that S is the subset of every
relation with property P containing R, then S is called as closure of R with respect to P

We can obtain closures of relations with respect to property P in the following ways –

  1. Reflexive Closure – \Delta = \{(a,a)\:|\:a\in A\} is the diagonal relation on set A. The reflexive closure of relation R on set A is R\cup \Delta.
  2. Symmetric Closure – Let R be a relation on set A, and let R^{-1} be the inverse of R. The symmetric closure of relation R on set A is R\cup R^{-1}.
  3. Transitive Closure – Let R be a relation on set A. The connectivity relation is defined as – R^* = \bigcup\limits_{n=1}^{\infty} R^n. The transitive closure of R is R^*.

Example – Let R be a relation on set \{1, 2, 3, 4\} with R = \{(1,1), (1,4), (2,3), (3,1), (3,4)\}. Find the reflexive, symmetric, and transitive closure of R.

Solution –
For the given set, \Delta = \{(1, 1), (2, 2), (3, 3), (4, 4)\}. So the reflexive closure of R is R \cup \Delta = \{(1,1), (1,4), (2,2), (2,3), (3,1), (3,3), (3,4), (4,4)\}

For the symmetric closure we need the inverse of R, which is
R^{-1} = \{(1,1), (1,3), (3,2), (4,1), (4,3)\}.
The symmetric closure of R is-
\{(1,1), (1,3), (1,4), (2,3), (3,1), (3,2), (3,4), (4,1), (4,3)\}

For the transitive closure, we need to find R^*.
\therefore we need to find R^1, R^2, ... , until R^{n} = R^{n-1}. We stop when this condition is achieved since finding higher powers of R would be the same.
R^{1} = \{(1,1), (1,4), (2,3), (3,1), (3,4)\}
R^{2} = \{(1,1), (1,4), (2,1), (2,4), (3,1), (3,4)\}
R^{3} = \{(1,1), (1,4), (2,1), (2,4), (3,1), (3,4)\}
Since, R^{2} = R^{3} we stop the process.
Transitive closure, R^* = R^1 \cup R^2 –
\{(1,1), (1,4), (2,1), (2,3), (2,4), (3,1), (3,4)\}

Author: Deepak Chahar

Leave a Reply

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