Fields Institute Communications Volume 00, 0000

Some Remarks About Asymptotic Couples

Matthias Aschenbrenner

Department of Mathematics University of Illinois at Urbana-Champaign Urbana, IL 61801, U.S.A. Current address: Department of Mathematics University of California at Berkeley Berkeley, CA 94720, U.S.A.

                                maschenb@math.uiuc.edu

Abstract. Asymptotic couples (of H-type) try to capture the structure induced by the derivation of a Hardy field K on the value group of the natural valuation on K. In this note we continue the study of algebraic and model-theoretic aspects of asymptotic couples undertaken in [1]. We give a short exposition of some basic facts about asymptotic couples, and address a few topics left out in that paper: the (non-) minimality of the “closure” of an asymptotic couple of H-type, the Vapnik-Chernovenkis property for sets definable in closed asymptotic couples of H-type, and the relation of asymptotic couples of H-type to the “contraction groups” of [6].

Introduction

Let K be a Hardy field, that is (see [3], [17]), an ordered differential field of germs at +∞ of real-valued differentiable functions defined on intervals (a, +∞), with a ∈ ℝ. (So two such functions determine the same element of K if they coincide on an interval (b, +∞) on which they are both defined; we will use the same letter for a function and its germ.) Every element f of K is ultimately monotonic, so lim_{x→∞} f(x) exists as an element of ℝ ∪ {±∞}. The valuation

v: K^{×} = K \ {0} → V = v(K^{×})

associated to the place f ↦ lim_{x→∞} f(x) (where we identify +∞ and −∞) has the crucial property that v(f′) only depends on v(f), for f ∈ K^{×} with v(f) ≠ 0. (This is a consequence of L’Hospital’s Rule, see [17].) So we have a well-defined map ψ: V^{∗} = V \ {0} → V given by

ψ(v(f)) := v(f′/f) for any f ∈ K^{×} such that v(f) ≠ 0.
\begin{matrix}c \\ ◯ \end{matrix}0000 American Mathematical Society

1991 Mathematics Subject Classification. Primary 03C10, 06F20; Secondary 26A12, 12H05.

Key words and phrases. Asymptotic couples, Hardy fields.

The pair V = (V, ψ), called the asymptotic couple of K, is of key importance in understanding the interaction of the ordering and the derivation of K. It has the following fundamental properties: For all elements f, g ∈ K^{×} with a = v(f) ≠ 0, b = v(g) ≠ 0, (A1) ψ(ra) = ψ(a) for all r ∈ ℤ, r ≠ 0, (A2) ψ(a + b) ≥ min{ψ(a), ψ(b)}, where ψ(0) := ∞ > V, (A3) ψ(a) < ψ(b) + |b|. (See [14], Theorem 4.) Property (A2) expresses the fact that ψ is a valuation on the ordered abelian group V (taking values in V itself). In particular, it follows that for a, b as above, ψ(a + b) = min{ψ(a), ψ(b)} if ψ(a) ≠ ψ(b). Property (A3) may be seen as a valuation-theoretic formulation of L’Hospital’s Rule, see [15].

Moreover, the map ψ is decreasing on the set of positive elements of V: For all a, b ∈ V,

(H) 0 < a ≤ b ⟹ ψ(a) ≥ ψ(b). (Hence by (A1), ψ is increasing on the set of negative elements of V.) Note that if the Hardy field K contains the germ x of the identity function on ℝ, then ψ(1) = 1, where we put 1 := v(x^{−1}) > 0.

By an asymptotic couple, we mean a pair V = (V, ψ) consisting of an ordered abelian group V and a map ψ: V^{∗} → V satisfying (A1)–(A3) above, for all a, b ∈ V^{∗}. As in [2], we say that an asymptotic couple V = (V, ψ) is of H-type if (H) holds for all a, b ∈ V. We will sometimes also say “V is an H-asymptotic couple” instead of “V is an asymptotic couple of H-type.” Rosenlicht, in a series of papers ([14], [15], [16], [18]) studied in detail the asymptotic couples (V, ψ) where the ordered abelian group V has finite rank. The paper [1] contains an investigation of the basic model-theoretic properties of H-asymptotic couples. In this note, we want to supplement it by considering a few issues left open in that paper. Our hope is that insight into algebraic and model-theoretic properties of asymptotic couples will ultimately become useful in the recently initiated project of understanding the model theory of Hardy fields and the field of LE-series. (See [2], [5].)

In section 1, we first review some basic facts about asymptotic couples. We only give a few proofs, referring to [1] and [2] for a more detailed exposition. From results of [1], it follows that the theory of H-asymptotic couples has a model companion (in a natural language), the theory of “closed H-asymptotic couples.” (The definition of a closed H-asymptotic couple, as well as the statement of the main theorem from [1], can be found in section 2. See [12] for the notion “model companion”.) In particular, each H-asymptotic couple V can be embedded into a closed one. In section 3, we show that in general there is no closed H-asymptotic couple containing V minimally. Section 4 consists of a few remarks about another model-theoretic property of the class of closed H-asymptotic couples, called the independence property. Finally, in section 5 we discuss a connection to Kuhlmann’s “contraction groups” from [6].

