Monotone subsequence via ultrapower

Piotr Błaszczyk; Vladimir Kanovei; Mikhail G. Katz; Tahl Nowik

doi:10.1515/math-2018-0015

Article Open Access

Monotone subsequence via ultrapower

Piotr Błaszczyk , Vladimir Kanovei , Mikhail G. Katz and Tahl Nowik

Published/Copyright: March 2, 2018

Published by

Become an author with De Gruyter Brill

Submit Manuscript Author Information Explore this Subject

$Open Mathematics$

From the journal Open Mathematics Volume 16 Issue 1

Abstract

An ultraproduct can be a helpful organizing principle in presenting solutions of problems at many levels, as argued by Terence Tao. We apply it here to the solution of a calculus problem: every infinite sequence has a monotone infinite subsequence, and give other applications.

Keywords: Ordered structures; Monotone subsequence; Ultrapower; Saturation; Compactness

MSC 2010: 26A06; 26A48; 26E35; 40-99

1 Introduction

Solutions to even elementary calculus problems can be tricky but in many cases, enriching the foundational framework available enables one to streamline arguments, yielding proofs that are more natural than the traditionally presented ones.

We explore various proofs of the elementary fact that every infinite sequence has a monotone infinite subsequence, including some that proceed without choosing a convergent one first.

An ultraproduct can be a helpful organizing principle in presenting solutions of problems at many levels, as argued by Terence Tao Tao in [1]. We apply it here to the solution of the problem mentioned above. A related but different problem of proving that every infinite totally ordered set contains a monotone sequence is treated by Hirshfeld in [2, Exercise 1.2, p. 222]. We first present the ultrapower construction in Section 2. Readers familiar with ultraproducts can skip ahead to the proof in Section 3.

2 Ultrapower construction

Let us outline a construction (called an ultrapower) of a hyperreal extension ℝ ↪ ^∗ℝ exploited in our solution in Section 3. Let ℝ^ℕ denote the ring of sequences of real numbers, with arithmetic operations defined termwise. Then we have a totally ordered field ^∗ℝ = ℝ^ℕ/MAX where “MAX” is a suitable maximal ideal. Elements of ^∗ℝ are called hyperreal numbers. Note the formal analogy between the quotient ^∗ℝ = ℝ^ℕ/MAX and the construction of the real numbers as equivalence classes of Cauchy sequences of rational numbers. In both cases, the subfield is embedded in the superfield by means of constant sequences, and the ring of sequences is factored by a maximal ideal.

We now describe a construction of such a maximal ideal MAX ⊆ ℝ^ℕ exploiting a suitable finitely additive measure ξ: 𝓟(ℕ) → {0, 1} (thus ξ takes only two values, 0 and 1) taking the value 1 on each cofinite set, ^[1] where 𝓟(ℕ) is the set of subsets of ℕ. The ideal MAX consists of all “negligible” sequences 〈u_n〉, i.e., sequences which vanish for a set of indices of full measure ξ, namely, ξ({n ∈ ℕ: u_n = 0}) = 1. The subset 𝓤 = 𝓤_ξ ⊆ 𝓟 (ℕ) consisting of sets of full measure ξ is called a free ultrafilter (these can be shown to exist using Zorn’s lemma). A similar construction applied to ℚ produces the field ^∗ℚ of hyperrational numbers. The construction can also be applied to a general ordered set F to obtain an ultrapower extension denoted ^∗F = F^ℕ/𝓤.

Definition 2.1

The order on the field^∗Fis defined by setting

$[〈un〉]<[〈vn〉] if and only ifξ({n∈N:un<vn})=1$

or equivalently {n ∈ ℕ: u_n < v_n} ∈ 𝓤.

In particular, every element x ∈ F is canonically identified with the class [〈x〉] of the constant sequence 〈x〉 with general term x. Then x ∈ ^∗F satisfies x < v if and only if {n ∈ ℕ: x < v_n} ∈ 𝓤.

3 Solution

Let F be an ordered field. We are mainly interested in the cases F = ℚ and F = ℝ though the arguments go through in greater generality for an arbitrary totally ordered set.

Theorem 3.1

