Question

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

R1R_1: ∀a,b∈G\forall a, b \in G, aR1ba R_1 b if and only if ∃g∈G\exists g \in G such that a=g−1bga = g^{-1}bg
R2R_2: ∀a,b∈G\forall a, b \in G, aR2ba R_2 b if and only if a=b−1a = b^{-1}

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

Choose one option
Official answer and solution
Official answer
B
From
Official GATE 2019 answer key

Solution

Check reflexivity, symmetry, and transitivity for each given relation on group G.

Examining R1R_1 (Conjugacy relation):

  • Reflexivity: For any a∈Ga \in G, choose g=eg = e (identity element). Then a=e−1aea = e^{-1}ae, so aR1aa R_1 a. (Reflexive)
  • Symmetry: If aR1ba R_1 b, then ∃g∈G\exists g \in G such that a=g−1bga = g^{-1}bg. Multiplying by gg on the left and g−1g^{-1} on the right gives b=gag−1=(g−1)−1a(g−1)b = g a g^{-1} = (g^{-1})^{-1} a (g^{-1}). Choosing h=g−1∈Gh = g^{-1} \in G, we have b=h−1ahb = h^{-1}ah, so bR1ab R_1 a. (Symmetric)
  • Transitivity: If aR1ba R_1 b and bR1cb R_1 c, then a=g1−1bg1a = g_1^{-1} b g_1 and b=g2−1cg2b = g_2^{-1} c g_2. Substituting gives a=g1−1(g2−1cg2)g1=(g2g1)−1c(g2g1)a = g_1^{-1}(g_2^{-1} c g_2)g_1 = (g_2 g_1)^{-1} c (g_2 g_1). Since g2g1∈Gg_2 g_1 \in G, aR1ca R_1 c. (Transitive)
    Thus, R1R_1 is an equivalence relation.

Examining R2R_2:
aR2b  ⟺  a=b−1a R_2 b \iff a = b^{-1}. For R2R_2 to be reflexive, every element must satisfy aR2a  ⟺  a=a−1  ⟺  a2=ea R_2 a \iff a = a^{-1} \iff a^2 = e. In an arbitrary group, not every element is self-inverse (for example, in (Z4,+)(\mathbb{Z}_4, +), 1−1=3≠11^{-1} = 3 \ne 1). Thus, R2R_2 is not reflexive in general, so it is NOT an equivalence relation.

Hence, only R1R_1 is an equivalence relation.

Final answer

B

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2019 Computer Science and Information Technology (CS)
Question
20 of 65, printed as CS Q.10
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.