Quantifiers in Limits

H. Jerome Keisler University of Wisconsin, Madison

Abstract

The standard definition of lim_{z→∞} F (z) = ∞ is an ∀∃∀ sentence. Mostowski showed that in the standard model of arithmetic, these quantifiers cannot be eliminated. But Abraham Robinson showed that in the nonstandard setting, this limit property for a standard function F is equivalent to the one quantifier statement that F (z) is infinite for all infinite z. In general, the number of quantifier blocks needed to define the limit depends on the underlying structure M in which one is working. Given a structure M with an ordering, we add a new function symbol F to the vocabulary of M and ask for the minimum number of quantifier blocks needed to define the class of structures (M, F) in which lim_{z→∞} F (z) = ∞ holds.

We show that the limit cannot be defined with fewer than three quantifier blocks when the underlying structure M is either countable, special, or an o-minimal expansion of the real ordered field. But there are structures M which are so powerful that the limit property for arbitrary functions can be defined in both two-quantifier forms.

1 Introduction

An important advantage of the nonstandard approach to elementary calculus is that it eliminates two quantifiers in the definition of a limit. For example, the standard definition of

lim_{z→∞} F (z) = ∞

requires three quantifier blocks,

∀x ∃y ∀z [y ≤ z ⇒ x ≤ F (z)].

Mostowski showed that in the standard model of arithmetic, these quantifiers cannot be eliminated. But Abraham Robinson showed that in the nonstandard setting, this limit property is equivalent to the one quantifier statement

∀z [z ∈ I ⇒ F (z) ∈ I],

where F is a standard function and I is the set of infinite elements. Because of the quantifiers, beginning calculus students cannot follow the standard definition but have no trouble with the nonstandard definition. Since all the basic notions in the calculus depend on limits, students often find the nonstandard approach to the calculus to be easier to understand than the standard approach (see [Ke2], [Su]).

In general, the number of quantifier blocks needed to define the limit depends on the underlying structure M in which one is working. Given a structure M with an ordering, we add a new function symbol F to the vocabulary of M and ask for the minimum number of quantifier blocks needed to define the class of structures (M, F) in which lim_{z→∞} F (z) = ∞ holds.

We show that in the standard setting the limit cannot be defined with fewer than three quantifier blocks when the underlying structure M is not too powerful. We obtain this result in the case that M is countable, and in the case that M is an o-minimal expansion of the real field R = (ℝ, ≤, +, ·).

As is usual in the literature, we consider the quantifier hierarchy which takes into account both n-quantifier forms. For each n, one can ask whether a property is Π_{n}, Σ_{n}, both Π_{n} and Σ_{n} (called Δ_{n}), or Boolean in Π_{n}. Each of Σ_{n} and Π_{n} implies Boolean in Π_{n}, which in turn implies Δ_{n+1}. The standard definition of limit is Π_{3}.

In Section 4 we will see that the limit property can never be Boolean in Π_{1} sentences. However, if M = (ℝ, ≤, ℕ, g) where g maps ℝ onto ℝ^{ℕ}, then the limit property is Δ_{2}. What happens here is that there is a standard definition of limit which uses one less quantifier block than the usual definition, but needs a function which codes sequences of real numbers by real numbers, and is therefore beyond the scope of an elementary calculus course.

In Section 5 we show that when M is countable, the limit property is not Σ_{3}. In Section 6 we prove that the limit property is not Σ_{3} when M is the real ordering with an embedded structure with universe ℕ. In Section 7 we prove that the limit property is not Σ_{3} when M is a saturated or special structure, even when one adds a predicate for the set of infinite elements. This shows that Robinson’s result for standard functions does not carry over to arbitrary functions.

In Section 8 we consider infinitely long sentences. In an ordered structure M with universe set ℝ and at least a constant symbol for each natural number, the limit property can be expressed naturally by a countable conjunction of countable disjunctions of Π_{1} sentences. We show that the limit property cannot be expressed by a countable disjunction of countable conjunctions of Σ_{1} sentences.

In Section 9 we prove our main result: If M is an o-minimal expansion of the real ordered field , then the limit property is not Boolean over Π_{2}. We leave open the question of whether one can improve this result by showing that the limit property is not Σ_{3}.

We also consider the similar but simpler property of a function being bounded. The standard definition of boundedness is Σ_{2}, or alternatively, a countable disjunction of universal sentences. We show that when M is countable, special, or an o-minimal expansion of the real ordered field, the boundedness property is not Π_{2}. When M has universe set ℝ, boundedness cannot be expressed by a countable conjunction of existential sentences.

2 Preliminaries

We introduce a general framework for the study of quantifiers required for defining limits.

We assume throughout that M is an ordered structure with no greatest element. That is, M is a first order structure for a vocabulary L(M) that contains at least the order relation ≤, and ≤ is a linear ordering with no greatest element. We will consider structures K = (M, f) where f : M → M is a unary function. The vocabulary of (M, f) is L(M) ∪ {F } where F is an extra unary function symbol. For a formula φ(x⃗, y⃗) of L(M) ∪ {F }, the notation φ(f, x⃗, y⃗) means that (M, f) ⊧ φ(x⃗, y⃗).

We use the notation |X| for the cardinality of X, ≡ for elementary equivalence, ≺ for elementary substructure, and ≅ for isomorphic.

Quantifier-free formulas are called Π_{0} formulas and also called Σ_{0} formulas. A Π_{n+1} formula is a formula of the form ∀x⃗ θ where θ is a Σ_{n}-formula. A Σ_{n+1} formula is one a formula of the form ∃x⃗ θ where θ is a Π_{n}-formula. The negation of a Π_{n} formula is equivalent to a Σ_{n} formula, and vice versa. A formula is said to be Boolean in Π_{n} if it is built from Π_{n} formulas using ∧, ∨, ¬. Any formula which is Boolean in Π_{n} is equivalent to both a Π_{n+1} formula and a Σ_{n+1} formula.

Definition 2.1 In the language L(M) ∪ {F }, BDD is the Σ_{2} sentence which says that f is bounded,

BDD = ∃x∀y F (y) ≤ x.

LIM is the Π_{3} sentence which says that lim_{x→∞} f(x) = ∞,

LIM = ∀x∃y∀z[y ≤ z ⇒ x ≤ F (z)].

We will say that a sentence θ of L(M) ∪ {F } is Π_{n} over M if there is a Π_{n} sentence of L(M) ∪ {F } which is equivalent to θ in every structure (M, f). Similarly for Σ_{n}. We say that θ is Δ_{n} over M if it is both Π_{n} and Σ_{n} over M. We will say that θ is Boolean in Π_{n} over M, or B_{n} over M, if there is a sentence of L(M) ∪ {F } which is Boolean in Π_{n} and is equivalent to θ in every structure (M, f). With this terminology, there are two quantifier hierarchies of sentences over M,

Δ_{1} ⊂ Π_{1} ⊂ B_{1} ⊂ Δ_{2} ⊂ Π_{2} ⊂ B_{2} ⊂ Δ_{3} ⊂ Π_{3},
Δ_{1} ⊂ Σ_{1} ⊂ B_{1} ⊂ Δ_{2} ⊂ Σ_{2} ⊂ B_{2} ⊂ Δ_{3} ⊂ Σ_{3}.

By the quantifier level of a sentence over M we mean the lowest class in these hierarchies to which a sentence belongs over M. Note that the level of a sentence over an expansion of M is at most its level over M.

In this paper we will consider the following problem.

Problem Find the quantifier level of BDD and LIM over a given structure M.

For any M, BDD is at most Σ_{2} and LIM is at most Π_{3} over M.

We remark that whenever M is an expansion of an ordered field, the limit property lim_{x→0} f(x) = c will be at the same quantifier level as LIM. This can be seen by the change of variables z = 1/x. Similar remarks can be made for other limit concepts in the calculus.

3 Results of Mostowski and Robinson

In order to compare the results in this paper to earlier results of Mostowski and Robinson, we define the quantifier level of a sentence over a structure M relative to a set F ⊆ M^{M}, where M^{M} is the set of all functions from M into M. We way that a sentence θ of L(M) ∪ {F } is Π_{n} over M relative to F if there is a Π_{n} sentence of L(M)∪{F } which is equivalent to θ in every structure (M, f) with f ∈ F. Similarly for Σ_{n}. Thus a sentence is Π_{n} over M in our original sense iff it is Π_{n} over M relative to M^{M}.

Note that if a sentence is Π_{n} over M, then it is Π_{n} over M relative to every set F ⊆ M^{M}, and similarly for Σ_{n}. Thus for ever M and F, BDD is at most Σ_{2} over M relative to F, and LIM is at most Π_{3} over M relative to F.

