# Equivalence Relation on Symmetric Group by Image of n is Congruence Modulo Subgroup

## Theorem

Let $S_n$ denote the symmetric group on $n$ letters $\set {1, \dots, n}$.

Let $\sim$ be the relation on $S_n$ defined as:

$\forall \pi, \tau \in S_n: \pi \sim \tau \iff \map \pi n = \map \tau n$

Then $\sim$ is an equivalence relation which is congruence modulo a subgroup.

## Proof

We claim that $\sim$ is left congruence modulo $S_{n - 1}$, the symmetric group on $n - 1$ letters $\set {1, \dots, n - 1}$.

Notice that every element of $S_{n - 1}$ fixes $n$.

For all $\pi, \tau \in S_n$ such that $\pi \sim \tau$:

 $\ds \map {\paren {\pi^{-1} \circ \tau} } n$ $=$ $\ds \map {\pi^{-1} } {\map \tau n}$ Definition of Composition of Mappings $\ds$ $=$ $\ds \map {\pi^{-1} } {\map \pi n}$ Definition of $\sim$ $\ds$ $=$ $\ds \map {\paren {\pi^{-1} \circ \pi} } n$ Definition of Composition of Mappings $\ds$ $=$ $\ds n$ Definition of Inverse Element

so $\pi^{-1} \circ \tau$ fixes $n$ as well.

This shows that $\pi^{-1} \circ \tau \in S_{n - 1}$.

By definition of Left Congruence Modulo Subgroup:

$\pi \equiv^l \tau \pmod {S_{n - 1} }$

Now we show the converse.

Suppose $\pi \equiv^l \tau \pmod {S_{n - 1} }$.

Then $\pi^{-1} \circ \tau \in S_{n - 1}$.

Hence $\map {\paren {\pi^{-1} \circ \tau} } n = n$.

Then:

 $\ds \map \pi n$ $=$ $\ds \map \pi {\map {\paren {\pi^{-1} \circ \tau} } n}$ $\ds$ $=$ $\ds \map {\paren {\pi \circ \pi^{-1} \circ \tau} } n$ Definition of Composition of Mappings $\ds$ $=$ $\ds \map \tau n$ Definition of Inverse Element $\ds \leadsto \ \$ $\ds \pi$ $\sim$ $\ds \tau$

Therefore $\sim$ and left congruence modulo $S_{n - 1}$ are equivalent.

The fact that $\sim$ is an equivalence relation follows from Left Congruence Modulo Subgroup is Equivalence Relation.

$\blacksquare$