A sequence 〈u_n〉 of elements ofFnecessarily contains a subsequence 〈u_{n_k}〉 such that eitheru_{n_k} ≥ u_{n_ℓ}wheneverk > ℓ, oru_{n_k} ≤ u_{n_ℓ}wheneverk > ℓ.

This is an immediate consequence of the following more detailed result.

Theorem 3.2

Letu ∈ ^∗F = F^ℕ/𝓤 be the element obtained as the equivalence class of the sequence 〈u_n〉. Consider the partition ℕ = A ⊔ B ⊔ Cwhere A = {n ∈ ℕ: u_n < u}, B = {n ∈ ℕ: u_n = u}, C = {n ∈ ℕ: u_n > u}. Then exactly one of the following three possibilities occurs:

B ∈ 𝓤 and then 〈u_n〉 contains an infinite constant subsequence;
A ∈ 𝓤 and then 〈u_n〉 contains an infinite strictly increasing subsequence;
C ∈ 𝓤 and then 〈u_n〉 contains an infinite strictly decreasing subsequence.

Proof

By the property of an ultrafilter, exactly one of the sets A, B, C is in 𝓤. If B ∈ 𝓤 then u is an element of the subfield F ⊆ ^∗F (embedded via constant sequences). Since B ⊆ ℕ is necessarily infinite, enumerating it we obtain the desired subsequence.

Now assume A ∈ 𝓤. We choose any element u_n₁ ∈ A to be the first term in the subsequence. We then inductively choose the index n_k+1 > n_k in A so that u_{n_k+1} is the earliest term greater than u_{n_k} and therefore closer to u than the previous term u_{n_k} If the subsequence were to terminate at, say, u_p, this would imply that {n ∈ ℕ: u_n ≤ u_p} ∈ 𝓤 and therefore u ≤ u_p, contradicting the definition of the set A. Therefore we necessarily obtain an infinite increasing subsequence.

The case C ∈ 𝓤 is similar and results in a decreasing sequence. □

Remark 3.3

The proof is essentially a two-step procedure: (1) we plug the sequence into the ultrapower construction, producing an elementu ∈ ^∗F; (2) in each of the cases specified by the element u, we inductively find a monotone subsequence.

The approach exploiting ^∗F has the advantage that the proof does not require constructing a completion of the field in the case F = ℚ. To work with the ultrapower, one needs neither advanced logic nor a crash course in NSA, since the ultrapower construction involves merely quotienting by a maximal ideal as is done in any serious undergraduate algebra course (see Section 2).

A monotone sequence can also be chosen by the following more traditional consideration. If the sequence is unbounded, one can choose a sequence that diverges to infinity. If the sequence is bounded, one applies the Bolzano-Weierstrass theorem (each bounded sequence has a convergent subsequence) to extract a convergent subsequence. Finally, a convergent sequence contains a monotone one by analyzing the terms lying on one side of the limit (whichever side has infinitely many terms).

The proof via an ultrapower allows one to bypass the issue of convergence. Once one produces a monotone subsequence, it will also be convergent in the bounded case but only when the field is complete. Furthermore, one avoids the use of the Bolzano–Weierstrass theorem.

Since in the case of F = ℚ the Bolzano–Weierstrass theorem is inapplicable, one would need first to complete ℚ to ℝ by an analytic procedure which is arguably at least as complex as the algebraic construction involved in the ultrapower of Section 2.

There is a clever proof of the same result, as follows (see e.g., problem 6 on page 4 in Newman [3]). Call a term in the sequence a peak if it is larger than everything which comes after it. If there are infinitely many peaks, they form an infinite decreasing subsequence. If there are finitely many peaks, start after the last one. From here on every term has a larger term after it, so one inductively forms an increasing subsequence (from this lemma one derives a simple proof of the Bolzano–Weierstrass theorem).

Remark 3.4

The proof in Newman consists of two steps: (1) introduce the idea of a peak; (2) consider separately the cases when the number of peaks is finite or infinite to produce the desired monotone subsequence. While the basic structure of the proof is similar to that using the ultrapower (see Remark 3.3), the basic difference is that step (1) in Newman is essentially ad-hoc, is tailor-made for this particular problem, and is not applicable to solving other problems. Mean while, the ultrapower construction is applicable in many other situations (see e.g., Section 4).