In [1], we mainly worked in the setting of “H-couples”: these are H-asymptotic couples (V, ψ) of a certain kind, where V has additional structure as an ordered vector space over an ordered field. In Section 6 of that paper, we showed how to adapt the results about H-couples to the case of H-asymptotic couples. Here, we right away restrict our attention to H-asymptotic couples, for convenience. We don’t assume familiarity of the reader with [1]. In fact, sections 1–4 of the present note may serve as a quick overview of some of the results from that paper. However, we will freely use basic model-theoretic notions (see e.g. [12]).

Acknowledgements. The author would like to thank Lou van den Dries for numerous discussions around the topics of this paper, and Franz-Viktor Kuhlmann, Salma Kuhlmann, and Murray Marshall for organizing the Valuation Theory Conference 1999, where some of the results of this paper were first presented.

Notations. Throughout, m and n range over the set ℕ = {0, 1, 2, … } of natural numbers. Our notations concerning linearly ordered sets and ordered abelian groups are fairly standard. (If in doubt, see [1], §1.) If V is an ordered abelian group, we let V^{∗} = V \ {0}, and we put S^{>0} = {v ∈ S : v > 0}, S^{<0} = {v ∈ S : v < 0}, for a subset S of V. We define an equivalence relation ∼ on V by

v ∼ w :⟺ |v| ≤ m|w| and |w| ≤ n|v| for some m, n > 0.

The equivalence class of an element v ∈ V is written as [v], and is called its archimedean class. By [V] we denote the set of archimedean classes of V, and we set [V^{∗}] := [V] \ {[0]}. We linearly order [V] by setting

[v] < [w] :⟺ n|v| < |w| for all n
⟺ [v] ≠ [w] and |v| < |w|.

Some simple facts about archimedean classes: For v, w ∈ V, r ∈ ℤ \ {0}, we have 1. [v] = {0} ⟺ v = 0,

2. [v] = [rv],
3. [v + w] ≤ max{[v], [w]}, with [v + w] = max{[v], [w]}, if [v] ≠ [w].

If V′ is an ordered abelian group containing V as ordered subgroup, the inclusion map V ↪ V′ induces an embedding [V] → [V′] of linearly ordered sets. We identify [V] with its image under this embedding.

We consider V as a subgroup of the divisible abelian group ℚV = ℚ ⊗_{ℤ} V by means of the embedding v ↦ 1 ⊗ v. We equip ℚV with the unique linear ordering extending the one on V and making ℚV into an ordered abelian group. Note that [ℚV] = [V]. We consider a divisible ordered abelian group as an ordered vector space over the ordered field ℚ as usual.

1 Basic Properties

In this section, V = (V, ψ) is an asymptotic couple. We set Ψ := ψ(V^{∗}), and with id denoting the identity function on V, we let

(id +ψ)(V^{∗}) = {x + ψ(x) : x ∈ V^{∗}}.

Similarly, we define (id +ψ)(V^{>0}) and (id +ψ)(V^{<0}). Also, let V_{∞} := V ∪ {∞}, with ∞ > v for all v ∈ V and v + ∞ = ∞ + v = −∞ = ∞ for all v ∈ V_{∞}. It is convenient to extend ψ to a map V_{∞} → V_{∞} by ψ(0) := ψ(∞) := ∞.

Remark For a ∈ V we define ψ + a: V^{∗} → V by (ψ + a)(x) := ψ(x) + a. Then clearly (V, ψ + a) is also an asymptotic couple, with (ψ + a)(V^{∗}) = Ψ + a. Also, (V, ψ) satisfies (H) if and only if (V, ψ + a) does.

For the next proposition, see also [1], §3, and [2], Proposition 2.3. Part (2.) is Theorem 5 in [15]; we give here a much shorter proof.

Proposition 1.1 Let v, w ∈ V.

1. If v, w ≠ 0, then n(ψ(w) − ψ(v)) < |v|.

2. If v, w, v − w ≠ 0, then [ψ(v) − ψ(w)] < [v − w].

3. The map x ↦ x + ψ(x): V^{∗} → V is strictly increasing.

Proof For (1.), let v, w ∈ V^{∗}, n ∈ ℕ. We may assume ψ(w) > ψ(v), v, w > 0, and n > 0. By passing from ψ to ψ − ψ(v), if necessary, we can reduce to the case that ψ(v) = 0 < ψ(w). We then have to show nψ(w) < v. We proceed by induction on n. In the case n = 1, nψ(w) = ψ(w) < v + ψ(v) = v holds by axiom (A3) for asymptotic couples. Now assume that nψ(w) < v. If (n + 1)ψ(w) ≤ ψ(u) for some u ∈ V^{∗}, we clearly have (n + 1)ψ(w) ≤ ψ(u) < v + ψ(v) = v, by axiom (A3) again. So we can assume that (n + 1)ψ(w) > Ψ. Note that ψ^{2}(w) > 0, since ψ(w) > 0, so ψ(w) < ψ(w) + ψ(ψ(w)). Hence

ψ(v − (n + 1)ψ(w)) = min{ψ(v), ψ^{2}(w)} = ψ(v) = 0,

by (A2), so we get

Ψ < |v − (n + 1)ψ(w)| + ψ(v − (n + 1)ψ(w)) = |v − (n + 1)ψ(w)|.

