# Sets of Permutations of Equivalent Sets are Equivalent

## Theorem

Let $A$ and $B$ be sets such that:

$A \sim B$

where $\sim$ denotes set equivalence.

Let $\map \Gamma A$ denote the set of permutations on $A$. Then:

$\map \Gamma A \sim \map \Gamma B$

## Proof

By definition of set equivalence, let $f: A \to B$ be a bijection.

Define $\Phi : \map \Gamma A \to \map \Gamma B$ by:

$\map \Phi \gamma := f \circ \gamma \circ f^{-1}$

By definition of permutation, each $\gamma \in \map \Gamma A$ is a bijection.

By Composite of Bijections is Bijection, each $f \circ \gamma$ is a bijection.

By Inverse of Bijection is Bijection, the inverse mapping $f^{-1}$ is a bijection.

Then by Composite of Bijections is Bijection, each $\map \Phi \gamma = f \circ \gamma \circ f^{-1}$ is a bijection.

Thus each $\map \Phi \gamma$ is a permutation of $B$, so $\Phi$ is well-defined.

Define $\Psi : \map \Gamma B \to \map \Gamma A$ by:

$\map \Psi \delta := f^{-1} \circ \delta \circ f$

$\Psi$ is a well-defined mapping by the same reasoning as for $\Phi$.

Then for each $\gamma \in \map \Gamma A$:

 $\ds \map {\paren {\Psi \circ \Phi} } \gamma$ $=$ $\ds \map \Psi {\map \Phi \gamma}$ $\ds$ $=$ $\ds \map \Psi {f \circ \gamma \circ f^{-1} }$ $\ds$ $=$ $\ds f^{-1} \circ \paren {f \circ \gamma \circ f^{-1} } \circ f$ $\ds$ $=$ $\ds \paren {f \circ f^{-1} } \circ \gamma \circ \paren {f^{-1} \circ f}$ Composition of Mappings is Associative $\ds$ $=$ $\ds I_B \circ \gamma \circ I_A$ Composite of Bijection with Inverse is Identity Mapping $\ds$ $=$ $\ds \gamma \circ I_A$ Identity Mapping is Left Identity $\ds$ $=$ $\ds \gamma$ Identity Mapping is Right Identity

Thus $\Psi \circ \Phi = I_{\map \Gamma A}$.

Similarly, for each $\delta \in \map \Gamma B$:

 $\ds \map {\Phi \circ \Psi} {\delta}$ $=$ $\ds \map \Phi {\map \Psi \delta}$ $\ds$ $=$ $\ds \map \Phi {f^{-1} \circ \delta \circ f}$ $\ds$ $=$ $\ds f \circ \paren {f^{-1} \circ \delta \circ f} \circ f^{-1}$ $\ds$ $=$ $\ds \paren {f^{-1} \circ f} \circ \delta \circ \paren {f \circ f^{-1} }$ Composition of Mappings is Associative $\ds$ $=$ $\ds I_A \circ \delta \circ I_B$ Composite of Bijection with Inverse is Identity Mapping $\ds$ $=$ $\ds \delta \circ I_B$ Identity Mapping is Left Identity $\ds$ $=$ $\ds \delta$ Identity Mapping is Right Identity

Thus $\Phi \circ \Psi = I_{\map \Gamma B}$.

By Bijection iff Left and Right Inverse, both $\Phi$ and $\Psi$ are bijections.

In particular:

$\map \Gamma A \sim \map \Gamma B$

$\blacksquare$