GATE CS 2019 Q10 — Monoids and Groups

To determine which relations are equivalence relations, we test them for reflexivity, symmetry, and transitivity.

1. Analysis of $R_1$ (Conjugacy Relation):

• Reflexive: For any $a \in G$, we can choose the identity element $g = e \in G$. Since $a = e^{-1}ae$, we have $a R_1 a$.
• Symmetric: If $a R_1 b$, then $a = g^{-1}bg$ for some $g \in G$. Multiplying by $g$ on the left and $g^{-1}$ on the right gives $gag^{-1} = b$, which can be written as $b = (g^{-1})^{-1}a(g^{-1})$. Since $g^{-1} \in G$, we have $b R_1 a$.
• Transitive: If $a R_1 b$ and $b R_1 c$, then $a = g^{-1}bg$ and $b = h^{-1}ch$ for some $g, h \in G$. Substituting $b$ into the first equation gives: $$a = g^{-1}(h^{-1}ch)g = (hg)^{-1}c(hg)$$ Since $hg \in G$, we have $a R_1 c$.

Since $R_1$ is reflexive, symmetric, and transitive, it is an equivalence relation.

2. Analysis of $R_2$:

• Reflexive: For $R_2$ to be reflexive, we must have $a R_2 a$ for all $a \in G$, which means $a = a^{-1}$ (or $a^2 = e$) for every element. This is not true for an arbitrary group $G$ (for example, in the group of integers under addition, $1 \neq -1$).

Since $R_2$ is not reflexive, it is not an equivalence relation.

Thus, only $R_1$ is an equivalence relation.