GATE CSE 2021 Set 1 | Question: 43

Question

A relation $R$ is said to be circular if $a\text{R}b$ and $b\text{R}c$ together imply $c\text{R}a$.

Which of the following options is/are correct?

• A. If a relation $S$ is reflexive and symmetric, then $S$ is an equivalence relation.
• B. If a relation $S$ is circular and symmetric, then $S$ is an equivalence relation.
• C. If a relation $S$ is reflexive and circular, then $S$ is an equivalence relation.
• D. If a relation $S$ is transitive and circular, then $S$ is an equivalence relation.

Comments

@Mohitdas

one correction needed in the representation for Transitive  (the path should be from first to last).

---

Yes,you are right...

---

Video Explanation 

https://youtu.be/Bk0KTt1gtzc?si=t5Rr8vsVd_TBD2iJ

Answer 1

Let $S$ be an empty relation

Empty relation is all symmetric, transitive and circular (as all these three are conditional)

But it is not reflexive.

equivalence relation : reflexive, symmetric and transitive

$S$ is both circular and symmetric but not reflexive, hence B is false

$S$ is both transitive and circular but not reflexive, hence D is false

option A clearly does not follow the definition of equivalence relation,

so only option left is C

and C indeed is the correct answer as proved below

---

Let S be both reflexive and circular,

case 1: x has only diagonal elements ( $a\text{S}a$ exists for all a)

Then $S$ is all reflexive, symmetric, transitive and circular  (hence equivalence )

case 2:  let for some 3 different elements a,b,c  $a\text{S}b$  exists  but $b\text{S}c$ does not exist

Both $a\text{S}a, b\text{S}b$ also exist   (it is given reflexive)

$(a\text{S}a$ and $a\text{S}b) \rightarrow b\text{S}a $    (from circular property),

so, $a\text{S}b \rightarrow b\text{S}a $, hence it is symmetric

And transitive as well (because i assumed if $a\text{S}b$ exists then no $b\text{S}c$ exists for any three different elements $a,b,c$)

Hence this case will also be equivalence

case 3: let for some 3 different elements a,b,c both  $a\text{S}b,\ b\text{S}c$ exists

$a\text{S}a, b\text{S}b, c\text{S}c$    (exists from reflexive property)

$b\text{S}b$ and $b\text{S}c \rightarrow c\text{S}b$   (from circular property) (Hence it is symmetric)

$a\text{S}b$ and $b\text{S}c\rightarrow c\text{S}a$   (from circular property)

$c\text{S}a \rightarrow a\text{S}c$   (from symmetric property)    (already proved symmetric 2 steps above)

so, we can conclude,

$a\text{S}b$ and $b\text{S}c\rightarrow a\text{S}c$   (hence it is transitive as well)

as we just proved it as both symmetric and transitive, it is definitely equivalence relation

In all three cases we proved that if $S$ is both reflexive and circular then it an is equivalence relation.

C is correct ans.

Comments

@Nikhil

For Option A, if we take B={1,2,3} and the relation = {(1,1) (2,2,) (3,3)}, then option A holds true. Because it is reflexive and symmetric and by default it becomes transitive, so the equivalence relation does hold. Aren’t I right?

Edit: Found the counter example : {(1,1) (2,2,) (3,3),(1,3),(3,1),(2,3)(3,2)} which is not transitive

Answer 2

If a relation R is reflexive and circular then it is symmetric : True

Proof : Assume $a\text{R}b.$ Then since $R$ is reflexive, we have $b\text{R}b.$ Since $R$ is circular, so, $a\text{R}b, b\text{R}b$ will mean that we have $b\text{R}a.$ So, $R$ is symmetric. 

If R is reflexive and circular then it is transitive : True 

Proof : Assume $a\text{R}b, b\text{R}c.$ Since $R$ is circular, so, $c\text{R}a,$ and since $R$ is symmetric(we proved above) so $a\text{R}c$ so $R$ is transitive.

So, option C is correct. 

---

Option B is false. For counter example, take a set $A = \{a,b,c\},$ define relation $R$ on $A$ as follows : $R = \{ (a,a) \}, R$ is symmetric and circular but not equivalence relation. 

