Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Properties of Relations
2.
Reflexive Closure
3.
Symmetric Closure
4.
Transitive Closure
4.1.
Warshall's Algorithm for Transitive Closure
5.
Frequently Asked Questions
5.1.
A set S with 9 distinct elements has how many binary relations?
5.2.
In what way can R be an asymmetric relation between A and B? 
5.3.
Can a relationship be symmetrical and asymmetrical?
6.
Conclusion
Last Updated: Mar 27, 2024

Properties of Relation

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Properties of Relation

In discrete mathematics, we examine certain characteristics of binary relations. Each characteristic applies only to binary relations within a single set. Each property that satisfies a relation is assigned a reflexive, symmetric, and transitive classification. Some properties of relations may or may not be satisfied, and a relation doesn't need to satisfy these properties.

The relation R is said to be a relation "on set A" because it is a relation from A to A. In other words, R⊆A×A.

Here we will explore these properties of relation.

Properties of Relations

There are 3 properties of relation:

  1. Reflexive Closure
  2. Symmetric Closure
  3. Transitive Closure

Reflexive Closure

In a binary relation R on a set A, a reflexive closure of R is the smallest reflexive relation of set S that contains relation R. To find Rr+, which is the reflexive closure relation of the binary relation R, we need to find the smallest reflexive relation R.

The formula Rr+= RU{(x, x) | x∈A}, where S is a set.
 

Example:

The relation R on the set S=[3,6,9,12] contains  the ordered pairs (3,9),(6,6),(9,9),(8,12). Determine the reflexive closure of R.

Solution:

R ={(3,9),(6,6),(9,9),(8,12)}

S = {3,6,9,12}
We know that reflexive closure of Rr+= RU{(x, x)|a ∈S} this means we have to include all the ordered pairs in the relation R. We need to find the smallest reflexive relation that contains R must include the ordered pair(3,3), (12,12).

So, Rr+={(3,9),(6,6),(9,9),(8,12),(3,3),(12,12)}.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Symmetric Closure

In a binary relation R on a set A, a symmetric closure of R is the smallest symmetric relation of set S that contains relation R. To find Rs+, which is the symmetric closure relation of the binary relation R, we need to find the smallest symmetric relation R.

The formula Rs+= RU{(x, y) | (y, x)∈S}, where S is a set.
 

Example: 

The relation R on the set S=[3,6,9,12] contains  the ordered pairs (3,6),(3,3)(3,9)(9,3)(9,9), and (12,3). Determine the symmetric closure of R.

Solution:

We have,

R ={(3,6),(3,3)(3,9)(9,3)(9,9),(12,3)}

S = {3,6,9,12}
We know that symmetric closure of Rs+= RU{(x, y) | (y, x)∈S} this means we have to include all the ordered pairs in the relation R.
We need to find the smallest symmetric relation that contains R must include the ordered pairs (6,3), (3,12).

So, Rs+={(3,6),(3,3)(3,9)(9,3)(9,9),(12,3),(6,3), (3,12)}.

Transitive Closure

In a binary relation R on a set A, the transitive closure of R is the smallest transitive relation of set S that contains relation R. To find Rt+, which is the transitive closure relation of the binary relation R, we need to find the smallest transitive relation R.

The formula Rt+= RU{(x, z) | (x, y)∈S then (y, z)∈S} where S is a set.

 

Example: 

The relation R on the set S=[3,6,9] contains the ordered pairs (3,3),(6,3) and (9,3). Determine the transitive closure of R.

Solution:

We have,

R ={(6,3),(3,9),(3,3)}

S = {3,6,9}
We know that symmetric closure of Rt+= RU{(x, z) | (x, y)∈S then (y, z)∈S} this means we have to include all the ordered pairs in the relation R.
We need to find the smallest transitive relation that contains R must include the ordered pair (6,9).

So, Rt+={(6,3),(3,9),(3,3),(6,9)}.

Warshall's Algorithm for Transitive Closure

It isn't always easy to find all ordered pairs in transitive closure. There are many efficient methods to find the transitive closure, including Warshall's Algorithm.

Example:

The transitive closure of the relation must be found by using the Warshall Algorithm given that the relation R={(6,3),(6,9)(9,3),(9,12),(12,3),(12,9)} on set S={3,6,9,12}.

Solution:

The first step is to represent the relation R in matrices by placing 1 in the position of each of the ordered pairs in the question and 0 in the other positions. 

illustrative image

A set of 4 elements consists of 4 steps. As a result, four steps are required to obtain the transitive closure of relation R.

Here are the steps:

  1. Consider the first column and the first row of the above matrix, i.e., C1 and R1. Then write all positions where 1 appears in column 1.
    C1={6,9,12}
    similarly, write all positions where  1 is present in row 1.
    R1= ∅
    Now, take the cross-product of C1 and R1.
    C1XR1= ∅, which means no ordered pair needs to be added.
     
  2. Now consider the 2nd column and 2nd row of the above matrix.
    C2= ∅
    R2={3,9}
    C2xR2= ∅, which means no ordered pair needs to be added.
     
  3. Now consider the 3rd column and 3rd row of the above matrix.
    C3={6,12}
    R3={3,12}
    C2xR2={(6,3)(6,12),(12,3)(12,12)}, which means we have to put 1 in all these positions. Here is the new matrix:
illustrative image

  4. Now consider the 4th column and 4th row of the above matrix.
      C4={6,9,12}
      R4={3,9,12}
      C4xR4={(6,3)(6,9)(6,12)(9,3)(9,9)(9,12),(12,3)(12,9)(12,12)}, which means we have to put 1 in all these positions. 
      Here is the new matrix:

illustrative image


Therefore the transitive closure Rt+= {(6,3)(6,9)(6,12)(9,3)(9,9)(9,12),(12,3)(12,9)(12,12)}.

Frequently Asked Questions

A set S with 9 distinct elements has how many binary relations?

There are nine elements in set S. S*S is the relation between S. This relation consists of 92 pairs of ordered elements. So, the number of binary relations is 2(9*9) = 281.

In what way can R be an asymmetric relation between A and B? 

Relationships are asymmetric when both antisymmetric and irreflexive aspects are present. Therefore, a transitive and asymmetric relationship must be in a strict partial order.

Can a relationship be symmetrical and asymmetrical?

A non-empty relationship can't be both symmetric and asymmetric since if a and b are related, they cannot be related in the same way.

Conclusion

In this blog, we have seen the properties of relations such as Reflexive, irreflexive, Symmetric, Antisymmetric, transitive, and equivalence by understanding them with some examples.

We hope that this blog has helped you enhance your knowledge about properties of relation and if you would like to learn more, check out our articles on the link. Do upvote our blog to help other ninjas grow. 

Happy Coding!

Previous article
Types of relation
Next article
Equivalence of Relations
Live masterclass