Constructing Subsequences

Building a Subsequence by Choosing Indices

The definition of a subsequence tells us what a selection must look like: its indices must be nonnegative integers in strictly increasing order. A useful next question is how to construct such a selection when we want the chosen terms to satisfy a particular condition. The basic idea is to select an eligible index, then select another eligible index farther along, and continue.

For this procedure to keep working, eligible indices must occur infinitely often. An infinite set of nonnegative integers cannot be confined to a finite initial segment, so there is always another eligible index beyond any index already selected. The least such choice gives a precise recursive construction.

Proof. Suppose instead that \(E\) were bounded above by some \(M\in\mathbb{N}_0\). Because every element of \(E\) is a nonnegative integer, this would give \(E\subseteq\{0,1,\ldots,M\}\). The set on the right is finite, so \(E\) would be finite. This contradicts the assumption that \(E\) is infinite. Therefore \(E\) is unbounded above. \(\square\)

Proof. Since \(E\) is nonempty, the well-ordering principle gives a least element of \(E\); call it \(n_0\). Suppose \(n_k\in E\) has been chosen. By the lemma, \(E\) is unbounded above, so there is at least one \(e\in E\) such that \(e>n_k\). The set of such eligible indices is nonempty and, by the well-ordering principle, has a least element. Define

This defines \(n_{k+1}\) at every step. By construction, \(n_{k+1}\in E\) and \(n_{k+1}>n_k\). Thus \(n_0<n_1<n_2<\cdots\), so the selected terms form a subsequence of \((a_n)\). Every selected index belongs to \(E\), as required. \(\square\)

This construction is sometimes called choosing the least eligible index at each step. Its value is not that the least choice is always necessary; any eligible index beyond the last choice would work. Rather, choosing the least one makes the procedure precise and ensures that each next step has a specified index.

Selecting Terms That Satisfy a Condition

A property of terms can be translated into a set of eligible indices. If \(P(n)\) is a condition that may hold or fail at each index, define

If \(P(n)\) holds for infinitely many indices, then \(E\) is infinite. The construction theorem therefore gives a subsequence for which \(P\) holds at every selected index. This is the basic method for constructing subsequences with a prescribed property.

Proof. Let \(E=\{n\in\mathbb{N}_0:P(n)\text{ holds}\}\). The assumption says exactly that \(E\) is infinite. Apply the construction theorem to obtain a subsequence whose indices all belong to \(E\). Membership \(n_k\in E\) means that \(P(n_k)\) holds for each \(k\). \(\square\)

The hypothesis “infinitely many” matters. A condition that holds at many indices might still hold only finitely often. For example, if it holds precisely at indices \(0,1,\ldots,100\), then those indices cannot provide an infinite subsequence. An infinite supply of eligible indices is what lets the recursive construction continue indefinitely.

Infinite Sets Can Be Split into Finitely Many Classes

Sometimes eligibility is not described by one simple condition. Instead, the eligible indices are divided into a finite number of classes. At least one class must still contain infinitely many indices. Otherwise, combining finitely many finite classes would leave only finitely many eligible indices.

Proof. Suppose, to the contrary, that every set \(E\cap E_i\) is finite. Since \(E\subseteq E_1\cup\cdots\cup E_r\), every element of \(E\) belongs to at least one of these intersections. Therefore

The right side is a union of finitely many finite sets, and hence is finite. This would make \(E\) finite, contradicting the assumption. Thus at least one intersection \(E\cap E_i\) is infinite. \(\square\)

This theorem supplies a useful two-part strategy: first divide eligible indices according to which of finitely many conditions they satisfy; then choose an infinite class and construct a subsequence from its indices. The class need not be known in advance. The theorem guarantees that one exists, and once it is identified, the earlier construction applies.

Choosing Indices Beyond Any Threshold

The constructed indices do more than increase: as shown in the previous tutorial, a strictly increasing sequence of nonnegative integer indices satisfies \(n_k\geq k\). Consequently, for any fixed \(N\in\mathbb{N}_0\), every selected index with \(k\geq N\) satisfies \(n_k\geq N\). So a subsequence eventually lies entirely beyond any specified starting index in the original sequence.

This fact is useful when the desired condition is known to hold on a tail, or when an initial segment must be avoided. For instance, if infinitely many eligible indices remain after index \(N\), the construction can be started at the least eligible index greater than or equal to \(N\), and then continued by choosing the least eligible index strictly beyond the last one. The same unboundedness argument guarantees that every step is possible.

A common mistake is to treat “infinitely many terms satisfy \(P\)” as if it automatically provided a subsequence without explaining how the indices are ordered. The recursive rule fills that gap: each choice belongs to the eligible set and is strictly later than the preceding choice. Conversely, a finite collection of eligible indices can never be used to define an infinite subsequence, no matter how many terms it contains.

If the eligible indices are divided into finitely many categories, first use the finite partition principle to find a category containing infinitely many of them. Then apply the same selection procedure within that category. This combination of an infinite-set argument and an increasing-index construction is a standard way to build subsequences tailored to a proof.