Option A is false. For counter example, take a set $A = \{a,b,c\},$ define relation $R$ on $A$ as follows: $R = \{ (a,a), (b,b),(c,c), (a,b),(b,a), (a,c),(c,a) \},$ $R$ is symmetric and reflexive but not transitive so not equivalence relation. 

Option D is false. For counter example, take a set $A = \{a,b,c\},$ define relation R on A as follows: $R = \{ (a,a) \},$ $R$ is transitive and circular but not equivalence relation.  

---

Some more variations :

1. Converse of Statement in option C is also true. i.e.

Theorem : If R is an equivalence relation then R is reflexive and circular.

Proof :

Reflexive: As, the relation $R$ is an equivalence relation. So, reflexivity is the property of an equivalence relation. Hence, $R$ is reflexive.

Circular: Let $(a, b) \in R$ and $(b, c) ∈ R$
                  $⇒ (a, c) ∈ R$       (∵ R is transitive)
                  $⇒ (c, a) ∈ R$       (∵ R is symmetric)

Thus, $R$ is Circular.

So, we can say that

“A relation S is reflexive and circular if and only if  S is an equivalence relation.”

2. If a relation $R$ is transitive and circular then it is symmetric : False.

3. If a relation $R$ is transitive and circular then it is reflexive : False.

Counter example(for both above statements) : $R = \{ (a,b) \}$

PS : Similarly you can try to prove or disprove more similar statements and their converses.  

Comments

For the counter-eample given for this, i.e.  R={(a,b)} ….Here aRb and aRb, so shouldn’t R also contain bRa since it is circular. ?

The definition of circular relation, given in the question, requires $(x,y), (y,z)$ to imply $(x,z).$

$(a,b),(a,b)$ doesn’t have that format. 

---

best one...

---

This should be the best ans.. !!!

Answer 3

Only C the correct answer.

• A. Option A is not correct because a relation is equivalence iff it is reflexive, symmetric and transitive.
• B. Consider the relation  {(2,3),(3,2)} on set {1,2,3} as a counter solution to option B.
• C. Option C is correct.
• D. Consider the relation {(2,2)(2,3)(3,2)} on set {1,2,3} as counter solution to option D. 

Comments

According to the counter example of option d –> (3,2) (2,3) => (3,3) (as it is transitive) so it is perfectly reflexive, symmetric and transitive.

---

But theres no (1,1) .hence not reflexive

---

Please correct your set for option b.....u have included only {(2,3),(3,2)} in your example which is not circular. Plz add (2,2) and (3,3) as well to make it circular...

Answer 4

1. Option A is not correct as a relation has to be reflexive, symmetric and transitive for being equivalence. ( by definition )
2. Option B : a relation is symmetric and cyclic implies that it is transitive . But reflexivity is not implied there. In case there is an isolated node in the relation, then a loop to itself is not guaranteed.  So reflexivity not guaranteed. Hence, the relation need not be equivalence.
3. Option C: a relation is reflexive and circular implies symmetricly and transitivity. Hence it is correct.
4. Option D: a circular and transitive relation implies symmetricly but nor reflexivity for the reason stated in point 2.

So option C is the right answer.

We can verify this by defining the above relations on a set of four elements and keeping one node isolated. 

Comments

Sir in option A it is given the relation is reflexive and transitive,that doesn’t mean it is not transitive right?

For example let us take a simple set S={1,2,3}

the relation {(1,1),(2,2),(3,3)} As mentioned in the option it is both reflexive and symmetric and additionally it is also Transitive.Can’t we concluse that it equivalent relation?

---

Sir in option A it is given the relation is reflexive and transitive,that doesn’t mean it is not transitive right?

For example let us take a simple set S={1,2,3}

the relation {(1,1),(2,2),(3,3)} As mentioned in the option it is both reflexive and symmetric and additionally it is also Transitive.Can’t we conclude that it equivalent relation?

---

@Tarunreddy consider R= {(1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3)} on A = {1,2,3} is symmetric and reflexive, but not transitive.