リニアリーオーダードセット（線形順序集合）に対して、ファイナイトサブセット（有限部分集合）は一列に並べることができることの記述/証明
話題
About: セット（集合）
この記事の目次
開始コンテキスト
ターゲットコンテキスト
- 読者は、任意のリニアリーオーダードセット（線形順序集合）に対して、任意のファイナイトサブセット（有限部分集合）は一列に並べることができるという命題の記述および証明を得る。
オリエンテーション
本サイトにてこれまで議論された定義たちの一覧があります。
本サイトにてこれまで議論された命題たちの一覧があります。
本体
1: 構造化された記述
ここに'構造化された記述'のルールたちがある。
エンティティ（実体）たち:
\(S'\): \(\in \{\text{ 全てのリニアリーオーダードセット（線形順序集合）たち }\}\)で、オーダリング（順序）\(\lt\)を持つもの
\(S\): \(\in \{S' \text{ の全ての非空ファイナイトサブセット（有限部分集合）たち }\}\), \(= \{s_1, ..., s_n\}\)
//
ステートメント（言明）たち:
\(\exists \sigma \in \{(1, ..., n) \text{ の全てのパーミュテーション（並べ替え）たち }\} (s_{\sigma_1} \lt ... \lt s_{\sigma_n})\)
//
2: 証明
全体戦略: それをインダクティブ（帰納的）に証明する; ステップ1: それは、\(n = 1\)および\(n = 2\)である時、成立することを見る; ステップ2: それは、\(n = n' - 1\)である時に成立すると仮定し、それは、\(n = n'\)である時に成立することを見る; ステップ3: 本命題を結論する。
ステップ1:
それは、\(n = 1\)である時、空虚に成立する。
それは、\(n = 2\)である時に成立することを見よう。
\(S = \{s_1, s_2\}\)。
\(s_1 \lt s_2\)または\(s_2 \lt s_1\)、リニアリーオーダードセット（線形順序集合）の定義によって。
\(s_1 \lt s_2\)である時は、(\sigma\)を、\(: 1 \mapsto 1; 2 \mapsto 2\)としよう。
すると、\(s_{\sigma_1} \lt s_{\sigma_2}\)。
\(s_2 \lt s_1\)である時は、\(\sigma\)を\(: 1 \mapsto 2; 2 \mapsto 1\)としよう。
すると、\(s_{\sigma_1} \lt s_{\sigma_2}\)。
したがって、いずれにせよ、その\(\sigma\)がある。
ステップ2:
それは、\(n = n' - 1\)、ここで、\(3 \le n'\)、である時に成立すると仮定しよう。
それは、\(n = n'\)である時に成立することを見よう。
\(S = \{s_1, ..., s_{n' - 1}, s_{n'}\}\)。
インダクションプリンシプル（帰納法）によって、以下を満たすある\(\sigma: \{1, ..., n' - 1\} \to \{1, ..., n' - 1\}\)、つまり、\(s_{\sigma_1} \lt ... \lt s_{\sigma_{n' - 1}}\)、がある。
\(\widetilde{S} := \{j \in \{1, ..., n' - 1\} \vert s_{\sigma_j} \lt s_{n'}\} \subseteq \{1, ..., n' - 1\}\)を取ろう。
\(\widetilde{S}\)は、非空か空である。
\(\widetilde{S}\)が非空である時、\(m := Max (\widetilde{S})\)がある、任意のリニアリーオーダードセット（線形順序集合）に対して、任意の非空ファイナイト（有限）サブセット（部分集合）はマキシマム（最大）およびミニマム（最小）を持つという命題によって: \(\{1, ..., n' - 1\}\)はあるリニアリーオーダードセット（線形順序集合）である、リニアリーオーダードセット（線形順序集合）のサブセット（部分集合）でインデュースト（誘導された）リニアオーダリング（線形順序）を持つものの定義によって。
それが意味するのは、\(s_{\sigma_1} \lt ... \lt s_{\sigma_m} \lt s_{n'} \lt s_{\sigma_{m + 1}} \lt ... \lt s_{\sigma_{n' - 1}}\)、ここで、\(m = n' - 1\)である時は、それは、本当には、\(s_{\sigma_1} \lt ... \lt s_{\sigma_m} \lt s_{n'}\)である。
すると、\(\sigma': \{1, ..., n'\} \to \{1, ..., n'\}, 1 \mapsto \sigma_1; ...; m \mapsto \sigma_m; m + 1 \mapsto n'; m + 2 \mapsto \sigma_{m + 1}; ...; n' \mapsto \sigma_{n' - 1}\)を取ろう。
\(\sigma'\)は本当にあるバイジェクション（全単射）である、したがって、あるパーミュテーション（並べ替え）である。
\(s_{\sigma'_1} = s_{\sigma_1} \lt ... \lt s_{\sigma'_m} = s_{\sigma_m} \lt s_{\sigma'_{m + 1}} = s_{n'} \lt s_{\sigma'_{m + 2}} = s_{\sigma_{m + 1}} \lt ... \lt s_{\sigma'_{n'}} = s_{\sigma_{n' - 1}}\)。
したがって、\(s_{\sigma'_1} \lt ... \lt s_{\sigma'_{n'}}\)。
\(\widetilde{S}\)が空である時は、\(s_{n'} \lt s_{\sigma_1} \lt ... \lt s_{\sigma_{n' - 1}}\)。
すると、\(\sigma': \{1, ..., n'\} \to \{1, ..., n'\}, 1 \mapsto n'; 2 \mapsto \sigma_1; ...; n' \mapsto \sigma_{n' - 1}\)を取ろう。
\(\sigma'\)は本当にあるバイジェクション（全単射）である、したがって、あるパーミュテーション（並べ替え）である。
\(s_{\sigma'_1} = s_{n'} \lt s_{\sigma'_2} = s_{\sigma_1} \lt ... \lt s_{\sigma'_{n'}} = s_{\sigma_{n' - 1}}\)。
したがって、\(s_{\sigma'_1} \lt ... \lt s_{\sigma'_{n'}}\)。
したがって、いずれにせよ、以下を満たすその\(\sigma'\)、つまり、\(s_{\sigma'_1} \lt ... \lt s_{\sigma'_{n'}}\)、がある。
したがって、それは、\(n = n'\)である時に成立する。
ステップ3:
したがって、インダクションプリンシプル（帰納法）によって、それは、任意の\(n \in \mathbb{N} \setminus \{0\}\)に対して成立する。
