Proof of Monotone Sequences, Subsequences and Bounded Sequences: Comparison of All Terms, Growth of the Indices, Subsequences of Subsequences, and Two-Sided Bounds

Throughout, $\mathbb{N}$ carries its order $\le$, a total order whose strict relation is $<$, as recorded in Subsequences §subsequence; the rules for this order used below are those of Arithmetic and Order of the Natural Numbers.

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 $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 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. Let $\sigma:\mathbb{N}\to\mathbb{N}$ be 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. Taking $k=N$ gives $N\le\sigma(N)$.

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. Let $\sigma,\tau:\mathbb{N}\to\mathbb{N}$ be 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, if $b=a\circ\sigma$ is a subsequence of $(a_{n})$ and $b\circ\tau$ a subsequence of $b$, then $b\circ\tau=a\circ(\sigma\circ\tau)$ with $\sigma\circ\tau$ strictly increasing, which is a subsequence of $(a_{n})$ by Subsequences §subsequence.

Clause bounded. Let $F$ be an ordered field and $(a_{n})$ a sequence in $F$. Suppose first that $(a_{n})$ is bounded, with $M\in F$ such that $|a_{n}|\le M$ for every $n\in\mathbb{N}$. By Rules of Arithmetic and Order in an Ordered Field §absolute-value, $-M\le a_{n}\le M$ for every $n$, so $M$ is an upper bound and $-M$ a lower bound of $\{a_{n}:n\in\mathbb{N}\}$ in the sense of Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §bounds; thus $(a_{n})$ is bounded above and bounded below.

Conversely, let $U$ be an upper bound and $V$ a lower bound of $\{a_{n}:n\in\mathbb{N}\}$, and put $M=|U|+|V|$. Since $0\le|U|$ and $0\le|V|$ by Rules of Arithmetic and Order in an Ordered Field §absolute-value, Rules of Arithmetic and Order in an Ordered Field §order-sum gives $|U|\le M$ and $|V|\le M$, hence $-M\le-|V|$ by Rules of Arithmetic and Order in an Ordered Field §order-negative. Using $U\le|U|$ and $-|V|\le V$ from Rules of Arithmetic and Order in an Ordered Field §absolute-value, for every $n\in\mathbb{N}$

$$-M\le-|V|\le V\le a_{n}\le U\le|U|\le M,$$

so $-M\le a_{n}\le M$, that is $|a_{n}|\le M$ by Rules of Arithmetic and Order in an Ordered Field §absolute-value. Hence $(a_{n})$ is bounded.