While the proof in Newman does not rely on an ultrapower, the idea of the ultrapower proof is more straightforward once one is familiar with the ultrapower construction, since it is natural to plug a sequence into it and examine the consequences.

We provide another illustration of how the element u = [〈u_n〉] can serve as an organizing principle that allows us to detect properties of monotone subsequences. To fix ideas let F = ℝ. An element u ∈ ^∗ℝ is called finite if –r < u < r for a suitable r ∈ ℝ. Let ^𝔥ℝ ⊆ ^∗ℝ be the subring of finite elements of ^∗ℝ. The standard part function st: ^𝔥ℝ → ℝ rounds off each finite hyperreal u to its nearest real number u₀ = st(u).

Proposition 3.5

Ifu ∈ 𝔥ℝ and u > u₀then the sequence 〈u_n〉 possesses a strictly decreasing subsequence.

Proof

Since u > u₀ we have {n ∈ ℕ: u_n > u₀} ∈ 𝓤. We start with an arbitrary n₁ ∈ {n ∈ ℕ: u_n > u₀} and inductively choose n_k+1 so that u_{n_k+1} is closer to u than u_{n_k}. We argue as in the proof of Theorem 3.2 to show that the process cannot terminate and therefore produces an infinite subsequence. □

4 Compactness

A more advanced application is a proof of the nested decreasing sequence property for compact sets (Cantor’s intersection theorem) using the property of saturation. Such a proof exbibits compactness as closely related to the more general property of saturation, shedding new light on the classic property of compactness.

A typical proof of Cantor’s intersection theorem for a nested decreasing sequence of compact subsets A_n ⊆ ℝ would use the monotone sequence 〈u_n〉 where u_n is the minimum of each A_n. We will present a different and more conceptual proof.

Each set A ⊆ ℝ has a natural extension denoted ^∗A ⊆^∗ℝ. Similarly, the powerset P = 𝓟(ℝ) has a natural extension ^∗ identified with a proper subset of 𝓟(^∗ℝ). Each element of ^∗𝓟 is naturally identified with a subset of ^∗ℝ called an internal set.

The principle of saturation holds for arbitrary nested decreasing sequences of internal sets but we will present it in a following special case.

Theorem 4.1 (Saturation)

If 〈A_n: n ∈ ℕ〉 is a nested decreasing sequence of nonempty subsets of ℝ then the sequence 〈^∗A_n: n ∈ ℕ〉 has a common point.

Proof

Let ℙ = 𝓟(ℝ) be the set of subsets of ℝ. We view the sequence 〈A_n ∈ ℙ: n ∈ ℕ〉 as a function f: ℕ → ℙ, n ↦ A_n. By the extension principle we have a function ^∗f: ^∗ℕ → ^∗ℙ. Let B_n = ^∗f(n). For each finite n we have B_n = ^∗A_n ∈ ^∗ℙ. For each infinite value of the index n = H the entity B_H ∈ ^∗ℙ is by definition internal but is not (necessarily) the natural extension of any subset of ℝ.

If 〈A_n〉 is a nested sequence in ℙ then by transfer 〈B_n: n ∈ ^∗ℕ〉 is a nested sequence in ^∗ℙ with each B_n nonempty. Let H be a fixed infinite index. Then for each finite n the set ^∗A_n ⊆ ^∗ℝ includes B_H. Choose any element c ∈ B_H. Then c is contained in ^∗A_n for each finite n so that c ∈ ∩_{n ∈ ℕ}^∗A_n as required. □

Remark 4.2

An equivalent formulation of Theorem 4.1 is as follows. If the family of subsets {A_n}_{n ∈ ℕ}has the finite intersection property then ∃c ∈ ∩_{n ∈ ℕ}^∗A_n.

Let X be a topological space. Let p ∈ X. The halo of p, denoted 𝔥(p) is the intersection of all ^∗U where U runs over all neighborhoods of p in X (a neighborhood of p is an open set that contains p). A point y ∈ ^∗X is called nearstandard in X if there is p ∈ X such that y ∈ 𝔥(p).

Theorem 4.3

A spaceXis compact if and only if every y ∈ ^∗Xis nearstandard inX.

