description/proof of that permutation bijectively maps set of permutations onto set of permutations by composition from left or right
Topics
About: set
The table of contents of this article
- Starting Context
- Target Context
- Orientation
- Main Body
- 1: Structured Description
- 2: Natural Language Description
- 3: Proof
Starting Context
Target Context
- The reader will have a description and a proof of the proposition that any permutation bijectively maps the set of all the permutations onto the set of all the permutations by composition from left or right.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\(S\): \(\subseteq \mathbb{N}\)
\(f\): \(\in \{\text{ the sequences over } S\}\)
\(P\): \(= \{\text{ the permutations of } f\}\)
\(\sigma_0\): \(\in P\)
\(l_{\sigma_0}\): \(P \to P, \sigma \mapsto \sigma_0 \circ \sigma\)
\(r_{\sigma_0}\): \(P \to P, \sigma \mapsto \sigma \circ \sigma_0\)
//
Statements:
\(l_{\sigma_0} \in \{\text{ the bijections }\}\).
\(\land\)
\(r_{\sigma_0} \in \{\text{ the bijections }\}\).
//
2: Natural Language Description
For any subset, \(S \subseteq \mathbb{N}\), any sequence, \(f\), such that \(dom f = S\), the set of all the permutations of \(f\), \(P\), any permutation, \(\sigma_0 \in P\), \(l_{\sigma_0}\): \(P \to P, \sigma \mapsto \sigma_0 \circ \sigma\), and \(r_{\sigma_0}\): \(P \to P, \sigma \mapsto \sigma \circ \sigma_0\), \(l_{\sigma_0}\) and \(r_{\sigma_0}\) are some bijections.
3: Proof
Whole Strategy: Step 1: see that \(l_{\sigma_0}\) and \(r_{\sigma_0}\) are well-defined; Step 2: take \({\sigma_0}^{-1} \in P\); Step 3: see that \(l_{\sigma_0}\) is bijective, using \({\sigma_0}^{-1}\); Step 4: see that \(r_{\sigma_0}\) is bijective, using \({\sigma_0}^{-1}\).
Step 1:
\(l_{\sigma_0}\) and \(r_{\sigma_0}\) are well-defined (the codomain is indeed \(P\)), because the composition of any 2 bijections with the codomain of the 1st bijection equaling the domain of the 2nd bijection is a bijection, by the proposition that any finite composition of bijections is a bijection, if the codomains of the constituent bijections equal the domains of the succeeding bijections.
Step 2:
There is the inverse, \({\sigma_0}^{-1} \in P\), of \(\sigma_0\), such that \({\sigma_0}^{-1} \circ \sigma_0 = \sigma_0 \circ {\sigma_0}^{-1} = id\), because \(\sigma_0\) is a bijection and also \({\sigma_0}^{-1}\) is a bijection.
Step 3:
Let us prove that \(l_{\sigma_0}\) is an injection.
Let \(\sigma \neq \sigma' \in P\) be any permutations. Let us suppose that \(\sigma_0 \circ \sigma = \sigma_0 \circ \sigma'\). \(\sigma = {\sigma_0}^{-1} \circ \sigma_0 \circ \sigma = {\sigma_0}^{-1} \circ \sigma_0 \circ \sigma' = \sigma'\), a contradiction. So, \(\sigma_0 \circ \sigma \neq \sigma_0 \circ \sigma'\).
Let us prove that \(l_{\sigma_0}\) is a surjection.
Let \(\sigma' \in P\) be any permutation. \({\sigma_0}^{-1} \circ \sigma' \in P\) and \(\sigma_0 \circ {\sigma_0}^{-1} \circ \sigma' = \sigma'\).
Step 4:
Let us prove that \(r_{\sigma_0}\) is an injection.
Let \(\sigma \neq \sigma' \in P\) be any permutations. Let us suppose that \(\sigma \circ \sigma_0 = \sigma' \circ \sigma_0\). \(\sigma = \sigma \circ \sigma_0 \circ {\sigma_0}^{-1} = \sigma' \circ \sigma_0 \circ {\sigma_0}^{-1} = \sigma'\), a contradiction. So, \(\sigma \circ \sigma_0 \neq \sigma' \circ \sigma_0\).
Let us prove that \(r_{\sigma_0}\) is a surjection.
Let \(\sigma' \in P\) be any permutation. \(\sigma' \circ {\sigma_0}^{-1} \in P\) and \(\sigma' \circ {\sigma_0}^{-1} \circ \sigma_0 = \sigma'\).