In the paper [Mo2], Mostowski showed that several limit concepts, including BDD and LIM, have the highest possible quantifier level over the standard model of arithmetic. In fact, over this particular structure, he obtains the stronger result that BDD and LIM have the highest possible quantifier level relative to the set of primitive recursive functions.

Theorem 3.1 (Mostowski [Mo2]). Let F be the set of all primitive recursive functions, and let N be the standard model of arithmetic with a symbol for every function in F.

(i) BDD is not Π_{2} over N relative to F.

(ii) LIM is not Σ_{3} over N relative to F.

The proof of Theorem 2 in [Mo2] shows that for every Σ_{2} formula θ(y) in L(N) there is a primitive recursive function g(x, y) such that θ(y) defines the set of y for which g(·, y) is bounded. By the Arithmetical Hierarchy Theorem of Kleene [Kl] and Mostowski [Mo1], θ may be taken to be Σ_{2} but not Π_{2} over N, and (i) follows.

Similarly, the proof of Theorem 3 in [Mo2] shows that for every Π_{3} formula ψ(y) in L(N) there is a primitive recursive function h(x, y) such that ψ(y) defines the set of y for which lim_{x→∞} h(x, y) = ∞, and (ii) follows by taking ψ to be Π_{3} but not Σ_{3} over N.

Abraham Robinson’s characterization of infinite limits with one universal quantifier uses an elementary extension of M.

Definition 3.2 In an elementary extension ^{∗}M of M, an element is infinite (over M) if it is greater than every element of M. By a hyperextension of M we mean a structure (^{∗}M, I) where ^{∗}M is an elementary extension of M with at least one infinite element, and I is a unary predicate for the set of infinite elements. A function ^{∗}f : ^{∗}M → ^{∗}M is standard if there is a function f : M → M such that (^{∗}M,^{∗}f) is an elementary extension of (M, f).

Theorem 3.3 (A. Robinson) Let (^{∗}M, I) be a hyperextension of M. Then BDD and LIM are Π_{1} over (^{∗}M, I) relative to the set standard functions.

In fact, Robinson shows that for every standard function ^{∗}f : ^{∗}M → ^{∗}M, (^{∗}M,^{∗}f) satisfies

BDD ⇔ ∀x[F (x) = 0 ⇒ ¬I(x)],
LIM ⇔ ∀x[I(x) ⇒ I(F (x))].

In the nonstandard treatment of elementary calculus, one works in a hyperextension of the system ℝ of real numbers or the system ℕ of natural numbers. The extra predicate I for infinite elements eliminates one quantifier block in the definition of boundedness and two quantifier blocks in the definition of limit. The question we address here is whether one can also eliminate these quantifiers in the original first order language L(M) ∪ {F }. That is, are there any “quantifier shortcuts” for the statements BDD or LIM in M? This question is completely standard in nature, but is motivated by Robinson’s results in nonstandard analysis.

4 Cases with Low Quantifier Level

In this section we show that when the underlying structure M is sufficiently powerful, the properties BDD and LIM are equivalent to sentences in both two quantifier forms. All that is needed is a symbol for a particular function which is first order definable in the real field with a predicate for the natural numbers. This gives a warning that some restrictions are needed on M in order to show that BDD and LIM are higher than Δ_{2} over M. We also show that BDD and LIM can never be B_{1} over M.

Theorem 4.1 Let M = (ℝ, ≤, ℕ, g) be the ordered set of real numbers with a predicate for the natural numbers and a function g : ℝ × ℕ → ℝ such that x ↦ g(x, ·) maps ℝ onto ℝ^{ℕ}, that is, for each y ∈ ℝ^{ℕ} there exists x ∈ ℝ such that y = g(x, ·).

(i) BDD is Δ_{2} over M.

(ii) LIM is Δ_{2} over M.

Proof. The language L(M) has the vocabulary {ℕ, ≤, G}.

(i) BDD is itself a Σ_{2} sentence. In every structure (M, f), the negation of BDD is equivalent to the Σ_{2} sentence

∃x(∀n ∈ ℕ) n ≤ F (G(x, n)).

(ii) In every structure (M, f), LIM is equivalent to the Σ_{2} sentence

∃x(∀n ∈ ℕ)∀y[G(x, n) ≤ y ⇒ n ≤ F (y)],

and the negation of LIM is equivalent to the Σ_{2} sentence

(∃m ∈ ℕ)∃x(∀n ∈ ℕ)[n ≤ G(x, n) ∧ F (G(x, n)) ≤ m].

It is well known that in the above theorem, the function g can be taken to be definable by a first order formula in the structure (ℝ, ≤, +, ·, ℕ). One way to do this is to let π : ℕ × ℕ → ℕ be a definable pairing function, and for irrational x, let h(x, ·) ∈ ℕ^{ℕ} be the continued fraction expansion of x, and take g(x, n) = z iff ∀m h(z, m) = h(x, π(m, n)).

We now show that for an arbitrary M, LIM and BDD cannot be Boolean in Π_{1}.

Theorem 4.2 Let M be an ordered structure with no greatest element. (i) BDD is not Boolean in Π_{1} over M. (ii) LIM is not Boolean in Π_{1} over M.

Proof. Let φ be a sentence of L(M) ∪ {F } which is Boolean in Π_{1}. Since conjunctions and disjunctions of Π_{1} sentences are equivalent to Π_{1} sentences, and similarly for Σ_{1}, φ is equivalent to a sentence

(α_{1} ∨ β_{1}) ∧ ⋯ ∧ (α_{n} ∨ β_{n})

where each α_{i} is Σ_{1} and each β_{i} is Π_{1}. We may assume that α_{i} and β_{i} have the form

α_{i} = ∃x⃗ ∃y⃗ [F (x⃗) = y⃗ ∧ \overline{α}_{i}(x⃗, y⃗)],
β_{i} = ∀x⃗ ∀y⃗ [F (x⃗) = y⃗ ⇒ \overline{β}_{i}(x⃗, y⃗)]

where \overline{α}_{i} and \overline{β}_{i} are quantifier-free formulas of L(M). (This can be proved by induction on the number of occurrences of F).

Let us say that a pair of tuples (a⃗, b⃗) in M decides φ if for any f, g : M → M such that f(a⃗) = g(a⃗) = b⃗, φ holds in either both or neither of the models (M, f), (M, g).

Claim: There is a pair (a⃗, b⃗) which decides φ.

Proof of Claim: The proof is by induction on n. The claim is trivial for n = 0, where the empty conjunction is taken to be always true. Suppose n > 0 and the claim holds for n − 1. Then there is a pair (a⃗, b⃗) which decides

(α_{1} ∨ β_{1}) ∧ ⋯ ∧ (α_{n−1} ∨ β_{n−1}).

A pair (c⃗, d⃗) is called compatible with (a⃗, b⃗) if b_{i} = d_{j} whenever a_{i} = c_{j}, that is, there exists a function f with f(a⃗, c⃗) = (b⃗, d⃗).

Case 1. There is a pair (c⃗, d⃗) compatible with (a⃗, b⃗) such that \overline{α}_{n}(c⃗, d⃗). Then f(c⃗) = d⃗ implies α_{n}.

Case 2. Case 1 fails but there is a pair (c⃗, d⃗) compatible with (a⃗, b⃗) such that ¬\overline{β}_{n}(c⃗, d⃗). Then f(a⃗, c⃗) = (b⃗, d⃗) implies ¬(α_{n} ∨ β_{n}).

Case 3. For every pair (c⃗, d⃗) compatible with (a⃗, b⃗),

¬\overline{α}_{n}(c⃗, d⃗) ∧ \overline{β}_{n}(c⃗, d⃗).

Then f(a⃗) = b⃗ implies β_{n}.

In each case, (a⃗ ∪ c⃗, b⃗ ∪ d⃗) decides φ, completing the induction.

Now let (a⃗, b⃗) decide φ. There are functions f, g such that f(a⃗) = g(a⃗) = b⃗, but BDD holds in (M, f) and fails in (M, g). Therefore φ cannot be equivalent to BDD over M. A similar argument holds for LIM.

5 Countable Structures

In this section we consider the case that the universe of M is countable. In that case, we apply Mostowski’s Theorem 3.1 to show that BDD and LIM have the highest possible quantifier level. We first observe that Mostowski’s proof of Theorem 3.1 also gives a relativized form of the result.

Theorem 5.1 Let α be a finite tuple of finitary functions on ℕ, let F(α) be the set of all functions which are primitive recursive in α, and let N be the standard model of arithmetic with an extra symbol for each function in the set F(α).

