Sets of Permutations of Equivalent Sets are Equivalent

From ProofWiki
Jump to navigation Jump to search

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$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sets_of_Permutations_of_Equivalent_Sets_are_Equivalent&oldid=566894"