Proof of The Diagonal Subsequence Lemma for Bounded Real Arrays

Throughout, $\Sigma$ denotes the set of strictly increasing functions $\mathbb{N}\to\mathbb{N}$, a subset of the set of all functions $\mathbb{N}\to\mathbb{N}$; it contains the identity $\mathrm{id}$ and is closed under composition by Monotone Sequences and Subsequences: Comparison of All Terms, Growth of the Indices, and Subsequences of Subsequences (iii), and for $\sigma\in\Sigma$ we use $k\le\sigma(k)$ and the equivalence of $\sigma(j)<\sigma(k)$ with $j<k$, from Monotone Sequences and Subsequences: Comparison of All Terms, Growth of the Indices, and Subsequences of Subsequences (ii).

Step 1: a canonical convergent subsequence. Let $b=(b_{n})$ be a bounded sequence in $\mathbb{R}$ and let $L_{b}=\limsup_{n\to\infty}b_{n}$ be its limit superior. We first show: for every real $\varepsilon>0$ and every $u\in\mathbb{N}$ there is $n\in\mathbb{N}$ with $u<n$ and $|b_{n}-L_{b}|<\varepsilon$. By Properties of the Limit Superior and the Limit Inferior: Tail Formula, Order, Comparison, Bounds, Eventual and Frequent Inequalities, Subsequences, Negation and Convergence (v) there is $N\in\mathbb{N}$ with $b_{n}<L_{b}+\varepsilon$ for every $n\ge N$. By Properties of the Limit Superior and the Limit Inferior: Tail Formula, Order, Comparison, Bounds, Eventual and Frequent Inequalities, Subsequences, Negation and Convergence (vi), applied with the index $N+u$, there is $n\ge N+u$ with $L_{b}-\varepsilon<b_{n}$. Then $n\ge N$ and $n>u$, so $L_{b}-\varepsilon<b_{n}<L_{b}+\varepsilon$, as claimed.

Hence, for $j,u\in\mathbb{N}$, the set

$$E_{b}(j,u)=\{n\in\mathbb{N}:u<n\text{ and }|b_{n}-L_{b}|<1/j\}$$

is nonempty and so has a least element by Arithmetic and Order of the Natural Numbers (xv); call it $\mu_{b}(j,u)$. By Recursion on the Natural Numbers Starting at One (i) there is exactly one function $\sigma_{b}:\mathbb{N}\to\mathbb{N}$ with

$$\sigma_{b}(1)=\mu_{b}(1,1),\qquad\sigma_{b}(j+1)=\mu_{b}\bigl(j+1,\sigma_{b}(j)\bigr)\quad(j\in\mathbb{N}).$$

By the definition of $E_{b}$, $\sigma_{b}(j)<\sigma_{b}(j+1)$, so $\sigma_{b}\in\Sigma$, and $|b_{\sigma_{b}(j)}-L_{b}|<1/j$ for every $j\in\mathbb{N}$ (for $j=1$ directly, for a successor $j$ from the recursion). Since $1/j\to0$ by Completeness of the Real Numbers for Sequences: Monotone Convergence, the Bolzano-Weierstrass Theorem and Cauchy Sequences (i), 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 (xii). The function $\sigma_{b}$ is determined by $b$ alone.

Step 2: nested index sequences. For $k\in\mathbb{N}$ and $\sigma\in\Sigma$ let $c^{k,\sigma}$ be the sequence $i\mapsto a_{\sigma(i),k}$. It is bounded: if $|a_{m,k}|\le M$ for every $m$, then $|a_{\sigma(i),k}|\le M$ for every $i$. So, by Step 1, $(k,\sigma)\mapsto\sigma\circ\sigma_{c^{k+1,\sigma}}$ is a function $\mathbb{N}\times\Sigma\to\Sigma$, and Recursion on the Natural Numbers Starting at One (i) gives a sequence $(\tau_{k})_{k\in\mathbb{N}}$ in $\Sigma$ 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: for $k=1$ it is $c^{1,\mathrm{id}}\circ\sigma_{c^{1,\mathrm{id}}}$, and for $k=l+1$ it is $c^{l+1,\tau_{l}}\circ\sigma_{c^{l+1,\tau_{l}}}$, both convergent by Step 1. Let $A_{k}$ be its limit.

Step 3: nesting. We show by induction on $j\in\mathbb{N}$: for every $k\le j$ there is $\pi\in\Sigma$ with $\tau_{j}=\tau_{k}\circ\pi$. For $j=1$ the only $k$ is $1$, and $\pi=\mathrm{id}$ works. Suppose the assertion holds for $j$, and let $k\le j+1$. If $k=j+1$, take $\pi=\mathrm{id}$. Otherwise $k\le j$, and with $\pi$ from the hypothesis, $\tau_{j+1}=\tau_{j}\circ\rho_{j}=\tau_{k}\circ(\pi\circ\rho_{j})$ with $\pi\circ\rho_{j}\in\Sigma$.

Step 4: the diagonal. Put $m_{j}=\tau_{j}(j)$ for $j\in\mathbb{N}$. Since $j<j+1\le\rho_{j}(j+1)$, we get

$$m_{j}=\tau_{j}(j)<\tau_{j}\bigl(\rho_{j}(j+1)\bigr)=\tau_{j+1}(j+1)=m_{j+1},$$

so $(m_{j})$ is strictly increasing. Fix $k\in\mathbb{N}$; we show that $(a_{m_{j},k})_{j}$ converges to $A_{k}$. Let $\varepsilon>0$. First choose, by Convergent Sequences of Real Numbers (i) and Step 2, $I\in\mathbb{N}$ with $|a_{\tau_{k}(i),k}-A_{k}|<\varepsilon$ for every $i\ge I$; then put $J=k+I$. Let $j\ge J$. Then $k\le j$, so Step 3 gives $\pi\in\Sigma$ with $\tau_{j}=\tau_{k}\circ\pi$, whence $m_{j}=\tau_{k}(\pi(j))$; and $\pi(j)\ge j\ge I$. Therefore

$$|a_{m_{j},k}-A_{k}|=|a_{\tau_{k}(\pi(j)),k}-A_{k}|<\varepsilon\qquad(j\ge J).$$

So $(a_{m_{j},k})_{j}$ converges to $A_{k}$ by Convergent Sequences of Real Numbers (i). As $k$ was arbitrary, $(m_{j})$ is as required by (i).