(i) BDD is not Π_{2} over N relative to F(α).

(ii) LIM is not Σ_{3} over N relative to F(α).

Corollary 5.2 Let N be an expansion of the standard model of arithmetic with the natural ordering <.

(i) BDD is not Π_{2} over N.

(ii) LIM is not Σ_{3} over N.

Theorem 5.3 Suppose M is an ordered structure with no greatest element and the universe of M is countable.

(i) BDD is not Π_{2} over M.

(ii) LIM is not Σ_{3} over M.

Proof. We may assume that the vocabulary of M is finite, since only finitely many symbols occur in a Σ_{3} formula. We may also assume that the universe of M is the set ℕ of natural numbers. Let <_{M} be the ordering of M (which may be different from the natural order < of ℕ). Since M has no greatest element, there is a function h : ℕ → ℕ such that h(n) <_{M} h(n + 1) for each n, and ∀x∃n x ≤_{M} h(n). For each x let λ(x) be the least n such that x ≤_{M} h(n).

We prove (ii). The proof of (i) is similar. We observe that for each function g : ℕ → ℕ, lim_{x→∞} h(g(λ(x))) = ∞ with respect to <_{M} if and only if lim_{x→∞} g(x) = ∞ with respect to <. If LIM is not Σ_{3} over an expansion of M, then it is not Σ_{3} over M. We may therefore assume that M has symbols for <, +, ·, h, and λ.

Now suppose that LIM is Σ_{3} over M, that is, there is a Σ_{3} sentence ∃x⃗ ∀y⃗ ∃z⃗ φ(x⃗, y⃗, z⃗) of L(M) ∪ {F } which is equivalent to LIM in all structures (M, f). To complete the proof we will get a contradiction.

Let ψ(x⃗, y⃗, z⃗) be the formula obtained from φ(x⃗, y⃗, z⃗) by replacing each term F (u) by h(F (λ(u))). By our observation above, for any function g : ℕ → ℕ, we have lim_{x→∞} g(x) = ∞ with respect to < if and only if (M, g) satisfies the Σ_{3} sentence ∃x⃗ ∀y⃗ ∃z⃗ ψ(x⃗, y⃗, z⃗). This contradicts Corollary 5.2 and completes the proof.

We also give a second argument, which will be useful later. Instead of Corollary 5.2, this argument uses the following analogous fact from descriptive set theory (see [Kec, Exercise 23.2):

In ℕ^{ℕ}, the set L of functions g with lim_{x→∞} g(x) = ∞ is Π_{3} but not Σ_{3} in the Borel hierarchy.

We have

L = ⋃_{x⃗∈ℕ} ⋂_{y⃗∈ℕ} ⋃_{z⃗∈ℕ}{g : (M, g) ⊧ ψ(x⃗, y⃗, z⃗)}).

For each (x⃗, y⃗, z⃗), the set {g : (M, g) ⊧ ψ(x⃗, y⃗, z⃗)} depends only on finitely many values of g and thus is clopen in ℕ^{ℕ}. It follows that L is Σ_{3} in ℕ^{ℕ}, contrary to the preceding paragraph.

The next corollary follows by the Löwenheim-Skolem theorem.

Corollary 5.4 Let M be an ordered structure with no greatest element.

(i) There is no Π_{2} sentence of L(M) ∪ {F } which is equivalent to BDD in all models of T h(M).

(ii) There is no Σ_{3} sentence of L(M) ∪ {F } which is equivalent to LIM in all models of T h(M).

A result in this direction was previously obtained by Kathleen Sullivan in [Su]. She showed that there is no Σ_{2} sentence of L(M) ∪ {F }, and no Π_{2} sentence of L(M) ∪ {F }, which is equivalent to LIM in all models of T h(M).

6 The Real Line

The sentence LIM is a Π_{3} sentence in the vocabulary with the single relation symbol ≤. It is therefore natural to ask whether LIM is Σ_{3} over the real ordering (ℝ, ≤). In this section we show that the answer is no. Given a structure N with universe ℕ, we let (ℝ, ≤, N) be the structure formed by adding to (ℝ, ≤) a symbol for ℕ and the relations of N.

Theorem 6.1 Let N be a structure with universe ℕ.

(i) BDD is not Π_{2} over (ℝ, ≤, N).

(ii) LIM is not Σ_{3} over (ℝ, ≤, N).

Proof. We prove (ii). The proof of (i) is similar. We may assume that N has a countable vocabulary. Let ℚ be the set of rational numbers, and let λ(x) = min{n ∈ ℕ : x ≤ n}.

Claim 1: (ℚ, ≤, N) is an elementary substructure of (ℝ, ≤, N).

Proof of Claim 1. We note that for any two increasing n-tuples a⃗, b⃗ in ℝ such that a⃗ ∩ ℕ = b⃗ ∩ ℕ and λ(a⃗) = λ(b⃗), there is an automorphism of (ℝ, ≤, N) which sends a⃗ to b⃗. Claim 1 now follows from the Tarski-Vaught test ([CK], Proposition 3.1.2).

Define the function α : ℕ^{ℕ} → ℝ^{ℝ} by (α(g))(x) = g(λ(x)), and let β(g) be the restriction of α(g) to ℚ.

Claim 2: For each function g ∈ ℕ^{ℕ}, (ℚ, ≤, N , β(g)) is an elementary substructure of (ℝ, ≤, N , α(g)).

To see this, note that by Claim 1, (ℚ, ≤, (N , g)) is an elementary substructure of (ℝ, ≤, (N , g)). It is easily seen that λ is definable in (ℝ, ≤, ℕ), and hence α(g) is definable in (ℝ, ≤, (N , g)). Claim 2 follows.

Let L be the set of g ∈ ℕ^{ℕ} such that (M, α(g)) ⊧ LIM. We note that lim_{n→∞} g(n) = ∞ in ℕ^{ℕ} if and only if g ∈ L, and hence that L is not Σ_{3} in ℕ^{ℕ}. Now suppose that LIM is Σ_{3} over (ℝ, ≤, N), and take a Σ_{3} sentence

θ = ∃x⃗ ∀y⃗ ∃z⃗ φ(x⃗, y⃗, z⃗)

of L(ℝ, ≤, N)∪{F } which is equivalent to LIM in all structures (ℝ, ≤, N , f). By Claim 2, for each g ∈ ℕ^{ℕ}, (ℝ, ≤, N , α(g)) satisfies θ if and only if (ℚ, ≤, N , β(g)) satisfies θ. Therefore

L = ⋃_{x⃗∈ℚ} ⋂_{y⃗∈ℚ} ⋃_{z⃗∈ℚ}({g : φ(β(g), x⃗, y⃗, z⃗)}).

For each (x⃗, y⃗, z⃗), the set ({g : φ(β(g), x⃗, y⃗, z⃗)}) depends only on finitely many values of g and thus is clopen in ℕ^{ℕ}. Since ℚ is countable, it follows that L is Σ_{3} in ℕ^{ℕ}. This contradiction proves (ii).

We remark that the above theorem also holds, with the same proof, when ℝ is replaced by any dense linear ordering with a cofinal copy of ℕ.

7 Saturated and Special Structures

In this section we show that BDD and LIM have the highest possible quantifier level if the underlying structure M is saturated, or more generally, special. This happens even if one adds a symbol for the set I of infinite elements to the vocabulary. Thus Robinson’s Theorem 3.3 for standard functions cannot be extended to the set of all functions on a special structure.

We recall some basic facts (See [CK], Chapter 5). By definition, a structure M is κ-saturated if every set of fewer than κ formulas with parameters in M which is finitely satisfiable in M is satisfiable in M. M is saturated if it is |M|-saturated. M is special if it is the union of an elementary chain of λ^{+}-saturated structures where λ ranges over all cardinals less than |M|.

Let us call a cardinal κ nice if κ = ∑_{λ<κ} 2^{λ}. For example, every inaccessible cardinal is nice, every strong limit cardinal is nice, and every cardinal λ^{+} = 2^{λ} is nice.

Facts 7.1 (i) If ω ≤ |M| < κ and κ is nice then M has a special elementary extension of cardinality κ.

(ii) Any two elementarily equivalent special models of the same cardinality are isomorphic.

(iii) Reducts of special models are special.

(iv) If M is special, then (M, a⃗) is special for each finite tuple a⃗ in M.

Theorem 7.2 Suppose M is an ordered structure with no greatest element, M is special, |M| is nice, and |L(M)| < |M|.

(i) BDD is not Π_{2} over M.

(ii) LIM is not Σ_{3} over M.