Suppose v ≤ (n + 1)ψ(w). Then, in particular, ψ(w) < (n + 1)ψ(w) − v, hence v < nψ(w), contradicting the induction hypothesis. Therefore (n + 1)ψ(w) < v, completing the induction step.— For (2.), let v, w ≠ 0 with d := v − w ≠ 0. We have to show n|ψ(v) − ψ(w)| < |d| for all n. If ψ(d) > ψ(w), then ψ(v) = ψ(w), since ψ is a valuation on the ordered abelian group V. Suppose ψ(d) ≤ ψ(w). Then we have ψ(d) ≤ ψ(v), hence by (1.):

nψ(d) ≤ nψ(w) < nψ(d) + |d|, nψ(d) ≤ nψ(v) < nψ(d) + |d|.

Thus n|ψ(v) − ψ(w)| < |d| in all cases.— Property (3.) follows easily from (2.).

By (A1) and part (1.) of the proposition above, ψ extends uniquely to a map (ℚV)^{∗} → V, also denoted by ψ, such that (ℚV, ψ) is an asymptotic couple. Note that ψ((ℚV)^{∗}) = Ψ.

Some properties of H-asymptotic couples. From now on, we want to concentrate on H-asymptotic couples. So suppose that V = (V, ψ) is of H-type. Note that by axioms (A1) and (H), we have

[v] ≤ [w] ⟹ ψ(v) ≥ ψ(w)  for all v, w ∈ V^{∗}.  (1.1)

In particular, ψ is constant on archimedean classes of V, i.e., for all v, w ∈ V with [v] = [w], we have ψ(v) = ψ(w). The argument used for making ℚV into an asymptotic couple extending (V, ψ) may be generalized, using (1.1), to show:

Corollary 1.2 Let V′ be an ordered abelian group containing V as ordered subgroup such that [V] = [V′]. Then there is a unique extension of ψ to a function ψ′: (V′)^{∗} → V′ such that (V′, ψ′) is an H-asymptotic couple.

Lemma 1.3 Let w ∈ V^{∗}. If [ψ(w)] ≥ [w], then [ψ(ψ(w))] = [ψ(w)].

Proof By (1.1), we may suppose that [ψ(w)] > [w]. By Proposition 1.1, (2.), and property (3.) of archimedean classes listed in the introduction, we have [ψ(w) − ψ(ψ(w))] < [w − ψ(w)] = [ψ(w)] and hence [ψ(ψ(w))] = [ψ(w)].

Remark The lemma and (1.1) imply that if w ∈ V^{∗} satisfies [w] ≤ [ψ(w)], then y + ψ(y) = 0 for y = −ψ(w) or y = −ψ(ψ(w)).

The following facts about id +ψ are fundamental (see also [1], Section 3):

Corollary 1.4 The set (id +ψ)(V^{>0}) is closed upward. The set (id +ψ)(V^{<0}) is closed downward, and

(− id +ψ)(V^{>0}) = (id +ψ)(V^{<0}) = {a ∈ V : a < ψ(x) for some x ∈ V^{∗}}. (1.2)

There is at most one element v ∈ V such that Ψ < v < (id +ψ)(V^{>0}). If Ψ has a largest element, then there is no v ∈ V with Ψ < v < (id +ψ)(V^{>0}).

Proof Let a > x + ψ(x) for some x > 0; we want to show a ∈ (id +ψ)(V^{>0}). Passing from (V, ψ) to (V, ψ − a) if necessary, we reduce to the case a = 0. Then [x] ≤ [ψ(x)], hence a = 0 ∈ (id +ψ)(V^{>0}) by the previous remark and Proposition 1.1, (3.). So (id +ψ)(V^{>0}) is closed upward, and similarly one shows that (id +ψ)(V^{<0}) is closed downward.

The equalities in (1.2) are clear except for the inclusion “⊇” in the last equation. For this, let a, x ∈ V, x < 0, with a < ψ(x); we want to show that a ∈ (id +ψ)(V^{<0}). As above, we may assume that a = 0. If [x] ≤ [ψ(x)], it follows as before that 0 ∈ (id +ψ)(V^{<0}). If [ψ(x)] < [x], then 0 < x + ψ(x), hence 0 ∈ (id +ψ)(V^{<0}), since (id +ψ)(V^{<0}) is closed downward.

If u, v ∈ V satisfy ψ(w) ≤ u < v < w + ψ(w) for all w ∈ V^{>0}, then v < (v − u) + ψ(v − u) ≤ (v − u) + u = v, a contradiction. This shows the rest.

As a consequence of the last corollary, V \(id +ψ)(V^{∗}) has at most one element, and (id +ψ)(V^{∗}) ≠ V if and only if Ψ has a supremum in V, and in this case V \ (id +ψ)(V^{∗}) = {sup Ψ}. We refer the reader to [1], Figure 1, for a picture of the behavior of the maps ψ and id +ψ on V^{∗}.

2 Closed H-Asymptotic Couples

A cut of an H-asymptotic couple (V, ψ) is a set P ⊆ V which is closed downward, contains Ψ, and is disjoint from (id +ψ)(V^{>0}). (So P < (id +ψ)(V^{>0}).) By Corollary 1.4, an H-asymptotic couple (V, ψ) has at most two cuts, and it has two cuts if and only if Ψ < v < (id +ψ)(V^{>0}) for some v ∈ V. If Ψ has a maximum, then (V, ψ) has exactly one cut P = {a ∈ V : a ≤ ψ(x) for some x ∈ V^{∗}}.

Definition 2.1 An H-asymptotic couple V = (V, ψ) is closed if

1. V is divisible (as an abelian group),

2. (id +ψ)(V^{∗}) = V, and

