0
$\begingroup$

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

2 Answers 2

1

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.

1

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

  • 0
    It should be easy for you to do that yourself based on my remarks above.2012-11-15