Math Concepts

Equivalence Relation

15th Oct '200 views8 mins read

Table of Contents 

15 October  2020

Reading Time: 7 Minutes

Introduction

A relation is a subset of a cross-product of two sets. Thus, if A and B are two sets, then a relation from A to B is a subset of \(\begin{align}A \times B\end{align}\)
So, R is a relation from A to \(\begin{align}B \Leftrightarrow R \subseteq A \times B,\end{align}\)
     We are here to learn about a special type of relation called equivalence relations. The term equivalent means to be equal in value, function, or meaning. The relation of equality is an example of equivalence relations that follows the following properties.
                            x =x     (reflexive property)
                    If x = y, then y =x          (symmetric property)
                    If x = y and y = z, then x = z        (transitive property)

If all these hold true, it is known as an equivalence relation.


Equivalence Relation

Let us now study equivalence relations in detail.

What is an equivalence relation?

An equivalence relation on a set A is defined as a subset of its cross-product, i.e. \(\begin{align}A \times A\end{align}\) . Equalities are an example of an equivalence relation. For example, in a given set of triangles, ‘is similar to’ denotes equivalence relations. Another example would be the modulus of integers.

Equivalence Properties 

 An equivalence relation is a collection of the ordered pair of the components of A and satisfies the following properties -

  1. Reflexive -  x R x, for all \(\begin{align}x \in A\end{align}\)
  2. Symmetric - x R y implies y R x, for all x,\(\begin{align}y \in A\end{align}\)
  3. Transitive - x R y and y R z imply x R z, for all x,y,\(\begin{align}z \in A\end{align}\)

Equivalence Properties Images


Equivalence Relation Examples

To understand how equivalence relation examples look we should look at some common ones. Sp, equivalence relation examples include:

1. Let F be a set of fractions such that
             \(\begin{align}\{ \frac{a}{b}:a,b \in Z,\rm{and}\,\,b \ne 0\} \end{align}\)
            Then, \(\begin{align}\frac{p}{q}\,R\,\frac{r}{s}\end{align}\), If ps = rq is an equivalence relation.

2. For any set A, the identity relation is an equivalence relation.

3. Equalities is an important example of equivalence relations.

4. Modulus  \(\begin{align}( \equiv )\end{align}\)  are also a type of equivalence relation.


Equivalence relation Proof 

Let us look at an example in Equivalence relation to reach the equivalence relation proof.

If R is a relation on the set of ordered pairs of natural numbers such that \(\begin{align}\left\{ {\left( {p,q} \right);\left( {r,s} \right)} \right\} \in R,\end{align}\), only if pq = rs.Let us now prove that R is an equivalence relation. 

To do that, we need to prove that R follows all the three properties of equivalence relation, i.e. it is reflexive, symmetric, and transitive.

Reflexive

According to this property, if \(\begin{align}\left( {p,p} \right) \in R\end{align}\), for every \(\begin{align}p \in N\end{align}\)

For all ordered pairs of natural numbers:

