Proof of The Diagonal Subsequence Lemma for Bounded Real Arrays

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 proof uses no form of choice: at each stage a specific subsequence is singled out by a formula, and the sequences built in stages are given by the recursion of Recursion on the Natural Numbers Starting at One §recursion. By The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §reals, $\mathbb{R}$ is an ordered field, with the rules of Rules of Arithmetic and Order in an Ordered Field carried by the setting. Natural numbers are read in $\mathbb{R}$ as in The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §identification, this reading being that of The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §embedding, and the order agrees whether formed in $\mathbb{N}$ or in $\mathbb{R}$, by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §agreement. In particular $0<n$ in $\mathbb{R}$ for every $n\in\mathbb{N}$, by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §naturals. $\mathbb{N}$ carries its order, with the facts of Arithmetic and Order of the Natural Numbers; strictly increasing sequences in $\mathbb{N}$ are as in Monotone Sequences §monotone, and $\Sigma$ denotes the set of strictly increasing $\sigma\in\mathbb{N}^{\mathbb{N}}$, with $\mathbb{N}^{\mathbb{N}}$ the set of maps of Sets and Maps: Ordinary Notation §maps; $\Sigma$ is a set, being a subset of $\mathbb{N}^{\mathbb{N}}$ given by a property, by Sets and Maps: Ordinary Notation §set-builder. By Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §identity, $\mathrm{id}_{\mathbb{N}}$ is a map $\mathbb{N}\to\mathbb{N}$ with $\mathrm{id}_{\mathbb{N}}(u)=u$ for every $u\in\mathbb{N}$, so $\mathrm{id}_{\mathbb{N}}\in\Sigma$ by Arithmetic and Order of the Natural Numbers §successor, and $\Sigma$ is closed under composition by Monotone Sequences and Subsequences: Comparison of All Terms, Growth of the Indices, and Subsequences of Subsequences §composition.

Step 1 (A canonical convergent subsequence). Let $b$ be a bounded sequence in $\mathbb{R}$. By Limits of Sequences of Real Numbers: Uniqueness, Boundedness, Constants, Tails, Arithmetic, Quotients, Absolute Values, Finite Sums, Order, Squeezing, Domination and Subsequences §two-sided it is bounded above and bounded below, so by Bounded Sequences of Real Numbers §bounded its set of terms has an upper bound $M^{+}$ and a lower bound $M^{-}$. For $n\in\mathbb{N}$ let $T_{n}=\{z\in\mathbb{R}: z=b_{m}\text{ for some }m\in\mathbb{N}\text{ with }n\le m\}$, a subset of $\mathbb{R}$ by Sets and Maps: Ordinary Notation §set-builder. It contains $b_{n}$, as $n\le n$ by Arithmetic and Order of the Natural Numbers §partial-order, and is bounded above by $M^{+}$, so it has a supremum by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §supremum, which is unique by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §supremum; let $U_{n}$ be this supremum. If $n\le n'$, then $T_{n'}\subseteq T_{n}$, so $U_{n}$ is an upper bound of $T_{n'}$ and $U_{n'}\le U_{n}$; and $M^{-}\le b_{n}\le U_{n}$. Since $U_{n}$ is defined for every $n\in\mathbb{N}$, the set $\{z\in\mathbb{R}: z=U_{n}\text{ for some }n\in\mathbb{N}\}$, a subset of $\mathbb{R}$ by Sets and Maps: Ordinary Notation §set-builder, is nonempty and bounded below by $M^{-}$, so it has an infimum by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §infimum, which is unique by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §supremum; let $L_{b}$ be this infimum.

(A) For every positive $\varepsilon\in\mathbb{R}$ and every $u\in\mathbb{N}$ there is $m\in\mathbb{N}$ with $u<m$ and $|b_{m}-L_{b}|<\varepsilon$. By Arbitrary Positive Slack, and Approximation of Suprema and Infima, in the Real Numbers §epsilon-below choose $n_{0}\in\mathbb{N}$ with $U_{n_{0}}<L_{b}+\varepsilon$, and put $n=n_{0}+u$, so $n_{0}<n$ and $u<n$ by Arithmetic and Order of the Natural Numbers §difference and Arithmetic and Order of the Natural Numbers §commutative. Then $L_{b}\le U_{n}\le U_{n_{0}}<L_{b}+\varepsilon$. By Arbitrary Positive Slack, and Approximation of Suprema and Infima, in the Real Numbers §epsilon-above there is $m\in\mathbb{N}$ with $n\le m$ and $U_{n}-\varepsilon<b_{m}$; thus $L_{b}-\varepsilon\le U_{n}-\varepsilon<b_{m}\le U_{n}<L_{b}+\varepsilon$, so $L_{b}-\varepsilon<b_{m}<L_{b}+\varepsilon$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §mixed. Subtracting $L_{b}$ by Rules of Arithmetic and Order in an Ordered Field §order-sum gives $-\varepsilon<b_{m}-L_{b}<\varepsilon$, so $|b_{m}-L_{b}|<\varepsilon$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §absolute-strict. Finally $u<m$: by Arithmetic and Order of the Natural Numbers §partial-order, $n\le m$ means $n<m$ or $n=m$, and in the first case $u<m$ follows from $u<n$ by the strict transitivity in the same clause.

