Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Definition
2.1.
Reflexive 
2.1.1.
Example
2.2.
Symmetric
2.2.1.
Example
2.3.
Transitive
2.3.1.
Example
3.
Proof of Equivalence Relation
3.1.
Proof of Reflexive Property
3.2.
Proof of Symmetric Property
3.3.
Proof of Transitive Property
4.
Examples of Equivalence Relation
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Equivalence of Relations

Author Aniket Majhi
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

If you have a basic knowledge about the relations and sets and their different properties, you are good to go. Here in this blog post, I will be discussing the Equivalence of Relations with pertinent details. At the end of this blog, everything will be clear to you.
So, without further ado, let’s start the topic.

Definition

A relation on a set is an equivalence relation if the relation is reflexivesymmetric, and transitive. Got confused about what is reflexive, symmetric and transitive properties?
Let’s first discuss each one of them.

Reflexive 

A relation R on a set A is reflexive if (a, a) ∈ R for every element a ∈ A.
Too many mathematical terms, right?
Okay, let me simplify it,
Consider a set A = {1 , 2 , 3 }.
Let’s define all possible elements in a relation(Cartesian product) in the form of a matrix.
A X A = 

Now, the relations that contain the diagonal elements of the above matrix are considered the Reflexive relations.
R = 

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

Example

Let the set be A = {1, 2, 3}
Let’s define some of the relations on the set,
R1 = {(1,1),(2,2),(3,3)}
R2 = {(1,1),(2,2),(1,3),(2,3)}
R3 = {(1,1),(2,2),(3,3),(1,3),(2,3)}
Now, First, try to identify the Reflexive relations by yourself.
If your answer is R1 and R3, then you are right.
You might be thinking, why R3, right?
See, We are only concerned about the (a, a) ∈ R for all a ∈ A. If any additional (a,b) ∈ R where a,b ∈ A then also the Relation would be Reflexive.
I think now you got it.
Let’s now move to the Symmetric Property.

Symmetric

A relation R on a set A is Symmetric if (b, a) ∈ R whenever (a, b) ∈ R for all a, b ∈ A.
Here also we are considering the same set A = {1,2,3}
So, according to the definition, if (1,2) ∈ R, then (2,1) must also belong to R.
Let’s understand it in terms of a matrix,
Let’s R = {(1,2),(1,1),(2,1),(2,3),(3,2)}
The matrix representation of the relation is,
R = 

RT =  

If R = RT, then only the relation is symmetric.

Example

Let’s define some of the relations over the set A = {1, 2, 3}
R1 = {(1,1),(1,2),(2,1),(2,2)}
R2 = {(1,1),(1,2),(2,2),(2,3)}
R3 = {(2,3),(3,2),(1,2)}
Try to identify the symmetric relations.
If your answer is only R1, then you are correct.
For, R1 
(1,1) is present
(1,2) is present, and (2,1) is also present.
(2,2) is present
For, R2 
(1,2) is present but not (2,1)
(2,3) is present but not (3,2)
For, R3 
(1,2) is present but not (2,1)
I hope it is clear to you.
Let’s now move to the Transitive property,

Transitive

A Relation R on a set is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R, then (a,c) ∈ R for a,b,c ∈ A.
Now for the set A = {1 , 2, 3}
If (1, 2) ∈ R and (2,3) ∈ R then (1,3) ∈ R.

Example

Let’s define some of the relations over the set A = {1, 2, 3}
R1 = {(1,1),(1,2),(2,1),(2,2)} Transitive
R2 = {(1,1),(1,2),(2,2),(2,3)} Transitive
R3 = {(2,3),(3,2),(1,2)} Not Transitive (2, 3) ∈ R and (3, 2) ∈ R but (2, 2) ∉ R.
So, a binary relation on a set is an Equivalence Relation If it is Reflexive, Symmetric and Transitive.

So, let a,b,c ∈ A.
If (a,a) ∈ R (Reflexive).
If (a,b) ∈ R if and only if (b ,a) ∈ R ( Symmetric).
If (a,b) ∈ R and (b,c) ∈ R then (a,c) ∈ R (Transitive)

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

Proof of Equivalence Relation

Let us consider an example to prove a relation as an Equivalence Relation.
Let’s define a relation R on the natural numbers N as (a,b) ∈ R if and only if a == b.

