811: Permutation Bijectively Maps Set of Permutations onto Set of Permutations by Composition from Left or Right

<The previous article in this series | The table of contents of this series | The next article in this series>

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

• The reader knows a definition of permutation of sequence.
• The reader admits 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.

---

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 }\}$.
$\wedge$
$r_{{\sigma }_0}\in \{\text{ the bijections }\}$.
//

---

2: Natural Language Description

For any subset, $S\subseteq \mathbb{N}$, any sequence, $f$, such that $domf=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 \ne {\sigma }^{\prime }\in P$ be any permutations. Let us suppose that ${\sigma }_0\circ \sigma ={\sigma }_0\circ {\sigma }^{\prime }$. $\sigma ={{\sigma }_0}^{-1}\circ {\sigma }_0\circ \sigma ={{\sigma }_0}^{-1}\circ {\sigma }_0\circ {\sigma }^{\prime }={\sigma }^{\prime }$, a contradiction. So, ${\sigma }_0\circ \sigma \ne {\sigma }_0\circ {\sigma }^{\prime }$.

Let us prove that $l_{{\sigma }_0}$ is a surjection.

Let ${\sigma }^{\prime }\in P$ be any permutation. ${{\sigma }_0}^{-1}\circ {\sigma }^{\prime }\in P$ and ${\sigma }_0\circ {{\sigma }_0}^{-1}\circ {\sigma }^{\prime }={\sigma }^{\prime }$.

Step 4:

Let us prove that $r_{{\sigma }_0}$ is an injection.

Let $\sigma \ne {\sigma }^{\prime }\in P$ be any permutations. Let us suppose that $\sigma \circ {\sigma }_0={\sigma }^{\prime }\circ {\sigma }_0$. $\sigma =\sigma \circ {\sigma }_0\circ {{\sigma }_0}^{-1}={\sigma }^{\prime }\circ {\sigma }_0\circ {{\sigma }_0}^{-1}={\sigma }^{\prime }$, a contradiction. So, $\sigma \circ {\sigma }_0\ne {\sigma }^{\prime }\circ {\sigma }_0$.

Let us prove that $r_{{\sigma }_0}$ is a surjection.

Let ${\sigma }^{\prime }\in P$ be any permutation. ${\sigma }^{\prime }\circ {{\sigma }_0}^{-1}\in P$ and ${\sigma }^{\prime }\circ {{\sigma }_0}^{-1}\circ {\sigma }_0={\sigma }^{\prime }$.

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>