3. Ψ = (id +ψ)(V^{<0}). (In this case, P = Ψ is the only cut of V.)

Example 1 Let K be a Hardy field containing ℝ and closed under exponentiation (that is, f ∈ K ⇒ exp f ∈ K) and integration (i.e. f ∈ K ⇒ ∃g ∈ K : g′ = f). Then the asymptotic couple of K (as defined in the introduction) is a closed Hasymptotic couple.

In [1], Definition 6.2, we also introduced the following notion, under the somewhat technical name “H_{0}-triple”:

Definition 2.2 An asymptotic triple of H-type, or H-asymptotic triple for short, is a triple (V, ψ, P), where (V, ψ) is an H-asymptotic couple and P a cut of (V, ψ), such that

1. V is divisible, and 2. there exists a positive element 1 of V with ψ(1) = 1. (Equivalently, 0 ∈

(id +ψ)(V^{<0}).)

By Proposition 1.1, (2.), the element 1 in (2.) is uniquely determined. If (V, ψ, P) is an H-asymptotic triple such that (V, ψ) is a closed H-asymptotic couple, then P = Ψ, and (V, ψ, Ψ) is called a closed H-asymptotic triple.

We can naturally consider asymptotic couples (V, ψ) as model-theoretic structures (V_{∞}, ψ) in the first-order language L = {0, +, −, ψ, ∞}. The H-asymptotic couples are then the models of a universal theory in L. Similarly, when dealing with H-asymptotic triples (V, ψ, P) as model-theoretic objects, we construe them as L_{P} -structures (V_{∞}, ψ, 1, P), where L_{P} is the extension of L by

1. a constant symbol 1 for the distinguished element 1 ∈ V^{>0} with ψ(1) = 1,

2. a unary predicate symbol for P, and

3. unary function symbols δ_{n} for each n > 0, to be interpreted on V as the scalar multiplication by 1/n (and δ_{n}(∞) := ∞).

The H-asymptotic triples are models of a universal theory in L_{P}. Let T be the theory of closed H-asymptotic couples, in the language L, and let T_{P} be the theory of closed H-asymptotic triples, in the language L_{P}. One of the main results from [1] (Corollary 6.2) is:

Theorem 2.3 The theory T_{P} is complete, decidable, and has elimination of quantifiers. It is the model completion of the theory of H-asymptotic triples.

From this we get immediately:

Corollary 2.4 The theory T is the model companion of the theory of Hasymptotic couples.

Remark The division symbols δ_{n} are included in the language L_{P} in order to guarantee quantifier elimination for T_{P}. Here is an instructive example to show that if we omit them, then in the resulting smaller language the theory of closed H-asymptotic triples would not eliminate quantifiers.

Let (W, ψ) be a closed H-asymptotic couple. Choose an element b ∉ W in an ordered vector space W′ := W ⊕ ℚb over ℚ extending W, such that Ψ < \frac{b}{2} < (id +ψ)(W^{>0}). Then, by Lemma 4.5 in [1], [W] = [W′], hence ψ extends uniquely to a map ψ′: (W′)^{∗} → W such that W′ = (W′, ψ′) is an H-asymptotic couple (Corollary 1.2). Note that [W] = [W′] implies

Ψ′ = Ψ < \frac{b}{2} < (id +ψ′)((W′)^{>0}).

Hence (W′, ψ′) has two cuts. Now consider the ordered abelian group V := W ⊕ ℤb ⊆ W′. Since Ψ′ = Ψ ⊆ W, (V, ψ′|V^{∗}) is an H-asymptotic couple with (V, ψ′|V^{∗}) ⊆ (W′, ψ′). One checks easily that the two distinct cuts of (W′, ψ′) have the same intersection with V, namely {v ∈ V : v ≤ ψ(w) for some w ∈ W }.

3 Non-Minimality of Closures

According to Theorem 2.3, every H-asymptotic triple can be embedded into a closed H-asymptotic triple. In fact, in the course of the proof of this theorem, we showed a more precise statement:

Proposition 3.1 Every H-asymptotic triple V = (V, ψ, P) has a closure, that is, a closed H-asymptotic triple V^{c} = (V^{c}, ψ^{c}, P^{c}) extending V, such that any embedding V → V′ into a closed H-asymptotic triple V′ extends to an embedding V^{c} → V′. Any two closures of V are isomorphic over V.

(See [1], Corollaries 5.3 and 6.1.) A natural question is if the closure V^{c} of an H-asymptotic triple V is always minimal over V, i.e. there exists no closed Hasymptotic triple W ⊇ V strictly contained in V^{c} as an L_{P} -substructure. This turns out to be false, in a very strong way:

Proposition 3.2 Let V = (V, ψ, P) be an H-asymptotic triple which is not closed. Then the closure V^{c} of V is not minimal over V.

(This is similar, e.g., to the situation encountered with differential fields and differential closures, [13].)

Before we give a proof of Proposition 3.2, we outline how V^{c} is constructed from V. One first shows the following embedding statements (see [1], Lemmas 3.5, 3.6 and 3.7 for a proof):

Lemma 3.3 Let V = (V, ψ, P) be an H-asymptotic triple.

