# Equivalence relation $E\subset X \times X$

If $X$ is a finite set, and $E\subset X \times X$ is an equivalence relation on $X$, show $\exists G \subset S_X$ subgroup s.t. the equivalence relation described by $x \equiv _G y, g\in G, g(x)=y$ is the equivalence relation $E$.

I don't understand how this question differs from my last question: Question(s) pertaining to equivalence relation. I know that $E\subset X \times X = \{(x,y): x,y\in X\}$, but this seems very similar.

• "described above"? Commented Feb 14, 2014 at 6:53
• Sorry. $x \equiv _G y, g\in G, g(x)=y.$ I will put that in the question. Commented Feb 14, 2014 at 6:54

Let $G=\{\,g\in S_X\mid \forall (x,y)\in E\colon (gx,gy)\in E\,\}$ and check that this is a group (this works because $E$ is an equivalence relation, with the three group axioms and the three equivalence axioms magically matching) and that $\equiv_G$ is $E$.
• So, to prove this, I show reflexive/symmetric/transitive properties. Reflexive: $g(x)=y \Rightarrow g^{-1}(y)=x \Rightarrow (x,y)\in E \Rightarrow (y,y)\in E \Rightarrow (gx,gx)\in E$ and so on? Commented Feb 14, 2014 at 7:00