For $j,u\in\mathbb{N}$ the set $E_{b}(j,u)=\{m\in\mathbb{N}:u<m,\ |b_{m}-L_{b}|<1/j\}$ is nonempty by (A), $1/j$ being positive: $0<j$ (shown at the start), so $j\neq0$ by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §strict-characterization, $1/j=1\cdot j^{-1}=j^{-1}$ by Negatives, Differences, Reciprocals and Quotients §reciprocal and the commutativity and unit law of Commutative Rings §ring, and $0<j^{-1}$ by Rules of Arithmetic and Order in an Ordered Field §positive-reciprocal, so it has a least element by Arithmetic and Order of the Natural Numbers §well-order, which is unique by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §least; let $\mu_{b}(j,u)$ be this least element. With $g(n,u)=\mu_{b}(n+1,u)$, a map $g:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ by Maps and Relations Given by Formulas §binary, Recursion on the Natural Numbers Starting at One §recursion gives exactly one map $\sigma_{b}:\mathbb{N}\to\mathbb{N}$ with $\sigma_{b}(1)=\mu_{b}(1,1)$ and $\sigma_{b}(j+1)=\mu_{b}(j+1,\sigma_{b}(j))$ for every $j\in\mathbb{N}$. Then $\sigma_{b}(j)<\sigma_{b}(j+1)$, so $\sigma_{b}\in\Sigma$; and, as every $j\in\mathbb{N}$ is $1$ or a successor by Arithmetic and Order of the Natural Numbers §predecessor, $|b_{\sigma_{b}(j)}-L_{b}|<1/j$ for every $j$. Since $1/j\to0$ by Completeness of the Real Numbers for Sequences: Monotone Convergence, the Bolzano-Weierstrass Theorem and Cauchy Sequences §reciprocals, the subsequence $b\circ\sigma_{b}$ converges to $L_{b}$ by Limits of Sequences of Real Numbers: Uniqueness, Boundedness, Constants, Tails, Arithmetic, Quotients, Absolute Values, Finite Sums, Order, Squeezing, Domination and Subsequences §domination. Since $L_{b}$ is the unique infimum (Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §supremum) and $\sigma_{b}$ the unique map above, $\sigma_{b}$ is determined by $b$ alone.

Step 2 (Nested index sequences, by recursion). For $k\in\mathbb{N}$ and $\tau\in\Sigma$ let $c^{k,\tau}$ be the sequence $i\mapsto a_{\tau(i),k}$, a map $\mathbb{N}\to\mathbb{R}$ by Sets and Maps: Ordinary Notation §maps, as $a_{\tau(i),k}\in\mathbb{R}$ for every $i\in\mathbb{N}$. It is bounded: if $|a_{m,k}|\le M$ for every $m\in\mathbb{N}$, then $|a_{\tau(i),k}|\le M$ for every $i$. By Step 1 and Maps and Relations Given by Formulas §binary, $(k,\tau)\mapsto\tau\circ\sigma_{c^{k+1,\tau}}$ is a map $\mathbb{N}\times\Sigma\to\Sigma$. As $\Sigma$ is a set (shown at the start), Recursion on the Natural Numbers Starting at One §recursion applies: there is a map $\mathbb{N}\to\Sigma$, $k\mapsto\tau_{k}$, with

$$\tau_{1}=\sigma_{c^{1,\mathrm{id}}},\qquad\tau_{k+1}=\tau_{k}\circ\rho_{k},\quad\text{where }\rho_{k}=\sigma_{c^{k+1,\tau_{k}}}\in\Sigma .$$

