The Diagonalization Strategy

From Separate Choices to One Sequence

The Integration Strategy converted information across an interval into a conclusion about total change or an average. A different difficulty arises when a proof has countably many requirements: one may be able to meet the first requirement by passing to a subsequence, then the second by passing to a further subsequence, and so on. The challenge is to make all those choices compatible in a single sequence.

Diagonalization solves this by arranging the choices in nested stages and then selecting one term from each stage. At stage \(k\), we preserve the first \(k\) requirements. The diagonal sequence moves farther into these stages, so any fixed requirement is eventually preserved. The method is useful precisely when the number of requirements is countable and each finite stage can be handled.

The word “diagonal” refers to the pattern of choices, not to a special algebraic operation. A common setup is an array of terms: each row has a convergent subsequence, and the goal is to find one subsequence that behaves well in every row. The diagonal choice takes its \(j\)-th term from the \(j\)-th nested selection.

A Selection Lemma for Nested Sets

The basic index-selection principle can be stated without mentioning convergence. It makes precise how to choose indices that eventually satisfy every one of countably many nested conditions.

Proof. Since \(A_1\) is infinite, choose \(n_1\in A_1\). Suppose \(n_1<\cdots<n_{j-1}\) have been chosen. The set \(A_j\) is infinite, so it cannot be contained in the finite set \(\{1,\ldots,n_{j-1}\}\). Choose \(n_j\in A_j\) with \(n_j>n_{j-1}\). This defines a strictly increasing sequence with \(n_j\in A_j\) at every stage. If \(j\geq k\), nesting gives \(A_j\subseteq A_k\), and therefore \(n_j\in A_k\). \(\square\)

The final assertion explains the useful feature of the construction. Membership in \(A_k\) is not required of the first \(k-1\) selected indices, but it holds for every subsequent one. In sequence arguments, “eventually” is enough: convergence and many other limiting properties are unaffected by finitely many initial terms.

One Subsequence for Countably Many Sequences

The selection lemma underlies a central convergence form of diagonalization. The only compactness input needed here is the Bolzano–Weierstrass Theorem: every bounded real sequence has a convergent subsequence. Rather than finding a separate subsequence for each bounded sequence and stopping there, we make those extractions successively nested.

Proof. Begin with the full index sequence \(1,2,3,\ldots\). By the Bolzano–Weierstrass Theorem, the bounded sequence in row \(1\) has a convergent subsequence. Write its indices as an increasing sequence \(m_1^{(1)}<m_2^{(1)}<\cdots\). At stage \(2\), consider row \(2\) only along those indices. That sequence is still bounded, so it has a convergent subsequence; denote the resulting indices by \(m_1^{(2)}<m_2^{(2)}<\cdots\). They form a subsequence of the stage \(1\) indices. Continue inductively: at stage \(k\), extract from the stage \(k-1\) indices a subsequence along which row \(k\) converges. Each later stage is a subsequence of every earlier stage.

Define \(n_j=m_j^{(j)}\), the \(j\)-th index chosen at stage \(j\). These indices increase strictly. Indeed, the stage \(j+1\) sequence is a subsequence of the stage \(j\) sequence. Its \((j+1)\)-st term must occur after the \(j\)-th term of the stage \(j\) sequence, so \(m_{j+1}^{(j+1)}>m_j^{(j)}\).

Now fix a row \(k\). For each \(j\geq k\), the index \(n_j=m_j^{(j)}\) belongs to the stage \(k\) sequence, because stage \(j\) is nested inside stage \(k\). As \(j\) increases, these selected indices occur in increasing order within the stage \(k\) sequence. Thus, after omitting the finitely many terms with \(j<k\), the values \(x_{n_j}^{(k)}\) form a subsequence of the convergent sequence obtained at stage \(k\). Every subsequence of a convergent sequence has the same limit. Hence \((x_{n_j}^{(k)})\) converges. Since \(k\) was arbitrary, this one sequence of indices works for every row. \(\square\)

The convergence limits may differ from row to row. The theorem asserts simultaneous convergence, not convergence to a common value. It also does not assert that the original sequences converge: the selected indices are allowed to depend on the entire family of rows.

Using the Theorem on Countable Sets

A frequent application is to a sequence of functions whose values are bounded at each point of a countable set. Enumerate that set as \(D=\{q_1,q_2,\ldots\}\). For each fixed \(k\), the values \(f_n(q_k)\) form one sequence of real numbers. If each such sequence is bounded, the Diagonal Subsequence Theorem selects one subsequence of functions whose values converge at every point of \(D\).

This distinction is important. Diagonalization handles countably many tests because the tests can be listed and addressed one at a time. A conclusion about every point of an uncountable domain requires additional information, such as regularity or a separate uniform estimate. The diagonal choice alone cannot turn countably many pointwise conclusions into uniform convergence.

When Diagonalization Is the Right Strategy

Use diagonalization when a problem has a countable list of conditions and each finite initial list can be satisfied by a suitable subsequence or choice. The essential structure is nested: stage \(k+1\) must refine stage \(k\), not replace it with an unrelated choice. Then select a term from a progressively later stage so that every fixed condition is eventually inherited.

A common mistake is to choose one subsequence for each condition independently and assume that these choices combine. They may have no common subsequence with the desired behavior. The nested construction avoids this problem by making each new selection from the one already in hand. Another mistake is to claim more than the construction proves. In the function example, convergence at every point of a countable set did not establish convergence on the whole domain or uniform convergence.

The diagonalization strategy is a method for organizing infinitely many compatible choices. Its proof is complete only after verifying both parts of the construction: the selected indices form a subsequence, and every fixed requirement holds along a tail of that subsequence.