# GATE CSE 2021 Set 1 | Question: 43

359 views

A relation $R$ is said to be circular if $aRb$ and $bRc$ together imply $cRa$.

Which of the following options is/are correct?

1. If a relation $S$ is reflexive and symmetric, then $S$ is an equivalence relation.
2. If a relation $S$ is circular and symmetric, then $S$ is an equivalence relation.
3. If a relation $S$ is reflexive and circular, then $S$ is an equivalence relation.
4. If a relation $S$ is transitive and circular, then $S$ is an equivalence relation.

recategorized

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 don’t follow the definition of equivalence relation,

so only option left is C

and C indeed is the correct ans. proved below

Let S be both reflexive and circular,

case 1: x only have diagonal elements ( $aSa$ 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  $aSb$  exists  but $bSc$ doesn’t exists

both $aSa, bSb$ are also exists   (it is given reflexive)

$(aSa\ and\ aSb) \rightarrow bSa$    (from circular property),

so, $aSb \rightarrow bSa$, hence it is symmetric

and transitive as well (because i assumed if $aSb$ exists then no $bSc$ exists for any three diffrent elements a,b,c)

hence this case will also be equivalence

case 3: let for some 3 different elements a,b,c both  $aSb,\ bSc$ exists

$aSa, bSb, cSc$    (exists from reflexive property)

$bSb\ and\ bSc \rightarrow cSb$   (from circular property) (Hence it is symmetric)

$aSb\ and\ bSc\rightarrow cSa$   (from circular property)

$cSa \rightarrow aSc$   (from symmetric property)    (already proved symmetric 2 steps above)

so, we can conclude,

$aSb\ and\ bSc\rightarrow aSc$   (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.

1 vote

1. Option A is not correct because a relation is equivalence iff it is reflexive, symmetric and transitive.
2. Consider the relation  {(2,3),(3,2)} on set {1,2,3} as a counter solution to option B.
3. Option C is correct.
4. Consider the relation {(2,2)(2,3)(3,2)} on set {1,2,3} as counter solution to option D.
0
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.
0
But theres no (1,1) .hence not reflexive
1 vote

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

Proof :

Assume aRb. Then since R is reflexive, we have bRb. Since R is circular, so, aRb, bRb will mean that we have bRa, so, R is symmetric.

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

Proof :

Assume aRb, bRc. Since R is circular, so, cRa, and since R is symmetric(we proved above) so aRc 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) ∈ 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.

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.

0
Thanx sir for such a detailed explaination.
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.

ago

## Related questions

1 vote
1
404 views
In the context of operating systems, which of the following statements is/are correct with respect to paging? Paging helps solve the issue of external fragmentation Page size has no impact on internal fragmentation Paging incurs memory overheads Multi-level paging is necessary to support pages of different sizes
1 vote
Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive? $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is ... $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$
Which of the following standard $C$ library functions will always invoke a system call when executed from a single-threaded process in a $\text{UNIX/Linux}$ operating system? $\textsf{exit}$ $\textsf{malloc}$ $\textsf{sleep}$ $\textsf{strlen}$