GATE CSE 2019 | Question: 10

Question

Let $G$ be an arbitrary group. Consider the following relations on $G$:

• $R_1: \forall a , b \in G, \: a R_1 b \text{ if and only if } \exists g \in G \text{ such that } a = g^{-1}bg$
• $R_2: \forall a , b \in G, \: a R_2 b \text{ if and only if } a= b^{-1}$

Which of the above is/are equivalence relation/relations?

• A. $R_1$ and $R_2$
• B. $R_1$ only
• C. $R_2$ only
• D. Neither $R_1$ nor $R_2$

Comments

B should be the ans

---

@Deepak Poonia , Sir Will you please explain, How to prove R1?

Answer 1

Answer: (B) 
Explanation: Given R1 is a equivalence relation, because it satisfied reflexive, symmetric, and transitive conditions:

• Reflexive: a = g–1ag can be satisfied by putting g = e, identity “e” always exists in a group.
• Symmetric:

  aRb ⇒ a = g–1bg for some g
  ⇒ b = gag–1 = (g–1)–1ag–1
  g–1 always exists for every g ∈ G. 

• Transitive:

  aRb and bRc ⇒ a = g1–1bg1 
  and b = g2–1 cg2 for some g1g2 ∈ G.
  Now a = g1–1 g2–1 cg2g1 = (g2g1)–1 cg2g1
  g1 ∈ G and g2 ∈ G ⇒ g2g1 ∈ G 
  since group is closed so aRb and aRb ⇒ aRc
  
  

R2 is not equivalence because it does not satisfied reflexive condition of equivalence relation:

aR2a ⇒ a = a–1 ∀a which not be true in a

Answer 2

For $R_1$:

As it’s given that $G$ be any arbitrary group , then it’s a must that every element has an inverse .

So , as given that $\forall a , b \in G, \: a R_1 b \text{ if and only if } \exists g \in G \text{ such that } a = g^{-1}bg$

Let the inverse of $g$ be $\alpha$ , So we can say $g^{-1}$ = $\alpha$ and $\alpha ^{-1} = g $

Therefore, our equation looks like this : $a = \alpha bg$

And also there exists an identity element $’e’$ , as it’s a group.

Now,

Reflexivity :

We have to just prove that every element is related to itself , and also $a.e = e.a = a$ , here $e$ is an identity element

Now we can say if $(a,a)$ has to belong to the relation then it must satisfy :

$a = g^{-1}ag$ , and we can assume that element $’g’$ to be equivalent to our identity element $’e’$.

Then it becomes $a = e^{-1}ae$

$a = eae$  ($e^{-1}=e$)

$a = ae$

$a = a$

Hence , our relation is reflexive

Symmetric :

For relation to be symmetric $aRb$ and $bRa$ for all $a,b \in G$

So we just have to prove $b = k^{-1}ak  $ such that there $\exists k$ and $k \in G$ 

$a = g^{-1}bg$

(Left multiplication with g)

$ga = gg^{-1} b g$

$ga = ebg$ (As $ gg^{-1} = e$)

(Right multiplication with $g^{-1}$)

$gag^{-1} = bgg^{-1}$

$gag^{-1} = be$

$gag^{-1} = b$

$b = gag^{-1}$

And from our assumption we know $g^{-1}=\alpha$ and $\alpha^{-1}=g$

Therefore , we can write it as :

$b = \alpha^{-1}a\alpha$

And this satisfies the above equation as $\alpha$ do exists and belong to G. And , hence our relation is symmetric

Transitivity:

We have to prove $aRb$ and $bRa$ , then $aRc$

Let there be to element $g$ and $k$ such that :

$a = g^{-1}bg$ and $b = k^{-1}ck$

From above we can say : $b = \alpha^{-1}a\alpha$

So

$\alpha^{-1}a\alpha = k^{-1}ck$

(Left multiplication with $\alpha$)

$a\alpha = \alpha k^{-1}ck$

$a\alpha =  g^{-1}k^{-1}ck$ (As $\alpha = g^{-1}$ )

(Right Multiplication with $\alpha^{-1}$)

$a =g^{-1}k^{-1}ck\alpha $

$a =g^{-1}k^{-1}ckg $  (As $\alpha^{-1}=g$)

Now what’s the inverse of $g^{-1}k^{-1}$ ? it would be $kg$

Because :

$g^{-1}k^{-1}*$ ____= $e$

So we’ve to operate it with $kg$ in order to get e

$g^{-1}k^{-1}kg = e$

$g^{-1}eg = e$ (As, $k^{-1}k = e$) 

$g^{-1}eg = e$

$g^{-1}g = e$

$e = e$

(Credits to Sir Shaik Masthan for this)

And, let $h = kg$ 

So $h^{-1} = g^{-1}k^{-1}$

Therefore our equation would look like this :

$a =h^{-1}ch $

Hence , relation is also transitive .

Therefore, $R_1$ is an equivalence relation.

---

For $R_2$:

$a = b^{-1}$ , doesn’t tells us anything.

 $b^{-1}$ might be equal to $a^{-1}$ or not.

Hence it’s not a reflexive relation, therefore not an equivalence relation

 

 

 

 

 

 

Answer 3

R1 is equivalence relation

Answer 4

R is reflexive:

aRa because e −1ae = a.

R is symmetric:

if aRb, i.e. if b = g −1ag for some g, then a = gbg−1 = (g −1 ) −1 bg−1 and bRa.

R is transitive: if aRb, i.e. b = g −1ag, and bRc, i.e. c = h −1 bh, then c = h −1 g −1agh = (gh) −1a(gh)

Comments

This was asked for how many marks?

---

1 marks