Proof of Reflexive Property

Since every natural number is equal to itself, relation R is reflexive for every ∈ A, (a, a) ∈ R.

Proof of Symmetric Property

For a , b ∈ A if (a,b) ∈ R then a == b.
Now if a == b then conversely b == a which means (b , a) ∈ R.
So relation R is Symmetric.

Proof of Transitive Property

For a , b, c ∈ A if (a,b) ∈ R then a == b and (b,c) ∈ R then b == c.
Now if a == b and b == c then a == c. which means (a , c) ∈ R.
So relation R is Transitive.

Since R is Reflexive, Symmetric and Transitive, R is an Equivalence Relation.

Examples of Equivalence Relation

I have provided some of the typical examples of the Equivalence Relation, which might be helpful for you.

1. Let “≃” denote the relation on the set of symmetric matrices (symmetric means A = At ) defined as follows. A ≃ B if A = Bt.
Show that the above relation is an equivalence relation.

Ans: Let S be the set of symmetric matrices and R be the relation.
Now A, B, C ∈ S.

Reflexive:
We know that A = At(as A is a symmetric matrix). So A ≃ A.
So (A, A) ∈ R.
R is Reflexive.

Symmetric:
If A ≃ B, then A = B--------------------(i)
Now We can write B as,
B = (Bt)t
B = A(From i), implying B ≃ A.
R is Symmetric.

Transitive:
If A ≃ B, then A = B--------------------(i)
If B ≃ C, then B = C--------------------(ii)
Now we know that B = Bt (B being symmetric)
From (i), we get A = Bt = B 
From (ii), we get A = Ct, implying A ≃ C.
R is Transitive.

We showed that the relation R is Reflexive, Symmetric and Transitive, so R is an Equivalence relation.

2. Show that a relation F defined on the set of real numbers R as (a, b) ∈ F if and only if |a| = |b| is an equivalence relation.

Ans: We have to show that F is an equivalence relation.

Reflexive:
For any real number a ∈ R,
We know that |a| = |a|, implying (a, a) ∈ F.
Therefore, F is Reflexive.

Symmetric:
For any real numbers a , b  ∈ R let (a , b) ∈ F which implies |a| = |b|.
And again |a| = |b| implies |b| = |a| so (b,a)  ∈ F.
Therefore, F is Symmetric.

Transitive:
For a, b, c ∈ R,
Let  (a , b) ∈ F which implies |a| = |b|.
And (b , c) ∈ F which  implies |b| = |c|.
Now |a| = |b| and |b| = |c| implies |a| = |c|.
So, (a, c) ∈ F.
Therefore, F is Transitive.

We showed that relation F is Reflexive, Symmetric and Transitive. So F is an equivalence relation.

FAQs

  1. What is equivalence relation?
    A binary relation R on a set A is an equivalence relation if R is reflexive, symmetric and transitive. If any of the three conditions do not hold, the relation will not be equivalent.
     
  2. How do you find out the equivalence relation?
    If you want to find out whether a relation is an equivalence or not, then you need to show that the relation is reflexive, symmetric and transitive.
     
  3.  What are the three conditions to prove an equivalence relation?
    The three conditions for the equivalence relation are Reflexive, Symmetric and Transitive.
     
  4. What is an equivalence class?
    Let R be an equivalence relation on a set A. All elements related to an element a ∈ A are called the equivalence class.
     
  5.  Is an Empty relation an Equivalent relation?
     An empty relation on an empty set is equivalent, but an empty relation is not equivalent on a non-empty set.

Key Takeaways

In this article, we have extensively discussed the Equivalence of Relations and their implementations.

We have observed different aspects of Equivalence Relation, such as an equivalence relation, the conditions associated with equivalence relation and how to identify an equivalence relation with some examples.

We hope that this blog has helped you enhance your knowledge regarding the Equivalence of Relations and if you would like to learn more, check out our articles on Probability Permutations and Combinations. Do upvote our blog to help other ninjas grow.

Head over to our practice platform Coding Ninjas Studio to practise top problems, attempt mock tests, read interview experiences, and much more.!

Happy Reading!
 

Previous article
Properties of Relation
Next article
Partial Order Relations
Live masterclass