1. Suppose P has a largest element, and let V^{ε} := V ⊕ ℚε be an extension of the ℚ-vector space V. Then there exists a unique linear ordering of V^{ε}, a unique map ψ^{ε}: (V^{ε})^{∗} → V^{ε}, and a unique subset P^{ε} of V^{ε} such that (V^{ε}, ψ^{ε}, P^{ε}) is an H-asymptotic triple extending (V, ψ, P) with ε > 0 and max P = −ε + ψ^{ε}(ε).

2. Suppose there exists b ∈ V with P < b < (id +ψ)(V^{>0}). Let V^{ε} := V ⊕ ℚε be an extension of the ℚ-vector space V. Then there exists a unique linear ordering of V^{ε}, a unique map ψ^{ε}: (V^{ε})^{∗} → V^{ε}, and a unique subset P^{ε} ⊆ V^{ε} such that (V^{ε}, ψ^{ε}, P^{ε}) is an H-asymptotic triple extending (V, ψ, P) with ε > 0 and b = ε + ψ^{ε}(ε).

3. Suppose b ∈ P \Ψ. Let V^{a} := V ⊕ℚa be an extension of the ℚ-vector space V. There exists a unique linear ordering of V^{a}, a unique map ψ^{a}: (V^{a})^{∗} → V^{a}, and a unique P^{a} ⊆ V^{a}, such that (V^{a}, ψ^{a}, P^{a}) is an H-asymptotic triple extending (V, ψ, P) with a > 0 and ψ^{a}(a) = b.

Note that (V^{ε}, ψ^{ε}) as in (1.) or (2.) of the lemma has the property that ψ^{ε}((V^{ε})^{∗}) has a maximum. So part (1.) applies to (V^{ε}, ψ^{ε}, P^{ε}) in place of (V, ψ, P). Also, if (id +ψ)(V^{∗}) = V, then (id +ψ^{a})((V^{a})^{∗}) = V^{a}. Therefore, iterating (1.)–(3.), if necessary transfinitely often, we can obtain an increasing chain of H-asymptotic triples extending (V, ψ, P) whose union is a closure of (V, ψ, P).

Proof of Proposition 3.2. Let V = (V, ψ, P) be an H-asymptotic triple which is not closed. We have to find a closed H-asymptotic triple W with V ⊆ W which is strictly contained (as a substructure) in a closure of V. Let us first consider a special case:

Lemma 3.4 Suppose that P does not have a supremum in V, and P \ Ψ contains a strictly increasing sequence (a_{n})_{n∈ℕ}. Then the closure of V is not minimal over V.

Proof Using Lemma 3.3, (3.), we construct a strictly increasing sequence of H-asymptotic triples (V_{n})_{n∈ℕ} such that

1. V_{0} = V = (V, ψ, P),

2. V_{n+1} = V_{n} ⊕ ℚv_{n}, ψ_{n+1}(v_{n}) = a_{n}, for all n.

We let

V_{ω} := V ⊕ ⨁_{n∈ℕ} ℚv_{n} = ⋃_{n<ω} V_{n}, P_{ω} := ⋃_{n<ω} P_{n},

and ψ_{ω} the common extension of all ψ_{n} to V_{ω}. Now construct another strictly increasing sequence of H-asymptotic triples (V′_{n})_{n∈ℕ}, contained in the H-asymptotic triple V_{ω} = (V_{ω}, ψ_{ω}, P_{ω}), with the following properties:

1. V′_{0} = V,
2. V′_{n+1} = V′_{n} ⊕ ℚv′_{n} with v′_{n} := v_{n} + v_{n+1}, ψ′_{n+1}(v′_{n}) = a_{n}, for all n.

Note that [V_{n}] = [V′_{n}] for all n < ω. Again we let

V′_{ω} := ⋃_{n<ω} V′_{n} ⊆ V_{ω}, P′_{ω} := P_{ω} ∩ V′_{ω},

and ψ′_{ω} the common extension of all ψ′_{n} to V′_{ω}. Then V′_{ω} = (V′_{ω}, ψ′_{ω}, P′_{ω}) is an asymptotic couple such that V ⊆ V′_{ω} ⊆ V_{ω}, [V′_{ω}] = [V_{ω}], and one easily verifies that v_{n} ∉ V′_{ω} for all n. Fix a closure V^{c} = (V^{c}, ψ^{c}, P^{c}) of V_{ω}. (So V^{c} is also a closure of V.) Now using Lemma 3.3, (3.) repeatedly again, starting from V′_{ω}, we obtain a strictly increasing sequence (V′_{α})_{ω≤α<μ} of H-asymptotic triples (for some ordinal μ) such that

1. V′_{ω} ⊆ V′_{α} ⊆ V^{c} for all α < μ,

2. V′_{α+1} = V′_{α} ⊕ ℚv′_{α} with ψ′_{α+1}(v′_{α}) ∈ P′_{α} \ ψ′_{α}((V′_{α})^{∗}) for all α < α + 1 < μ,

3. V′_{λ} = ⋃_{α<λ} V′_{α} for all limit ordinals λ < μ, and
4. (V′)^{c} := ⋃_{α<λ} V′_{α} is closed.

So (V′)^{c} is a closure of V′_{ω}, and hence a closure of V, contained in the closure V^{c} of V. One verifies easily that v_{n} ∉ (V′)^{c} for all n. Hence V^{c} is not minimal over V, as claimed.

We now turn to the general case. Since V is assumed to be non-closed, one of the parts of Lemma 3.3 is applicable. The following three possibilities arise:

