Strictly Increasing Sequence on Ordered Set

From ProofWiki
Jump to navigation Jump to search

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