Strictly Increasing Sequence on Ordered Set
Lemma
Let $\struct {S, \preceq}$ be a totally ordered set.
Let $\sequence {r_k}_{p \mathop \le k \mathop \le q}$ be a finite sequence of elements of $\struct {S, \preceq}$.
Then $\sequence {r_k}_{p \mathop \le k \mathop \le q}$ is strictly increasing if and only if:
- $\forall k \in \closedint {p + 1} q: r_{k - 1} \prec r_k$
Proof
Let $\sequence {r_k}_{p \mathop \le k \mathop \le q}$ be strictly increasing.
Because $\forall k \in \N_{>0}: k - 1 < k$, it follows directly that:
- $\forall k \in \closedint {p + 1} q: r_{k - 1} \prec r_k$
For the other direction, we use a Proof by Contraposition.
To that end, suppose $\sequence {r_k}_{p \mathop \le k \mathop \le q}$ is not strictly increasing.
Let $K$ be the set of all $k \in \closedint p q$ such that:
- $\exists j \in \closedint p q$ such that $j < k$ and $r_k \preceq r_j$
The set $K$ is not empty because $\sequence {r_k}_{p \mathop \le k \mathop \le q}$ is not strictly increasing.
As $K \subset \N$ and the latter is well-ordered, then so is $K$.
Thus $K$ has a minimal element $m$.
Thus there exists $j \in \closedint p q$ such that:
- $j < m$
and:
- $r_m \preceq r_j$
Because $m - 1 < m$:
- $j \le m - 1$
and so:
- $m - 1 \notin K$
So:
- $r_m \preceq r_j\prec r_{m - 1}$
Since orderings are transitive, it follows
- $r_m \preceq r_{m - 1}$
From Rule of Transposition it follows that
- $\forall k \in \closedint {p + 1} q: r_{k - 1} \prec r_k \implies \sequence {r_k}_{p \mathop \le k \mathop \le q}$ is strictly increasing.
The result follows.
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 18$: Induced $N$-ary Operations: Lemma for Theorem $18.4$