Case 1: The cut P has a maximum. Let (V^{ε}, ψ^{ε}, P^{ε}) be as in Lemma 3.3, (1.); then P^{ε} \ Ψ^{ε} is the union of P \ Ψ and the set

{v + λε : v ∈ V, λ ∈ ℚ^{×}, and v < max P or v = max P & λ < 1}.

Hence P^{ε} \ Ψ^{ε} certainly contains a strictly increasing sequence (a_{n})_{n∈ℕ}. If (V′, ψ′, P′) is obtained from (V^{ε}, ψ^{ε}, P^{ε}) by ω many applications of Lemma 3.3, (1.), then P′ \ Ψ′ also contains the sequence (a_{n}), and P′ does not have a supremum in V′.

Case 2: We have P < b < (id +ψ)(V^{>0}) for some (uniquely determined) element b ∈ V. Then we let (V^{ε}, ψ^{ε}, P^{ε}) be as in Lemma 3.3, (2.). The set P^{ε} \ Ψ^{ε} is the union of P \ Ψ and

{v + λε : v ∈ V, λ ∈ ℚ^{×}, and v < b or v = b & λ < −1},

so contains a strictly increasing sequence (a_{n}). If (V′, ψ′, P′) ⊇ (V^{ε}, ψ^{ε}, P^{ε}) is obtained from (V^{ε}, ψ^{ε}, P^{ε}) by ω many applications of Lemma 3.3, (1.), then P′ \ Ψ′ also contains the sequence (a_{n}), and P′ does not have a supremum in V′.

Case 3: The cut P does not have a supremum in V, and there exists b ∈ P \Ψ. Let (V^{a}, ψ^{a}, P^{a}) be as in Lemma 3.3, (2.). Then one readily verifies (see proof of Lemma 3.7 in [1]) that P^{a} \ Ψ^{a} equals the union of P \ (Ψ ∪ {b}) and

{v + λa : v ∈ V, λ ∈ ℚ^{×}, λ > 0, b − v > a or λ < 0, v − b < a}.

In particular, P^{a} \ Ψ^{a} contains a strictly increasing sequence (a_{n}). Hence in all three situations, we can reduce to the special case treated in the lemma, and thus finish the proof of the proposition.

4 The Independence Property for Closed H-Asymptotic Couples

Let L be a language (in the sense of first-order logic) and φ(x, y) an L-formula, where x = (x_{1}, …, x_{m}) and y = (y_{1}, …, y_{n}). We say that the formula φ(x, y) has the independence property with respect to an L-structure A = (A, …) if for every k ∈ ℕ there is a sequence (a_{1}, …, a_{k}) of elements of A^{m} such that for all subsets I of {1, …, k}, there exists b_{I} ∈ A^{n} with

A ⊧ φ(a_{i}, b_{I}) ⟺ i ∈ I,

for all i = 1, …, k. A theory T in the language L is said to have the independence property if all formulas φ(x, y) as above have the independence property with respect to all A ⊧ T. A theory T not having the independence property signifies a certain well-behavedness of T, on a model-theoretic level: in this case, T shares many properties with stable theories (see [12]). There is an intriguing connection between the independence property and the notion of a Vapnik-Chernovenkis (VC) class from probability theory: A collection C of subsets of a set X is called a VC class if f_{C}(n) < 2^{n} for some n, where

f_{C}(n) := max{|C ∩ F | : F is an n-element subset of X}.

(In this case, f_{C}: ℕ → ℕ is in fact of polynomial growth; see [4], Chapter 5, for this and some other properties of VC classes.) Laskowski [9] proved that a formula φ(x, y) does not have the independence property with respect to A if and only if the collection C_{φ} = {φ^{A}(a, y) : a ∈ A^{m}}, where φ^{A}(a, y) := {b ∈ A^{n} : A ⊧ φ(a, b)}, is a VC class.

Suppose now that L contains a binary relation symbol <, and that T is a complete theory with quantifier elimination, all of whose models A = (A, <, …) are expansions of a dense linear ordering (A, <) without endpoints. A cut in (A, <) is a downward closed subset C ⊆ A. The following is a special case of a criterion due to Poizat [11]:

Lemma 4.1 The theory T does not have the independence property if for all models A and B of T with A ⪯ B and all cuts C of A, there exist at most 2^{|A|} simple extensions A ⊆ A⟨c⟩ ⊆ B with C < c < A \ C, up to isomorphism over A.

In [1], §6, we proved that given closed H-asymptotic triples (V, ψ, P) ⊆ (V′, ψ′, P′) and a cut C in V, there exist at most two simple extensions of (V, ψ, P) inside (V′, ψ′, P′) with generator c ∈ V′ such that C < c < V \C, up to isomorphism over V. This implies:

Corollary 4.2 The theory T_{P} of closed H-asymptotic triples does not have the independence property. (Hence the theory T of closed H-asymptotic couples also does not have the independence property.)

In fact, in [1] (Proposition 6.2) we showed something more: the theory T_{P} is weakly o-minimal, that is, for every closed H-asymptotic triple V = (V, ψ, P), every L_{P} -formula φ(x, y) with x = (x_{1}, …, x_{m}) and a single variable y, and every v ∈ V^{m}, the set φ^{V}(v, y) is a boolean combination of cuts in (V, <). This also implies the corollary above, by Proposition 7.3 in [10]. We want to remark that the argument indicated here also works in the two-sorted setting of “closed H-triples” as defined in [1], thus giving a natural example of a locally o-minimal (but not weakly o-minimal) theory without the independence property. (See [1], Proposition 5.1 for the definition of “locally o-minimal” and a proof of the local o-minimality of the theory of closed H-triples.) Unlike in the weakly o-minimal case, it seems not to be known whether every locally o-minimal theory extending the theory of dense linear orders does not have the independence property.

