Proof of Monotone Sequences and Subsequences: Comparison of All Terms, Growth of the Indices, and Subsequences of Subsequences

Each result cited is universally quantified over the data in its own statement.

Throughout, $\mathbb{N}$ carries the order $\le$ and the strict order $<$ of The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §order, as in Subsequences §subsequence. As in the statement, by Arithmetic and Order of the Natural Numbers §partial-order and Arithmetic and Order of the Natural Numbers §trichotomy, $\le$ is a total order on $\mathbb{N}$ whose strict relation is $<$. The rules for this order used below are those of Arithmetic and Order of the Natural Numbers, as in The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §laws.

Clause monotone. Let $(a_{n})$ be nondecreasing and $m\in\mathbb{N}$. If $n=m$, then $a_{m}\le a_{n}$ by reflexivity of the partial order $\le$ on $X$. If $m<n$, then by Arithmetic and Order of the Natural Numbers §difference there is $d\in\mathbb{N}$ with $n=m+d$, so it suffices to show $a_{m}\le a_{m+d}$ for every $d\in\mathbb{N}$. We induct on $d$, using Arithmetic and Order of the Natural Numbers §induction for the set of those $d\in\mathbb{N}$ with $a_{m}\le a_{m+d}$. For $d=1$ this is the defining inequality at $m$, namely $a_{m}\le a_{m+1}$. If $a_{m}\le a_{m+d}$, then, since $m+(d+1)=(m+d)+1$ by Arithmetic and Order of the Natural Numbers §associative, the defining inequality at $m+d$ gives $a_{m+d}\le a_{m+(d+1)}$, and transitivity of $\le$ gives $a_{m}\le a_{m+(d+1)}$. As $m\le n$ means $m<n$ or $m=n$ by Arithmetic and Order of the Natural Numbers §partial-order, this proves $a_{m}\le a_{n}$.

If $(a_{n})$ is strictly increasing and $m<n$, write again $n=m+d$ with $d\in\mathbb{N}$ and induct on $d$ in the same way: $a_{m}<a_{m+1}$ by definition, and $a_{m}<a_{m+d}$ together with $a_{m+d}<a_{m+(d+1)}$ gives $a_{m}<a_{m+(d+1)}$ by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §strict-transitive. The nonincreasing and strictly decreasing cases are the same arguments with every inequality between terms of $(a_{n})$ reversed: the induction on $d$ gives $a_{m+d}\le a_{m}$, respectively $a_{m+d}<a_{m}$.

Clause index. Recall that $\sigma:\mathbb{N}\to\mathbb{N}$ is strictly increasing. We show $k\le\sigma(k)$ by induction on $k$, using Arithmetic and Order of the Natural Numbers §induction for the set of those $k\in\mathbb{N}$ with $k\le\sigma(k)$. For $k=1$, $1\le\sigma(1)$ by Arithmetic and Order of the Natural Numbers §least. Suppose $k\le\sigma(k)$. Since $\sigma(k)<\sigma(k+1)$ by definition, and $k\le\sigma(k)$ means $k<\sigma(k)$ or $k=\sigma(k)$, we get $k<\sigma(k+1)$ by Arithmetic and Order of the Natural Numbers §partial-order. By Arithmetic and Order of the Natural Numbers §trichotomy, exactly one of $\sigma(k+1)<k+1$, $\sigma(k+1)=k+1$ and $k+1<\sigma(k+1)$ holds; the first is impossible, because then $k<\sigma(k+1)<k+1$, which Arithmetic and Order of the Natural Numbers §successor excludes. Hence $k+1\le\sigma(k+1)$, which completes the induction.

Let $j,k\in\mathbb{N}$. If $j<k$, then $\sigma(j)<\sigma(k)$ by clause monotone, applied to the strictly increasing sequence $\sigma$ in $\mathbb{N}$. Conversely, let $\sigma(j)<\sigma(k)$. If $j=k$, then $\sigma(j)=\sigma(k)$, and if $k<j$, then $\sigma(k)<\sigma(j)$ by what was just shown; both contradict $\sigma(j)<\sigma(k)$ by Arithmetic and Order of the Natural Numbers §trichotomy. So $j<k$, again by Arithmetic and Order of the Natural Numbers §trichotomy.

Clause composition. Recall that $\sigma,\tau:\mathbb{N}\to\mathbb{N}$ are strictly increasing. By Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §composition, $\sigma\circ\tau:\mathbb{N}\to\mathbb{N}$ is a map with $(\sigma\circ\tau)(n)=\sigma(\tau(n))$. For $n\in\mathbb{N}$ we have $\tau(n)<\tau(n+1)$, hence $\sigma(\tau(n))<\sigma(\tau(n+1))$ by clause index; so $\sigma\circ\tau$ is strictly increasing. For a sequence $a:\mathbb{N}\to X$, both $(a\circ\sigma)\circ\tau$ and $a\circ(\sigma\circ\tau)$ are maps from $\mathbb{N}$ to $X$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §composition, and for every $k\in\mathbb{N}$

$$\big((a\circ\sigma)\circ\tau\big)(k)=a\big(\sigma(\tau(k))\big)=\big(a\circ(\sigma\circ\tau)\big)(k),$$

so they are equal by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §equality.

Consequently, let $a$ be a sequence in a set $X$. By Subsequences §subsequence, a subsequence of a subsequence of $a$ is $(a\circ\sigma')\circ\tau'$ for some strictly increasing $\sigma',\tau':\mathbb{N}\to\mathbb{N}$. What was just shown, applied to $\sigma'$ and $\tau'$ in place of $\sigma$ and $\tau$, gives $(a\circ\sigma')\circ\tau'=a\circ(\sigma'\circ\tau')$ with $\sigma'\circ\tau'$ strictly increasing, which is a subsequence of $a$ by Subsequences §subsequence.