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:

Reflexive Closure

Symmetric Closure

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 R_{r}^{+}, which is the reflexive closure relation of the binary relation R, we need to find the smallest reflexive relation R.

The formula R_{r}^{+}= 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 R_{r}^{+}= 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, R_{r}^{+}={(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 R_{s}^{+}, which is the symmetric closure relation of the binary relation R, we need to find the smallest symmetric relation R.

The formula R_{s}^{+}= 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 R_{s}^{+}= 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, R_{s}^{+}={(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 R_{t}^{+}, which is the transitive closure relation of the binary relation R, we need to find the smallest transitive relation R.

The formula R_{t}^{+}= 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 R_{t}^{+}= 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, R_{t}^{+}={(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.

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:

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.

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.

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:

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:

Therefore the transitive closure R_{t}^{+}= {(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.