5 Relation to Contraction Groups

Our couples resemble the contraction groups of Kuhlmann [6], [7], and there is indeed a formal connection as indicated below. (A difference is that contraction groups have nothing like our cut P.)

Contraction groups arise as follows: let K be a Hardy field closed under taking logarithms (i.e. f ∈ K^{>0} ⇒ log f ∈ K), with its valuation v: K^{×} → V = v(K^{×}). The logarithm map then induces a so-called contraction map χ: V^{<0} → V^{<0} by

χ(v(f)) := v(log f) for all f ∈ K^{>0} with v(f) < 0,

which we extend to a map V → V by requiring χ(−y) = −χ(y). If K is also closed under exponentiation, then V is divisible, and χ is surjective (χ(V) = V). This means that the pair (V, χ) (ordered group with contraction map) is a divisible centripetal contraction group, as axiomatized in [6], where it was shown that the elementary theory of non-trivial divisible centripetal contraction groups is complete and has quantifier elimination in its natural language. (See the appendix of [8] for an exposition of these results.)

In the example above, we have for f ∈ K^{>0}, with y = v(f) < 0:

ψ(y) = v((log f)′) = v((log f)′/ log f) + v(log f) = ψ(χ(y)) + χ(y)

Let now (V, ψ) be any closed H-asymptotic couple. For y < 0 in V, let χ(y) = z be the unique solution in V^{∗} of the equation

z + ψ(z) = ψ(y).  (5.1)

For y > 0, set χ(y) := −χ(−y), and χ(0) := 0. It is easily seen that then (V, χ) is a non-trivial divisible centripetal contraction group; clearly χ is definable (without parameters) in (V, ψ). Hence in particular, (V, χ) is weakly o-minimal, by Proposition 6.2 in [1]. We want to point out that the weak o-minimality of the theory of non-trivial divisible centripetal contraction groups (proved in [7]; see also [8], Theorem A.34) is a consequence of its completeness and the preceding observation: any model of this theory can be elementarily embedded into one of the form (V, χ) with χ definable in a closed H-asymptotic couple (V, ψ) (by choosing (V, ψ) sufficiently saturated), and hence is weakly o-minimal. (As the theory of closed H-asymptotic couples, the theory of non-trivial divisible centripetal contraction groups does not have the Steinitz exchange property for the definable closure operation.)

However, we cannot definably reconstruct ψ in (V, χ):

Proposition 5.1 In no divisible centripetal contraction group (V, χ) can one define, even allowing parameters, a function ψ: V^{∗} → V such that (V, ψ) is a closed H-asymptotic couple and χ + ψ ∘ χ = ψ on V^{<0}.

Before we can prove this we need some preparations. We let (V, ψ) denote a closed H-asymptotic couple. We also assume that 0 ∈ Ψ, so there exists 1 ∈ V^{∗} such that ψ(1) = 1 > 0.

Iterates of ψ. For n > 0, let ψ^{n}: V_{∞} → V_{∞} be the n-fold functional composition ψ ∘ ψ ∘ ⋯ ∘ ψ. Put

D_{n} := {v ∈ V : ψ^{n}(v) ≠ ∞}.

For example D_{1} = V^{∗}, D_{2} = V^{∗} \ ψ^{−1}(0), etc. By induction on n one shows easily that ψ^{n}(D_{n}) = Ψ.

Lemma 5.2 Let v ∈ V^{∗} and n > 0 such that ψ^{n}(v) < 0. Then ψ^{i}(v) < 0 for all i = 1, …, n, and

[ψ^{n}(v)] < [ψ^{n−1}(v)] < ⋯ < [ψ(v)] < [v].

Proof For n = 1, note that [v] ≤ [ψ(v)] and (1.1) imply ψ(v) ≥ ψ(ψ(v)), hence −ψ(v) + ψ(−ψ(v)) ≤ 0 < (id +ψ)(V^{>0}). Thus ψ(v) > 0, a contradiction.

Assume inductively that the lemma holds for a certain n > 0. Let v ∈ D_{n+1} with ψ^{n+1}(v) < 0. Applying the case n = 1 to ψ^{n}(v) instead of v gives [ψ^{n+1}(v)] < [ψ^{n}(v)]. By the inductive assumption the remaining inequalities will follow from ψ^{n}(v) < 0. Suppose ψ^{n}(v) ≥ 0. Then ψ^{n}(v) ∈ Ψ^{>0}, thus [ψ^{n}(v)] ≤ [1] by (A3). Hence 0 > ψ^{n+1}(v) ≥ ψ(1) = 1 by (1.1), a contradiction.

Let D_{∞} := ⋂_{n>0} D_{n} and

V_{inf} := {v ∈ D_{∞} : ψ^{n}(v) < 0 for all n > 0},
V_{fin} := V \ V_{inf}.

Note that [v_{0}] < [v] for all v ∈ V_{inf}, and that V_{inf} ∩ V^{>0} is closed upward and V_{inf} ∩ V^{<0} is closed downward.

