Odd and Even Permutations of Set are Equivalent

Theorem

Let $n \in \N_{> 0}$ be a natural number greater than $0$.

Let $S$ be a set of cardinality $n$.

Let $S_n$ denote the symmetric group on $S$ of order $n$.

Let $R_e$ and $R_o$ denote the subsets of $S_n$ consisting of even permutations and odd permutations respectively.

Then $R_e$ and $R_o$ are equivalent.

Let $\tau$ be a transposition.

By definition of sign:

$\sgn \paren \rho = -1$

By definition of odd permutation:

$\tau \in R_o$

Moreover, also by definition of sign, for any $\rho \in R_e$ we have:

$\rho \circ \tau \in R_o$

Define the mapping $\phi$:

$\forall \rho \in R_e: \phi \paren \sigma = \rho \circ \tau$

We claim that $\phi$ is injective.

Suppose:

$\phi \paren {\rho_1} = \phi \paren {\rho_2}$

Then:

$\rho_1 \circ \tau = \rho_2 \circ\tau$

$\rho_1 = \rho_1 \circ \tau \circ \tau = \rho_2 \circ \tau \circ \tau = \rho_2$

Thus $\phi$ is indeed injective.

$\Box$

We claim that $\phi$ is also surjective.

Let $\sigma \in R_o$.

We need to show that there exists an element $\rho\in R_e$ such that:

$\phi \paren \rho = \sigma$

By definition of sign:

$\sigma \circ \tau \in R_e$

$\phi \paren {\sigma \circ \tau} = \sigma \circ \tau \circ \tau = \sigma$

Thus $\phi$ is surjective.

$\Box$

Since $\phi$ is injective and surjective, $\phi$ is the desired bijection.

Hence the result by definition of set equivalence.

$\blacksquare$

1968: Ian D. Macdonald: The Theory of Groups ... (previous) ... (next): Appendix: Elementary set and number theory