description/proof of that for linearly-ordered set, nonempty finite subset has maximum and minimum
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of linearly-ordered set.
- The reader knows a definition of subset of linearly-ordered set with induced linear ordering.
- The reader knows a definition of maximum of partially-ordered set.
- The reader knows a definition of minimum of partially-ordered set.
Target Context
- The reader will have a description and a proof of the proposition that for any linearly-ordered set, any nonempty finite subset has the maximum and the minimum.
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'\): \(\in \{\text{ the linearly-ordered sets }\}\) with any linear ordering, \(\lt'\)
\(S\): \(\in \{\text{ the nonempty finite subsets of } S'\}\)
//
Statements:
\(\exists Max (S)\)
\(\land\)
\(\exists Min (S)\)
//
2: Note
This proposition is prevalently assumed to be a matter of of course, but let us prove it rigorously.
3: Proof
Whole Strategy: prove it inductively with respect to the cardinality of \(S\); Step 1: see that the proposition holds when \(\vert S \vert = 1\); Step 2: suppose that the proposition holds for \(1 \le \vert S \vert \le n - 1\), and see that the proposition holds for \(\vert S \vert = n\); Step 3: conclude the proposition.
Step 0:
\(S\) is a linearly-ordered set, by the definition of subset of linearly-ordered set with induced linear ordering.
So, we think of \(S\) with the induced linear ordering, \(\lt\).
Step 1:
Let \(\vert S \vert = 1\).
\(S = \{s_1\}\).
\(s_1\) is the maximum, because \(\forall s \in S \setminus \{s_1\} (s \lt s_1)\) holds vacuously.
\(s_1\) is the minimum, because \(\forall s \in S \setminus \{s_1\} (s_1 \lt s)\) holds vacuously.
Step 2:
Let us suppose that the proposition holds for \(1 \le \vert S \vert \le n - 1\).
Let us suppose that \(\vert S \vert = n\).
\(S = \{s_1, ..., s_{n - 1}, s_n\}\).
\(\{s_1, ..., s_{n - 1}\}\) has the maximum, \(s'\).
\(s' \lt s_n\) or \(s_n \lt s'\), because \(S\) is linearly-ordered.
When \(s' \lt s_n\), for each \(s'' \in \{s_1, ..., s_{n - 1}\}\), \(s'' \le s' \lt s_n\), so, \(s'' \lt s_n\), so, \(s_n\) is the maximum of \(S\).
When \(s_n \lt s'\), for each \(s'' \in \{s_1, ..., s_{n - 1}\}\), \(s'' \le s'\) and \(s_n \lt s'\), so, \(s'\) is the maximum of \(S\).
So, \(S\) has the maximum anyway.
\(\{s_1, ..., s_{n - 1}\}\) has the minimum, \(s'\).
\(s_n \lt s'\) or \(s' \lt s_n\), because \(S\) is linearly-ordered.
When \(s_n \lt s'\), for each \(s'' \in \{s_1, ..., s_{n - 1}\}\), \(s_n \lt s' \le s''\), so, \(s_n \lt s''\), so, \(s_n\) is the minimum of \(S\).
When \(s' \lt s_n\), for each \(s'' \in \{s_1, ..., s_{n - 1}\}\), \(s' \le s''\) and \(s' \lt s_n\), so, \(s'\) is the minimum of \(S\).
So, \(S\) has the minimum anyway.
Step 3:
So, by the induction principle, \(S\) has the maximum and the minimum whenever \(\vert S \vert \in \mathbb{N} \setminus \{0\}\).
