search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
2 votes
359 views

GATE CSE 2021 Set 1 | Question-18.8

  1. GATE CSE 2021 Set 1 | Question-90
  2. GATE CSE 2021 Set 1 | Question-90
  3. GATE CSE 2021 Set 1 | Question-90
  4. GATE CSE 2021 Set 1 | Question-90

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.
in Set Theory & Algebra
recategorized by
359 views

4 Answers

2 votes

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

Only C the correct answer.

  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.
0 votes
  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
Answer:

Related questions

1 vote
2 answers
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
asked Feb 18 in Operating System Arjun 404 views
1 vote
3 answers
2
262 views
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 ^* \}$
asked Feb 18 in Theory of Computation Arjun 262 views
3 votes
1 answer
3
429 views
Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery. Which of the following statements is/are correct? The same undo and redo list ... any further All the transactions that are already undone and redone will not be recovered again The database will become inconsistent
asked Feb 18 in Databases Arjun 429 views
3 votes
3 answers
4
851 views
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}$
asked Feb 18 in Operating System Arjun 851 views
...