description/proof of for linearly-ordered set, finite subset can be ordered in line
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 permutation of sequence.
- The reader knows a definition of subset of linearly-ordered set with induced linear ordering.
- The reader admits the proposition that for any linearly-ordered set, any nonempty finite subset has the maximum and the minimum.
Target Context
- The reader will have a description and a proof of the proposition that for any linearly-ordered set, any finite subset can be ordered in a line.
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 the ordering, \(\lt\)
\(S\): \(\in \{\text{ the nonempty finite subsets of } S'\}\), \(= \{s_1, ..., s_n\}\)
//
Statements:
\(\exists \sigma \in \{\text{ the permutations of } (1, ..., n)\} (s_{\sigma_1} \lt ... \lt s_{\sigma_n})\)
//
2: Proof
Whole Strategy: prove it inductively; Step 1: see that it holds when \(n = 1\) and \(n = 2\); Step 2: suppose that it holds when \(n = n' - 1\) and see that it holds when \(n = n'\); Step 3: conclude the proposition.
Step 1:
It vacuously holds when \(n = 1\).
Let us see that it holds when \(n = 2\).
\(S = \{s_1, s_2\}\).
\(s_1 \lt s_2\) or \(s_2 \lt s_1\), by the definition of linearly-ordered set.
When \(s_1 \lt s_2\), let \(\sigma\) be \(: 1 \mapsto 1; 2 \mapsto 2\).
Then, \(s_{\sigma_1} \lt s_{\sigma_2}\).
When \(s_2 \lt s_1\), let \(\sigma\) be \(: 1 \mapsto 2; 2 \mapsto 1\).
Then, \(s_{\sigma_1} \lt s_{\sigma_2}\).
So, anyway, there is that \(\sigma\).
Step 2:
Let us suppose that it holds when \(n = n' - 1\) where \(3 \le n'\).
Let us see that it holds when \(n = n'\).
\(S = \{s_1, ..., s_{n' - 1}, s_{n'}\}\).
By the induction hypothesis, there is a \(\sigma: \{1, ..., n' - 1\} \to \{1, ..., n' - 1\}\) such that \(s_{\sigma_1} \lt ... \lt s_{\sigma_{n' - 1}}\).
Let us take \(\widetilde{S} := \{j \in \{1, ..., n' - 1\} \vert s_{\sigma_j} \lt s_{n'}\} \subseteq \{1, ..., n' - 1\}\).
\(\widetilde{S}\) is nonempty or empty.
When \(\widetilde{S}\) is nonempty, there is \(m := Max (\widetilde{S})\), by the proposition that for any linearly-ordered set, any nonempty finite subset has the maximum and the minimum: \(\{1, ..., n' - 1\}\) is a linearly ordered set, by the definition of subset of linearly-ordered set with induced linear ordering.
That means that \(s_{\sigma_1} \lt ... \lt s_{\sigma_m} \lt s_{n'} \lt s_{\sigma_{m + 1}} \lt ... \lt s_{\sigma_{n' - 1}}\), where when \(m = n' - 1\), it is really \(s_{\sigma_1} \lt ... \lt s_{\sigma_m} \lt s_{n'}\).
Then, let us take \(\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'\) is indeed a bijection, so, a permutation.
\(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}}\).
So, \(s_{\sigma'_1} \lt ... \lt s_{\sigma'_{n'}}\).
When \(\widetilde{S}\) is empty, \(s_{n'} \lt s_{\sigma_1} \lt ... \lt s_{\sigma_{n' - 1}}\).
Then, let us take \(\sigma': \{1, ..., n'\} \to \{1, ..., n'\}, 1 \mapsto n'; 2 \mapsto \sigma_1; ...; n' \mapsto \sigma_{n' - 1}\).
\(\sigma'\) is indeed a bijection, so, a permutation.
\(s_{\sigma'_1} = s_{n'} \lt s_{\sigma'_2} = s_{\sigma_1} \lt ... \lt s_{\sigma'_{n'}} = s_{\sigma_{n' - 1}}\).
So, \(s_{\sigma'_1} \lt ... \lt s_{\sigma'_{n'}}\).
So, anyway, there is that \(\sigma'\) such that \(s_{\sigma'_1} \lt ... \lt s_{\sigma'_{n'}}\).
So, it holds when \(n = n'\).
Step 3:
So, by the induction principle, it holds for any \(n \in \mathbb{N} \setminus \{0\}\).