Proof. We prove (ii). The proof of (i) is similar. Let T be the set of all Σ_{3} consequences of T h(M) ∪ {LIM}. Consider a finite subset T_{0} ⊆ T. The conjunction of T_{0} is equivalent to a Σ_{3} sentence θ, and T h(M)∪{LIM} ⊧ θ. By Corollary 5.4, we cannot have T h(M) ∪ {θ} ⊧ LIM, and therefore we cannot have T h(M) ∪ T_{0} ⊧ LIM. By the Compactness Theorem, there is a model (M_{0}, g) of T h(M) ∪ T ∪ {¬LIM}. Now let U be the set of all Π_{3} sentences which hold in (M_{0}, g). By the Compactness Theorem again, there is a model (M_{1}, f) of T h(M) ∪ U ∪ {LIM}. Then every Σ_{3}-sentence holding in (M_{1}, f) holds in (M_{0}, g). Let κ = |M|. Since |L(M)| < κ and κ is nice, it follows from Fact (i) that we may take (M_{0}, g) and (M_{1}, f) to be special models of cardinality κ. By Fact (ii), M_{0} and M_{1} are isomorphic to M, so we may take M_{1} = M_{0} = M. Then LIM holds in (M, f) and fails in (M, g), but every Σ_{3} sentence holding in (M, f) holds in (M, g). This proves (ii). The proof of (i) is similar.

Given a hyperextension (^{∗}M, I) of M, we will say that a function g : ^{∗}M → ∗M is standard if (^{∗}M, g) is an elementary extension of (M, f), or in other words, if (^{∗}M, g, I) is a hyperextension of (M, f). Robinson’s Theorem 3.3 shows that BDD and LIM are Π_{1} for standard functions over any hyperextension (^{∗}M, I) of M.

Our next theorem will show that Robinson’s result does not carry over to nonstandard functions. In fact, we will show that Theorem 7.2 holds even when a symbol for the set I of infinite elements is added to the vocabulary. Thus for nonstandard functions, one cannot lower the quantifier level of BDD or LIM by adding a symbol for I.

Lemma 7.3 Let M be an ordered structure with no greatest element, such that every element of M is a constant symbol of L(M). Suppose that (^{∗}M, I) a hyperextension of M of cardinality κ = |^{∗}M| such that |L(M)| < κ, κ is nice, (^{∗}M, f, g) is special, and every Π_{n} sentence of L(M) ∪ {F } true in (^{∗}M, f) is true in (^{∗}M, g). Then every Π_{n} sentence of L(M) ∪ {F, I} true in (^{∗}M, f, I) is true in (^{∗}M, g, I). Similarly for Σ_{n}.

Proof. The result for Σ_{n} follows from the result for Π_{n} by interchanging f and g. Let κ = |^{∗}M|. By the Keisler Sandwich Theorem ([CK], Proposition 5.2.7 and Exercise 5.2.7), there is a chain

(M_{0}, h_{0}) ⊆ (M_{1}, h_{1}) ⊆ ⋯ (M_{n}, h_{n})

such that

(M_{0}, h_{0}) ≡ (M, f), (M_{1}, h_{1}) ≡ (M, g),

and for each m < n − 1,

(M_{m}, h_{m}) ≺ (M_{m+2}, h_{m+2}).

By Fact (i) we may take each (M_{m}, h_{m}) to be a special structure of cardinality κ. For each m ≤ n let I_{m} be the set of elements of M_{m} greater than each element of M. We then have

(M_{0}, h_{0}, I_{0}) ⊆ (M_{1}, h_{1}, I_{1}) ⊆ ⋯ (M_{n}, h_{n}, I_{n}).

Since each element of M has a constant symbol in L(M), it follows from Fact (i) that

(M_{0}, h_{0}, I_{0}) ≅ (^{∗}M, f, I) and (M_{1}, h_{1}, I_{1}) ≅ (^{∗}M, g, I).

By remark (iv), (M_{m}, h_{m}, a⃗) is still special for each m and finite tuple a⃗ in M_{m}. Then by Fact (ii), for each m < n − 1 and finite tuple a⃗ in M_{m}, there is an isomorphism from (M_{m}, h_{m}) onto (M_{m+2}, h_{m+2}) which fixes a⃗ and each element of M. This isomorphism also sends I_{m} onto I_{m+2}, so

(M_{m}, h_{m}, I_{m}, a⃗) ≅ (M_{m+2}, h_{m+2}, I_{m+2}, a⃗).

Using the Tarski-Vaught criterion for elementary extensions ([CK], Proposition 3.1.2), it follows that

(M_{m}, h_{m}, I_{m}) ≺ (M_{m+2}, h_{m+2}, I_{m+2}).

By the Keisler Sandwich Theorem again, every Π_{n}-sentence true in (M_{0}, h_{0}, I_{0}) is true in (M_{1}, h_{1}, I_{1}), and hence every Π_{n}-sentence true in (^{∗}M, f, I) is true in (^{∗}M, g, I).

Theorem 7.4 Let M be an ordered structure with no greatest element, and let (^{∗}M, I) be a hyperextension of M such that ^{∗}M is special and |^{∗}M| is uncountable and nice.

(i) BDD is not Π_{2} over (^{∗}M, I).

(ii) LIM is not Σ_{3} over (^{∗}M, I).

Proof. We prove (ii). The proof of (i) is similar. By the proof of Theorem 7.2, there are functions f, g such that (^{∗}M, f) and (^{∗}M, g) are special, LIM holds in (^{∗}M, f) and fails in (^{∗}M, g), and every Σ_{3} sentence true in (^{∗}M, f) is true in (^{∗}M, g). By Facts (i) and (ii), we may take f and g so that (^{∗}M, f, g) is special. Then by the preceding lemma, every Σ_{3} sentence true in (^{∗}M, f, I) is true in (^{∗}M, g, I). Therefore LIM is not Σ_{3} over (^{∗}M, I).

8 Infinitely Long Sentences

In this section we consider the quantifier levels of BDD and LIM in the infinitary logic L_{ω_{1}ω} formed by adding countable conjunctions and disjunctions to first order logic. See [Ke1] for a treatment of the model theory of this logic.

Definition 8.1 Let Q be a set of sentences of L_{ω_{1}ω} in the vocabulary L(M). ⋀ Q denotes the set of countable conjunctions of sentences in Q. ⋁ Q denotes the set of countable disjunctions of sentences in Q. BQ denotes the set of finite Boolean combinations of sentences in Q.

For example, ⋁ ⋀ B ⋀ Π_{1} is the set of sentences of the form ⋁_{m} ⋀_{n} θ_{mn} where each θ_{mn} is a finite Boolean combination of countable conjunctions of universal first order sentences.

We say that M has cofinality ω if M has a countable increasing sequence a_{0}, a_{1}, … which is unbounded, that is, ∀x ⋁_{n} x ≤ a_{n}. Every countable M and every structure M with universe ℝ has cofinality ω. In this section our main focus will be uncountable M with cofinality ω.

Suppose that M has universe ℝ and a constant symbol for each natural number. Then BDD is ⋁ Π_{1} over M, because

(M, f) ⊧ LIM ⇔ ⋁_{n} ∀z F (z) ≤ n.

LIM is ⋀ ⋁ Π_{1} over M, because

(M, f) ⊧ LIM ⇔ ⋀_{m} ⋁_{n} ∀z [n ≤ z ⇒ m ≤ F (z)].

LIM is also ⋀ Σ_{2} over M, because

(M, f) ⊧ LIM ⇔ ⋀_{m} ∃y∀z [y ≤ z ⇒ m ≤ F (z)].

The next theorem shows that if M has cofinality ω, then BDD is not ⋀ Σ_{1} over M and LIM is not ⋁ ⋀ Σ_{1} over M. Thus if the outer quantifiers ∃ and ∀ are replaced by ⋁ and ⋀, then Theorem 5.3 holds for uncountable structures M of cofinality ω. In fact, we get a stronger result with B ⋀ Π_{1} in place of Σ_{1}.

Theorem 8.2 Suppose that M has cofinality ω.

(i) BDD is not ⋀ B ⋀ Π_{1} over M.

(ii) LIM is not ⋁ ⋀ B ⋀ Π_{1} over M.

Proof. We prove (ii). The proof of (i) is similar.

Let a_{n} be an unbounded strictly increasing sequence in M. Since each sentence of L_{ω_{1}ω} has countably many symbols, we may assume without loss of generality that the vocabulary L(M) is countable. We may also assume that L(M) has a constant symbol, say n, for each a_{n}, and a symbol for the function λ(x) = min{a_{n} : x ≤ a_{n}}. As in the proof of Theorem 5.3, we let α : ℕ^{ℕ} → M^{M} be the function defined by (α(g))(x) = g(λ(x)), and let L be the set of g ∈ ℕ^{ℕ} such that (M, α(g)) ⊧ LIM.