Proof

To prove the direction ⇒, assume X is compact, and let y ∈ ^∗X. Let us show that y is nearstandard (this direction does not require saturation). Assume on the contrary that y is not nearstandard. This means that it is not in the halo of any point p ∈ X. This means that every p ∈ X has a neighborhood U_p such that y ∉ ^∗U_p. The collection {U_p}_{p ∈ X} is an open cover of X. Since X is compact, the collection has a finite subcover U_p₁, …, U_{p_n}, so that X = U_p₁ ∪ … ∪ U_{p_n}. But for a finite union, the star of union is the union of stars. Thus ^∗X is the union of ^∗U_p₁, …, ^∗U_{p_n}, and so the point y is in one of the sets ^∗U_p₁, …, ^∗U_{p_n}, a contradiction.

Next we prove the direction ⇐ (this direction exploits saturation). Assume every y ∈ ^∗X is nearstandard, and let {U_a} be an open cover of X. We need to find a finite subcover.

Assume on the contrary that the union of any finite collection of U_a is not all of X. Then the complements of U_a are a collection of (closed) sets {S_a} with the finite intersection property. It follows that the collection {^∗S_a} similarly has the finite intersection property. By saturation (see Remark 4.2), the intersection of all ^∗S_a is non-empty. Let y be a point in this intersection. Let p ∈ X be such that y ∈ 𝔥(p). Now {U_a} is a cover of X so there is a U_b such that p ∈ U_b. But y is in ^∗S_a for all a, in particular y ∈ ^∗S_b, so it is not in ^∗U_b, a contradiction to y ∈ 𝔥(p) □.

Theorem 4.4 (Cantor’s intersection theorem)

A nested decreasing sequence of nonempty compact sets has a common point.

Proof

Given a nested sequence of compact sets K_n, we consider the corresponding decreasing nested sequence of internal sets, 〈^∗K_n: n ∈ ℕ〉. This sequence has a common point x by saturation. But for a compact set K_n, every point of ^∗K_n is nearstandard (i.e., infinitely close to a point of K_n) by Theorem 4.3. In particular, st(x) ∈ K_n for all n, as required. □

More advanced applications can be found in [4,5,6].

References

[1] Tao T., Hilbert’s fifth problem and related topics, Graduate Studies in Mathematics, 153, American Mathematical Society, Providence, RI, 2014.Search in Google Scholar

[2] Hirshfeld J., Nonstandard combinatorics, Studia Logica, 1988, 47, no. 3, 221–232.10.1007/BF00370553Search in Google Scholar

[3] Newman D., A problem seminar, Problem Books in Mathematics, Springer-Verlag, New York-Berlin, 1982.10.1007/978-1-4613-8214-0Search in Google Scholar

[4] Fletcher P., Hrbacek K., Kanovei V., Katz M., Lobry C., Sanders S., Approaches to analysis with infinitesimals following Robinson, Nelson, and others, Real Analysis Exchange 2017, 42, no. 2, 193–252. See https://arxiv.org/abs/1703.00425 and http://msupress.org/journals/issue/?id=50-21D-61F10.14321/realanalexch.42.2.0193Search in Google Scholar

[5] Herzberg F., Kanovei V., Katz M., Lyubetsky V., Minimal axiomatic frameworks for definable hyperreals with transfer, Journal of Symbolic Logic, to appear. See https://arxiv.org/abs/1707.00202 and http://dx.doi.org/10.1017/jsl.2017.4810.1017/jsl.2017.48Search in Google Scholar

[6] Nowik T., Katz M., Differential geometry via infinitesimal displacements, Journal of Logic and Analysis, 2015, 7, no. 5, 1–44. See http://www.logicandanalysis.org/index.php/jla/article/view/237 and http://arxiv.org/abs/1405.098410.4115/jla.2015.7.5Search in Google Scholar

Received: 2017-08-13

Accepted: 2018-01-31

Published Online: 2018-03-02

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Articles in the same Issue

DOI: doi.org/10.1515/math-2018-0015

Keywords for this article

Ordered structures; Monotone subsequence; Ultrapower; Saturation; Compactness

Creative Commons

BY-NC-ND 4.0