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

good Question, enjoyed doing it. Simply used basic group properties

---

https://www.youtube.com/watch?v=WPYCr_pao1I&list=PL767-rEuXhcNHqc2QrjTWNLpFf8mKYnSJ&index=61

---

nice question.....

Answer 1

$R_1 : \forall a,b \in G, aR_1b$ iff $\exists g \in G $ such that $a = g^{-1}bg$

let g and h are inverse for each other.

Reflexive:
$aR_1a$

$a = g^{−1}ag $

$ga = gg^{-1}ag$ //Left multiplication by $g$

$gag^{-1} = agg^{-1}$ //Right multiplication by $g^{-1}$

$gag^{-1} = a$

$a = gag^{-1}$

$a = h^{-1}ah$  ( $∃h∈G$ )

we have $aR_1a$. So the relation is reflexive.

Alternative :- in the group, there should exist identity element, So we can take it as some g.

Symmetric:

let (a,b) exist, then

$a = g^{−1}bg $

$gag^{-1} = b $

$h^{-1}ah = b $  ( $∃h∈G$ )

∴ (b,a) should be in the relation.

Hence the relation is symmetric.

Transitive:

If (a,b) and (b,c) present, then

$a = x^{−1} b x $ and $b = y^{−1} c y $

$a = \underline{x^{−1} \;y^{−1}} \;\;c \;\;\underline{y\; x} $

What is the inverse of $ x^{−1} y^{−1} $ ?

$ x^{−1} y^{−1} $ . _________ = Identity.

to cancel the term $ y^{−1} $, we must multiply with it's inverse.

to cancel the term $ x^{−1} $, we must multiply with it's inverse.

So, inverse of $ x^{−1} y^{−1} $ is $ y . x $

∴$a = p^{−1}\; c \;p \; \text{, where p is y.x} $

∴ (a,c) should be in the relation.

Hence the relation is transitive.

$R_1$ is equivalence relation.

 

$R_2 : \forall a,b \in G, aR_2b$ iff $a =b^{-1} $

Reflexive:

for including a pair of (a,a), we need to $a=a^{−1}$ .

For an arbitrary group this may not be true. So the relation is not reflexive.

$R_2$ is not equivalence relation.

 

Correct Answer (B).

Comments

In R1,  

Reflexivity:

take g = e (Inverse of e = e)

Inverse exists in any arbitrary group.

Symmetricity:

Assume (a, b) is present in R1, then

To Prove:  (b, a) is also present in R1. i.e.,  b = h⁻¹ a h,  (some h ∈ G)

a = g⁻¹ b g,    (Given)

g a = g g⁻¹ b g 

g a = b g

g a g⁻¹ = b g g⁻¹

g a g⁻¹ = b

(put h⁻¹ = g then h = g⁻¹ and hence proved)

Transitivity:

Assume (a, b) & (b, c) are present in R1, then

To Prove:  (a, c) is also present in R1. i.e.,  a = h⁻¹ c h,  (some h ∈ G)

a = g⁻¹ b g      &   b =  h⁻¹ c h   (Given)

g a g⁻¹ = b      &   b =  h⁻¹ c h

g a g⁻¹             =    h⁻¹ c h

g⁻¹ g a g⁻¹ g    =    g⁻¹ h⁻¹ c h g

a    =    g⁻¹ h⁻¹ c h g

(put k⁻¹ = g⁻¹ h⁻¹  then k = h g) (The inverse of  ( g⁻¹ h⁻¹ )  is  ( h g ) )

∴ R1 is Equivalence relation.

---

For R2, what if we consider a boolean group such that every element is its own inverse?

---

Nice explaination it is very understable and easy..

Answer 2

R2 is not Reflexive.

-R1 is Reflexive.means

we have to prove a= g^-1 .a .g for some g belonging to group

Since , identity element belong to every group.

For g=identity element(e).

[e^-1=e

e.a=a.e=a]

So, g^-1 .a . g = e^-1 .a . e = e . a = a

Hence, for all a there exist g( an identity element) such that a= g^-1 . a .g

- R1 is symmetric

Given: a= g^-1 .b . g and g belongs to the group.

To Prove: b = k^-1 . a . k for k belonging to group.

Premultiplying with g

g.a = g.g^-1.b.g= b.g

Postmultiplying with g^-1

g .a. g^-1= b.g.g^-1= b

implies

b= g.a.g^-1

g can be written as (g^-1)^-1

b=(g^-1)^-1 . a . g^-1

for k= g^-1

Since, g belongs to group g^-1 also belongs to group and hence k belongs to group

b= k^-1 . a . k

Hence, if there exist g such that a=g^-1.b.g

then there also exist g'(which is g^-1) such that b= g'^-1.a.g'

 

-Dont know about transitive

Answer 3

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

 

 

 

 

 

 

Comments

Amazing solution 👍

Answer 4

C option

R1 reflexive  symmetric and transitive

R1is reflexive:

aRa because e −1ae = a.

R1 is symmetric:

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

R1 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

@pream sagar would you proof how it is reflexive .

---

https://www.math.stonybrook.edu/~retakh/mat312/312_sol2.pdf

---

Direct  from this pdf  point no 6

Answer 5

b as r2 need not be reflexive.

And r1 is reflexive symmetric and transitive.

Comments

Can you please explain how R1 can be Equivalence?

---

I dont understand here :

Say G = (<0,1,2>,+3) and set A = {0,1,2}

here so Option 1 : (1,1) pair wont be present because :

for 1 R 1 there should exist a g such that         1 = g^-1 .1.g        now there will be no such g for which it exist then how the first option is true ?

What am i doing wrong ?

Answer 6

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