Claim: For each first order quantifier-free formula φ(F, x⃗) in the vocabulary L(M) ∪ {F }, the set

{g ∈ ℕ^{ℕ} : (M, α(g)) ⊧ ∃z⃗ φ(F, z⃗)}

is Σ_{1} in the Borel hierarchy.

Proof of Claim: We may assume without loss of generality that ∃z⃗ φ(F, z⃗) has the form

∃x⃗∃y⃗ [F (x⃗) = y⃗ ∧ ψ(x⃗, y⃗)]

where ψ(x⃗, y⃗) is a first order quantifier-free formula of L(M). Since (α(g))(x) = (α(g))(λ(x)) for all g and x, (M, α(g)) satisfies ∃z⃗ φ(F, z⃗) if and only if it satisfies

⋁_{p⃗} ⋁_{q⃗} [F (p⃗) = q⃗ ∧ ∃x⃗ [λ(x⃗) = p⃗ ∧ ψ(x⃗, q⃗)]].

Let

U = {(p⃗, q⃗) : M ⊧ ∃x⃗ [λ(x⃗) = p⃗ ∧ ψ(x⃗, q⃗)]}.

Then (M, α(g)) satisfies ∃z⃗ φ(F, z⃗) if and only if g(p⃗) = q⃗ for some (p⃗, q⃗) ∈ U. For each pair (p⃗, q⃗), the set {g : g(p⃗) = q⃗} is clopen in ℕ^{ℕ}, so the union of these sets over U is Σ_{1} in the Borel hierarchy, as required.

Now suppose to the contrary that there is a ⋁ ⋀ B ⋀ Π_{1} sentence

θ = ⋁_{m} ⋀_{n} φ_{mn}(F)

which is equivalent to LIM in all models (M, f), where φ_{mn}(F) is B ⋀ Π_{1} in the vocabulary L(M) ∪ {F }.

We observe that any finite conjunction or disjunction of ⋀ Π_{1} sentences is equivalent to a ⋀ Π_{1} sentence, and the negation of a ⋀ Π_{1} sentence is equivalent to a ⋁ Σ_{1} sentence. It follows that θ is equivalent to a sentence

⋁_{m} ⋀_{n} [⋀_{p} ∀z⃗φ_{mnp}(F, z⃗) ∨ ⋁_{q} ∃z⃗ ψ_{mnq}(F, z⃗)]

where each φ_{mnp}(F, z⃗) and ψ_{mnq}(F, z⃗) is a first order quantifier-free formula of L(M) ∪ {F }.

Using the claim, it follows that

L = ⋃_{m} ⋂_{n} (⋂_{p} A_{mnp} ∪ ⋃_{q} B_{mnq})

where each A_{mnp} and B_{mnq} is clopen in ℕ^{ℕ}. By renumbering and rearranging, we can get

L = ⋃_{m} ⋂_{n} ⋃_{q}(A_{mnq} ∪ B_{mnq}).

Therefore L is Σ_{3} in ℕ^{ℕ}. This is a contradiction, and proves (ii).

9 O-minimal Structures

In this section we show that BDD has the highest possible quantifier level, and that LIM is not Boolean in Π_{2}, in the case that M is an o-minimal expansion of the ordered field of real numbers. We leave open the question whether LIM can be Σ_{3}. We will use two lemmas from [FM] concerning fast and indiscernible functions.

An ordered structure is o-minimal if every set definable with parameters is a finite union of intervals and points. There is an extensive literature on the subject (e.g. see [VDD1], [VDD2]). An example of an o-minimal structure is the ordered field of reals with analytic functions restricted to the unit cube and with the (unrestricted) exponential function. It is easily seen that if M is o-minimal, then every ordered reduct of M is o-minimal, and the expansion of M formed by adding a symbol for each definable relation is o-minimal.

Throughout this section we let M be an o-minimal expansion of the real ordered field R = (ℝ, ≤, +, ·). “Definable” will always mean first order definable in M with parameters from M.

When working with o-minimal structures, one often restricts attention to definable functions. It is easily seen that LIM is Π_{2} over an o-minimal structure M relative to the set of definable functions, since LIM fails for a definable function f if and only if ∃x∃y∀z[x ≤ z ⇒ f(z) ≤ y]. However, here we consider arbitrary functions on M.

Definition 9.1 A strictly increasing sequence s of positive integers is M-fast if for each definable function f : ℝ → ℝ, there exists N ∈ ℕ such that f(s(k)) < s(k + 1) for all k > N. For convenience we also require that s(0) = 0.

Lemma 9.2 ([FM], 3.3) If L(M) is countable then there exists an M-fast sequence.

Given u⃗, v⃗ ∈ ℕ^{n} and N ∈ ℕ, we write u⃗ =_{N} v⃗ if min(u_{i}, N) = min(v_{i}, N) for i = 1, …, n, and u⃗ ∼ v⃗ if u⃗, v⃗ are order isomorphic, that is, u_{i} ≤ u_{j} iff v_{i} ≤ v_{j} for i, j = 1, …, n. We write u⃗ ∼_{N} v⃗ if u⃗ =_{N} v⃗ and u⃗ ∼ v⃗. Note that ∼_{N} is an equivalence relation on ℕ^{n} with finitely many classes.

Given an M-fast sequence s and a tuple u⃗ ∈ ℕ^{n}, we write s(u⃗) for (s(u_{1}), …, s(u_{n})).

Lemma 9.3 ([FM], 3.6). Suppose s is M-fast, h : ℝ^{n} → ℝ is definable, and g : ℕ^{n} → ℝ is the function given by u⃗ ↦ h(s(u⃗)). Then there exists N ∈ ℕ such that

g(u⃗) ≤ g(v⃗) ⇔ g(w⃗) ≤ g(z⃗)

whenever u⃗ =_{N} v⃗ and (u⃗, v⃗) ∼_{N} (w⃗, z⃗).

In [FM], the function g is called almost indiscernible. We will call N an indiscernibility bound for h.

Corollary 9.4 Suppose s is M-fast, A ⊆ ℝ^{n} is definable, and

B = {u⃗ ∈ ℕ^{n} : A(s(u⃗))}.

There exists N ∈ ℕ such that B(u⃗) ⇔ B(v⃗) whenever u⃗, v⃗ ∈ ℕ^{n} and u⃗ ∼_{N} v⃗.

Proof. The characteristic function h of A is definable. Let N be an indiscernibility bound for h, and let g be as in Lemma 9.3. Suppose u⃗, v⃗ ∈ ℕ^{n} and u⃗ ∼_{N} v⃗. Let k ∈ ℕ be greater than N and each u_{i} and v_{i}. By replacing the u_{i} by k + u_{i} whenever N ≤ u_{i}, we obtain a tuple w⃗ such that w⃗ ∼_{N} u⃗ and (u⃗, w⃗) ∼_{N} (v⃗, w⃗). By Lemma 9.3, g(u⃗) ≤ g(w⃗) iff g(v⃗) ≤ g(w⃗), and g(u⃗) ≥ g(w⃗) iff g(v⃗) ≥ g(w⃗). It follows that g(u⃗) = g(v⃗), so B(u⃗) ⇔ B(v⃗).

By an indiscernibility bound for a formula ψ of L(M) with parameters from M we mean an indiscernibility bound for the characteristic function of the set defined by ψ. It is clear that if N is an indiscernibility bound for ψ, then any M ≥ N is also an indiscernibility bound for ψ.

Theorem 9.5 Suppose that M is an o-minimal expansion of (ℝ, ≤, +, ·). Then BDD is not Π_{2} over M.

Proof. We may assume that M has a countable vocabulary. By Lemma 9.2 there is an M-fast sequence s. Suppose to the contrary that there is a Π_{2} sentence ∀x⃗φ(F, x⃗) of L(M) ∪ {F } which is equivalent to BDD in all structures (M, f). We may assume that ∀x⃗φ(F, x⃗) has the form

∀x⃗ ∃y⃗ ∃z⃗ [F (x⃗, y⃗) = z⃗ ∧ θ(x⃗, y⃗, z⃗)]

where θ is a quantifier-free formula in which F does not occur, |z⃗| = |x⃗| + |y⃗| = j + k, and

F (x⃗, y⃗) = (F (x_{1}), …, F (x_{j}), F (y_{1}), …, F (y_{k})).

