Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A relation $\sim$ on $C$ is equivalence if it is:

  • reflexive: $c\sim c$ for all colorings $c$ belonging to $C$
  • symmetric: $c_1\sim c_2$ implies $c_2\sim c_1$
  • transitive: $c_1\sim c_2$ and $c_2\sim c_3$ implies $c_1\sim c_3$

A set of objects $S$, a set of colorings of these objects $C$ and a group of permutations $G$ representing symmetries possessed by configurations of the objects. Two colorings in $C$ are equivalent if there is a permutation in $G$ that transforms a coloring into the other.

Show that $\sim$ is an equivalence relation on $C$. How do you prove that?

As well as that, prove that $G_c$ is a subgroup of $G$.

share|cite|improve this question

It’s pretty straightforward; everything follows from the definition of group of permutations.

  • Reflexivity: Since $G$ is a group, it contains the identity permutation, which transforms any coloring into itself.

  • Symmetry: If there is a permutation $g\in G$ transforming a coloring $c_1$ into $c_2$, the inverse permutation $g^{-1}$, which must be in $G$, transforms $c_2$ to $c_1$.

  • Transitivity: If there are permutations $g,h\in G$ transforming $c_1$ to $c_2$ and $c_2$ to $c_3$, respectively, they their group product $hg$, which necessarily belongs to $G$, transforms $c_1$ to $c_3$: it’s just a composition of functions.

share|cite|improve this answer

You have a group $G$ (here the symmetric group of permutations) acting on a set $C$. The relation in question is defined as $c_1\sim c_2\iff \exists g\in G\colon c_1=gc_2$. Such is always an equivalence relation because $G$ is a group (neutral element gives reflexivity, inverse gives symmetry, the group operation gives transitivity). Remark: The equivalence classes in such a case are called orbits of an element under the group action.

If $c\in C$ we call $G_c:=\{g\in G\mid gc=c\}$ the stabilizer or fixgroup of $c$. It is a group because the neutral element fixes $c$, the inverse of $g$ fixes $c$ if $g$ fixes $c$ and if both $g_1 $ and $g_2$ fix $c$ then so does theit composition $g_1g_2$.

share|cite|improve this answer
How would you do the second part? proof that Gc is a subgroup of G. – Max Nov 15 '12 at 18:49
@Max $Gc$ is not a soubgroup of $G$, it is an orbit withn $C$, isn't it? – Hagen von Eitzen Nov 15 '12 at 18:51 this is all I've found that might shed a light on the situation.. – Max Nov 15 '12 at 18:54
Oh, then why don't you write $G_c$ instead of $Gc$? What they write there as $\bar c$ is what I denoted $Gc$ - the orbit of $c$, whereas $G_c$ is the stabilizer. – Hagen von Eitzen Nov 15 '12 at 18:55
A subgroup you mean? and if it was to make it more mathematical, would there be a way? – Max Nov 15 '12 at 19:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.