EXTENSIONS OF ORDERED THEORIES BY GENERIC PREDICATES

ALFRED DOLICH, CHRIS MILLER, AND CHARLES STEINHORN

1. Introduction

Given a theory T extending that of dense linear orders without endpoints (DLO), in a language ℒ ⊇ {<}, we are interested in extensions T′ of T in languages extending ℒ by unary relation symbols that are each interpreted in models of T′ as sets that are both dense and codense in the underlying sets of the models.

There is a canonically “wild” example, namely, T = Th(⟨ℝ, <, +, ·⟩) and T′ = Th(⟨ℝ, <, +, ·, ℚ⟩). Recall that T is o-minimal, and so every open set definable in any model of T has only finitely many definably connected components. But it is well known that ⟨ℝ, <, +, ·, ℚ⟩, defines every real Borel set, in particular, every open subset of any finite cartesian power of ℝ and every subset of any finite cartesian power of ℚ. To put this another way, the definable open sets in models of T are essentially as simple as possible, while T′ has a model where the definable open sets are as complicated as possible, as is the structure induced on the new predicate.

In contrast to the preceding example, if ℝ_{alg} is the set of real algebraic numbers and T′ = Th(⟨ℝ, <, +, ·, ℝ_{alg}⟩), then no model of T′ defines any open set (of any arity) that is not definable in the underlying model of T. More generally, if 𝔅 is an o-minimal expansion of a densely ordered group and A is the underlying set of a dense elementary substructure of 𝔅, then Th(⟨𝔅, A⟩) is rather well behaved with respect to Th(𝔅), in particular, every open set definable in ⟨𝔅, A⟩ is definable in 𝔅; see [6, Section 5] for details. There is an orthogonal complement ([7]): If E ⊆ B is dense and definably independent with respect to 𝔅, then again, every open set definable in ⟨𝔅, E⟩ is definable in 𝔅.

Another class of examples is treated in [6, Section 6], namely, extensions T′ of ominimal theories T by “generic (unary) predicates”; this material was included in [6] only to illustrate some of the broader themes of that paper as a whole. Here, we shall relax the assumption that T be o-minimal and consider such extensions T′ in their own right. Some preliminary discussion of the underlying intuitive ideas is in order.

October 3, 2012. Some version of this document has been accepted for publication by the Journal of Symbolic Logic, but has not yet gone to press. Comments are welcome. Miller is the corresponding author. Miller partially supported by NSF grant DMS-1001176. Steinhorn partially supported by NSF Grant DMS–0801256.

Fix for the moment a positive integer N. We want to run a fair “pick N” lottery game on balls colored either black or white. The ways that we can mix and draw balls are fixed in advance. Some of these methods are unacceptable on the face of it, for example, anything that results in the first two balls drawn necessarily having the same color; we do our best to identify all unacceptable methods from the start so as to avoid using them. Given a set of colorable balls compatible with the accepted methods, we want to find a coloring of the balls that results in an unbiased draw no matter which of the allowed methods is used. Of course, even better would be that we can find a coloring of an infinite set of balls that works over any N ∈ ℕ, indeed, we would like to have many such colorings available to us. Finally, we would then like to know what happens if we introduce oracles for good colorings and let them interact with our original allowed methods to produce new allowed methods for other potential games. We now try to formalize all this.

Definition. Given a structure 𝔐 (not necessarily ordered), we say that a collection 𝒮 of subsets of M is naively generic for 𝔐 if: For every X ⊆ M^{n} (n ∈ ℕ) definable in 𝔐, if X contains a point having pairwise distinct coordinates each of which is algebraically independent (in 𝔐) over the parameters used to define X, then for every k ∈ ℕ, pairwise distinct S_{1}, …, S_{k} ∈ 𝒮 and I_{1}, …, I_{k} ⊆ {1, …, n}, there exists x ∈ X such that ⋀_{j=1}^{k}[⋀_{i∈I_{j}}(x_{i} ∈ S_{j})∧⋀_{i∉I_{j}}(x_{i} ∉ S_{j})]. We also say that (𝔐, (S)_{S∈𝒮}) is naively generic (over 𝔐) or that it is an expansion of 𝔐 by naively generic predicates (the elements of 𝒮). For singletons 𝒮 = {S}, we say that S is naively generic, and so on. Of course, if 𝔐 expands a linear order, then we may replace “algebraically independent” with “definably independent”.

Let us consider three illustrative examples.

