Proof of Every Sequence in a Totally Ordered Set Has a Monotone Subsequence

Each result cited below is universally quantified over the data in its own statement, and is applied to the data named where it is cited.

The total order $\le$ on $X$ is as in Sets and Maps: Ordinary Notation §orders, which the setting The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion of the statement carries; let $<$ be its strict relation. As in Subsequences §subsequence, $\mathbb{N}$ carries its order $\le$, a total order whose strict relation is $<$; by Arithmetic and Order of the Natural Numbers §partial-order, $u\le v$ holds if and only if $u<v$ or $u=v$, and $<$ is transitive on $\mathbb{N}$. By Arithmetic and Order of the Natural Numbers §well-order and Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §least-unique, every subset $s$ of $\mathbb{N}$ with at least one element has exactly one least element $\min s$. Every choice below is of such a least element, so no axiom of choice is used. For a map $\sigma:\mathbb{N}\to\mathbb{N}$, the terms of $a\circ\sigma$ are $(a\circ\sigma)(i)=a_{\sigma(i)}$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §composition.

Call $m\in\mathbb{N}$ a peak if $a_{n}<a_{m}$ for every $n\in\mathbb{N}$ with $m<n$, and let

$$P=\{m\in\mathbb{N}:\forall n\,((n\in\mathbb{N}\wedge m<n)\Rightarrow a_{n}<a_{m})\},$$

a subset of $\mathbb{N}$ by Sets and Maps: Ordinary Notation §set-builder; every set written $\{x\in A:\dots\}$ below is likewise a subset of $A$ by that clause. By the law of excluded middle, either for every $k\in\mathbb{N}$ there is $p\in P$ with $k<p$ (Case 1), or there is $k\in\mathbb{N}$ such that no $p\in P$ satisfies $k<p$ (Case 2).

Dichotomy, Case 1. For $u\in\mathbb{N}$ let $P_{u}=\{p\in P:u<p\}$; it has an element by the case assumption, so $\min P_{u}$ exists, lies in $P$, and satisfies $u<\min P_{u}$. By Maps and Relations Given by Formulas §binary there is a map $g:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ with $g(i,u)=\min P_{u}$. As $P_{1}\subseteq P$ has an element, $\min P$ exists. By Recursion on the Natural Numbers Starting at One §recursion, applied to the set $\mathbb{N}$, the element $\min P$ and $g$, there is a map $\sigma:\mathbb{N}\to\mathbb{N}$ with $\sigma(1)=\min P$ and $\sigma(i+1)=\min P_{\sigma(i)}$ for every $i\in\mathbb{N}$. Every value of $\sigma$ lies in $P$: $\sigma(1)=\min P\in P$, and if $i\neq1$, then $i=d+1$ for some $d\in\mathbb{N}$ by Arithmetic and Order of the Natural Numbers §predecessor, so $\sigma(i)=\min P_{\sigma(d)}\in P$. For every $i\in\mathbb{N}$, $\sigma(i)<\min P_{\sigma(i)}=\sigma(i+1)$, so $\sigma$ is strictly increasing and $a\circ\sigma$ is a subsequence of $(a_{n})$. Since $\sigma(i)$ is a peak and $\sigma(i)<\sigma(i+1)$, $a_{\sigma(i+1)}<a_{\sigma(i)}$ for every $i\in\mathbb{N}$, so $a\circ\sigma$ is strictly decreasing.

Dichotomy, Case 2. Fix such a $k$, let $K=k+1$ and $B=\{n\in\mathbb{N}:K\le n\}$, a subset of $\mathbb{N}$ containing $K$. Let $n\in B$. Since $k<k+1$ by Arithmetic and Order of the Natural Numbers §successor and $K\le n$, we have $k<n$, so $n\notin P$ by the case assumption. Hence there is $m\in\mathbb{N}$ with $n<m$ for which $a_{m}<a_{n}$ fails, that is, $a_{n}\le a_{m}$ by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §total-negation, the order on $X$ being total. So $T_{n}=\{m\in\mathbb{N}:n<m\wedge a_{n}\le a_{m}\}$ has an element, $\min T_{n}$ exists, $n<\min T_{n}$ and $a_{n}\le a_{\min T_{n}}$; moreover $K\le n<\min T_{n}$ gives $\min T_{n}\in B$. By Maps and Relations Given by Formulas §binary there is a map $h:\mathbb{N}\times B\to B$ with $h(i,u)=\min T_{u}$, and by Recursion on the Natural Numbers Starting at One §recursion, applied to the set $B$, the element $K$ and $h$, there is a map $\tau:\mathbb{N}\to B$ with $\tau(1)=K$ and $\tau(i+1)=\min T_{\tau(i)}$ for every $i\in\mathbb{N}$. As $B\subseteq\mathbb{N}$, $\tau$ is also a map from $\mathbb{N}$ to $\mathbb{N}$ by Functions, Values of a Function, and Functions from One Class to Another §map. For every $i\in\mathbb{N}$, $\tau(i)<\tau(i+1)$ and $a_{\tau(i)}\le a_{\tau(i+1)}$. Thus $\tau$ is strictly increasing, and $a\circ\tau$ is a subsequence of $(a_{n})$ that is nondecreasing.

In Case 1 the sequence has a strictly decreasing subsequence, and in Case 2 a nondecreasing one, which proves the dichotomy clause.

Monotone. By the dichotomy clause there is a subsequence $(b_{i})$ that is nondecreasing, hence monotone, or strictly decreasing. In the latter case $b_{i+1}<b_{i}$ gives $b_{i+1}\le b_{i}$ by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §strict-characterization, for every $i\in\mathbb{N}$, so $(b_{i})$ is nonincreasing and hence monotone by Monotone Sequences §monotone.