811: パーミュテーション（並べ替え）は、パーミュテーション（並べ替え）たちのセット（集合）をパーミュテーション（並べ替え）たちのセット（集合）の上へバイジェクティブ（全単射）にマップする、左または右からコンポジション（合成）によって

<このシリーズの前の記事 | このシリーズの目次 | このシリーズの次の記事>

パーミュテーション（並べ替え）は、パーミュテーション（並べ替え）たちのセット（集合）をパーミュテーション（並べ替え）たちのセット（集合）の上へバイジェクティブ（全単射）にマップする、左または右からコンポジション（合成）によって、ことの記述/証明

---

話題

About: セット（集合）

---

この記事の目次

• 開始コンテキスト
• ターゲットコンテキスト
• オリエンテーション
• 本体
• 1: 構造化された記述
• 2: 自然言語記述
• 3: 証明

---

開始コンテキスト

• 読者は、シーケンス（列）のパーミュテーション（並べ替え）の定義を知っている。
• 読者は、バイジェクション（全単射）たちの任意のファイナイト（有限）コンポジション（合成）はバイジェクション（全単射）である、もしも、構成要素バイジェクション（全単射）たちのコドメイン（余域）たちが、引き続くバイジェクション（全単射）たちのドメイン（定義域）たちに等しい場合、という命題を認めている。

---

ターゲットコンテキスト

• 読者は、任意のパーミュテーション（並べ替え）は、全てのパーミュテーション（並べ替え）たちのセット（集合）を全てのパーミュテーション（並べ替え）たちのセット（集合）の上へバイジェクティブ（全単射）にマップする、左または右からコンポジション（合成）によって、という命題の記述および証明を得る。

---

オリエンテーション

本サイトにてこれまで議論された定義たちの一覧があります。

本サイトにてこれまで議論された命題たちの一覧があります。

---

本体

---

1: 構造化された記述

ここに'構造化された記述'のルールたちがある。

エンティティ（実体）たち:
$S$: $\subseteq \mathbb{N}$
$f$: $\in \{S\text{ 上方の全てのシーケンス（列）たち }\}$
$P$: $=\{f\text{ の全てのパーミュテーション（並べ替え）たち }\}$
${\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$
//

ステートメント（言明）たち:
$l_{{\sigma }_0}\in \{\text{ 全てのバイジェクション（全単射）たち }\}$.
$\wedge$
$r_{{\sigma }_0}\in \{\text{ 全てのバイジェクション（全単射）たち }\}$.
//

---

2: 自然言語記述

任意のサブセット（部分集合）$S\subseteq \mathbb{N}$、以下を満たす任意のシーケンス（列）$f$、つまり、$domf=S$、$f$の全てのパーミュテーション（並べ替え）たちのセット（集合）$P$、任意のパーミュテーション（並べ替え）${\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$に対して、$l_{{\sigma }_0}$および$r_{{\sigma }_0}$はバイジェクション（全単射）たちである。

---

3: 証明

全体戦略: ステップ1: $l_{{\sigma }_0}$および$r_{{\sigma }_0}$はウェルデファインド（妥当に定義された）であることを見る; ステップ2: ${{\sigma }_0}^{-1}\in P$を取る; ステップ3: $l_{{\sigma }_0}$はバイジェクティブ（全単射）であることを見る、${{\sigma }_0}^{-1}$を使って; ステップ4: $r_{{\sigma }_0}$はバイジェクティブ（全単射）であることを見る、${{\sigma }_0}^{-1}$を使って。

ステップ1:

$l_{{\sigma }_0}$および$r_{{\sigma }_0}$はウェルデファインド（妥当に定義されている）（コドメイン（余域）は本当に$P$である）である、なぜなら、任意の2バイジェクション（全単射）のコンポジション（合成）で第1のバイジェクション（全単射）のコドメイン（余域）が第2のバイジェクション（余域）のドメイン（定義域）に等しいものはバイジェクション（全単射）である、バイジェクション（全単射）たちの任意のファイナイト（有限）コンポジション（合成）はバイジェクション（全単射）である、もしも、構成要素バイジェクション（全単射）たちのコドメイン（余域）たちが、引き続くバイジェクション（全単射）たちのドメイン（定義域）たちに等しい場合、という命題によって。

ステップ2:

${\sigma }_0$の以下を満たすインバース（逆）${{\sigma }_0}^{-1}\in P$、つまり、${{\sigma }_0}^{-1}\circ {\sigma }_0={\sigma }_0\circ {{\sigma }_0}^{-1}=id$、がある、なぜなら、${\sigma }_0$はバイジェクション（全単射）であり、${{\sigma }_0}^{-1}$もバイジェクション（全単射）である。

ステップ3:

$l_{{\sigma }_0}$はインジェクション（単射）であることを証明しよう。

$\sigma \ne {\sigma }^{\prime }\in P$は任意のパーミュテーション（並べ替え）たちであるとしよう。${\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 }$、矛盾。したがって、${\sigma }_0\circ \sigma \ne {\sigma }_0\circ {\sigma }^{\prime }$。

$l_{{\sigma }_0}$はサージェクション（全射）であることを証明しよう。

${\sigma }^{\prime }\in P$は任意のパーミュテーション（並べ替え）であるとしよう。${{\sigma }_0}^{-1}\circ {\sigma }^{\prime }\in P$および${\sigma }_0\circ {{\sigma }_0}^{-1}\circ {\sigma }^{\prime }={\sigma }^{\prime }$。

ステップ4:

$r_{{\sigma }_0}$はインジェクション（単射）であることを証明しよう。

$\sigma \ne {\sigma }^{\prime }\in P$は任意のパーミュテーション（並べ替え）たちであるとしよう。$\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 }$、矛盾。したがって、$\sigma \circ {\sigma }_0\ne {\sigma }^{\prime }\circ {\sigma }_0$。

$r_{{\sigma }_0}$はサージェクション（全射）であることを証明しよう。

${\sigma }^{\prime }\in P$は任意のパーミュテーション（並べ替え）であるとしよう。${\sigma }^{\prime }\circ {{\sigma }_0}^{-1}\in P$および${\sigma }^{\prime }\circ {{\sigma }_0}^{-1}\circ {\sigma }_0={\sigma }^{\prime }$。

---

参考資料

<このシリーズの前の記事 | このシリーズの目次 | このシリーズの次の記事>