Let \(G\) be a transitive subgroup of \(S_n\) acting on \(\{1,\ldots,n\}\). Assume that \(G\) is simple and that \(\sim\) is an equivalence relation on \(\{1,\ldots,n\}\) such that \[ i\sim j\quad\Longrightarrow\quad \sigma(i)\sim\sigma(j) \] for every \(\sigma\in G\). What can one conclude about the equivalence relation \(\sim\)?
Solution
Let \[ X=\{1,\ldots,n\}, \qquad \mathcal B=X/{\sim} \] be the set of equivalence classes.
1. The rule\[ \sigma\cdot[i]=[\sigma(i)] \]defines a transitive action of \(G\) on \(\mathcal B\).
The stated hypothesis gives \[ i\sim j \quad\Longrightarrow\quad \sigma(i)\sim\sigma(j). \] Applying the same implication to \(\sigma^{-1}\) shows the converse, so \[ i\sim j \quad\Longleftrightarrow\quad \sigma(i)\sim\sigma(j). \] Hence the displayed rule is well defined on equivalence classes.
For classes \([i]\) and \([j]\), transitivity of the action of \(G\) on \(X\) gives some \(\sigma\in G\) with \(\sigma(i)=j\). Then \(\sigma\cdot[i]=[j]\), so the induced action on \(\mathcal B\) is transitive.
2. If\[ K=\ker\bigl(G\to\operatorname{Sym}(\mathcal B)\bigr), \]then either \(K=G\) or \(K=\{1\}\).
The kernel \(K\) is a normal subgroup of \(G\). Since \(G\) is simple, it has no normal subgroups other than \(\{1\}\) and \(G\).
3. If \(K=G\), then \(\sim\) is the universal equivalence relation.
If \(K=G\), every element of \(G\) fixes every class in \(\mathcal B\). Fix \(i\in X\). For any \(j\in X\), transitivity gives \(\sigma\in G\) with \(\sigma(i)=j\). Since \(\sigma\) fixes the class \([i]\), one has \[ [j] =[\sigma(i)] = [i]. \] Thus every two elements of \(X\) are equivalent.
4. If \(K=\{1\}\), then the induced action of \(G\) on the set ofequivalence classes is faithful.
This is exactly the assertion that the kernel of \[ G\longrightarrow\operatorname{Sym}(\mathcal B) \] is trivial.
5. No stronger conclusion, such as saying that \(\sim\) must beeither equality or the universal relation, follows from the statedhypotheses.
Let \(G=A_5\) act on the set \(X=G\) by left multiplication. This action is transitive, and \(A_5\) is simple. Let \(H\le A_5\) be a subgroup of order \(2\), and define \[ x\sim y \quad\Longleftrightarrow\quad x^{-1}y\in H. \] The equivalence classes are the right cosets \(xH\), so each class has two elements and there is more than one class.
For \(g,x,y\in G\), \[ (gx)^{-1}(gy)=x^{-1}y, \] so left multiplication preserves the relation. Thus this is a nontrivial proper \(G\)-invariant equivalence relation satisfying all the hypotheses.
6. Consequently,\[ \boxed{ \text{$\sim$ is universal, or $G$ acts faithfully on $X/{\sim}$.} } \]
By step 2, the kernel of the induced action is either \(G\) or trivial. Step 3 identifies the first case with the universal relation, and step 4 identifies the second with a faithful action. Step 5 shows that the second case need not be the equality relation.
7. Q.E.D.
Step 6 gives the complete conclusion forced by the hypotheses.