Example 1.1. (It is easy to see via quantifier elimination that a subset of ℚ is naively generic for ⟨ℚ, <⟩ if and only if it is both dense and codense in ℚ. Let S_{1}, S_{2} ⊆ ℚ be such that all of S_{1}\S_{2}, S_{2}\S_{1} and S_{1}∩S_{2} are dense in ℚ; then {S_{1}, S_{2}} is naively generic for ⟨ℚ, <⟩. Continuing in this fashion, we construct a countably infinite, naively generic collection 𝒮 for ⟨ℚ, <⟩. The theory T′ of the resulting structure ⟨ℚ, <, (S)_{S∈𝒮}⟩ can be viewed as the obvious generalization to T := DLO of the classical example of the theory of countably many independent^{1} unary relations over the theory of pure identity (see e.g. Chang and Keisler [3, Example 3.4.2]), and can be similarly analyzed. It is easy to see that T′ is well behaved relative to T, in particular, every model of T′ is naively generic over its reduct to the given language of T.

Example 1.2. Every collection of nonempty subsets of ℚ is vacuously naively generic for ⟨ℚ, <, (q)_{q∈ℚ}⟩ because all elements of ℚ are trivially interalgebraic. Thus, our naive definition fails to rule out some undesirable degeneracies, but only for models of Th(⟨ℚ, <, (q)_{q∈ℚ}⟩) that are too small: For any ω-saturated model of the theory, the naively generic sets are again exactly the dense and codense unary sets. Hence, one possible approach to addressing shortcomings of naive genericity might involve passing to sufficiently saturated elementary extensions. But because ⟨ℚ, <, (q)_{q∈ℚ}⟩ is o-minimal, there is a more direct fix that does not require changing models at all; see [6, 6.9] for details.

1This is the classical terminology. One might argue that we should stick with it instead of using “generic”, but we regard this as unwise given that “independent” has such a firmly-entrenched meaning in contemporary model theory.

Example 1.3. We now encounter an indication of more serious trouble. Evidently, any naively generic collection for ⟨ℚ, <, ℕ⟩ is also naively generic for ⟨ℚ, <⟩. It would be reasonable to suspect that the converse should fail simply because ⟨ℚ, < ⟩ is o-minimal and ⟨ℚ, <, ℕ⟩ is not. But the converse does hold because if X ⊆ ℚ^{n} is bounded, definable in ⟨ℚ, <, ℕ⟩ and contains a point having pairwise distinct coordinates each of which is algebraically independent over the parameters used to define X, then X is definable in ⟨ℚ, <⟩. (Note that ⟨ℚ, <, ℕ⟩ is interdefinable with ⟨ℚ, <, f, g, 0⟩, where

f(x) = \begin{cases}⌊x⌋, & x ≥ 0 \\ 0, & x < 0 \end{cases} g(x) = \begin{cases}⌊x⌋ + 1, & x ≥ 0 \\ 0, & x < 0 \end{cases}

and ⌊x⌋ denotes the integer part of x. It is routine to check that ⟨ℚ, <, f, g, 0⟩ has quantifier elimination.) Thus, every dense and codense subset of ℚ is naively generic for ⟨ℚ, <, ℕ⟩. To put this another way, naive genericity fails to detect any difference between the o-minimal structure ⟨ℚ, <⟩ and its expansion by the infinite discrete set ℕ; we see this as a major failure of the naive definition to capture our original intent. Moreover, unlike Example 1.2, the situation does not improve by passing to nonstandard models (indeed, see the proof of Theorem 1.6 below). There are various ways that we might try to tinker with the definition of genericity in order to fix these problems, but as ℕ is nowhere dense in ℚ, this could reasonably be construed as straying too far beyond the intended scope of this paper (recall our opening paragraph). The question arises naturally: In the settings that do fall under the intended scope of this paper, how do we rule out the kinds of problems that have arisen in this example? We do have at least one good answer, as we now begin to explain.

Definition. Given a theory T (always assumed to be consistent) in a language ℒ and a collection 𝒫 of unary relation symbols none of which belong to ℒ, we say that a theory T′ is an extension of T by generic (unary) predicates if T′ is consistent and, for every 𝔐′ ⊧ T′, the collection of the interpretations of the P ∈ 𝒫 in 𝔐′ is naively generic for the reduct of 𝔐′ to ℒ. We also say that T′ is generic over T. Given a structure 𝔐, we say that a collection 𝒮 of subsets of M is generic for 𝔐 if Th(⟨𝔐, (S)_{S∈𝒮}⟩) is generic over Th(𝔐).

Note. The above is not the same definition of genericity used in [6], but we shall see in Theorem 1.6 below that the definitions are equivalent in practice when working over infinite linear orders.

Definition. As in [6], we say that a structure 𝔐 has uniform finiteness (UF, for short) if for every m ∈ ℕ and A ⊆ M^{m} × M definable in 𝔐 there exists N ∈ ℕ such that for every x ∈ M^{m} the set { y ∈ M : (x, y) ∈ A } either is infinite or contains at most N elements. We say that a theory T has UF if every model of T has UF. It is easy to see that UF is preserved under elementary equivalence, so a complete theory has UF if and only some model of it does.

The following key result is due essentially^{2} to Chatzidakis and Pillay [4, Section 2].

Theorem 1.4. Let T be a model complete ℒ-theory having UF and no finite models and 𝒫 be a collection of unary relation symbols not in ℒ. Then there is an (ℒ ∪ 𝒫)- theory T^{∗} ⊇ T such that T^{∗} is a model companion of T regarded as an (ℒ∪𝒫)-theory, and T^{∗} is generic over T and has UF.

Corollary 1.5. Let T be an ℒ-theory having UF and no finite models and 𝒫 be a collection of unary relation symbols not in ℒ. Then there is a generic (ℒ∪𝒫)-extension T_{𝒫} of T such that every generic (ℒ ∪ 𝒫)-extension of T is logically equivalent to some (ℒ ∪ 𝒫)-extension of T_{𝒫}. Moreover, T_{𝒫} has UF.

Proof. Let φ ↦ R_{φ} be an injective mapping of open ℒ-formulas into relation symbols not in ℒ ∪ 𝒫 such that R_{φ} has the same arity as φ. Let ℒ′ be the extension of ℒ by the symbols R_{φ} and T′ be the extension of T by the universal closures of the formulas φ ↔ R_{φ}. By Theorem 1.4, T′ has a model companion (T′)^{∗} ⊇ T′ as an (ℒ′∪𝒫)-theory. Let T_{𝒫} be the obvious syntactic translation of (T′)^{∗} into an ℒ_{𝒫}-theory. Recall that all model companions of any given theory are logically equivalent. □

Remark. If T_{1} is any theory having a model companion T_{2}, then the models of T_{2} are exactly the “infinitely generic” structures for T_{1}—see either Barwise and Robinson [1] or [3, Exercise 3.5.24] for details and more information—which partly explains our use of “generic”.

By [4, 2.11], UF is necessary for a model complete theory T to have a model companion as an (ℒ ∪ 𝒫)-theory. But UF is not needed for T to have generic (ℒ ∪ 𝒫)- extensions (we give a simple example in Proposition 2.2). This distinction disappears when working over linear orders; indeed, we are now ready to characterize genericity in our setting.

Theorem 1.6. If T is an extension of the theory of infinite linear orders in a language ℒ, then the following are equivalent.

(1) There is some extension of T by a single generic predicate.

2We shall explain this later in Section 2 below.

(2) No model of T defines a unary set having an initial segment isomorphic to ⟨ℕ, <⟩.

(3) T has UF.

(4) For every collection 𝒫 of unary relation symbols disjoint from ℒ there is a generic (ℒ ∪ 𝒫)-extension T_{𝒫} of T such that every generic (ℒ ∪ 𝒫)-extension of T is logically equivalent to some (ℒ ∪ 𝒫)-extension of T_{𝒫}.

(Recall Example 1.3 in connection with (2).)

Proof. (1)⇒(2). We illustrate the key ideas by doing the case that T is the theory of ⟨ℕ, <⟩ and leave the general case as an exercise. Let ⟨M, <⟩ ≡ ⟨ℕ, <⟩ and S ⊆ M be such that ⟨M, <, S⟩ is ω-saturated. It suffices to show that S is not naively generic for ⟨M, <⟩. Suppose otherwise. Fix for the moment some integer n ≥ 2. Let X be the set of all points x ∈ M^{n} such that each coordinate x_{i} is the immediate successor of x_{i−1}, i = 2, …, n. By saturation and genericity, there is a sequence of n consecutive points in M all of which are in S. As this is true for each n ≥ 2, the set S contains an infinite interval of M by saturation, thus violating genericity.

(2)⇒(3) is an easy exercise in compactness that we leave to the reader, (3)⇒(4) is immediate from Corollary 1.5 and (4)⇒(1) is trivial. □

We are now ready to turn to considering properties of T_{𝒫} that are particular to working over linear orders. For the remainder of this section: We assume that T is an extension of the theory of infinite linear orders (in a language ℒ ⊇ {<}) and T_{𝒫} is as in Theorem 1.6 (whenever T has UF). Our intuition is that passing from T to T_{𝒫} should be “topologically innocuous”, but we regard this notion as heuristic only and shall not attempt to make it precise. The case that T is o-minimal is treated in considerable detail in [6, Section 6]—see also Fratarcangeli [10] and Miller and Speissegger [12, 4.2]—so we focus here on more general results.

Definition. For our purposes, a cut in a linear order (M, <) is a convex subset C of M that is either unbounded above and bounded below with inf(C) ∉ M, or unbounded below and bounded above with sup(C) ∉ M. We say that an extension T′ of T (in a language ℒ′ ⊇ ℒ) has no new cuts over T if every cut definable in any model of T′ is definable in the reduct of the model to ℒ.

Note that if T is o-minimal then no model of T defines a cut. The presence of definable cuts in a structure tends to greatly increase the difficulty in analyzing the structure since some key basic tools from calculus such as the Intermediate Value Theorem are no longer applicable. This is well illustrated by the extra complications encountered in studying weakly o-minimal structures that are not o-minimal; see Macpherson et al. [11] and Examples 4.2 and 4.3 below.

Theorem 1.7. If T has UF, then T_{𝒫} has no new cuts over T.

(See Section 3 for the proof.)

Definition. An expansion of a linear order (M, <) is definably complete (or DC, for short) if sup(X) ∈ M for every definable ∅ ≠ X ⊆ M that is bounded above, equivalently, if inf(X) ∈ M for every definable ∅ ≠ X ⊆ M that is bounded below. A theory is definably complete (or DC) if the same is true of all of its models.

As an immediate consequence of Theorems 1.4 and 1.7:

Corollary 1.8. If T has UF and is definably complete, then the same is true of T_{𝒫}.

Definition. Given theories T_{1} ⊆ T_{2} in languages ℒ_{1} ⊆ ℒ_{2} such that every model of T_{2} is a first-order topological structure (as defined by Pillay [13]), we say that T_{2} has no new open sets over T_{1} if no model of T_{2} defines an open set (of any arity) that is not definable in the reduct of the model to ℒ_{1}.

The ultimate manifestation of topological innocuousness would be that T_{𝒫} has no new open sets over T, but this can easily fail (as we shall discuss further in Section 4). However, there is an interesting class of examples where it does hold, as we explain next.

Definition. The open core of a structure 𝔐 endowed with a definable topology is the structure on the underlying set of 𝔐 generated by the collection of all open sets that are definable in 𝔐.

Theorem 1.9. If T extends DLO and every model of T has o-minimal open core, then T has UF and T_{𝒫} has no new open sets over T.

(That T has UF is immediate by compactness.) When combined with Corollary 1.8 and [6, Theorem A], we obtain

Corollary 1.10. If T has UF, is definably complete and extends the theory of densely ordered groups, then T_{𝒫} has no new open sets over T.

A weaker version of Theorem 1.9 was established in [6] under the additional assumption that no model of T defines a unary function having a somewhere-dense graph—see the beginning of the proof of [6, 6.1]—but this extra condition is rather strong and is easily seen to fail in many concrete cases of interest; below are two (each already mentioned earlier):

Example 1.11. If 𝔅 is an o-minimal expansion of an ordered field and 𝔄 is a proper elementary substructure such that A is dense in B, then Th(⟨𝔅, A⟩) defines no new open sets over Th(𝔄) [6, §5]. Thus, every model of Th(⟨𝔅, A⟩) has o-minimal open core. But it is easy to see that every model of Th(⟨𝔅, A⟩) defines a unary function whose graph is dense; see van den Dries [8, p. 62].

Example 1.12 ([7]). If ℜ is an o-minimal expansion of a densely ordered group and E ⊆ R is dense and definably independent, then Th(⟨ℜ, E⟩) defines no new open sets over Th(ℜ), and every model of Th(⟨ℜ, E⟩) defines a unary function whose graph is dense.

Before proceeding to proofs, we digress briefly to expand on an issue raised in [6]. If 𝔐 has UF, then Th(𝔐) has generic extensions by Theorem 1.4. But this does not on the face of it imply that 𝔐 itself has any naively generic sets. So we ask: If T has UF and extends DLO, under what conditions do given models of T expand to models of T_{𝒫}? Modulo some obvious set-theoretic issues connected with the cardinality of 𝒫, the crucial points are already present when 𝒫 is a singleton, so we stick to this case. Some positive partial answers are given in [6, 6.4–6.5] for o-minimal T —in particular, every model of T with underlying set ℝ expands to a model of T_{𝒫}, and similarly if ℒ is countable and T extends the theory of ordered fields—but in fact we simply do not know of any concrete counterexamples. The next result suggests that caution is order. Recall that ℝ_{alg} denotes the set of all real algebraic numbers.

Proposition 1.13. (1) There are families ⟨f_{i} : i ∈ ω_{1}⟩ of pairwise distinct func-

tions ℝ_{alg} → ℝ_{alg} such that ℜ = ⟨ℝ_{alg}, +, ·, <, (f_{i})_{i∈ω_{1}}⟩ is o-minimal.

(2) Assuming the Continuum Hypothesis, the f_{i} can be chosen so that ℜ has no naively generic sets.

The proof is routine relative to a construction due to Wilkie [14] (for (1)). As this is but a side issue here, we shall leave details to the interested reader.

We now outline the rest of this paper. Section 2 consists of technical preliminaries, in particular, some global conventions and a brief review of some key results from [4], including the proof of 1.6. (The reasoning given in [4] for preservation of UF in passing from T to T_{𝒫} is flawed; we repair this.) We prove Theorem 1.7 in Section 3. In Section 4, we prove Theorem 1.9 and give some evidence as to why it is probably optimal.

Note. Throughout, we have dealt only with sets that are generic with respect to the underlying sets of structures, but our definition of genericity can be easily relativized to any fixed collection of subsets of the underlying set of a structure. As mentioned in [4], appropriate modifications of Theorem 1.4 are routine, hence also of all of our results as well.

Added during final revision. Our work in [6] and earlier-circulated versions of this paper inspired Boxall and Hieronymi to establish a version of Theorem 1.9 that holds over certain other first-order topological theories. Although their results were produced after the manuscript for this paper was submitted for publication, their paper ([2]) has already appeared due to the vagaries of research publishing. It must be said that their proof is considerably shorter than ours on paper, but we believe our methods might be of further use for establishing other results specific to the ordered setting.

2. Preliminaries

Global conventions. For the most part, the usual notational conventions from model theory are employed. Given a structure 𝔐 with underlying set M, a formula ϕ(\overline{x}, \overline{y}) (in the language of 𝔐) and a tuple \overline{b} ∈ M (that is, having coordinates in M) having the same length as \overline{y}, we let ϕ(M, \overline{b}) denote the set defined in 𝔐 by ϕ(\overline{x}, \overline{b}), and similarly for variants such as ϕ(\overline{a}, M). Algebraic closure with respect to a given theory T is denoted by acl_{T}; similarly, dcl_{T} is used for definable closure. Expressions of the form acl_{T} (z̄) are short for acl_{T} ({z_{1}, …, z_{n}}) where n is the length of \overline{z}, while “\overline{x} ∩ acl_{T} (\overline{z}) = ∅” means that no coordinate of \overline{x} lies in acl_{T} (\overline{z}).

Generally, |X| denotes the cardinality of a set X, except when applied to languages or theories, in which case |X| is the cardinality of X ∪ ℕ.

We abbreviate “quantifier elimination” by “QE”.

Recall that a theory T is said to eliminate ∃^{∞} (the quantifier “there exists infinitely many”) if, for every 𝔐 ⊧ T and formula ϕ(x, \overline{y}), the set \{ \overline{b} ∈ M : ϕ(M, \overline{b}) is infinite \} is definable in 𝔐. An easy compactness argument shows that T eliminates ∃^{∞} if and only if T has UF; the former terminology is used in [4], but we prefer the latter.

For the rest of this paper: ℒ ranges over first-order languages; T ranges over ℒ-theories; 𝒫 ranges over sets of unary relation symbols, none of which are in ℒ; and ℒ_{𝒫} abbreviates ℒ ∪ 𝒫.

We now recall a few key facts from [4].

Fact 1. If T has UF, then for every ℒ-formula ϕ(\overline{x}, \overline{y}) there is an ℒ-formula ψ(\overline{y}) such that

ψ(M) = \{ \overline{b} ∈ M : ∃\overline{a} ∈ M, \overline{a} ∩ acl(\overline{b}) = ∅ & 𝔐 ⊧ ϕ(\overline{a}, \overline{b}) \}

for every saturated 𝔐 ⊧ T.

Proof. If T has QE and is complete (global assumptions in [4, §2]), then this is just a rephrasing of [4, 2.3]. An examination of the proof shows that QE is irrelevant and it is enough to know that every model of T has UF (which holds by assumption, not completeness). □

Fact 2. If T has UF and is model complete as an ℒ-theory, then there is a generic ℒ_{𝒫}-extension T^{∗} of T such that T^{∗} is a model companion of T as an ℒ_{𝒫}-theory.

Proof. By arguing as in the proof of 1.5, it suffices to consider the case that T has QE. If T is complete and 𝒫 is a singleton, then the result is essentially just a rephrasing of [4, 2.4]. (Aside: In our setting, the expression ⋀_{i=1}^{n} S(x_{i}) is superfluous in the axiomatization.) Completeness of T is superfluous, as it is not needed for [4, 2.3] (Fact 1). The case that 𝒫 is not a singleton is a routine clerical modification. □

From now on: We let T_{𝒫} be as in Corollary 1.5 (whenever T has UF).

Fact 3 ([4, 2.6.3], essentially). If T has UF, 𝔐 ⊧ T_{𝒫} and a ∈ M is algebraic over A ⊆ M, then a is algebraic over A in the reduct of 𝔐 to ℒ.

(This was also proved in [4] under global assumptions that T has QE and is complete, but as before, these can be relaxed.)

Next is an extremely useful technical result that we use often.

Fact 4 ([4, 2.6.4]). If T has UF and QE, then every ℒ_{𝒫}-formula is T_{𝒫}-equivalent to a disjunction of formulae of the form ∃\overline{y}ψ(\overline{x}, \overline{y}), where ψ is quantifier free and there exists N ∈ ℕ such that T_{𝒫} ⊢ ∀\overline{x}∃^{≤N} \overline{y}ψ(\overline{x}, \overline{y}).

(Again, the completeness of T assumed in [4] is superfluous.)

We now complete the proof of Theorem 1.4 by establishing preservation of UF.

Theorem 2.1. Let T and T^{∗} be as in Fact 2. Then T^{∗} has UF.

(This was asserted in [4, 2.12.4], but the reasoning given there does not work, as we shall explain below after the proof.)

Proof. For ease of notation, we reduce to the case that T has QE and 𝒫 is a singleton {P }. Let 𝔐 ⊧ T^{∗}. We must show that 𝔐 has UF. It suffices to consider the case that 𝔐 is ω-saturated. Suppose to the contrary that UF fails for 𝔐; we derive a contradiction. By Fact 4, a formula witnessing the failure of UF is a disjunction of formulae of the form

∃\overline{z} [ϕ(x, \overline{y}, \overline{z}) ∧ ⋀_{1≤i≤l} P t_{i}(x, \overline{y}, \overline{z}) ∧ ⋀_{l<i≤n} ¬P t_{i}(x, \overline{y}, \overline{z})]

where ϕ is an ℒ-formula and the t_{i} are ℒ-terms. Without loss of generality we assume that there is only one disjunct. We denote the formula enclosed in square brackets by τ(x, \overline{y}, \overline{z}). By Fact 4, τ(b, \overline{a}, M) is finite for all \overline{a}, b in M. Let \{\overline{a}_{k} : k ∈ ω\} be a sequence witnessing that UF fails, namely there is an increasing sequence of natural numbers m_{k} so that |∃\overline{z} τ(M, \overline{a}_{k}, \overline{z})| = m_{k}.

For each equivalence relation E on \{1, …, n\} let τ_{E}(x, \overline{y}, \overline{z}) be the conjunction of τ(x, \overline{y}, \overline{z}) with

⋀_{⟨i,j⟩∈E} t_{i}(x, \overline{y}, \overline{z}) = t_{j}(x, \overline{y}, \overline{z}) ∧ ⋀_{⟨k,l⟩∉E} t_{k}(x, \overline{y}, \overline{z}) ≠ t_{l}(x, \overline{y}, \overline{z})

Note that τ(x, \overline{y}, \overline{z}) is equivalent to the disjunction of the τ_{E}(x, \overline{y}, \overline{z}) and thus some τ_{E} witnesses the failure of uniform finiteness. Hence without loss of generality we assume that if 𝔐 ⊧ τ(b, \overline{a}, \overline{c}) then t_{i}(b, \overline{a}, \overline{c}) ≠ t_{j}(b, \overline{a}, \overline{c}) for i ≠ j.

Suppose for some k ∈ ω that 𝔐 ⊧ ϕ(b, \overline{a}_{k}, \overline{c}). We assert that t_{i}(b, \overline{a}_{k}, \overline{c}) ∈ acl(\overline{a}_{k}) for some 1 ≤ i ≤ n (by Fact 3, we can take algebraic closure throughout to mean algebraic closure in the reduct of 𝔐 to ℒ). Otherwise, by genericity (Fact 2) and compactness we find d and \overline{e} so that 𝔐 ⊧ τ(d, \overline{a}_{k}, \overline{e}) and t_{i}(d, \overline{a}_{k}, \overline{e}) ∉ acl(\overline{a}_{k}) for all 1 ≤ i ≤ n. Since τ(d, \overline{a}_{k}, M) is finite, \overline{e} ∈ acl(d\overline{a}_{k}). As ∃\overline{z}τ(x, \overline{a}_{k}, \overline{z}) is finite d ∈ acl(\overline{a}_{k}). Hence \overline{e} ∈ acl(\overline{a}_{k}) and thus t_{i}(d, \overline{a}_{k}, \overline{e}) ∈ acl(\overline{a}_{k}) for all i, a contradiction.

By Fact 1 there is an ℒ-formula σ(\overline{y}) so that if 𝔐 ⊧ σ(\overline{a}) then at least one of t_{1}(p, \overline{a}, \overline{q}), …, t_{n}(p, \overline{a}, \overline{q}) lies in acl(\overline{a}) for all p, \overline{q} such that 𝔐 ⊧ ϕ(p, \overline{a}, \overline{q}). Without loss of generality we assume that ∀x \overline{y} \overline{z}(ϕ(x, \overline{y}, \overline{z}) → σ(\overline{y})). Thus by compactness we find ℒ-formulae ψ_{i}^{j}(x, \overline{y}) for 1 ≤ i ≤ n and 1 ≤ j ≤ m(i) so that

∀x \overline{y} \overline{z}[(ϕ(x, \overline{y}, \overline{z}) → ⋁_{1≤i≤n} ⋁_{1≤j≤m(i)} ∃^{<∞}w ψ_{i}^{j}(w, \overline{y}) ∧ ψ_{i}^{j}(t_{i}(x, \overline{y}, \overline{z}), \overline{y})].

For every I ⊆ \{1 … n\} with I ≠ ∅ let γ_{I}(x, \overline{y}, \overline{z}) be the ℒ-formula given by

⋀_{i∈I} ⋁_{1≤j≤m(i)} ∃^{<∞}w ψ_{i}^{j}(w, \overline{y}) ∧ ψ_{i}^{j}(t_{i}(x, \overline{y}, \overline{z}), \overline{y})

and let τ_{I}(x, \overline{y}, \overline{z}) be τ(x, \overline{y}, \overline{z}) ∧ γ_{I}(x, \overline{y}, \overline{z}). Thus for each k ∈ ω

𝔐 ⊧ ∃\overline{z}τ(x, \overline{a}_{k}, \overline{z}) ↔ ⋁_{I⊆\{1,...,n\},I≠∅} ∃\overline{z}τ_{I}(x, \overline{a}_{k}, \overline{z}).

It follows for some I ≠ ∅ that ∃\overline{z}τ_{I} witnesses the failure of uniform finiteness, and we replace τ by τ_{I}. Our proof now proceeds by induction on |{1, …, n} \ I|. Note that for each fixed k if 𝔐 ⊧ τ_{I}(b, \overline{a}_{k}, \overline{c}) then |I| is the minimum number of 1 ≤ i ≤ n so that t_{i}(b, \overline{a}_{k}, \overline{c}) ∈ acl(\overline{a}_{k}).

First suppose that |I| = n and 𝔐 ⊧ τ_{I}(b, \overline{a}_{k}, \overline{c}). Since there are only finitely many realizations of ∃\overline{z}τ_{I}(x, \overline{a}_{k}, \overline{z}), and for each x only finitely many realizations of τ_{I}(x, \overline{a}_{k}, \overline{z}), the set

\{w\overline{q} : 𝔐 ⊧ ϕ(w, \overline{a}_{k}, \overline{q}) and t_{i}(w, \overline{a}_{k}, \overline{q}) = t_{i}(b, \overline{a}_{k}, \overline{c}) for all 1 ≤ i ≤ n\}

is finite. This follows by a similar argument to that used above to guarantee that if 𝔐 ⊧ ϕ(b, \overline{a}_{k}, \overline{c}) then at least one of the t_{i}(b, \overline{a}_{k}, \overline{c}) lies in acl(\overline{a}_{k}). Let ρ(x, \overline{y}, \overline{z}) be the ℒ-formula

ϕ(x, \overline{y}, \overline{z}) ∧ γ_{I}(x, \overline{y}, \overline{z}) ∧ ∃^{<∞}w\overline{q}[ϕ(w, \overline{y}, \overline{q}) ∧ ⋀_{1≤i≤n} t_{i}(w, \overline{y}, \overline{q}) = t_{i}(x, \overline{y}, \overline{z})]

Clearly 𝔐 ⊧ ∃\overline{z}τ_{I}(x, \overline{a}_{k}, \overline{z}) → ∃\overline{z}ρ(x, \overline{a}_{k}, \overline{z}) for each k. We now assert that for any k if 𝔐 ⊧ ∃\overline{z}ρ(b, \overline{a}_{k}, \overline{z}) then b ∈ acl(\overline{a}_{k}). To see this, let \overline{c} be such that ρ(b, \overline{a}_{k}, \overline{c}) holds. As I = \{1, …, n\}, for each i we have t_{i}(b, \overline{a}_{k}, c̄) ∈ acl(\overline{a}_{k}). The formula ∃\overline{z}[ρ(x, \overline{a}_{k}, \overline{z}) ∧ ⋀_{1≤i≤n} t_{i}(x, \overline{a}_{k}, \overline{z}) = t_{i}(b, \overline{a}_{k}, \overline{c})] is thus a formula with parameters in acl(\overline{a}_{k}). This formula is satisfied by b and the last clause in the definition of ρ ensures there are only finitely many elements that satisfy it. Hence b ∈ acl(\overline{a}_{k}). Thus ∃\overline{z}ρ(x, \overline{y}, \overline{z}) is an ℒ-formula witnessing the failure of uniform finiteness, a contradiction.

Now suppose that |\{1, …, n\} \ I| < n. Let ζ_{I}(x, \overline{y}, \overline{z}) be the formula

∃^{<∞}w\overline{q} ⋀_{i∈I}(t_{i}(w, \overline{y}, \overline{q}) = t_{i}(x, \overline{y}, \overline{z})).

Then either ∃\overline{z}(τ_{I} ∧ ζ_{I}) or ∃\overline{z}(τ_{I} ∧ ¬ζ_{I}) witnesses the failure of UF. If ∃\overline{z}(τ_{I} ∧ ζ_{I}) witnesses the failure of UF then arguing just as above we produce an ℒ-formula that witnesses the failure of uniform finiteness, a contradiction. Now suppose that ∃\overline{z}(τ_{I} ∧ ¬ζ_{I}) witnesses the failure. Suppose for some k ∈ ω and b, \overline{c} ∈ M that 𝔐 ⊧ τ_{I}(b, \overline{a}_{k}, \overline{c}) ∧ ¬ζ_{I}(b, \overline{a}_{k}, \overline{c}). The set

\{w\overline{q} : 𝔐 ⊧ ϕ(w, \overline{a}_{k}, \overline{q}) and t_{i}(b, \overline{a}_{k}, \overline{c}) = t_{i}(w, \overline{a}_{k}, \overline{q}) for all i ∈ I\}

is infinite. Hence for some i ∈ \{1, … n\} \ I, t_{i}(b, \overline{a}_{k}, \overline{c}) ∈ acl(\overline{a}_{k}) since otherwise by the genericity of P (M) we find infinitely many realizations of ∃\overline{z}τ_{I}(x, \overline{a}_{k}, \overline{z}). Hence we have increased the number of t_{i}’s that we assume lie in acl(\overline{a}_{k}) for any k, i.e. we increase the size of I. Arguing using Fact 1, compactness, and the induction hypothesis we finish as in the |I| = n case. □

It was suggested in [4, 2.12.4] that Theorem 2.1 follows from preservation of algebraic closure (Fact 3). We now give an example due to M. Tychonievich (communicated to author Miller in conversation) showing that this approach does not work in general. Let S be the successor function on ℤ. Then Th(⟨ℤ, S, 0⟩) has UF (and is even complete and has QE) and acl is preserved in passing to Th(⟨ℤ, S, 0, <⟩), but the formula 0 < x < y witnesses failure of UF in ⟨ℤ, S, 0, <⟩. We leave it to the interested reader to check details.

We conclude this section with an example of a structure that does not have UF, yet does have generic (not just naively generic) sets:

Proposition 2.2. The set 2ℕ of even elements of ℕ is generic for the structure ⟨ℕ, E⟩, where E is the equivalence relation induced on ℕ by the partition { [k^{2} + k, (k + 1)^{2} + k] : k ∈ ℕ }.

Proof. It suffices to show that 2ℕ is generic for ⟨ℕ, E, (n)_{n∈ℕ}⟩. Observe that each equivalence class [k^{2} + k, (k + 1)^{2} + k] of E consists of 2(k + 1) elements, half of which are even. Thus, if ⟨M, R, (a_{n})_{n∈ℕ}, S⟩ is a model of Th(⟨ℕ, E, (n)_{n∈ℕ}, 2ℕ⟩) and C ⊆ M is an equivalence class of R, then either C is the class of some a_{n} or S is infinite and coinfinite in C. It follows that S is naively generic with respect to the quantifier-free definable (allowing parameters) sets of ⟨M, R, (a_{n})_{n∈ℕ}⟩. As Th(⟨ℕ, E, (n)_{n∈ℕ}⟩) has QE (an exercise), S is naively generic for ⟨M, R, (a_{n})_{n∈ℕ}⟩. Hence, 2ℕ is generic for ⟨ℕ, E, (n)_{n∈ℕ}⟩. □

3. No new cuts

This section consists of the proof of Theorem 1.7. Let T be an extension of the theory of infinite linear orders such that T has UF. We show that T_{𝒫} has no new cuts over T. We give details only for the case that 𝒫 is a singleton {P } and T has QE. We work in a sufficiently saturated model ℜ of T_{𝒫}. Suppose that ϕ(x, \overline{b}) is an ℒ_{𝒫}-formula defining a cut C in ℜ, which for convenience we assume is bounded above but has no least upper bound. We also assume without loss of generality that C is not bounded below. Our goal is to show that C is ℒ-definable.

For sets X, Y ⊆ R we say that X bounds Y if for every y ∈ Y there is x ∈ X so that x > y. We will say that X and Y are interbounded if X bounds Y and Y bounds X. Note that if X ⊆ Y and X bounds Y then X and Y are interbounded.

By quantifier elimination for T_{𝒫} (Fact 4) and that acl_{T} = dcl_{T} we assume that C is definable by a disjunction of formulae of the form

ψ(x, \overline{b}) ∧ ⋀_{i=1}^{l} P f_{i}(x) ∧ ⋀_{i=l+1}^{m} ¬P f_{i}(x)

where ψ(x, \overline{y}) is an ℒ-formula and the f_{i} are \overline{b}-definable functions. At least one of the disjuncts, let us call it σ(x), is interbounded with C. Notice that σ(R) does not have a least upper bound. To establish our result it suffices to show that there is an ℒ-definable set Z which is interbounded with σ(R).

Notice that for 1 ≤ i ≤ l and l + 1 ≤ j ≤ m the set {x : f_{i}(x) = f_{j}(x)} is disjoint from σ(R). Also we assume that for 1 ≤ i < j ≤ l or l + 1 ≤ i < j ≤ m the set {x : f_{i}(x) = f_{j}(x)} is not cofinal in σ(R). Otherwise in the case that 1 ≤ i < j ≤ l σ(R) is interbounded with the realizations of

ψ(x, \overline{b}) ∧ ⋀_{1≤k≤l,k≠j} P f_{k}(x) ∧ ⋀_{1≤r≤m} ¬P f_{r}(x)

and we work with this formula, which has one fewer conjunct, in place of σ. The case that l + 1 ≤ i < j ≤ m is similar. Hence without loss of generality we assume that ψ(x, \overline{b}) ⊢ ⋀_{1≤i≠j≤m} f_{i}(x) ≠ f_{j}(x).

For 0 ≤ j ≤ m we say that a pair of functions

(α, β) : {1, … j} × {1, … j} → {1, …, j} × R

is j-correct if α is one to one and β(i) ∈ P (M) if and only if 1 ≤ α(i) ≤ l. For (α, β) j-correct we let X(α, β) be the set of all x ∈ R so that

x ∈ ψ(R, \overline{b}) and f_{α(i)}(x) = β(i) for all 1 ≤ i ≤ j.

(Notice that if j = 0 then X(α, β) = ψ(R, \overline{b}).)

We show that it suffices to find an m-correct pair of functions. Suppose that (α, β) is m-correct. Then there are elements a_{i} ∈ P (M) for 1 ≤ i ≤ l and a_{i} ∈ R \ P (M) for l + 1 ≤ i ≤ m so that

\{x : x ∈ ψ(R, \overline{b}) and f_{i}(x) = a_{i} for all 1 ≤ i ≤ m\} ∩ σ(R)

bounds σ(R). This implies that

\{x : x ∈ ψ(R, \overline{b}) and f_{i}(x) = a_{i} for all 1 ≤ i ≤ m\}

is an ℒ-definable subset of σ(R) that bounds σ(R) and so we would be done.

To finish the proof, we now find an m-complete pair by inductively constructing for 0 ≤ j ≤ m j-complete pairs (α_{j}, β_{j}) so that X(α_{j}, β_{j}) ∩ σ(R) bounds σ(R).

The case j = 0 is trivial.

For induction suppose that there is a j-correct (α, β) so that X(α, β)∩σ(R) bounds σ(R). We show that there is a (j + 1)-correct (α^{∗}, β^{∗}) with α^{∗} extending α and β^{∗} extending β so that X(α^{∗}, β^{∗}) ∩ σ(R) bounds σ(R).

Note that X(α, β) is \overline{b}, β(1), …, β(j)-definable. Let S denote this parameter set. Let θ(x) be

ψ(x, \overline{b}) ∧ ∃w > x(w ∈ X(α, β) ∧ ⋀_{i∉range(α)} f_{i}(w) ∉ dcl(Sx)).

This is a first order ℒ-formula by Fact 1. By genericity (Fact 2) we have that σ(R) bounds θ(R). If C is not ℒ-definable then θ(R) does not bound σ(R). Fix c ∈ ψ(R, \overline{b}) so that c > θ(R) and c < e for some e so that ℜ ⊧ σ(e). Let p(x) be the ℒ-type

{x > c} ∪ {x ∈ X(α, β)} ∪ {f_{i}(x) ≠ d : i ∉ range(α) and d ∈ dcl(Sc)}

Since θ(R) does not bound σ(R) this is inconsistent. Hence there are finite sets E_{i} ⊂ R for i ∉ range(α) so that

ℜ ⊧ ∀x(x > c ∧ x ∈ X(α, β) → ⋁_{i∉range(α)} f_{i}(x) ∈ E_{i})

and thus

ℜ ⊧ ∀x(x > c ∧ x ∈ [X(α, β) ∩ σ(R)] → ⋁_{i∉range(α)} f_{i}(x) ∈ E_{i}).

Since X(α, β) ∩ σ(R) bounds σ(R) there is i ∉ range(α) and a ∈ E_{i} so that the set

{x : x ∈ X(α, β) and f_{i}(x) = a} ∩ σ(R)

bounds σ(R). Setting α^{∗}(j + 1) = i and β^{∗}(j + 1) = a completes the induction. □

4. No new open sets

This section is closely connected with our earlier work [6, Section 6]. Let T have UF and extend the theory of infinite linear orders. We are interested primarily in the case that T extends DLO, but we work in greater generality whenever convenient.

Having shown in the preceding section that T_{𝒫} has no new cuts over T, it is natural to ask whether T_{𝒫} has no new open sets over T. There is a serious constraint on T.

Proposition 4.1. If T_{𝒫} has no new open sets over T, then every unary open set definable in any model of T has finite boundary.

Proof. We show the contrapositive. Let U ⊆ M be open and definable in 𝔐 ⊧ T with infinite boundary. It suffices to consider the case that 𝒫 is a singleton {P } and 𝔐 is saturated. Let S ⊆ M be naively generic for 𝔐. We now show that (𝔐, S) defines an open set not definable in 𝔐. The set of all x in the boundary of U such that x is the left endpoint of a connected component of U is definable in 𝔐, and similarly for the right endpoints. Hence, we may reduce to the case that every connected component of U has a left endpoint. Let A be the set of these endpoints. As A infinite, so are both A ∩ S and A \ S by genericity. Then A ∩ S is not definable in 𝔐, again by genericity. Let V be the union of all connected components of U whose left endpoint lies in S. Then V is definable in (𝔐, S) but not in 𝔐. □

We do not regard the above as violating the heuristic that good topological properties should be preserved in passing to T_{𝒫}. Rather, we take the position that the presence of unary definable sets with infinite boundary while under the assumption of uniform finiteness suggests possible topological pathology, and preservation of pathology is rarely of any interest. Indeed, it is reasonable to wonder if these two conditions are incompatible. But there are examples of T satisfying UF where every model defines infinite discrete sets, even over the theory of ordered real-closed fields; see [6, 7.4]. If T additionally is definably complete, then examples are far more degenerate, for then T cannot extend the theory of ordered groups; see [6, 2.5, 7.1] for details. Thus, a natural next step is to concentrate on definably complete (DC) theories. We shall do so after a brief discussion of theories for which DC fails.

If T is not definably complete, then there is an obvious problem in analyzing definable sets in models: at this level of generality, we are unable to conclude much of anything about how complicated the definable open unary sets are, even if we assume that T extends the theory of ordered real-closed fields and every unary set definable in any model of T has finite boundary. We illustrate with two examples. In the first, T_{𝒫} has no new open sets (over T), while in the second, T_{𝒫} does have new open sets.

Example 4.2. Let T̄ be a complete o-minimal theory extending that of ordered fields. By definability of Skolem functions, we may assume that T̄ has quantifier elimination and is universally axiomatizable. Let T̄^{c} be the theory of all structures of the form (𝔅, V) where 𝔅 ⊧ T̄ and V ⊊ B is convex and closed under all ∅-definable continuous unary functions. Note that DC fails for T̄^{c}, since V is bounded and sup V does not exist. By van den Dries and Lewenberg [9], T̄^{c} is complete, has quantifier elimination, and is universally axiomatizable. It follows that T̄^{c} is weakly o-minimal, so it satisfies UF and every unary set definable in any model has finite boundary. By a routine modification of the proof that T̄_{𝒫} has no new open sets, we obtain the same for T̄_{𝒫}^{c}. (We provide a sketch at the end of this section.)

Example 4.3. We maintain the notation used in the preceding example but we assume that T̄ is simply the theory of real-closed ordered fields. Let T̄^{v} be obtained by expanding T̄^{c} to a two-sorted theory with a new sort for the value group induced by the convex subring V. Note that T̄^{v} is interpretable in T̄^{c}. Results from [5, Section 3] show that the theory T̄_{P}^{v} obtained by adding a generic predicate to the value group sort has new open sets.

The above examples illustrate that even if T is a weakly o-minimal extension of the theory of ordered fields, it is unclear whether T_{𝒫} has no new open sets.

We now turn to the case that T is definably complete; then every unary open set definable in any model of T is a finite union of intervals. This condition plays a crucial rôle in [6], and provides a hint for relaxing the assumption of o-minimality of T in [6, 6.1].

We begin to work toward the proof of Theorem 1.9, that is, if T extends DLO and every model of T has o-minimal open core, then T_{𝒫} has no new open sets over T. As usual, we give details only for the case that 𝒫 is a singleton {P }.

For the remainder of this section we fix ℜ_{P} ⊧ T_{𝒫} and let ℜ = ℜ_{P} ↾ ℒ. First, we observe that it suffices by Theorem 1.7, Corollary 1.8 and [6, 4.11] to show that every unary open set definable in ℜ_{P} is a finite union of open intervals. Unfortunately, this reduction does not seem to be at all helpful even for simplifying notation. Rather, as for our proof of preservation of UF in Section 2, it appears that we must return to the fundamental results of [4].

As the proof of Theorem 1.9 is quite technical we first present a simple example to illustrate a key insight. Suppose that T is an o-minimal theory and ℜ_{P} is a model of T_{𝒫} which is at least |T |^{+}-saturated. Let f : I → R be an ℒ-definable unary function where I ⊆ R is an interval, and let X = {x ∈ I : f(x) ∈ P }. By the quantifier elimination for T_{𝒫} (Fact 4) definable sets of this form are of fundamental interest. To establish that T_{𝒫} has no new open sets we need to show that the interior of X is definable in ℜ. As T is o-minimal we can reduce to the case where f is continuous and either monotone or constant on I. If f is constant the fact that int(X) is definable in ℜ is immediate. Hence we are left with the case where f is monotone increasing or decreasing. We claim in this case that X has empty interior and thus int(X) is definable in ℜ. Assume not, and let J be a subinterval of I with J ⊆ int(X). Let \overline{c} be the parameters needed to define f and J. By the saturation of ℜ_{P} and the monotonicity of f there is a ∈ J so that f(a) ∉ acl(\overline{c}). Applying genericity to the ℒ-formula ϕ(x, \overline{c}) asserting that ∃z(z ∈ J ∧ f(z) = x), it follows that there is some b ∈ J so that f(b) ∉ P. Hence b ∉ X contradicting that J ⊆ int(X). While this example shows why it might be expected that T_{𝒫} has no new open sets, the proof of Theorem 1.9 is signifcantly more involved because T is not assumed to be o-minimal, the set X may be a subset of a cartesian power of ℜ, and the definition of X may require conditions on the values of multiple definable functions.

We dispose of several notational preliminaries before beginning the proof proper. The arity of any given variable or tuple will be clear from context, so we dispense with the usual overbars in order to improve readability. We need some notation for dealing with basic open sets. For ℜ ⊧ T and ϵ_{1} … ϵ_{2n} ∈ R we let B(ϵ) ⊆ R^{n} be the open box (ϵ_{1}, ϵ_{2}) × ⋯ × (ϵ_{2n−1}, ϵ_{2n}). We always assume that ϵ_{2k−1} < ϵ_{2k}, that is, B(ϵ) is non-empty. In addition, for d ∈ R^{n} and ϵ ∈ R^{2n} we write B(d, ϵ) to represent the statement d ∈ B(ϵ). Thus the assertion

there is ϵ so that for all z ∈ B(d, ϵ)… is to be read as

there is ϵ ∈ R^{2n} with B(ϵ) ≠ ∅ and d ∈ B(ϵ), so that for all z ∈ B(ϵ)… (If T were to extend the theory of ordered groups, then we could interpret “z ∈ B(d, ϵ)” to have its usual meaning, that is, z lies in the box of radius ϵ centered at d.)

We require a technical lemma that will be applied in the proof of Theorem 1.9, specifically in Claim 4.10. To state the lemma we require some additional notation. Fix m ∈ ℕ. Let ℱ be the set of all functions from {1, ..., m} to ℕ. Let M ∈ ℱ, ϕ be an ℒ-formula, and ψ_{i} for 1 ≤ i ≤ m be ℒ-formulae. For 1 ≤ i ≤ m let f_{i} be ℒ-definable functions of some fixed arity. Let U(M) be the definable set of all x ∈ R for which there are ϵ and a_{1}^{i}, …, a_{M(i)}^{i} for 1 ≤ i ≤ m so that

ψ_{i}(a_{k}^{i}) for all 1 ≤ i ≤ m and 1 ≤ k ≤ M(i)

and, for all z ∈ B(x, ϵ)

either ϕ(z) or f_{i}(z) = a_{k}^{i} for some 1 ≤ i ≤ m and 1 ≤ k ≤ M(i).

Note that U(M) is open.

Lemma 4.4. Fix M^{∗} ∈ ℱ. There are finitely many elements e_{1}^{i}, ..., e_{r(i)}^{i} for 1 ≤ i ≤ m so that:

(1) ψ_{i}(e_{k}^{i}) holds for all 1 ≤ i ≤ m and 1 ≤ k ≤ r(i);

(2) for all z ∈ U(M^{∗}), either ϕ(z) or f_{i}(z) = e_{k}^{i} for some 1 ≤ i ≤ m and 1 ≤ k ≤ r(i).

Proof. Regard ℱ as lexicographically ordered and set:

ℱ^{∗} := {M ∈ ℱ : ∑_{i=1}^{m} M(i) ≤ 2 ∑_{i=1}^{m} M^{∗}(i) and M ≤ M^{∗}}

Notice that ℱ^{∗} is finite. For x ∈ U(M^{∗}) define M^{x} ∈ ℱ^{∗} to be the least element M of ℱ^{∗} such that x ∈ U(M). For M ∈ ℱ^{∗} set

V (M) = {x ∈ U(M^{∗}) : M^{x} = M}.

Notice that it follows from the definition of V (M) that

(1)  U(M^{∗}) = ⋃_{M∈ℱ^{∗}} V (M).

Furthermore V (M) is definable in ℜ^{∘}. This follows since for any N ∈ ℱ, the set U(N) is open and thus definable in ℜ^{∘} and by definition we have that

V (M) = (U(M) ∩ U(M^{∗})) \ ⋃_{{N∈ℱ^{∗}:N<M}} U(N).

Claim 4.5. If c ∈ V (M) there are a_{1}^{i}...a_{M(i)}^{i} for 1 ≤ i ≤ m and ϵ so that for all z ∈ B(c, ϵ) we have that:

( ⋀_{\begin{matrix}1≤i≤m \\ 1≤k≤M(i) \end{matrix}} ψ_{i}(a_{k}^{i})) ∧ (ϕ(z) ∨ ⋁_{\begin{matrix}1≤i≤m \\ 1≤j≤M(i) \end{matrix}} f_{i}(z) = a_{k}^{i})

Proof. This follows since we chose ϵ so that B(c, ϵ) witnesses that c ∈ U(M). Simply take a_{j}^{i} as in the definition of U(M). □

Claim 4.6. Let c ∈ V (M) and the a_{k}^{i} be as above. Suppose that b_{1}^{i}, ..., b_{M(i)}^{i} also satisfy the conditions on the a_{k}^{i} in Claim 4.5. Then for all i we have

{a_{1}^{i}, ..., a_{M(i)}^{i}} = {b_{1}^{i}, ..., b_{M(i)}^{i}}.

Proof. Fix ϵ witnessing that c ∈ U(M). We show by induction that if 1 ≤ i ≤ m then {a_{1}^{i}, ..., a_{M(i)}^{i}} = {b_{1}^{i}, ..., b_{M(i)}^{i}}. Fix i. We show by induction that for 0 ≤ j ≤ M(i) at least j elements of {a_{1}^{i}, ..., a_{M(i)}^{i}} belong to {b_{1}^{i}, ..., b_{M(i)}^{i}}.

If j = 0 then there is nothing to show. Suppose that j > 0 and without loss of generality that a_{k}^{i} = b_{k}^{i} for k < j. Choose z ∈ B(c, ϵ) so that:

(1) f_{l}(z) ≠ a_{k}^{l} for 1 ≤ l < i and 1 ≤ k ≤ M(l);

(2) f_{i}(z) ≠ a_{k}^{i} for k < j;

(3) f_{i}(z) ≠ a_{k}^{l} or f_{i}(z) ≠ b_{k}^{l} for l > i and 1 ≤ k ≤ M(l). If we cannot find such a z then c ∈ U(M′) where M′(i′) = M(i′) for i′ < i, M′(i) = j − 1, and M′(i′) = 2M(i′) if i′ > i. Notice that M′ < M and M′ ∈ ℱ^{∗}, contradicting that c ∈ V (M). Fix such a z ∈ B(c, ϵ). Thus f_{i}(z) = a_{k}^{i} for some k > j and f_{i}(z) = b_{k′}^{i} for some k′ > j. Hence a_{k}^{i} = b_{k′}^{i} and we are done. □

Claim 4.6 implies for c ∈ V (M), that we may set J^{i}(c) to be the set {a_{1}^{i}, ..., a_{M(i)}^{i}}, and we let J(c) be the sequence of sets ⟨J^{1}(c), ..., J^{m}(c)⟩.

Claim 4.7. For e ∈ V (M) let ϵ witness that e ∈ U(M), and let z ∈ B(e, ϵ) ∩ V (M). Then J(z) = J(e). Hence {z ∈ V (M) : J(z) = J(e)} is open in V (M).

Proof. Notice that J(e) satisfies the condition of Claim 4.5 for z. Hence by Claim 4.6 we have that J(z) = J(e). □

Claim 4.8. There are l ∈ ℕ and c_{1}, ..., c_{l} ∈ V (M) so that

V (M) = ⋃_{1≤j≤l}{x : J(x) = J(c_{j})}.

Proof. Since V (M) is definable in ℜ^{∘} we write V (M) = ⋃_{i=1}^{r} C_{i} where each C_{i} is a cell in ℜ^{∘}. Fix i ≤ r. Fix c ∈ C_{i} and let W = {x ∈ C_{i} : J(c) = J(x)}. To prove the claim we show that W = C_{i}. Note that W is definable in ℜ. By Claim 4.7 W is open in C_{i}. If W ≠ C_{i} then as C_{i} is a cell it is definably connected and thus W is not closed in C_{i}. Choose z ∈ (∂W ∩ C_{i}) \ W, where ∂W is the boundary of W. Such a point exists since otherwise W would be closed in C_{i}. Since z ∈ V (m) there is ϵ so that B(z, ϵ) ⊆ U(M). As z ∈ ∂W, there is some w ∈ W ∩ B(z, ϵ), and for such w we have that J(w) = J(c). By Claim 4.6 we have that J(w) = J(z) and hence J(z) = J(c) contradicting that z ∈ (∂W ∩ C_{i}) \ W. Hence W = C_{i}. □

It follows immediately from the display 1 and Claim 4.8 that for 1 ≤ i ≤ m there are elements e_{1}^{i}, ..., e_{r(i)}^{i} ∈ U(M^{∗}) so that if z ∈ U(M^{∗}) then

⋀_{\begin{matrix}1≤i≤m \\ 1≤k≤r(i) \end{matrix}} ψ_{i}(e_{k}^{i})) ∧ (ϕ(z) ∨ ⋁_{\begin{matrix}1≤i≤m \\ 1≤k≤r(i) \end{matrix}} f_{i}(z) = e_{k}^{i}).

With this, the proof of the Lemma 4.4 is complete. □

We are now ready to finish

Proof of Theorem 1.9. We show that if X ⊆ R^{n} is definable in ℜ_{P} then the interior int(X) of X is definable in ℜ. Without loss of generality we assume that ℜ_{P} is ω-saturated. As noted in the proof of Theorem 1.7 the quantifier elimination for T_{𝒫} and the fact that acl_{T} = dcl_{T} imply that X is a finite Boolean combination of sets definable in ℜ and sets of the form P f(z) where f is a function definable in ℜ, possibly of several variables. Thus X is definable by a conjunction of formulae of the form

σ(z) ∨ ⋁_{i=1}^{l} P f_{i}(z) ∨ ⋁_{j=l+1}^{m} ¬P f_{j}(z)

where σ is an ℒ-formula and f_{1} … f_{m} are ℜ-definable functions. Without loss of generality we assume that X is ∅-definable.

We begin by showing that

Claim 4.9. Let I_{0} ⊆ {x ∈ R : P x} and I_{1} ⊆ {x ∈ R : ¬P x} be finite sets. There is a function M : {1, ..., m} → ℕ such that for all d ∈ int(X) there are ϵ ∈ R and a_{k}^{i} ∈ dcl(d, ϵ) with 1 ≤ i ≤ m and 1 ≤ k ≤ M(i) so that a_{k}^{i} ∉ I_{0} ∪ I_{1} for all 1 ≤ i ≤ m and 1 ≤ k ≤ M(i) and for all z ∈ B(d, ϵ) one of the following holds:

(1) f_{i}(z) = f_{j}(z) for some 1 ≤ i ≤ l and l < j ≤ m;

(2) f_{i}(z) = c for some c ∈ I_{0} and 1 ≤ i ≤ l;

(3) f_{j}(z) = c for some c ∈ I_{1} and l < j ≤ m;

(4) f_{i}(z) = a_{k}^{i} for some 1 ≤ i ≤ m and 1 ≤ k ≤ M(i).

(5) σ(z).

Note that we allow for M(i) = 0, which just means that there are no a_{k}^{i}.

Proof. By the saturation of ℜ_{P} it suffices to show that for each d ∈ int(X) we can find an M satisfying the conditions of the claim. Fix d ∈ int(X) and choose ϵ so that B(d, ϵ) ⊆ int(X).

Let Γ(z) be the following set of formulae.

(a) z ∈ B(d, ϵ).

(b) For all c_{1}, …, c_{m} ∈ dcl(d, ϵ) ∪ I_{0} ∪ I_{1} with P c_{i} for 1 ≤ i ≤ l and ¬P c_{i} for l < i ≤ m the formula

f_{1}(z) ≠ c_{1} ∧ ⋯ ∧ f_{m}(z) ≠ c_{m}.

(c) f_{i}(z) ≠ f_{j}(z) for 1 ≤ i ≤ l and l < j ≤ m.

(d) ¬σ(z) We assert that Γ(z) is inconsistent. Indeed, suppose not and choose c realizing Γ. Let

J_{0} := {i : 1 ≤ i ≤ m and f_{i}(c) ∈ dcl(ϵ, d)}

and J_{1} = {1, ..., m} \ J_{0}. Note that since c ∈ X and realizes Γ we must have that either P f_{i}(c) holds for some 1 ≤ i ≤ l or ¬P f_{j}(c) holds for some l < j ≤ m and hence J_{1} ≠ ∅. Let J_{2} be a maximal subset of J_{1} so that if i, j ∈ J_{2} then f_{i}(c) ≠ f_{j}(c). For i ∈ J_{2} let

J_{1}^{i} := {j ∈ J_{1} : j ≠ i and f_{i}(c) = f_{j}(c)}.

Consider the following formula γ(\overline{y}) where \overline{y} is a tuple of variables y_{i} for i ∈ J_{2}:

γ(\overline{y}) := ∃z ∈ B(d, ϵ)( ⋀_{i∈J_{2}} f_{i}(z) = y_{i}∧ ⋀_{i∈J_{0}} f_{i}(z) = f_{i}(c)∧ ⋀_{i∈J_{2},j∈J_{1}^{i}} f_{i}(z) = f_{j}(z) ∧ ¬σ(z)).

Of course ⟨f_{i}(c) : i ∈ J_{2}⟩ realizes γ(\overline{y}). Also \{f_{i}(c) : i ∈ J_{2}\} ∩ dcl(ϵ, d) = ∅ and the elements of the set {f_{i}(c) : i ∈ J_{2}} are distinct. Hence by the genericity of P we find b_{i} for i ∈ J_{2} realizing γ so that if 1 ≤ i ≤ l then ¬P b_{i} and if l < i ≤ m then P b_{i}. Choose e ∈ B(d, ϵ) witnessing that \overline{b} realizes γ. Thus if 1 ≤ i ≤ l then ¬P f_{i}(e) and if l < j ≤ m then P f_{j}(e). Hence e ∉ X, a contradiction. So Γ(z) is inconsistent. Choose a finite Γ_{0} ⊆ Γ which is inconsistent. Using Γ_{0} we readily find the desired M and a_{k}^{i}. □

Claim 4.10. There is a finite set I ⊂ R so that for all z ∈ int(X) one of the following holds.

(1) For some 1 ≤ i ≤ l and some l < i′ ≤ m, f_{i}(z) = f_{i′}(z).

(2) For some 1 ≤ i ≤ l and c ∈ I, f_{i}(z) = c and P c.

(3) For some l < i′ ≤ m and c ∈ I, f_{i′}(z) = c and ¬P c.

(4) σ(z).

Proof. We show by induction on j ≤ m that there are finite sets I_{j} such that I_{j} ⊆ I_{j+1} and for all z ∈ int(X) there are J ⊆ {1, ..., m} of cardinality at least j and elements c_{i} ∈ I_{j} for i ∈ J so that one of the following holds:

(a) For some 1 ≤ i ≤ l and l < i′ ≤ m, f_{i}(z) = f_{i′}(z);

(b) f_{i}(z) = c_{i} for all i ∈ J;

(c) For some i ∈ J with 1 ≤ i ≤ l, P c_{i} and f_{i}(z) = c_{i}; (d) For some i ∈ J with l < i ≤ m, ¬P c_{i} and f_{i}(z) = c_{i};

(e) σ(z).

Assume now that the above holds for all j′ < j. Let K_{0} := {x ∈ I_{j−1} : P x} and K_{1} := I_{j−1} \ K_{0} = {x ∈ I_{j−1} : ¬P x}.

By Claim 4.9 there is M^{∗} : {1, ..., m} → ℕ such that int(X) is a subset of the set U(M^{∗}) of all x ∈ R for which there are ϵ and a_{k}^{i} for 1 ≤ i ≤ m and 1 ≤ k ≤ M^{∗}(i) so that

a_{k}^{i} ≠ c for all 1 ≤ i ≤ m, 1 ≤ k ≤ M^{∗}(i), and c ∈ I_{j−1}

and, for all z ∈ B(x, ϵ), one of the following holds:

(i) f_{i}(z) = f_{i′}(z) for some 1 ≤ i ≤ l and l < i′ ≤ m; (ii) f_{i}(z) = c for some 1 ≤ i ≤ l and c ∈ K_{0}; (iii) f_{i}(z) = c for some l < i ≤ m and c ∈ K_{1}; (iii) f_{i}(z) = a_{k}^{i} for some 1 ≤ i ≤ m and 1 ≤ k ≤ M^{∗}(i); (iv) σ(z).

Let ψ_{i} := ⋀_{c∈I_{j−1}} x ≠ c and let ϕ(x) be the disjunction over all J′ ⊆ {1, …, m} of size j − 1 and choices c_{i} ∈ I_{j−1} for i ∈ J′ of formulas asserting that conditions (a),(c),(d), and (e) hold for the particular choice of J′ ⊆ {1, …, m} and the c_{i}’s. We apply Lemma 4.4 to find elements e_{k}^{i} for 1 ≤ i ≤ m and 1 ≤ k ≤ M^{∗}(i) such that ψ_{i}(e_{k}^{i}) holds for all 1 ≤ i ≤ m and 1 ≤ k ≤ M^{∗}(i) and for all z ∈ U(M^{∗}) either ϕ(z) holds or f_{i}(z) = e_{k}^{i} for some 1 ≤ i ≤ m and 1 ≤ k ≤ M^{∗}(i). Let I_{j} := I_{j−1} ∪ {e_{k}^{i} : 1 ≤ i ≤ m and 1 ≤ k ≤ M^{∗}(i)}.

Suppose that z ∈ int(X). Since I_{j−1} ⊆ I_{j}, by induction hypothesis there is J′ ⊆ {1, ..., m} of cardinality at least j − 1 and c_{i} for i ∈ J′ for which conditions (a)–(e) hold for z. If there are J′ and c_{i} for i ∈ J′ such that one of conditions (a),(c),(d), or (e) holds for z then we may extend J′ to J arbitrarily and freely choose c_{i} for i ∈ J \ J′ to continue the induction. Hence we assume that for no choice of J′ and c_{i} for i ∈ J′ does z satisfy one of (a), (c), (d), or (e). Fix J′ and c_{i} for i ∈ J′ as guaranteed by induction hypothesis. For all i ∈ J′, we have that f_{i}(z) = c_{i}, and that ¬P c_{i} if 1 ≤ i ≤ l and P c_{i} if l < i ≤ m. By the definition of the elements e_{k}^{i}, for some 1 ≤ i^{∗} ≤ m and 1 ≤ k ≤ M^{∗}(i^{∗}) we have f_{i^{∗}}(z) = e_{k}^{i^{∗}} and e_{k}^{i^{∗}} ≠ c_{i} for all for i ∈ J′. In particular i^{∗} ∉ J′. We then set J = J′ ∪ {i^{∗}}.

When the induction is complete we have a finite set I_{m} so that for all z ∈ int(X) there are elements c_{i} ∈ I_{m} for i = 1, …, m so that one of (a)-(e) holds with J = {1, …, m}.

To finish the proof of Claim 4.10 set I = I_{m}. Let z ∈ int(X). By construction one of conditions (a)-(e) holds with J = {1, …, m}. Observe that the conclusion of the claim holds for z provided that z satisfies one of conditions (a),(c),(d), or (e) for some choice of c_{1}, …, c_{m} ∈ I. For contradiction assume that only condition (b) holds for z for all choices of c_{1}, …, c_{m} ∈ I. Let c_{i} ∈ I for i = 1, …, m be such that f_{i}(z) = c_{i} for all i. Since z ∈ X and condition (e) fails we must have that either P f_{i}(z) holds for some 1 ≤ i ≤ l or ¬P f_{i}(z) holds for some l < i ≤ m. In the first case condition (c) holds whilst in the second case (d) holds. In either case we have reached a contradiction, and the proof of the claim is complete. □

Finally we complete the proof of Theorem 1.9.

Fix I as in Claim 4.10. Let I_{0} = {x ∈ I : P x} and I_{1} = I \ I_{0}. Let Y consist of all z ∈ R^{n} so that one of the following holds:

(1) f_{i}(z) = f_{j}(z) for some 1 ≤ i ≤ l and l < j ≤ m;

(2) f_{i}(z) = c for some c ∈ I_{0} and 1 ≤ i ≤ l;

(3) f_{j}(z) = c for some c ∈ I_{1} and l < j ≤ m.

(4) σ(z). Notice that Y ⊆ X and that Claim 4.10 implies that int(X) ⊆ Y. Hence int(Y) = int(X) and thus int(X) is definable in ℜ. This ends the proof of Theorem 1.9. □

We close with the

Verification of Example 4.2. With all data there, repeat the argument of the proof of Theorem 1.9 up to the statement of Claim 4.9. Now, ℜ is of the form (ℜ_{0}, V), where ℜ_{0} ⊧ T̄ and V ⊆ R is T̄-convex. Since T̄^{c} has quantifier elimination and universal axiomatization, every function definable in (ℜ_{0}, V) is given piecewise by terms, which in turn are given by the functions that are ∅-definable in ℜ_{0}. Thus, by weak o-minimality, given a finite collection ℱ of unary functions definable in (ℜ_{0}, V) there are a finite collection 𝒢 of functions definable in ℜ_{0} and a finite partition 𝒞 of R into convex sets such that for all f ∈ ℱ and C ∈ 𝒞 we have f↾C = g↾C for some g ∈ 𝒢. Hence, if X has interior, then it contains an interval I such that the restrictions to I of the functions f_{1}, …, f_{m} in the expression ⋁_{i=1}^{l} P f_{i}(z) ∨ ⋁_{j=l+1}^{m} ¬P f_{j}(z) are definable in ℜ_{0}. To show that X has no interior is thus the same as if T̄^{c} were ominimal, so the rest of the proof goes through unchanged. The proof for o-minimal T is considerably easier, and can be obtained by appropriately modifying arguments found in [6] or [10].

References

[1] Jon Barwise and Abraham Robinson, Completing theories by forcing, Annals of Pure and Applied Logic 2 (1970), no. 2, 119–142.

[2] Gareth Boxall and Philipp Hieronymi, Expansions which introduce no new open sets, Journal of Symbolic Logic 77 (2012), 111–121.

[3] C.C. Chang and H.J. Keisler, Model theory, North-Holland Publishing Co., Amsterdam, 1990.

[4] Zoé Chatzidakis and Anand Pillay, Generic structures and simple theories, Annals of Pure and Applied Logic 95 (1998), 71–92.

[5] Alfred Dolich, A note on definable completeness and weak o-minimality, Notre Dame Journal of Formal Logic 48 (2007), 281–292.

[6] Alfred Dolich, Chris Miller, and Charles Steinhorn, Structures having o-minimal open core, Transactions of the American Mathematical Society 362 (2010), 1371–1411.

[7] , Expansions of o-minimal structures by independent sets, in preparation.

[8] Lou Van Den Dries, Dense pairs of o-minimal structures, Fundamenta Mathematicae 157 (1998), 61–78.

[9] Lou Van Den Dries and Adam H. Lewenberg, T -convexity and tame extensions, The Journal of Symbolic Logic 60 (1995), 74–102.

[10] Sergio Fratarcangeli, Expansions of o-minimal theories by generic sets, The Journal of Symbolic Logic 70 (2005), 1150–1160.

[11] Dugald Macpherson, David Marker, and Charles Steinhorn, Weakly o-minimal structures and real closed fields, Transactions of the American Mathematical Society 352 (2000), 5435–5483.

[12] Chris Miller and Patrick Speissegger, Expansions of the real line by open sets: o-minimality and open cores, Fundamenta Mathematicae 162 (1999), 193–208.

[13] Anand Pillay, First order topological structures and theories, Journal of Symbolic Logic 52 (1987), 763–778.

[14] A.J. Wilkie, An algebraically conservative, transcendental function, Paris 7 preprints (1998), no. 66.

Department of Mathematics and Computer Science, Chicago State University, Chicago, IL 60628

Current address: Department of Mathematics and Computer Science, Kingsborough Community College, 2001 Oriental Boulevard, Brooklyn NY 11235, USA

E-mail address: alfredo.dolich@kbcc.cuny.edu

Department of Mathematics, The Ohio State University, Columbus OH 43210, USA

E-mail address: miller@math.osu.edu

Department of Mathematics, Vassar College, Poughkeepsie NY 12604, USA

E-mail address: steinhorn@vassar.edu