Remark The previous lemma, together with ψ^{n}(D_{n}) = Ψ, implies that for all n > 0, we can find an element v ∈ D_{n} such that all iterates

ψ(v), ψ^{2}(v), …, ψ^{n}(v)

are negative. Hence if (V, ψ) is ℵ_{0}-saturated, then V_{inf} ≠ ∅.

The proof of the next lemma is easy and left to the reader.

Lemma 5.3 V_{fin} is a convex subspace of V, and (V_{fin}, ψ|V_{fin}^{∗}) is a closed Hasymptotic couple. Moreover, ψ(V_{inf}) = V_{inf} ∩ V^{<0}.

Let χ be the contraction map defined by ψ(v) = χ(v) + ψ(χ(v)) for all v < 0.

Lemma 5.4 Let v ∈ V^{<0} and ψ^{3}(v) < 0. Then χ(v) = ψ(v) − ψ^{2}(v).
Proof We have [v] > [ψ(v)], so ψ(v) − ψ^{2}(v) < 0. We compute:
(ψ(v) − ψ^{2}(v)) + ψ(ψ(v) − ψ^{2}(v)) = (ψ(v) − ψ^{2}(v)) + ψ^{2}(v) = ψ(v).

By the defining equation (5.1) of χ, it follows that χ(v) = ψ(v) − ψ^{2}(v).

Proof of Proposition 5.1. Suppose (V, ψ) is a closed H-asymptotic couple such that we can define ψ in (V, χ). We may assume that (V, ψ) is ℵ_{0}-saturated. For ease of notation we shall also assume that ψ is actually defined without parameters in (V, χ). (In the general case the role of V_{fin} below is taken over by the convex hull in V of a closure inside (V, ψ) of the substructure of (V, ψ) generated by the finitely many parameters used to define ψ.) If 0 ∈ (id +ψ)(V^{<0}), then (V, ψ, Ψ) is a closed H-asymptotic triple. Otherwise, we let 1 ∈ V^{>0} be the unique solution to the equation x+ψ(x) = 0, and pass from (V, ψ) to (V, ψ_{0}), where ψ_{0} := ψ+1−ψ(1), so that ψ_{0}(1) = 1 > 0. We see that we may in fact assume that (V, ψ, Ψ) is a closed H-asymptotic triple, with a distinguished positive element 1.

We now modify ψ to a function ψ̃: V^{∗} → V by putting

ψ̃(v) := \begin{cases}ψ(v), & if v ∈ V_{fin}^{∗} \\ ψ(v) + 1, & if v ∈ V_{inf}. \end{cases}

Then (V, ψ̃) is still an H-asymptotic couple, and ψ̃(V_{inf}) = ψ(V_{inf}), as is easily checked. Thus Ψ = ψ̃(V^{∗}), so (V, ψ̃) is even a closed H-asymptotic couple. Let χ̃ be the contraction map associated to (V, ψ̃). By completeness of the theory of closed H-asymptotic triples, the same formula that defines ψ in (V, χ) will define ψ̃ in (V, χ̃). By Lemma 5.4, χ = χ̃, hence ψ = ψ̃, contradiction.

References

1. M. Aschenbrenner, L. van den Dries, Closed asymptotic couples, J. Algebra 225 (2000), 309– 358.

2. , H-fields and their Liouville extensions, Math. Z. 242 (2002), 543–588.

3. N. Bourbaki, Fonctions d’une Variable Réelle, Chapitre V, Appendice Corps de Hardy. Fonctions (H ), Hermann, Paris (1976).

4. L. van den Dries, Tame Topology and O-Minimal Structures, London Mathematical Society Lecture Note Series 248, Cambridge University Press, Cambridge (1998).

5. L. van den Dries, D. Marker, A. Macintyre, Logarithmic-exponential series, Ann. Pure Appl. Logic 111 (2001), 61–113.

6. F.-V. Kuhlmann, Abelian groups with contractions, I, Contemp. Math. 171 (1994), 217–241.

7. , Abelian groups with contractions, II: Weak o-minimality, in: A. Facchini, C. Menini (eds.): Abelian Groups and Modules, Kluwer, Dordrecht (1995), 323–342.

8. S. Kuhlmann, Ordered Exponential Fields, Fields Institute Monographs 12, American Mathematical Society, Providence, RI (2000).

9. M. C. Laskowski, Vapnik-Chernovenkis classes of definable sets, J. London Math. Soc. (2) 45 (1992), 377–384.

10. D. Macpherson, D. Marker, C. Steinhorn, Weakly o-minimal structures and real closed fields, Trans. Amer. Math. Soc. 352 (2000), 5435–5483 (electronic).

11. B. Poizat, Théories instables, J. Symbolic Logic 46 (1981), 513–522.

12. , Cours de Théorie des Modèles, Nur al-Mantiq wal-Ma’rifah, Lyon (1985).

13. M. Rosenlicht, The nonminimality of the differential closure, Pacific J. Math. 52 (1974), 529–537.

14. , On the value group of a differential valuation, Amer. J. Math. 101 (1979), 258–266.

15. , Differential valuations, Pacific J. Math. 86 (1980), 301–319.

16. , On the value group of a differential valuation, II, Amer. J. Math. 103 (1981), 977– 996.

17. , Hardy fields, J. Math. Analysis and Appl. 93 (1983), 297–311.

18. , The rank of a Hardy field, Trans. Amer. Math. Soc. 280 (1983), 659–671.