(This can be proved by induction on the number of occurrences of F in φ). Let f : ℝ → ℝ be the function such that f(x) = x if x = s(4i) for some i ∈ ℕ, and f(x) = 0 otherwise. For each m ∈ ℕ let f_{m} : ℝ → ℝ be the function such that f_{m}(x) = f(x) for x ≤ s(m) and f_{m}(x) = 0 for x > s(m). Then each f_{m} is bounded but f is unbounded. Therefore ∀x⃗ φ(f_{m}, x⃗) holds for each m ∈ ℕ, but ∀x⃗φ(f, x⃗) fails. (Recall that ∀x⃗ φ(f, x⃗) means that (M, f) satisfies ∀x⃗ φ(F, x⃗).) Hence there exists a tuple a⃗ such that ¬φ(f, a⃗).

The notation w⃗_{1} < w⃗ < w⃗_{2} means that each coordinate of w⃗ is strictly between each coordinate of w⃗_{1} and w⃗_{2}, that is, w⃗ is in the open box with vertices w⃗_{1} and w⃗_{2}. We will deal with variables which are outside the range of s by putting them into an open box with vertices in the range of s.

By Corollary 9.4, there is an N ∈ ℕ which is an indiscernibility bound for each formula of the form

∃w⃗ [w⃗_{1} < w⃗ < w⃗_{2} ∧ θ(a⃗, y⃗, z⃗)]

where w⃗ ⊆ y⃗. We also take N so that s(N) > max(a⃗).

By hypothesis, we have

∃y⃗ ∃z⃗ [f_{N}(a⃗, y⃗) = z⃗ ∧ θ(a⃗, y⃗, z⃗)].

Choose b⃗ in M such that

∃z⃗ [f_{N}(a⃗, b⃗) = z⃗ ∧ θ(a⃗, b⃗, z⃗)].

Then θ(a⃗, b⃗, f_{N}(a⃗, b⃗)).

We wish to find e⃗ in M such that θ(a⃗, e⃗, f(a⃗, e⃗)). This will show that φ(f, a⃗), contrary to hypothesis, and complete the proof that BDD is not Π_{2} over M. We cannot simply take e⃗ = b⃗, because b could have a coordinate b_{i} such that f(b_{i}) ≠ f_{N}(b_{i}). This happens when b_{i} = s(4m) where 4m > N, so that f(b_{i}) = b_{i} but f_{N}(b_{i}) = 0.

Claim: For each u⃗ ∈ ℕ^{n} there exists v⃗ ∈ ℕ^{n} such that v⃗ ∼_{N} u⃗, f(s(v⃗)) = f_{N}(s(v⃗)), and if u_{j} = u_{i} + 1 then v_{j} = v_{i} + 1.

Proof of Claim: Take v⃗ such that v⃗ ∼_{N} u⃗, and v_{i} is not a multiple of 4 when v_{i} > N, and v_{j} = v_{i} + 1 when u_{j} = u_{i} + 1. Then v_{i} = u_{i} below N, and f(s(v_{i})) = f(s(u_{i})) = f_{N}(s(v_{i})) = f_{N}(s(u_{i})) = 0 when u_{i} > N. It follows that f(s(v⃗)) = f_{N}(s(v⃗)).

We may rearrange b⃗ into a k-tuple (c⃗, d⃗) such that the terms of c⃗ belong to the range of s and the terms of d⃗ do not. Then f_{N}(d⃗) = 0 is a tuple of 0’s. Let (t⃗, w⃗) be the corresponding rearrangement of y⃗. Then |c⃗| = |t⃗| = n. Let d⃗_{1}, d⃗_{2} be the vertices of the smallest open box containing d⃗ with coordinates in the range of s. That is, d⃗_{1} < d⃗ < d⃗_{2} and the coordinates of d⃗_{1}, d⃗_{2} are consecutive in the range of s. Then

∃w⃗ [d⃗_{1} < w⃗ < d⃗_{2} ∧ θ(a⃗, c⃗, w⃗, f_{N}(a⃗, c⃗),0)]

holds in M. We have (c⃗, d⃗_{1}, d⃗_{2}) = s(u⃗) for some u⃗ ∈ ℕ^{n}. Take v⃗ as in the claim and let (e⃗_{0}, d⃗_{3}, d⃗_{4}) = s(v⃗). Then by indiscernibility,

∃w⃗ [d⃗_{3} < w⃗ < d⃗_{4} ∧ θ(a⃗, e⃗_{0}, w⃗, f_{N}(a⃗, e⃗_{0}),0)].

Note that s(N) > max(a⃗), so f(a⃗) = f_{N}(a⃗). Now let e⃗ = (e⃗_{0}, e⃗_{1}) where e⃗_{1} is a witness for w⃗ in the above formula. Since the coordinates of d⃗_{3} and d⃗_{4} are consecutive in the range of s, the coordinates of e⃗_{1} must be outside the range of s, where f and f_{N} are 0. It follows that f(a⃗, e⃗) = f_{N}(a⃗, e⃗). Therefore θ(a⃗, e⃗, f(a⃗, e⃗)), and hence BDD is not Π_{2} over M.

Corollary 9.6 Suppose that M is an o-minimal expansion of (ℝ, ≤, +, ·). Then (i) BDD is not ⋀ Π_{2} over M. (ii) LIM is not ⋀ Π_{2} over M.

Proof. This follows from the proof of Theorem 9.5. For (i), we suppose that there is a ⋀ Π_{2} sentence ⋀_{i} ∀x⃗φ_{i}(F, x⃗) which is equivalent to BDD in all structures (M, f), choose i ∈ ℕ such that ∀x⃗ φ_{i}(f, x⃗) fails, and get a contradiction as in the proof of Theorem 9.5.

For part (ii), we first observe that all the functions f : M → M used in the proof of (i) satisfy the Π_{1} sentence

∀x [F (x) = x ∨ F (x) = 0].

Call this sentence β(F). It follows that β(F) ∧ BDD(F) is not ⋀ Π_{2} over M. We also note that

β(F) ⇔ β(x − F (x))

and

β(f) ⇒ [BDD(F) ⇔ LIM(x − F (x))].

Now suppose that LIM(F) is ⋀ Π_{2} over M. Then β(F) ⇒ LIM(x − F (x)) is also ⋀ Π_{2} over M. Hence β(F) ∧ BDD(F) is ⋀ Π_{2} over M, a contradiction.

Theorem 9.7 Suppose that M is an o-minimal expansion of (ℝ, ≤, +, ·). Then LIM is not ⋁ B_{2} over M.

Proof. We may assume that M has a countable vocabulary. By Lemma 9.2 there is an M-fast sequence s. Suppose to the contrary that there is a ⋁ B_{2} sentence ψ which is equivalent to LIM in all structures (M, f). Then ¬ψ is equivalent to a ⋀ B_{2} sentence. Since finite conjunctions and disjunctions of Π_{2} sentences are equivalent to Π_{2} sentences, and similarly for Σ_{2}, ¬ψ is equivalent to a sentence

⋀_{m}(α_{m} ∨ β_{m})

where each α_{m} is Σ_{2} and each β_{m} is Π_{2}. We may assume that α_{m} and β_{m} have the form

α_{m} = ∃x⃗ ∀y⃗ ∀z⃗ [F (x⃗, y⃗) = z⃗ ⇒ \overline{α}_{m}(x⃗, y⃗, z⃗)],
β_{m} = ∀x⃗ ∃y⃗ ∃z⃗ [F (x⃗, y⃗) = z⃗ ∧ \overline{β}_{m}(x⃗, y⃗, z⃗)]

where \overline{α}_{m} and \overline{β}_{m} are quantifier-free formulas of L(M).

We now define a family of functions from ℕ into ℕ which we will later use to build functions from ℝ into ℝ. We begin with a sequence h : ℕ → ℕ with the following properties:

(a) For each m ∈ ℕ, h(m) ≤ m and h(m) is either 0 or a power of 2.

(b) Each power of 2 occurs infinitely often in the sequence h,

(c) If h(m) > 0, them m is halfway between two powers of 2.

Note that h(i) is “usually” 0, and that whenever i < j and h(i) > 0, h(j) > 0, we have h(h(i)) = 0 and 2i ≤ j. For each finite or infinite sequence of natural numbers σ, let h_{σ} be the function obtained from h by putting h_{σ}(i) = 0 if h(i) = 2^{n} and i > σ(n), and putting h_{σ}(i) = h(i) otherwise. Thus when n is in the domain of σ, h_{σ}^{−1}{2^{n}} is the finite set h^{−1}{2^{n}} ∩ {0, …, σ(n)}. When σ is finite and n is outside its domain, h_{σ}^{−1}{2^{n}} is the infinite set h^{−1}{2^{n}}.