For every $k\in\mathbb{N}$ the sequence $(a_{\tau_{k}(i),k})_{i\in\mathbb{N}}$ converges: it is $c^{1,\mathrm{id}}\circ\sigma_{c^{1,\mathrm{id}}}$ if $k=1$, and $c^{l+1,\tau_{l}}\circ\sigma_{c^{l+1,\tau_{l}}}$ if $k=l+1$, which converge by Step 1; every $k$ is of one of these forms by Arithmetic and Order of the Natural Numbers §predecessor.

Step 3 (Nesting). Let $P$ be the set of $j\in\mathbb{N}$ such that for every $k\in\mathbb{N}$ with $k\le j$ there is $\pi\in\Sigma$ with $\tau_{j}=\tau_{k}\circ\pi$. Then $1\in P$: $k\le1$ forces $k=1$ by Arithmetic and Order of the Natural Numbers §least and Arithmetic and Order of the Natural Numbers §partial-order, and $\pi=\mathrm{id}_{\mathbb{N}}$ works, as $\tau_{1}=\tau_{1}\circ\mathrm{id}_{\mathbb{N}}$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §identity-neutral. Let $j\in P$ and $k\le j+1$. If $k=j+1$, take $\pi=\mathrm{id}_{\mathbb{N}}$, again by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §identity-neutral. Otherwise $k<j+1$, hence $k\le j$ by Arithmetic and Order of the Natural Numbers §successor and Arithmetic and Order of the Natural Numbers §trichotomy; with $\pi$ from $j\in P$, $\tau_{j+1}=(\tau_{k}\circ\pi)\circ\rho_{j}=\tau_{k}\circ(\pi\circ\rho_{j})$ and $\pi\circ\rho_{j}\in\Sigma$, by Monotone Sequences and Subsequences: Comparison of All Terms, Growth of the Indices, and Subsequences of Subsequences §composition. So $j+1\in P$, and $P=\mathbb{N}$ by Arithmetic and Order of the Natural Numbers §induction.

Step 4 (The diagonal). Put $n_{j}=\tau_{j}(j)$ for $j\in\mathbb{N}$. We have $j<j+1$ by Arithmetic and Order of the Natural Numbers §successor and $j+1\le\rho_{j}(j+1)$ by Monotone Sequences and Subsequences: Comparison of All Terms, Growth of the Indices, and Subsequences of Subsequences §index; by Arithmetic and Order of the Natural Numbers §partial-order, the latter means $j+1<\rho_{j}(j+1)$ or $j+1=\rho_{j}(j+1)$, so $j<\rho_{j}(j+1)$, using the strict transitivity in that clause in the first case. Hence Monotone Sequences and Subsequences: Comparison of All Terms, Growth of the Indices, and Subsequences of Subsequences §index gives $n_{j}=\tau_{j}(j)<\tau_{j}(\rho_{j}(j+1))=\tau_{j+1}(j+1)=n_{j+1}$; so $(n_{j})$ is strictly increasing, and $(a_{n_{j},k})_{j}$ is a subsequence of $(a_{m,k})_{m}$ for every $k$. Fix $k\in\mathbb{N}$; by Step 2, $(a_{\tau_{k}(i),k})_{i}$ converges to some $L\in\mathbb{R}$. Let $\varepsilon\in\mathbb{R}$ be positive. First choose, by Convergent Sequences of Real Numbers §converges, $I\in\mathbb{N}$ with $|a_{\tau_{k}(i),k}-L|<\varepsilon$ for every $i\ge I$; then put $J=k+I$, so that $k<J$ and $I<J$ by Arithmetic and Order of the Natural Numbers §difference and Arithmetic and Order of the Natural Numbers §commutative. Let $j\ge J$. By Arithmetic and Order of the Natural Numbers §partial-order, $J\le j$ means $J<j$ or $J=j$, so $k<j$ from $k<J$, using the strict transitivity in that clause in the first case, and hence $k\le j$ by the same clause. So by Step 3 there is $\pi\in\Sigma$ with $\tau_{j}=\tau_{k}\circ\pi$, whence $n_{j}=\tau_{k}(\pi(j))$. Moreover $j\le\pi(j)$ by Monotone Sequences and Subsequences: Comparison of All Terms, Growth of the Indices, and Subsequences of Subsequences §index, so $J\le\pi(j)$ by the transitivity in Arithmetic and Order of the Natural Numbers §partial-order; as $I<J$, this gives $I<\pi(j)$ in the same way as above, and so $I\le\pi(j)$. Hence $|a_{n_{j},k}-L|<\varepsilon$. By Convergent Sequences of Real Numbers §converges, $(a_{n_{j},k})_{j}$ converges to $L$. As $k$ was arbitrary, $(n_{j})$ is as required.