リニアリーオーダードセット（線形順序集合）に対して、非空ファイナイト（有限）サブセット（部分集合）はマキシマム（最大）およびミニマム（最小）を持つことの記述/証明
話題
About: セット（集合）
この記事の目次
開始コンテキスト
- 読者は、リニアリーオーダードセット（線形順序集合）の定義を知っている。
- 読者は、リニアリーオーダードセット（線形順序集合）のサブセット（部分集合）でインデュースト（誘導された）リニアオーダリング（線形順序）を持つものの定義を知っている。
- 読者は、パーシャリーオーダードセット（半順序集合）のマキシマム（最大）の定義を知っている。
- 読者は、パーシャリーオーダードセット（半順序集合）のミニマム（最小）の定義を知っている。
ターゲットコンテキスト
- 読者は、任意のリニアリーオーダードセット（線形順序集合）に対して、任意の非空ファイナイト（有限）サブセット（部分集合）はマキシマム（最大）およびミニマム（最小）を持つという命題の記述および証明を得る。
オリエンテーション
本サイトにてこれまで議論された定義たちの一覧があります。
本サイトにてこれまで議論された命題たちの一覧があります。
本体
1: 構造化された記述
ここに'構造化された記述'のルールたちがある。
エンティティ（実体）たち:
\(S'\): \(\in \{\text{ 全てのリニアリーオーダードセット（線形順序集合）たち }\}\)で、任意のリニアオーダリング（線形順序）\(\lt'\)を持つもの
\(S\): \(\in \{S' \text{ の非空ファイナイト（有限）サブセット（部分集合）たち }\}\)
//
ステートメント（言明）たち:
\(\exists Max (S)\)
\(\land\)
\(\exists Min (S)\)
//
2: 注
本命題は当然のことと広く想定されているが、それを厳密に証明しよう。
3: 証明
全体戦略: それを、\(S\)のカーディナリティ（濃度）に関してインダクティブ（帰納的）に証明する; ステップ1: \(\vert S \vert = 1\)である時に本命題が成立することを見る; ステップ2: \(1 \le \vert S \vert \le n - 1\)に対して本命題が成立すると仮定し、\(\vert S \vert = n\)に対して本命題が成立することを見る; ステップ3: 本命題を結論する。
ステップ0:
\(S\)はあるリニアリーオーダードセット（線形順序集合）である、リニアリーオーダードセット（線形順序集合）のサブセット（部分集合）でインデュースト（誘導された）リニアオーダリング（線形順序）を持つものの定義によって。
したがって、\(S\)でインデュースト（誘導された）リニアオーダリング（線形順序）\(\lt\)を持つもののことを考える。
ステップ1:
\(\vert S \vert = 1\)としよう。
\(S = \{s_1\}\)。
\(s_1\)はマキシマム（最大）である、なぜなら、\(\forall s \in S \setminus \{s_1\} (s \lt s_1)\)は空虚に成立する。
\(s_1\)はミニマム（最小）である、なぜなら、\(\forall s \in S \setminus \{s_1\} (s_1 \lt s)\)は空虚に成立する。
ステップ2:
本命題は、\(1 \le \vert S \vert \le n - 1\)に対して成立すると仮定しよう。
\(\vert S \vert = n\)であると仮定しよう。
\(S = \{s_1, ..., s_{n - 1}, s_n\}\)。
\(\{s_1, ..., s_{n - 1}\}\)はマキシマム（最大）\(s'\)を持つ。
\(s' \lt s_n\)または\(s_n \lt s'\)、なぜなら、\(S\)はリニアリーオーダード（線形順序付き）である。
\(s' \lt s_n\)である時、各\(s'' \in \{s_1, ..., s_{n - 1}\}\)に対して、\(s'' \le s' \lt s_n\)、したがって、\(s'' \lt s_n\)、したがって、\(s_n\)は\(S\)のマキシマム（最大）である。
\(s_n \lt s'\)である時、各\(s'' \in \{s_1, ..., s_{n - 1}\}\)に対して、\(s'' \le s'\)および\(s_n \lt s'\)、したがって、\(s'\)は\(S\)のマキシマム（最大）である。
したがって、\(S\)はマキシマム（最大）を持つ、いずれにせよ。
\(\{s_1, ..., s_{n - 1}\}\)はミニマム（最小）\(s'\)を持つ。
\(s_n \lt s'\)または\(s' \lt s_n\)、なぜなら、\(S\)はリニアリーオーダード（線形順序付き）である。
\(s_n \lt s'\)である時、各\(s'' \in \{s_1, ..., s_{n - 1}\}\)に対して、\(s_n \lt s' \le s''\)、したがって、\(s_n \lt s''\)、したがって、\(s_n\)は\(S\)のミニマム（最小）である。
\(s' \lt s_n\)である時、各\(s'' \in \{s_1, ..., s_{n - 1}\}\)に対して、\(s' \le s''\)および\(s' \lt s_n\)、したがって、\(s'\)は\(S\)のミニマム（最小）である。
したがって、\(S\)はミニマム（最小）を持つ、いずれにせよ。
ステップ3:
したがって、インダクションプリンシプル（帰納法）によって、\(S\)は、\(\vert S \vert \in \mathbb{N} \setminus \{0\}\)である時いつもマキシマム（最大）およびミニマム（最小）を持つ。