For each σ, define the function f_{σ} : ℝ → ℝ by putting f_{σ}(s(i)) = s(h_{σ}(i)) if h_{σ}(i) > 0, and f_{σ}(x) = x for all other x. Note that for each infinite sequence σ we have lim_{x→∞} f_{σ}(x) = ∞, so LIM holds in (M, f_{σ}). But for each finite sequence σ we have lim inf_{x→∞} f_{σ}(x) < ∞, so LIM fails in (M, f_{σ}).

We will now build an infinite sequence σ = (σ(0), σ(1), …) such that (M, f_{σ}) satisfies ¬ψ. This will give us the desired contradiction, since (M, f_{σ}) satisfies LIM. We will simultaneously build a sequence of tuples a⃗_{m}, m ∈ ℕ, and a strictly increasing “growth sequence” g(0) < g(1) < · · ·. We will form an increasing chain

σ[0] ⊂ σ[1] ⊂ ⋯

of finite sequences, and take σ to be their union. This chain will have the property that each term of σ[m] \ σ[m − 1] will be ≥ g(m − 1). Whenever possible, σ[m] will be chosen so that α_{m} holds in (M, f_{σ[m]}), and a⃗_{m} will be a witness for the initial existential quantifiers of α_{m}.

For convenience we let σ[−1] denote the empty sequence and put g(−1) = 1. Suppose m ∈ ℕ and we already have σ[i], a⃗_{i}, and g(i) for each i < m. We have two cases.

Case 1. There is a finite sequence η ⊃ σ[m − 1] such that α_{m} holds in (M, f_{η}), and each term of η \ σ[m − 1] is ≥ g(m − 1). In this case we take σ[m] to be such an η, and take a⃗_{m} to be a tuple in ℝ which witnesses the initial existential quantifiers of α_{m} in (M, f_{σ[m]}), that is,

∀y⃗ ∀z⃗ [f_{σ[m]}(a⃗_{m}, y⃗) = z⃗ ⇒ \overline{α}_{m}(a⃗_{m}, y⃗, z⃗)].

Case 2. Otherwise. In this case we take σ[m] to be an arbitrary finite sequence such that σ[m] ⊃ σ[m−1] and each term of σ[m]\σ[m−1] is ≥ g(m−1), and let a⃗_{m} be an arbitrary tuple in ℝ.

We now define g(m). By Corollary 9.4, there is an N ∈ ℕ which is an indiscernibility bound for each formula of the form

∀w⃗[w⃗_{1} < w⃗ < w⃗_{2} ⇒ \overline{α}_{m}(a⃗_{m}, y⃗_{1}, w⃗, z⃗_{1}, w⃗)]

where w⃗ ⊆ y⃗, y⃗_{1} is the part of y⃗ outside w⃗, and z⃗_{1} is the corresponding part of z⃗.

Let p be the number of variables in the sentences α_{i}, β_{i}, i ≤ m. Take g(m) so that:

(d) g(m) ≥ N, g(m) ≥ 2p, g(m) > g(m − 1), g(m) > max(σ[m]),

(e) s(g(m)) > max(a⃗_{m}),

(f) The condition stated before Claim 2.

Finally, we define σ to be the union σ = ⋃_{m} σ[m]. To complete the proof we prove two claims, Claim 1 concerning α_{m} and Claim 2 concerning β_{m}. Condition (f) will not be used in Claim 1, but will be needed later for Claim 2.

Claim 1: Suppose α_{m} holds in (M, f_{σ[m]}) (Case 1 above). Then α_{m} holds in (M, f_{σ}).

Proof of Claim 1: We show that

∀y⃗ ∀z⃗ [f_{σ}(a⃗_{m}, y⃗) = z⃗ ⇒ \overline{α}_{m}(a⃗_{m}, y⃗, z⃗)].

Suppose not. Then there is a tuple b⃗ in M such that

¬∀z⃗ [f_{σ}(a⃗_{m}, b⃗) = z⃗ ⇒ \overline{α}_{m}(a⃗_{i}, b⃗, z⃗)].

As in the proof of Theorem 9.5, we may rearrange b⃗ into a k-tuple (c⃗, d⃗) such that the terms of c⃗ belong to the range of s and the terms of d⃗ do not. Then f_{σ}(c⃗) is also in the range of s, and f_{σ}(d⃗) = d⃗. Let (t⃗, w⃗) be the corresponding rearrangement of y⃗. Let d⃗_{1}, d⃗_{2} be the vertices of the smallest open box containing d⃗ with coordinates in the range of s. Then

¬∀w⃗ [d⃗_{1} < w⃗ < d⃗_{2} ⇒ \overline{α}_{m}(a⃗_{m}, c⃗, w⃗, f_{σ}(a⃗_{m}, c⃗), w⃗)].

Let u⃗ be the sequence in ℕ such that (c⃗, d⃗_{1}, d⃗_{2}) = s(u⃗). Since the terms of σ beyond σ[m] are greater than g(m), we have h_{σ}(i) = h_{σ[m]}(i) for all i ≤ g(m) and f_{σ}(x) = f_{σ[m]}(x) for all x ≤ s(g(m)). For i > g(m) we have either h_{σ}(i) = h_{σ[m]}(i), or h_{σ}(i) = 0 and h_{σ[m]}(i) > 0. Recall that g(m) ≥ 2p ≥ 2|u⃗|, where p is the number of variables in α_{m} ∨ β_{m}. It follows that the sequence h_{σ[m]} has enough zeros to insure that there is a sequence v⃗ in ℕ^{p} such that:

(g) For each i, (u⃗, 2^{i}) ∼_{g(m)} (v⃗, 2^{i}),

(h) v_{i} = u_{i} whenever h_{σ}(i) > 0,

(i) If u_{i} = u_{i} + 1 then v_{i} = v_{i} + 1,

(j) h_{σ[m]}(v⃗) = h_{σ}(u⃗).

Therefore (v⃗, h_{σ[m]}(v⃗)) ∼_{g(m)} (u⃗, h_{σ}(u⃗)). Let (e⃗_{0}, d⃗_{3}, d⃗_{4}) = s(v⃗). Then by (d), (e), (g), and indiscernibility, we have

¬∀w⃗ [d⃗_{3} < w⃗ < d⃗_{4} ⇒ \overline{α}_{m}(a⃗_{m}, e⃗_{0}, w⃗, f_{σ[m]}(a⃗_{m}, e⃗_{0}), w⃗)].

We may therefore extend e⃗_{0} to a tuple e⃗ = (e⃗_{0}, e⃗_{1}) such that

d⃗_{3} < e⃗_{1} < d⃗_{4} ∧ ¬ \overline{α}_{m}(a⃗_{m}, e⃗, f_{σ[m]}(a⃗_{m}, e⃗_{0}), e⃗_{1}).

The coordinates of d⃗_{1} and d⃗_{2} are consecutive in the range of s, so by (i) the coordinates of d⃗_{1} and d⃗_{2} are consecutive in the range of s. Therefore the coordinates of e⃗_{1} are outside the range of s, so f_{σ[m]}(e⃗_{1}) = e⃗_{1}. Then

¬ \overline{α}_{m}(a⃗_{m}, e⃗, f_{σ[m]}(a⃗_{m}, e⃗).

This contradicts the fact that

∀y⃗ ∀z⃗ [f_{σ[m]}(a⃗_{i}, y⃗) = z⃗ ⇒ \overline{α}_{m}(a⃗_{m}, y⃗, z⃗)].

and completes the proof of Claim 1.

We now state the postponed condition (f) for the growth sequence g. Recall that p is the number of variables in the sentences α_{i}, β_{i}, i ≤ m.

(f) For each u⃗ ∈ ℕ^{p} there exists v⃗ ∈ ℕ^{p} with the following properties: (f1) max(v⃗) < g(m), (f2) If u_{j} = u_{i} + 1 then v_{j} = v_{i} + 1, (f3) (v⃗, h_{σ[m]}(v⃗)) ∼_{m} (u⃗, h_{σ[m]}(u⃗)).

There is a g(m) with these properties because the equivalence relation ∼_{m} has only finitely many classes.

Claim 2: The sentence ¬ψ holds in (M, f_{σ}).

Proof of Claim 2. We must show that for each m ∈ ℕ, α_{m} ∨ β_{m} holds in (M, f_{σ}). Since LIM fails in (M, f_{σ[m]}), α_{m} ∨ β_{m} holds in (M, f_{σ[m]}). In Case 1 above, by definition α_{m} holds in (M, f_{σ[m]}), and by Claim 1, α_{m} holds in (M, f_{σ}).

In Case 2, α_{m} fails in (M, f_{σ[r]}) for each r ≥ m, and therefore β_{m} holds in (M, f_{σ[r]}) for each r ≥ m. In this case we prove that β_{m} holds in (M, f_{σ}). We fix a tuple a⃗ in M and prove

∃y⃗ ∃z⃗ [f_{σ}(a⃗, y⃗) = z⃗ ∧ \overline{β}_{m}(a⃗, y⃗, z⃗)].

By Corollary 9.4 there is an M ∈ ℕ which is an indiscernibility bound for each formula of the form

∃w⃗[w⃗_{1} < w⃗ < w⃗_{2} ∧ \overline{β}_{m}(a⃗, y⃗_{1}, w⃗, z⃗_{1}, w⃗)]

where w⃗ ⊆ y⃗, y⃗_{1} is the part of y⃗ outside w⃗, and z⃗_{1} is the corresponding part of z⃗.

Take r large enough so that r ≥ m and r ≥ M, and s(r) > max(a⃗). Since β_{m} holds in (M, f_{σ[r]}), we have

∃y⃗ ∃z⃗ [f_{σ[r]}(a⃗, y⃗) = z⃗ ∧ \overline{β}_{m}(a⃗, y⃗, z⃗)].

We may therefore choose b⃗ in M so that

\overline{β}_{m}(a⃗, b⃗, f_{σ[r]}(a⃗, b⃗)).

As in the proof of Theorem 9.5, we may rearrange b⃗ into a tuple (c⃗, d⃗) such that the terms of c⃗ belong to the range of s and the terms of d⃗ do not. Then f_{σ[r]}(d⃗) = d⃗. Let (t⃗, w⃗) be the corresponding rearrangement of y⃗, and let d⃗_{1}, d⃗_{2} be the vertices of the smallest open box containing d⃗ with coordinates in the range of s. Then

∃w⃗ [d⃗_{1} < w⃗ < d⃗_{2} ∧ \overline{β}_{m}(a⃗, c⃗, w⃗, f_{σ[r]}(a⃗, c⃗), w⃗)].

Let u⃗ be the tuple in ℕ such that s(u⃗) = (c⃗, d⃗_{1}, d⃗_{2}). Then there is a tuple v⃗ in ℕ such that conditions (f1)–(f3) hold with r in place of m. Here p is the number of variables in α_{i}, β_{i}, i ≤ r, so β_{m} has at most p variables, and u⃗ can be taken with length p.

Let s(v⃗) = (e⃗_{0}, d⃗_{3}, d⃗_{4}). Since r ≥ M, by (f3) and indiscernibility we have

∃w⃗ [d⃗_{3} < w⃗ < d⃗_{4} ∧ \overline{β}_{m}(a⃗, e⃗_{0}, w⃗, f_{σ[r]}(a⃗, e⃗_{0}), w⃗)].

Take e⃗_{1} in M such that

d⃗_{3} < e⃗_{1} < d⃗_{4} ∧ \overline{β}_{m}(a⃗, e⃗_{0}, e⃗_{1}, f_{σ[r]}(a⃗, e⃗_{0}), e⃗_{1}).

By (f2), every coordinate of e⃗_{1} is outside the range of s, so f_{σ[r]}(e⃗_{1}) = e⃗_{1}. Putting e⃗ = (e⃗_{0}, e⃗_{1}), we have

\overline{β}_{m}(a⃗, e⃗, f_{σ[r]}(a⃗, e⃗)).

It remains to prove that f_{σ}(a⃗, e⃗) = f_{σ[r]}(a⃗, e⃗). Suppose i ≤ g(r) and h_{σ[r]}(i) = 2^{j}. If j is in the domain of σ[r], then h_{σ}(i) = 2^{j} because σ(j) = σ[r](j). Otherwise σ(j) ≥ g(r), hence i ≤ g(r) < σ(j) and h(i) = 2^{j}, and again h_{σ}(i) = 2^{j}. If h_{σ[r]}(k) = 0 then h_{σ}(k) = 0. Therefore h_{σ}(k) = h_{σ[r]}(k) for all k ≤ g(r).

By (f1), max(v⃗) < g(r). Therefore h_{σ}(v⃗) = h_{σ[r]}(v⃗), and hence f_{σ}(v⃗) = f_{σ[r]}(v⃗). Since we also have max(a⃗) < s(r), it follows that f_{σ}(a⃗, e⃗) = f_{σ[r]}(a⃗, e⃗). Therefore

\overline{β}_{m}(a⃗, e⃗, f_{σ}(a⃗, e⃗)),

and we have the required formula

∃y⃗ ∃z⃗ [f_{σ}(a⃗, y⃗) = z⃗ ∧ \overline{β}_{m}(a⃗, y⃗, z⃗)].

This establishes Claim 2 and completes the proof.

We conclude with a problem which we state as a conjecture.

Conjecture 9.8 Suppose that M is an o-minimal expansion of (ℝ, ≤, +, ·). Then LIM is not Σ_{3} over M.

10 Conclusion

Given an ordered structure M, the quantifier level of a sentence θ of L(M)∪{F } over M is the lowest class in the hierarchies Δ_{1} ⊂ Π_{1} ⊂ B_{1} ⊂ Δ_{2} ⊂ Π_{2} … and Δ_{1} ⊂ Σ_{1} ⊂ B_{1} ⊂ Δ_{2} ⊂ Σ_{2} … which contains a sentence equivalent to θ in all structures (M, f). We investigate the quantifier levels of the Σ_{2} sentence BDD, which says that f is bounded, and the Π_{3} sentence LIM, which says that lim_{z→∞} f(z) = ∞, over a given ordered structure M. This work is motivated by Mostowski’s result that BDD is not Π_{2} and LIM is not Σ_{3} relative to the primitive recursive functions over the standard model of arithmetic, and Abraham Robinson’s result which characterizes BDD and LIM for standard functions by Π_{1} sentences in a language with an added predicate for the set of infinite elements.

We show that BDD and LIM can never be B_{1} over a structure M, but if M is an expansion of the real ordered field with a symbol for ℕ and each definable function, then BDD and LIM are at the lowest possible level Δ_{2} over M. We show that BDD is at its highest possible level, Σ_{2} but not Π_{2}, and that LIM is at its highest possible level, Π_{3} but not Σ_{3}, in the following cases: M is countable, M is the real ordering with an embedded structure on the natural numbers, and M is special of nice cardinality with an extra predicate for the infinite elements.

When M has universe ℝ, we obtain analogous results with the outer quantifiers replaced by countable disjunctions and conjunctions. In that case we show that BDD cannot be expressed by a countable conjunction of existential sentences, and LIM cannot be expressed by a countable disjunction of countable conjunctions of existential sentences.

The most interesting case is where M is an o-minimal expansion of the real ordered field. In that case we show that BDD is at the maximum level, and that LIM is not B_{2}. Moreover, BDD and LIM are not ⋀ Π_{2}, and LIM is not ⋁ B_{2}. We leave open the question of whether LIM is at its maximum level, not Σ_{3}, in that case.

References

[CK] C.C. Chang and H. Jerome Keisler. Model Theory, Third Edition. Elsevier 1990.

[VDD1] Lou van den Dries. o-minimal structures. pages 137-185 in: Logic: From Foundations to Applications. W. Hodges et al. eds. Oxford 1996.

[VDD2] Lou van den Dries. Tame Topology and o-minimal Structures. Cambridge University Press, 1998.

[FM] Harvey Friedman and Chris Miller. Expansions of o-minimal structures by fast sequences. Journal of Symbolic Logic 70:410–418, 2005.

[Kec] Alexander Kechris. Classical Descriptive Set Theory. Springer-Verlag 1995.

[Ke1] H. Jerome Keisler. Model Theory for Infinitary Logic. North-Holland 1971.

[Ke2] H. Jerome Keisler. Elementary Calculus. An Infinitesimal Approach. Second Edition, Prindle, Weber and Schmidt, 1986.

        Online Edition, http://www.math.wisc.edu/~keisler/, 2000.

[Kl] Stephen C. Kleene. Recursive predicates and quantifiers. Transactions of the American Mathematical Society 53:41–73. 1943.

[Mo1] Andrzej Mostowski. On definable sets of positive integers. Fundamenta Mathematicae 34:81–112. 1947.

[Mo2] Andrzej Mostowski. Examples of sets definable by means of two and three quantifiers. Fundamenta Mathematicae 42:259–270. 1955.

[Ro] Abraham Robinson. Non-standard Analysis. North-Holland 1966.

[Su] Kathleen Sullivan. The Teaching of Elementary Calculus: An Approach Using Infinitesimals. Ph. D. Thesis, University of Wisconsin, Madison, 1974.