\(\begin{align}\{ \left( {p,q} \right),\left( {p,q} \right) \in R.\end{align}\)

Here, we can say pq = pq for all natural numbers.

Thus, the reflexive property is proved………….(1)

Symmetric

According to this property if \(\begin{align}\left( {p,q} \right) \in R,\end{align}\) then \(\begin{align}\left( {q,p} \right) \in R\end{align}\) should also hold true.

For the set of Natural numbers,

If \(\begin{align}\left\{ {\left( {p,q} \right),\left( {r,s} \right)} \right\} \in R,\rm{then}\,\,\left\{ {\left( {r,s} \right),\left( {p,q} \right)} \right\} \in R.\end{align}\)

Since multiplication is commutative in Natural numbers, we can say ps = rq

Thus, \(\begin{align}\left\{ {\left( {r.s} \right),\left( {p,q} \right)} \right\} \in R\end{align}\)

Thus, the symmetric property is proved……………(2)

Transitive Property 

According to this property, if \(\begin{align}\left( {p,q} \right),\left( {q,r} \right) \in R,\end{align}\) then \(\begin{align}\left( {p,r} \right) \in R\end{align}\)

For a given set of ordered pairs in Natural numbers,

if \(\begin{align}\{ \left( {p,q} \right),\left( {r,s} \right) \in R\end{align}\) and  \(\begin{align}\left\{ {\left( {r,s} \right),\left( {x,y} \right)} \right\} \in R,\end{align}\)

then \(\begin{align}\{ \left( {p,q} \right),\left( {x,y} \right) \in R.\end{align}\)

Let us here assume that {(p,q), (r,s)}  R and {(r,s), (x,y)}  R.

Then we get that ps= qr and ry = sx.

This further implies that \(\begin{align}\frac{p}{q} = \frac{r}{s}\,\rm{and}\,\frac{r}{s} = \frac{x}{y}\end{align}\)

Thus, \(\begin{align}\frac{p}{q} = \frac{x}{y}\end{align}\)

Thus, py = xq.

Thus,\(\begin{align}\left\{ {\left( {p,q} \right),\left( {x,y} \right)} \right\} \in R.\end{align}\)

Thus, the transitive property is proved……………..(3)

From (1), (2), and (3) we prove equivalence relation in Natural Numbers. This is basically what entails a equivalence relation proof.


Equivalence Questions

Example 1

 

 

A relation R is defined on the set of Integers Z by “xRy if x – y leaves a remainder of 0, when divided by 10. ” for x, y ∈ Z. Show that R is an equivalence relation on Z.

Solution:

The Hypothesis x-y = 0 is true when x-y is divisible by 10. Let us prove this.

(i) Let x ∈ Z. Then x – x =0 is divisible by 10. Therefore xRx holds true for all x in Z. Hence, R is reflexive.

(ii) Let x, y  ∈ Z , and xRy hold true. Then x – y is divisible by 10 and therefore y-x is also divisible by 10.

Thus, xRy ⇒ yRx . Hence, R is symmetric.

(iii) Let x, y, z ∈ Z , and xRy, yRz both hold true. Then x – y and y – z are both divisible by 10.

Therefore x – y = (x – y) + (y – z) is divisible by 10.

Thus, xRy and yRz  ⇒ xRz  Hence, R is transitive.

Since R is reflexive symmetric transitive. Hence, R is an equivalence relation on Z.

Example 2

 

 

Let P be the set of all lines in three-dimensional space. A relation R is defined on P by “aRb if and only if a lies on the plane of b” for a, b ∈ P.

Check if R is an equivalence relation.

Solution:

(i) Reflexive: Let a ∈ P. Then a is coplanar with itself.

Therefore, aRa holds for all a in P.

Hence, R is reflexive

(ii)  Symmetric: Let a, b ∈ P and aRb holds true. Then a lies on the plane of b.

Therefore, b lies on the plane of a. Thus, aRb ⇒  bRa. Hence, R is symmetric.

(iii) Transitive: Let a, b, c ∈ P and aRb, bRc both hold true. Then a lies in the plane of b and b lies in the plane of c. This however does not always imply that a lies in the plane of c.

That is, aRb and bRc do not necessarily imply aRc.

Hence, R is not transitive.

Since R is reflexive and symmetric but not transitive so, R is not an equivalence relation on set Z.
 
Let us now have a look at some conditions where relations do not follow all the three equivalence properties. 


Reflexive and Symmetric but not Transitive

Let us look a a case when the set is Reflexive and Symmetric but not Transitive.

Let  X = {1,2,3}

A relation R is defined on X as

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

If a ∈ X,(a,a) ∈ R, that implies {(1,1),(2,2),(3,3)} ∈ R. Hence, it is reflexive.

If a,b ∈ X, (x,y) ∈ R and (y,x) ∈ R,that implies {(1,2),(2,1),(2,3),(3,2)} ∈ R . Hence, it is symmetric.

If  a,b ∈ R and b,c ∈ R, that implies (1,2) ∈ R and (2,3) ∈ R

But  \(\begin{align}\left( {1,3} \right) \notin R.\end{align}\)  Hence, it is not transitive.

Thus, the relation is reflexive and symmetric but not transitive. Also, not an equivalence relation.


Symmetric and Transitive but not Reflexive

Let us look at a case when the set is Symmetric and Transitive but not Reflexive.

Let X = {−3, −4}.

A relation R is defined on X as:

R = {(−3, −4), (−4, −3), (−3, −3)}

Relation R is not reflexive as (−4, −4) ∉ R.

Relation R is symmetric as (−3, −4) ∈ R and (−4, −3)∈ R.

It is seen that (−3, −4), (−4, −3) ∈ R. Further, (−3, −3) also ∈ R.

Hence, the relation R is transitive.

Thus, relation R is symmetric and transitive but not reflexive. And also, not an equivalence relation.


Reflexive and Transitive but not Symmetric

Let us have a look at when a set is Reflexive and Transitive but not Symmetric.

A relation R is defined as 

R ={(a,b) : a3 b3

Clearly (a, a) ∈ R since a = a3

Hence, R is reflexive.

Moving on,

(2, 1) ∈ R (since 23 ≥ 13)

But,

(1, 2) ∉ R (as 13 < 23)

Hence,R is not symmetric.

Again,

Let (a, b), (b, c) ∈ R.

⇒ a3 ≥ b3 and b3 ≥ c3

⇒ a3 ≥ c3

⇒ (a, c) ∈ R

Hence, R is transitive.

Thus we can conclude that the relation R is reflexive and transitive but not symmetric. And thus, not an equivalence relation.


SUMMARY

  • Equivalence relations are a special type of relation. They are derived from the term equivalent meaning to be equal in value, function, or meaning.
  • They are Reflexive -  x R x, for all x ∈ A
  • They are Symmetric - x R y implies y R x, for all x,y ∈ A
  • They are Transitive - x R y and y R z imply x R z, for all x,y,z ∈ A
  • Only when a relation satisfies all the three properties, it can be classified as an equivalence relation. This is the equivalence relation proof. 
  • We even looked at cases when sets are reflexive symmetric transitive, and when sets are reflexive and symmetric but not transitive and also when sets are reflexive and transitive but not symmetric and lastly when a set is symmetric and transitive but not reflexive. 

Written  by Aarti Agarwal


FAQS

What is an equivalence relation?

An equivalence relation on a set A is a relation that is reflexive, symmetric, transitive.      

What is the use of equivalence relations?

It allows us to partition a set in such a way that, the components of a given part for all our purposes are equal.

Equivalence relation proof?

To check for equivalence relation in a given set or subset one needs to check for all its properties. If the set is reflexive symmetric transitive, it is an equivalence relation.


Related Articles
GIVE YOUR CHILD THE CUEMATH EDGE
Access Personalised Math learning through interactive worksheets, gamified concepts and grade-wise courses
Learn More About Cuemath