1
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – user113525
    Commented Feb 14, 2014 at 7:00
  • $\begingroup$ Yes, that's what you have to show, though your implications make me frown $\endgroup$ Commented Feb 14, 2014 at 7:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .