AN UPGRADE TO “TAMENESS IN EXPANSIONS OF THE REAL FIELD”

CHRIS MILLER

Abstract. What might it mean for a first-order expansion of the field of real numbers to be tame or well behaved? In recent years, much attention has been paid by model theorists and real-analytic geometers to the o-minimal setting: expansions of the real field in which every definable set has finitely many connected components. But there are expansions of the real field that define sets with infinitely many connected components, yet are tame in some well-defined sense (e.g., the topological closure of every definable set has finitely many connected components, or every definable set has countably many connected components). The analysis of such structures often requires a mixture of model-theoretic, analytic-geometric and descriptive set-theoretic techniques. An underlying idea is that first-order definability, in combination with the field structure, can be used as a tool for determining how complicated is a given set of real numbers.

Throughout, m and n range over ℕ (the non-negative integers).

Given a first-order structure 𝔐 with underlying set M, “definable” (in 𝔐) means “definable in 𝔐 with parameters from M” unless otherwise noted. If no ambient space M^{n} is specified, then “definable set” means “definable subset of some M^{n}”. I use “reduct” and “expansion” in the sense of definability, that is, given structures 𝔐_{1} and 𝔐_{2} with common underlying set M, I say that 𝔐_{1} is a reduct of 𝔐_{2}—equivalently, 𝔐_{2} is an expansion of 𝔐_{1}, or 𝔐_{2} expands 𝔐_{1}—if every set definable in 𝔐_{1} is definable in 𝔐_{2}. For the most part, we shall be concerned with the definable sets of a structure, so we identify 𝔐_{1} and 𝔐_{2} if they are interdefinable (that is, each is a reduct of the other). An expansion 𝔐 of a dense linear order (M, <) is o-minimal if every definable subset of M is a finite union of points and open intervals.

From now on, ℜ denotes a fixed, but arbitrary, expansion of the real line (ℝ, <). “Definable” means “definable in ℜ” unless noted otherwise. The real field (ℝ, +, ·) is denoted by \overline{ℝ}.

The sequel consists of two parts: Part 1 is mostly expository and somewhat informal; technical details and proofs are mostly deferred to Part 2. General references for background include: van den Dries [9] (a model-theoretic survey of o-minimality) and [12] (a text on topological o-minimality, with essentially no model theory); van den Dries and Miller [13] (focussing on the analytic geometry of o-minimal expansions of \overline{ℝ}); and anything along the lines of Hausdorff [23], Kechris [27], Kuratowski [29] and Oxtoby [41]. Please note: I attempt neither to cite only original sources nor to provide an historical survey.

Numbering. Lemmas, propositions, theorems and corollaries are not numbered explicitly if they appear singly within a section or subsection (or perhaps if they are not referred to later in the paper). For example, if there is one theorem in §5, then it will not be numbered, but referred to later as Theorem 5; if there are two propositions in §3.2, then they will be labelled as Propositions 3.2.1 and 3.2.2 respectively (and so on).

January 19, 2017. The original version of this paper appears in Logic Colloquium ’01 (Vienna), Lecture Notes in Logic vol. 20, ASL, Urbana, 2005, 281–316. Bibliography has been updated and expanded, and I have added several footnotes to better reflect the current state of the art.

Part 1

1. Introduction

What might it mean for a first-order expansion of \overline{ℝ} to be tame or well behaved? In recent years, much attention has been paid by model theorists and real-analytic geometers to the o-minimal setting: expansions of \overline{ℝ} in which every definable subset of ℝ is a finite union of points and open intervals; indeed, for any fixed p ∈ ℕ, every definable set is a finite disjoint union of connected embedded C^{p}-submanifolds, each of which is definable. But there are expansions of \overline{ℝ} that define sets having infinitely many connected components (even locally), yet are tame in some well-defined sense.

1.1. Consider the following structures:

• \overline{ℝ}

• (\overline{ℝ}, 2^{ℤ}), where 2^{ℤ} = \{ 2^{k} : k ∈ ℤ \}

• (\overline{ℝ}, Fib), where Fib = \{ Fibonacci numbers \}

• (\overline{ℝ}, ψ), where ψ: ℝ^{2} → ℝ is defined by

(x, y) ↦ \begin{cases}2^{(log_{2} x)(log_{2} y)} & if x, y ∈ 2^{ℤ} \\ 0 & otherwise. \end{cases}

• (\overline{ℝ}, S), where S = \{ (e^{t} cos t, e^{t} sin t) : t ∈ ℝ \}

• (\overline{ℝ}, ℝ_{alg}), where ℝ_{alg} denotes the set of all real algebraic numbers

• (\overline{ℝ}, ℤ) Now, \overline{ℝ} is o-minimal, and is generally considered to be very well behaved. The study of

its definable sets leads to the subject of real algebraic geometry (see Bochnak et al. [3]). At the other end, the structure (\overline{ℝ}, ℤ) may be identified with the real projective hierarchy of classical descriptive set theory, that is, A ⊆ ℝ^{n} is definable in (\overline{ℝ}, ℤ) if and only A is projective (see [27, (37.6)] and [12, pg. 16]). From now on, we write PH instead of (\overline{ℝ}, ℤ). PH is quite complicated. Many set-theoretic independence issues arise naturally in the study of its definable sets; for example, the statement that every real projective set is Lebesgue measurable is independent of ZFC. (Of course, compared to arbitrary sets in ℝ^{n}, projective sets might be regarded as rather tame). All of the structures listed above are reducts of PH.

It follows from [6, Theorem III] that every subset of ℝ definable in (\overline{ℝ}, 2^{ℤ}) is the union of an open (definable) set and finitely many (definable) discrete sets; indeed, this holds with 2^{ℤ} replaced by α^{ℤ} (= \{ α^{k} : k ∈ ℤ \}) for any α > 0. Hence, ℚ is not definable in (\overline{ℝ}, 2^{ℤ}), so neither is ℤ. In other words, (\overline{ℝ}, 2^{ℤ}) is a proper reduct of PH. Moreover, Th(\overline{ℝ}, 2^{ℤ}) is decidable [6, Theorem I].

Every subset of ℝ definable in (\overline{ℝ}, Fib) is also the union of an open set and finitely many discrete sets, because Fib is definable in (\overline{ℝ}, φ^{ℤ}), where φ = (1 + \sqrt{5})/2. (Note that

Fib = \{ (φ^{2n} − φ^{−2n})/\sqrt{5} : n ≥ 1 \} ∪ \{ (φ^{2n+1} + φ^{−2n−1})/\sqrt{5} : n ≥ 0 \}.)

An isomorphic copy of (ℤ, +, ·) is definable in (\overline{ℝ}, ψ), namely

( 2^{ℤ}, ·↾(2^{ℤ} × 2^{ℤ}), ψ↾(2^{ℤ} × 2^{ℤ}) ).

(Here and throughout, given a map f: X → Y and A ⊆ X, f↾A denotes the restriction of f to A.) By comparison with PH, one might think (\overline{ℝ}, ψ) would be quite complicated. Of course, Th(\overline{ℝ}, ψ) is undecidable, but what about the definable sets? We shall see that, like (\overline{ℝ}, 2^{ℤ}), every subset of ℝ definable in (\overline{ℝ}, ψ) is the union of an open set and finitely many discrete sets.

The set S is an infinite spiral and a trajectory of the linear vector field

(x, y) ↦ (x − y, x + y): ℝ^{2} → ℝ^{2}.

The natural parameterization of S involves the exponential, sine and cosine functions, but none of these functions are definable in (\overline{ℝ}, S) (as we shall see later). Indeed, again, every subset of ℝ definable in (\overline{ℝ}, S) is the union of an open set and finitely many discrete sets.

(More properties of the structures (\overline{ℝ}, α^{ℤ}), (\overline{ℝ}, ψ) and (\overline{ℝ}, S) are established in sections 3 and 4.)

Now, ℝ_{alg} is dense and co-dense in ℝ, so certainly not the union of an open set and finitely many discrete sets. But (\overline{ℝ}, ℝ_{alg}) is, loosely speaking, topologically almost o-minimal: By [11, Theorem 4], every closed definable subset of ℝ is a finite union of points and open intervals. This has nice consequences for all definable sets (to be made precise in §5). In particular, ℤ is not definable in (\overline{ℝ}, ℝ_{alg}).

1.2. The properties of the structures (\overline{ℝ}, 2^{ℤ}) and (\overline{ℝ}, ℝ_{alg}) suggest that we look beyond o-minimality for other kinds of tame behavior. First, let us consider some notions already in use by model theorists or analytic geometers.

An expansion 𝔐 of a dense linear order (M, <) is weakly o-minimal if every definable subset of M is a finite union of convex definable sets, and is locally o-minimal if for every definable A ⊆ M and x ∈ M, there exist a, b ∈ M such that a < x < b and A ∩ (a, b) is a finite union of points and open intervals. Of course, if M = ℝ, then 𝔐 is weakly o-minimal if and only if it is o-minimal, since a convex subset of the real line is just an interval of some sort. Now, there are expansions of the real line that that are locally o-minimal but not o-minimal—(ℝ, <, +, ℤ) is one; see e.g. Friedman and Miller [20]—but every locally o-minimal expansion of \overline{ℝ} is o-minimal (the proof is an exercise). Consequently, for expansions of \overline{ℝ}, neither weak nor local o-minimality yields any generality beyond o-minimality. There are yet more exotic variations—for examples, see Belegradek et al. [1] and Macpherson [32]—but they either do not generalize o-minimality for expansions of \overline{ℝ} or are not enough topologically based for present purposes (some do not even make sense over ℝ).

Based on differential- and analytic-geometric considerations, useful forays have been made beyond the realm of first-order structures—for example, geometric categories [13] and Shiota’s 𝔛-systems [49]—but still, all sets dealt with have locally only finitely many connected components.

Another natural model-theoretic condition we might impose on ℜ is uniform finiteness: for each definable A ⊆ ℝ^{m+n}, there exists N_{A} ∈ ℕ such that for every x ∈ ℝ^{m}, the set { y ∈ ℝ^{n} : (x, y) ∈ A } is finite only if it contains at most N_{A} elements. Every o-minimal structure has the uniform finiteness property, but so does (\overline{ℝ}, ℝ_{alg}) [11, Corollary 4.5]. If ℜ expands \overline{ℝ} and has the uniform finiteness property, then—like (\overline{ℝ}, ℝ_{alg})—every closed definable set is a finite union of points and open intervals (see Proposition 5.2 below); in particular, ℜ defines no infinite discrete sets.

1.3. The approach taken in this paper is to work with first-order structures on (ℝ, <) under various topological, measure- or descriptive set-theoretic assumptions, with special emphasis on expansions of \overline{ℝ} that define infinite discrete sets. Now, “topological definability theory” is certainly not new; see e.g. A. Robinson [44] or Pillay [42] (and basic o-minimality as exposed in [12] may be regarded as topological definability theory). However, unlike most model-theoretic investigations, we do not shy away from making full use of special facts about the real numbers: uncountability, completeness, separability of the topology, measure theory, descriptive set theory, and so on (indeed, some proofs rely so heavily on the combination of separability and the Baire category theorem that I would not know how to avoid it). This approach is not particularly new in the study of o-minimal expansions of \overline{ℝ} either, but here we focus on moving beyond o-minimality. (In addition to the abovementioned [6, 11, 20], a first paper in this direction is Miller and Speissegger [38].)

I regard many of the results herein as preliminary or suggestive of further lines of inquiry. A number of questions are scattered throughout. Probably, some are relatively easy, but many appear to be quite hard. Possibly, some are independent of ZFC (but I have tried to avoid asking such questions). Many are posed for arbitrary expansions of the real line, but I am interested primarily in the answers for expansions of \overline{ℝ}.

Here is an outline of the remainder of Part 1. Some topological preliminaries are established in §2. In §3, we consider some conditions, more general than o-minimality, to impose on the definable subsets of ℝ, and investigate some corresponding consequences for all definable sets. Fundamental to the study of o-minimal structures are the notions of “cell” and “decomposition”. By relaxing the definition of decomposition, we obtain tameness conditions that make sense for any definable set (as opposed to just the definable subsets of the line); see §4. We go further in §5 by relaxing the definition of cell, via the notion of the open core of a structure. Some structures that are interdefinable with PH are given in §6.^{1}

2. Topological preliminaries

Let X be a topological space. Equip cartesian powers X^{m} with the product topology. (X^{0} = {∅}; regard a map f: X^{0} → X^{n} as the corresponding constant f(∅).) If A ⊆ X^{m} × X^{n}, then πA denotes the projection of A on the first m coordinates; for x ∈ X^{m}, put

A_{x} = { y ∈ X^{n} : (x, y) ∈ A },

the fiber of A over x. Whenever convenient, we identify X^{m} × X^{n} with X^{m+n}. Let A ⊆ X.

1See [36] for some necessary conditions for avoiding PH in expansions of \overline{ℝ} by sequences. See also [26] for significant recent developments.

Put:

int(A) = the interior of A
cl(A) = the closure of A
bd(A) = the boundary of A ( = cl(A) \ int(A) )
fr(A) = the frontier of A ( = cl(A) \ A)
isol(A) = the isolated points of A

If X = ℝ^{n} and A ⊆ ℝ^{n} is definable, then so are each of the above sets. (This does not depend on working over ℝ, rather, only that the collection of all open boxes in ℝ^{n} is a definable family.) We say that A:

• is constructible if it is a (finite) boolean combination of open sets.

• is discrete if A = isol(A).

• has no interior if int(A) = ∅ and has interior if int(A) ≠ ∅.

• is dense if cl(A) = X, co-dense if cl(X \ A) = X, somewhere dense if cl(A) has interior, and nowhere dense if cl(A) has no interior.

• is meager if it is countable union of nowhere dense sets. For x ∈ A, A is locally closed at x if there is an open neighborhood U of x such that

A ∩ U = cl(A) ∩ U; A is locally closed if A is locally closed at each x ∈ A. It is easy to check that the following are equivalent:

• A is locally closed.

• A = cl(A) ∩ U for some open U.

• A = F ∩ U for some open U and closed F.

• fr(A) is closed.

• A ∩ cl(fr(A)) = ∅. If X = ℝ^{n} and A ⊆ ℝ^{n} is definable and locally closed, then A = cl(A) ∩ U for some definable open U ⊆ ℝ^{n}; see e.g. [12, pg. 18] or [13, Appendix B].

Let lc(A) denote the set of all locally closed points of A, equivalently, lc(A) = A\cl(fr(A)). Note that lc(A) is locally closed and is the relative interior of A in cl(A). We say that A has a locally closed point if lc(A) ≠ ∅.

For ordinals λ, define sets A^{(λ)} as follows:

A^{(0)} = A
A^{(λ+1)} = A^{(λ)} \ lc(A^{(λ)})
A^{(λ)} = A \ ⋃_{μ<λ} lc(A^{(μ)}) if λ is a limit.

If B ⊆ X^{m+n} and x ∈ X^{m}, then B_{x}^{(λ)} denotes (B_{x})^{(λ)}, not (B^{(λ)})_{x}. (There is an obvious notion of rank arising from this construction, but we shall not bother to define it formally.) If X = ℝ^{n} and A ⊆ ℝ^{n} is definable, then so is each A^{(k)}, k ∈ ℕ.

2.1. The following are equivalent:

(1) A is constructible.

(2) There exists k ∈ ℕ such that A^{(k)} = ∅.

(3) There exists k ∈ ℕ such that A = ⋃_{j=0}^{k} lc(A^{(j)}).

(4) A is a finite disjoint union of locally closed sets.

(For 1⇒2, see Dougherty and Miller [5]. Indeed, if j ∈ ℕ is such that A is boolean combination of 2j open sets, then A^{(j+1)} = ∅.)

2.2 ([23, §30] or [29, §34, VI]). If X is a Polish space, then A ∈ F_{σ} ∩ G_{δ} if and only if there is a countable ordinal λ such that A^{(λ)} = ∅. In particular, if ∅ ≠ A ∈ F_{σ} ∩ G_{δ}, then lc(A) ≠ ∅.

For ordinals λ, define sets A^{[λ]} as follows:

A^{[0]} = A
A^{[λ+1]} = A^{[λ]} \ isol(A^{[λ]})
A^{[λ]} = A \ ⋃_{μ<λ} isol(A^{[μ]}) if λ is a limit.

If B ⊆ X^{m+n} and x ∈ X^{m}, then B_{x}^{[λ]} denotes (B_{x})^{[λ]}, not (B^{[λ]})_{x}. The Cantor-Bendixson rank (often defined only for closed sets) arises from this construction. Note that isol(A) = isol(cl(A)), so A^{[λ]} = ∅ if cl(A)^{[λ]} = ∅, but the converse need not hold. If X = ℝ^{n} and A ⊆ ℝ^{n} is definable, then so is each A^{[k]} for k ∈ ℕ.

2.3. The set A is the union of an open set and finitely many discrete sets if and only if there exists k ∈ ℕ such that (A \ int(A))^{[k]} = ∅.

(The proof is an exercise.)

We make frequent (but often without explicit mention) use of the following consequences of 2.1 and 2.3.

2.4. A definable set is:

• constructible if and only it is a finite disjoint union of locally closed definable sets.

• the union of an open set and finitely many discrete sets if and only if it is the disjoint union of an open definable set and finitely many discrete definable sets.

The dimension of a nonempty set A ⊆ X^{n}, denoted by dim A, is the maximal integer d such that, after some permutation of coordinates, the projection of A on the first d coordinates has interior. (Put dim ∅ = −∞ and X^{−∞} = ∅.) Clearly, if A ⊆ B ⊆ X^{n}, then dim A ≤ dim B.

Let Π(n, m) denote the collection of all coordinate projection maps

(x_{1}, …, x_{n}) ↦ (x_{λ(1)}, …, x_{λ(m)}) : X^{n} → X^{m},

where λ is a strictly increasing function from {1, …, m} into {1, …, n}. If d ∈ ℕ and A ⊆ X^{n}, then dim A ≥ d if and only if there exists μ ∈ Π(n, d) such that μA has interior.

From now on, unless otherwise noted, “box” means “nonempty open box” and topological notions will be taken with respect to the box topologies induced by the order topology of the real line.

3. Tameness conditions on definable subsets of the line

In this section, we consider various conditions to impose on the definable subsets of ℝ, and begin to investigate the corresponding consequences for all definable sets.

3.1. Many candidates for tameness conditions on ℜ imply that every definable subset of ℝ either has interior or is nowhere dense.

Conditions. Every definable subset of ℝ:

(1) has interior or is finite.

(2) has interior or is a finite union of discrete sets.

(3) is constructible.

(4) has interior or is countable.

(5) has interior or an isolated point (or is empty).

(6) has interior or is null (that is, has Lebesgue measure 0).

(7) is F_{σ}.

(8) has a locally closed point (or is empty).

(9) has interior or is nowhere dense.

Proposition. 1⇒2⇒(3 & 4). 3⇒7. 4⇒(5 & 6 & 7). 5⇒8. 6⇒9. 7⇒8⇒9.

Proof. Most of these implications are obvious. (Observe that if A ⊆ ℝ is dense and co-dense in an open interval I, then lc(A ∩ I) = ∅ and: at most one of A ∩ I, A \ I is countable; at most one of A ∩ I, A \ I is meager; and at most one of A ∩ I, A \ I is null.) For 4⇒5, recall that every nonempty perfect subset of ℝ is uncountable. For 7⇒8, use 2.2. □

Question. (\overline{ℝ}, 2^{ℤ}) witnesses 2⇏1. Do the other converse implications fail?^{2}

Lifting the conditions. Condition 1 holds if and only if ℜ is o-minimal, so an assumption on the definable subsets of ℝ implies that all definable sets have certain nice properties. What might the other conditions listed above imply about all definable sets?

3.2. Constructibility. Rather than working sequentially through the list, we start with what is probably the best known of these “lifting questions”:

Question 3.2.1. If every definable subset of ℝ is constructible, is every definable set constructible?

As far as I know, even the following weaker version is still open:

Question 3.2.2. If for every 𝔐 ≡ ℜ, every subset of M definable in 𝔐 is constructible, is every set definable in ℜ constructible?

Why doesn’t the stronger assumption seem to help? First, a routine compactness argument (using 2.1) shows that Question 3.2.2 is equivalent to:

Question 3.2.3. Suppose that for every m and definable A ⊆ ℝ^{m+1} there exists N ∈ ℕ such A_{x}^{(N)} = ∅ for all x ∈ ℝ^{m}. Does it follow that for every m and definable A ⊆ ℝ^{m+1} there exists N ∈ ℕ such (A^{(N)})_{x} = ∅ for all x ∈ ℝ^{m}?

Now let F ⊆ [0, 1]^{2} be closed and σ be a permutation of [0, 1]. Put A = F \ graph(σ); then every fiber A_{x}—as well as every set { x ∈ ℝ : (x, y) ∈ A }—is locally closed. Certainly, it can happen that lc(A) = ∅, even if F is nowhere dense (indeed, take F to be an arbitrary Cantor subset of the unit cube). And, of course, one can remove from F much more complicated sets than the graph of a permutation of [0, 1]. Such constructions appear to make unlikely a positive answer to Question 3.2.2, as well as to the obvious lifting question associated to Condition 8. However, if we rule out wild behavior by the dimension 0 definable sets, then we begin to obtain some positive results.

2It is shown in [19] that 9⇏ 8. It follows from the proof of [26, 5.1] that 4⇏ 3.

Proposition. If every dimension 0 definable set has a locally closed point, then A^{(1)} is nowhere dense in A, for every definable set A.

(See §8.1 for the proof.)

Hence, if every dimension 0 definable set has a locally closed point, then for any definable set A we have:

A = lc(A) ∪ A^{(1)}
= lc(A) ∪ lc(A^{(1)}) ∪ A^{(2)}
⋮
= lc(A) ∪ ⋯ ∪ lc(A^{(k)}) ∪ A^{(k+1)}
⋮

where lc(A^{(k)}) ≠ ∅ or A^{(k+1)} = ∅. Of course, in general, there is no reason to believe that this process terminates after finitely many iterations—that A is constructible—even if dim A = 0. This suggests trying a weaker formulation of Question 3.2.2, and finally we have a reasonable result:

Theorem. Suppose that for every 𝔐 ≡ ℜ, every dimension 0 set definable in 𝔐 is constructible. Then every set definable in ℜ is constructible.

(See §8.2 for the proof.) The converse also holds. The assumption is equivalent to: For every m, n and definable A ⊆ ℝ^{m+n} there exists N ∈ ℕ such that for all x ∈ ℝ^{m} either dim A_{x} > 0 or A_{x}^{(N)} = ∅.

3.3. The proof of Theorem 3.2 uses special facts about ℝ. Moreover, the most natural way to construct a proof is via results that are established first for the “interior or nowhere dense” condition. Hence, we jump to the end of the list.

Convention. From now on, p ranges over ℕ.

Theorem. Suppose every definable subset of ℝ has interior or is nowhere dense. Then every definable set has interior or is nowhere dense. If U ⊆ ℝ^{m} is open and f: U → ℝ is definable, then there is an open definable V ⊆ U such that U \ V is nowhere dense and the restriction f↾V : V → ℝ is continuous. If m = 1, then V may be chosen so that for each connected component I of V, f↾I is either constant or strictly monotone. If moreover ℜ expands \overline{ℝ}, then the above holds with “C^{p}”in place of “continuous”(so

⋂_{p∈ℕ}{ x ∈ U : f is C^{p} on an open ball about x }

is dense-G_{δ} in U).

(See §8.3 for the proof.)

3.4. Smoothness and d-minimality. “Submanifold” always means “embedded submanifold, everywhere of the same dimension, but not necessarily connected”. For A ⊆ ℝ^{n}, let reg^{p}(A) denote the set of a ∈ A such that for some d ∈ ℕ, μ ∈ Π(n, d) and box U about a, μ↾(A ∩ U) maps A ∩ U C^{p}-diffeomorphically onto an open subset of ℝ^{d}. (A C^{0}-diffeo-morphism is just a homeomorphism.) Note that reg^{p}(A) is open in A and is a finite disjoint union of C^{p}-submanifolds of ℝ^{n}. If dim A = 0, then reg^{p}(A) = isol(A). If A is open, then reg^{p}(A) = A. If A is definable, then reg^{0}(A) is definable; if moreover ℜ expands \overline{ℝ}, then each reg^{p}(A) is definable (see e.g. [13, Appendix B]).

Proposition. If every dimension 0 definable subset of ℝ has an isolated point, then A \ reg^{0}(A) is nowhere dense in A, for every definable set A. If moreover ℜ expands \overline{ℝ}, then this holds for each p (so ⋂_{p∈ℕ} reg^{p}(A) is dense-G_{δ} in A).

(See §8.4 for the proof.)

Informally, the above says that if ℜ expands \overline{ℝ} and defines no Cantor subsets of the line, then every definable set is something like a countable union of C^{∞}-submanifolds: For every fixed p and definable set A, we have:

A = reg^{p}(A) ∪ (A \ reg^{p}(A))
= reg^{p}(A) ∪ reg^{p}(A \ reg^{p}(A)) ∪ (A \ reg^{p}(A \ reg^{p}(A)))
⋮

Again, there is no apparent reason to believe that this process stabilizes after finitely many iterations (consider (\overline{ℝ}, E), where E is a countable closed subset of ℝ with infinite Cantor-Bendixson rank). Naturally, we might prefer that it does.

Now, Condition 2 may be rephrased as: Every definable subset of ℝ is a finite disjoint union of particularly nice C^{p}-submanifolds, each of which is definable. This condition does lift to all definable sets if we assume some extra uniformity (but I don’t know if the extra assumption is necessary). We need some definitions before we can make this precise.

I say that ℜ is d-minimal (short for “discrete-minimal”) if for every 𝔐 ≡ ℜ, every subset of M definable in 𝔐 is the union of an open set and finitely many discrete sets. Equivalently (by a routine compactness argument), ℜ is d-minimal if for every m and definable A ⊆ ℝ^{m+1} there exists N ∈ ℕ such that for all x ∈ ℝ^{m}, A_{x} either has interior or is a union of N discrete sets. Note that if ℜ is d-minimal, then every reduct of ℜ over (ℝ, <) is d-minimal.

Aside. The notion of d-minimality makes sense as stated for expansions of arbitrary firstorder topological structures (as defined in [42]) but it is unclear to me how useful it would be (even over arbitrary real closed fields). In this paper, every interesting fact established about d-minimality seemingly depends on working over ℝ. In any case, here I only scratch the surface of the subject; another paper is in preparation.^{3}

Let us say that a d-dimensional C^{p}-submanifold M of ℝ^{n} is special if there exists μ ∈ Π(n, d) such that for each y ∈ μM there is an open box B about y such that each connected component X of M ∩ μ^{−1}(B) projects C^{p}-diffeomorphically (via μ↾X) onto B, i.e., μ↾M: M → μM is a C^{p}-smooth covering map. (For d = 0 or d = n, every dimension d submanifold of ℝ^{n} is special: a dimension 0 submanifold of ℝ^{n} is just a discrete set; a dimension n submanifold of ℝ^{n} is just an open set.) If we wish to keep track of the projection μ, then say that M is μ-special. Note that if M is μ-special and S ⊆ μM is simply connected, then (after some permutation of coordinates) M ∩ μ^{−1}(S) is a countable disjoint union of graphs of C^{p} maps S → ℝ^{n−d}.

3I never produced a single such paper. I concentrated at first on producing examples that would justify more general investigation ([21, 40]), then got distracted by other issues. Meanwhile, Antongiulio Fornasiero worked extensively on d-minimality in a more abstract setting (expansions of “definably comnplete” ordered fields). While doing so, he found a flaw in the proof of Theorem 3.4.1 below; this was only recently repaired [50]. See also [39].

A collection A of subsets of ℝ^{n} is compatible with a collection B of subsets of ℝ^{n} if for every A ∈ A and B ∈ B, either A is contained in B or A is disjoint from B. A set A ⊆ ℝ^{n} is compatible with B if {A} is compatible with B, and similarly for A being compatible with a set B ⊆ ℝ^{n}.

Theorem 3.4.1. ^{4} Assume ℜ is d-minimal. Let A be a finite collection of definable subsets of ℝ^{n}. Then there is a finite partition of ℝ^{n} into special C^{0}-submanifolds, each of which is definable and compatible with A. If ℜ expands \overline{ℝ}, then the above holds with “C^{p}”in place of “C^{0}”.

(See §8.5 for the proof.) More can be said if ℜ expands (ℝ, <, +), as we shall see in the next section. But first we consider some examples.^{5}

Clearly, every o-minimal structure is d-minimal, but more is true: every locally o-mini-mal expansion of (ℝ, <) is d-minimal (since every definable subset of ℝ has interior or is discrete).

The field of exponents of an expansion of \overline{ℝ} is the set of all r ∈ ℝ such that the power function t ↦ t^{r}: (0, ∞) → ℝ is definable.

Theorem 3.4.2. Suppose α > 0 and ℜ is o-minimal, expands \overline{ℝ} and has field of exponents ℚ. Then (ℜ, α^{ℤ}) is d-minimal.

(See §8.6 for the proof.) \overline{ℝ} is o-minimal and has field of exponents ℚ—this is an easy consequence of quantifier elimination (in the language of ordered rings)—but there are far more exotic examples; see van den Dries and Speissegger [14, 15] and Rolin et al. [47].

Note. There is a converse of sorts: Every proper subgroup of (ℝ^{>0}, ·) is either cyclic or both dense and co-dense in (0, ∞), so if α > 1 and r is irrational, then the set { xy^{r} : x, y ∈ α^{ℤ} } is dense and co-dense in the positive real line. Hence, if ℜ is an expansion of (ℝ, +, ·, α^{ℤ}) such that every definable set has interior or is nowhere dense, then ℜ has field of exponents ℚ and every proper definable subgroup of (ℝ^{>0}, ·) is of the form α^{qℤ} for some q ∈ ℚ.

Corollary (joint with P. Speissegger). (\overline{ℝ}, S) is d-minimal, where S is the infinite spiral defined in §1.1.

Proof. The structure ℝ^{RE} := (\overline{ℝ}, exp ↾[0, 2π], sin ↾[0, 2π]) is o-minimal and has field of exponents ℚ; see [7]. (Here and throughout, exp denotes the function t ↦ e^{t}: ℝ → ℝ.) Note that cos ↾[0, 2π] is definable. Put α = e^{2π}. Then

(x, y) ∈ S ⇔ ∃g ∈ α^{ℤ}, ∃t ∈ [0, 2π), x = ge^{t} cos t & y = ge^{t} sin t.

4A flaw was found by Fornasiero in my proof of this; so far, it has only been repaired for the case that ℜ expands (ℝ, <, +) and either defines a pole or all of the sets in A are bounded. More details are in later footnotes at the appropriate places in the proof.

5See also [21, 40].

Hence, S is definable in (ℝ^{RE}, α^{ℤ}). Apply Theorem 3.4.2. □

Remarks.

• The restriction of exp to any bounded interval is definable in ℝ^{RE}, so the argument goes through for any spiral { (e^{at} cos t, e^{at} sin t) : t ∈ ℝ }, a ≠ 0.

• No restriction to an unbounded interval I of any of exp, sin or exp · sin is definable in any d-minimal expansion of (\overline{ℝ}, S): We have

(\overline{ℝ}, sin ↾I) = (\overline{ℝ}, exp · sin ↾I) = PH

(since I ∩ πℤ = { t ∈ I : sin t = 0 } = { t ∈ I : e^{t} sin t = 0 }). The group e^{2πℤ} is definable in (\overline{ℝ}, S) and (\overline{ℝ}, e^{2πℤ}, exp ↾I) = PH (exp is definable over \overline{ℝ} from exp ↾I, hence so is log: (0, ∞) → ℝ).

• ℝ^{RE} is of interest in its own right; see [8]. The next result produces some rather exotic examples built on some of those that we

have obtained so far. Let E ⊆ ℝ. Put S_{0} := {ℝ^{0}, ∅}. Let S_{n+1} be the collection of all subsets of ℝ^{n+1} of the form

A = ⋃_{α∈I} ⋂_{u∈P_{α}} Y_{u}

where m ∈ ℕ, (P_{α})_{α∈I} is an indexed family of subsets of the cartesian power E^{m}, and Y is of one of the following forms:

X × ℝ
{ (x, t) ∈ ℝ^{n+1} : x ∈ X & f(x) = t }
{ (x, t) ∈ ℝ^{n+1} : x ∈ X & f(x) < t }
{ (x, t) ∈ ℝ^{n+1} : x ∈ X & t < g(x) }
{ (x, t) ∈ ℝ^{n+1} : x ∈ X & f(x) < t < g(x) }

where X ⊆ ℝ^{n} is definable in ℜ and f, g: ℝ^{n} → ℝ are functions definable in ℜ. There are no conditions on the functions f, g other than definability, and the index sets I are allowed to be completely arbitrary. Let (ℜ, E)^{∞} denote the expansion of ℜ by all elements of each S_{k} (k ≥ 1). Every set definable in ℜ, as well as every subset of any E^{k} (k ≥ 1), is definable in (ℜ, E)^{∞}. Of course, if E is finite, then the construction is of no interest—we just wind up with ℜ—so we take E to be infinite. (On the other hand, it’s not hard to see that if ℜ defines a function f: ℝ^{n} → ℝ such that f(E^{n}) is dense, then each S_{k} is equal to the power set of ℝ^{k}, so again the construction is of no further interest.)

Theorem (joint with H. Friedman, [20]). Suppose ℜ is an o-minimal expansion of (ℝ, <, +). Let A ⊆ ℝ^{m+1} be definable in (ℜ, E)^{∞}. Then there exist l ∈ ℕ and f: ℝ^{l+m} → ℝ definable in ℜ such that for every x ∈ ℝ^{m} either A_{x} has interior or

A_{x} ⊆ cl{ f(u, x) : u ∈ E^{l} }.

(The above is not stated explicitly in [20], but follows from the claim there on page 62.)

Corollary. Suppose ℜ is an o-minimal expansion of (ℝ, <, +), E has no interior and (ℜ, E) is d-minimal. Then (ℜ, E)^{∞} is d-minimal.

Proof. Since E has no interior and (ℜ, E) is d-minimal, E is a finite union of discrete sets, hence countable. For any l, m ∈ ℕ, f: ℝ^{l+m} → ℝ definable in ℜ and x ∈ ℝ^{m}, the set { f(u, x) : u ∈ E^{l} } is countable and definable in (ℜ, E), so it is a finite union of discrete sets. Then the same is true of cl{ f(u, x) : u ∈ E^{l} }. By d-minimality, there exists N ∈ ℕ independent of x such that cl{ f(u, x) : u ∈ E^{l} } is a union of N discrete sets. Apply the theorem. □

By combining with Theorem 3.4.2:

Corollary. Suppose α > 0 and ℜ is o-minimal, expands \overline{ℝ} and has field of exponents ℚ. Then (ℜ, α^{ℤ})^{∞} is d-minimal.

Corollary. (\overline{ℝ}, ψ) (as defined in §1.2) is d-minimal.

Proof. (\overline{ℝ}, 2^{ℤ})^{∞} is d-minimal and (\overline{ℝ}, ψ) is a reduct of (\overline{ℝ}, 2^{ℤ})^{∞}. □

Question. Suppose every definable subset of ℝ either has interior is a finite union of discrete sets. Is ℜ d-minimal? What if ℜ expands \overline{ℝ}?

3.5. Countability. C^{0}-submanifolds of ℝ^{n} have only countably many connected components, so if ℜ is d-minimal, then every definable set has only countably many connected components.

Question. If every definable subset of ℝ has interior or is countable, does every definable set have only countably many connected components?

It might seem reasonable, at first thought, that the answer should be “Yes”; after all, this is certainly true for every open definable set, and is easily seen to be true for every dimension 0 definable set. But complications similar to those associated to Question 3.2.2 arise; perhaps further assumptions on ℜ are needed.

3.6. Lebesgue measure. Condition 6 almost lifts:

Proposition. Suppose every definable subset of ℝ has interior or is null. Then every definable set has interior or is null if and only if every definable set is Lebesgue measurable.

By Fubini’s theorem and its converse, the above follows easily from Proposition 3.1 and Theorem 3.3 (the details are left to the reader). Unfortunately, knowing that a subset of ℝ^{n} is null doesn’t really say much (especially for n > 1) and one might hope for stronger results, e.g., if every dimension 0 definable set has Hausdorff dimension 0, does every definable set have integer-valued Hausdorff dimension? But probably we would need yet further assumptions on ℜ.^{6}

3.7. Borel structures. Here is the most general lifting result associated to Condition 7 that I know of:

Proposition. Suppose ℜ is an expansion in the syntactic sense of (ℝ, <) by Borel relations and functions. If every ∅-definable subset of ℝ is F_{σ}, then ℜ is Borel.

(I say that ℜ is Borel if every definable set is Borel.)

Proof. Since boolean combinations and fibers of Borel sets are Borel, it suffices to show that if A ⊆ ℝ^{n+1} is ∅-definable and Borel, then πA ⊆ ℝ^{n} is Borel. By assumption, each fiber A_{x} (x ∈ ℝ^{n}) is F_{σ}. Apply Arsenin and Kunugui [27, (35.46)]. □

6See [18, 26].

Remark. The above holds without the assumption that ℜ defines <.

Every Borel set is projective, but not every projective set is Borel. Hence, every Borel expansion of \overline{ℝ} is a proper reduct of PH. The structure (\overline{ℝ}, ℝ_{alg}) is Borel; indeed, every definable set is a boolean combination of definable F_{σ} sets (this follows from [11, Theorem 1]). Hence, all particular proper reducts of PH that we have examined so far are Borel.

A set A ⊆ ℝ^{n} is analytic (also called “Souslin” or “Suslin” in the literature) if it is the continuous image of a Borel subset of ℝ. By Souslin’s Theorem [27, (14.11)], A is Borel if and only if both A and its complement are analytic. Hence, if ℜ is not Borel, then ℜ defines a non-analytic set.

Powerful tools from geometric measure theory can be used to analyze the definable sets in Borel expansions of \overline{ℝ}. I will not go into details in this paper (but see Edgar and Miller [17, 16] for some related material).

4. Cells and decompositions

Another way to generalize the notion of o-minimality is to relax one of the fundamental definitions in the subject; for convenience, we review it (but see [12, Chapter 3] for a thorough treatment).

Cells (ℜ-cells, if more precision is needed) are defined by induction on n: • ℝ^{0} is the unique cell contained in ℝ^{0}.

• Let D ⊆ ℝ^{n} be a cell. Then D × ℝ is cell. Let f: D → ℝ be continuous and definable; then

graph(f)
{ (x, t) ∈ D × ℝ : f(x) < t }
{ (x, t) ∈ D × ℝ : t < f(x) }

are cells. If g: D → ℝ is continuous and definable and f(x) < g(x) for all x ∈ D, then { (x, t) ∈ D × ℝ : f(x) < t < g(x) } is a cell.

Cells are simply connected and special (as defined in §3.4) C^{0}-submanifolds. Indeed, a cell is definably homeomorphic to an open cell in ℝ^{dim A} via some μ ∈ Π(n, dim A).

Note. Every cell is a PH-cell.

A (finite) decomposition of ℝ^{n} is defined by induction on n:

• {ℝ^{0}} is the unique decomposition of ℝ^{0}.

• A decomposition of ℝ^{n+1} is a finite partition D of ℝ^{n+1} into cells such that the

collection of projections πD := { πD : D ∈ D } is a decomposition of ℝ^{n}. Different kinds of cells and decompositions are defined by imposing extra conditions. In

particular, C^{p}-cells are defined by requiring that the functions f and g (in the definition of “cell”) be C^{p}. Again, C^{p}-cells are simply connected and special C^{p}-submanifolds, each definably C^{p}-diffeomorphic to an open C^{p}-cell in ℝ^{dim A} via some coordinate projection.

Arguably, the most fundamental result in o-minimality is the following:

Cell Decomposition (Pillay and Steinhorn, [43]). ℜ is o-minimal if and only if for every n and finite collection A of definable subsets of ℝ^{n} there is a finite decomposition of ℝ^{n} compatible with A.

If ℜ expands \overline{ℝ}, the theorem holds using C^{p}-cells and finite C^{p}-decompositions; see [12, Chapter 7]. (These results do not rely on working over ℝ.)

It is natural to consider relaxing the definitions of cells, decompositions, or both. In this section, we retain the definition of cell and relax the definition of decomposition.

First, let us consider what might be the weakest acceptable notion of a cell decomposition. Define a weak decomposition of ℝ^{n} by induction on n:

• {ℝ^{0}} is the unique weak decomposition of ℝ^{0}.

• A weak decomposition of ℝ^{n+1} is a partition D of ℝ^{n+1} into cells such that πD is a

weak decomposition of ℝ^{n} and ⋃{ D ∈ D : int(D) = ∅ } has no interior. Let us say that ℜ admits weak decomposition if for every n and finite collection A of definable subsets of ℝ^{n} there is a weak decomposition of ℝ^{n} compatible with A. It is immediate from the definitions that if ℜ admits weak decomposition, then every definable set has interior or is nowhere dense. I doubt if the converse holds, but a counterexample is needed. (Of course, it could be that the notion of “weak decomposition” is too weak to be useful.)

Define a countable decomposition of ℝ^{n} by induction on n:

• {ℝ^{0}} is the unique countable decomposition of ℝ^{0}.

• A countable decomposition of ℝ^{n+1} is a countable partition D of ℝ^{n+1} into cells

such that πD is a countable decomposition of ℝ^{n}. ℜ admits countable decomposition if, for every n and finite collection A of definable subsets of ℝ^{n}, there is a countable decomposition of ℝ^{n} compatible with A.

As with finite decompositions, different kinds of weak or countable decompositions are obtained by imposing extra conditions on the cells; for example, a countable C^{p}-decompo-sition of ℝ^{n} is a countable decomposition of ℝ^{n} by C^{p}-cells.

Theorem. Every d-minimal expansion of (ℝ, <, +)^{7} admits countable decomposition. Every d-minimal expansion of \overline{ℝ} admits countable C^{p}-decomposition.

(See §8.7 for the proof.)

Question. If ℜ expands the field and admits countable C^{p}-decomposition, is ℜ d-minimal? (I doubt it.)

Of course, (\overline{ℝ}, ℝ_{alg}) does not admit even weak decomposition. But there is a connection to cell decomposition, as we shall see in the next section.

Remark. For a survey of notions of cell decompositions for structures other than expansions of dense linear orders, see Mathews [33].

5. Open cores

Finally we consider an option—a pseudo-cell decomposition condition—for dealing with the case that ℜ does not satisfy the “interior or nowhere dense” condition. (The material in this section is based in part on joint work with P. Speissegger; see [38] for more detailed information, examples and applications.)

The open core of ℜ, denoted by ℜ^{∘}, is the reduct of ℜ generated by the collection of all open sets definable in ℜ. Note that ℜ^{∘} expands (ℝ, <) and is a reduct of PH. If every set definable in ℜ is constructible, then ℜ^{∘} = ℜ. If ℜ expands \overline{ℝ} and defines ℤ, then ℜ^{∘} = PH (and conversely). Fortunately, we have less trivial examples. In particular, suppose ℜ expands \overline{ℝ} and is o-minimal. Let M be the underlying set of a proper elementary substructure of ℜ. By [11, Theorem 5], the open core of (ℜ, M) is ℜ. A canonical example is ℜ = \overline{ℝ} and M = ℝ_{alg}, so (\overline{ℝ}, ℝ_{alg})^{∘} = \overline{ℝ}; indeed, (\overline{ℝ}, K)^{∘} = \overline{ℝ} for any real closed subfield K of ℝ. (Aside: There are projective, but non-Borel, real closed subfields of \overline{ℝ}, so dense pairs provide examples of proper reducts of PH that are not Borel. But I do not know of any expansions of \overline{ℝ} by constructible sets that are not Borel, other than PH.^{8})

7Assume also that ℜ has a pole. This is related to the flaw in the proof of 3.4.1.

Every constructible set definable in ℜ is definable in ℜ^{∘} (so a set in ℝ^{n} is an ℜ-cell if and only if it is an ℜ^{∘}-cell). In particular, if A is definable in ℜ, then all of int(A), cl(A), lc(A) and isol(A) are definable in ℜ^{∘}. This suggests that if the sets definable in ℜ^{∘} are suitably well behaved, then the behavior of the sets definable in ℜ should not be too much worse. This loose notion can be made more precise: Proposition 5.1. ℜ^{∘} is o-minimal if and only if for every m and finite collection A of subsets of ℝ^{m} definable in ℜ, there is a finite decomposition D of ℝ^{m} such that for each A ∈ A and D ∈ D, either A is disjoint from D, or A contains D, or A is dense and co-dense in D.

(As usual, if ℜ expands \overline{ℝ}, then the above holds using C^{p}-cells and decompositions.)

Proof. See [38, pg. 203] for the forward implication.

Conversely, assume that such a pseudo-decomposition property holds for ℜ. Then every constructible definable subset of ℝ is a finite union of points and open intervals, so it suffices to show that every set definable in ℜ^{∘} is constructible. Now, every set that is quantifier-free definable in ℜ^{∘} (regarded in its natural language) is constructible, so it suffices to show that if A ⊆ ℝ^{m+1} is constructible and definable, then πA is constructible, and for this it suffices to show that A is a finite union of cells. Put A = {A} and let D be a decomposition of ℝ^{m+1} as described. If A is dense in some some cell D ∈ D, then A is not co-dense in D—since both A and D are constructible—so A contains D. Hence, A is a disjoint union of cells in D. □

Note an easy consequence: Corollary. ℜ is o-minimal if and only if ℜ^{∘} is o-minimal and every subset of ℝ definable in ℜ has interior or is nowhere dense.

As the reader might imagine, one can formulate various results of the above kind, based on whatever nice properties ℜ^{∘} might have (e.g., d-minimality). Of course, knowing that ℜ^{∘} = PH would not very useful: PH is the open core of the expansion of (ℝ, <) by all subsets of each ℝ^{n} (n ≥ 1), so it is difficult to see how any interesting conclusions could be drawn about the sets definable in ℜ.

There is nothing special in the preceding two results about working over the real numbers; they both hold for expansions of arbitrary dense linear orders. The next result is quite a different matter. Theorem (joint with P. Speissegger, [38]). If every definable subset of ℝ is finite or uncountable, then ℜ^{∘} is o-minimal. If ℜ expands \overline{ℝ}, then ℜ^{∘} is o-minimal if and only if every discrete definable subset of ℝ is finite.

8See [19] for an example of a compact E ⊆ ℝ such that (\overline{ℝ}, E) is non-Borel but does not define ℤ.

The techniques used in the proof rely, in a seemingly crucial way, upon that ℝ (with its natural metric) is a Polish space.^{9}

Informal corollary. The study of expansions of \overline{ℝ} breaks down to the study of those with o-minimal open core and those that define an infinite discrete subset of ℝ.

There is an important (but logically trivial) dichotomy in the case that ℜ^{∘} is o-minimal: Either ℜ defines a function whose graph is somewhere dense, or it does not. We shall not pursue this matter in this paper (but see [38, pg. 204]). Also, there is an a priori subdivision of the case that ℜ defines an infinite discrete set: Either ℜ defines an infinite discrete closed subset of ℝ or it does not (I don’t know if the latter can happen, even if ℜ expands \overline{ℝ}). The next result (another consequence of the preceding theorem; see [38, pg. 201]) illustrates why we are interested in this distinction.

Corollary. Suppose ℜ expands \overline{ℝ}. Let A ⊆ ℝ^{m+n} be definable and constructible. Then there is a closed definable B ⊆ ℝ^{m+2} such that the projection of B on the first m coordinates is equal to the projection of A on the first m coordinates. If moreover ℜ defines an infinite discrete closed subset of ℝ, then B may be taken in ℝ^{m+1}.

Corollary. Suppose ℜ expands \overline{ℝ}, defines an infinite discrete closed subset of ℝ, and πA is constructible for every n and closed definable A ⊆ ℝ^{n+1}. Then every definable set is constructible.

Question. If A ⊆ ℝ is infinite and discrete, does (\overline{ℝ}, A) define an infinite discrete closed set?^{10} (For example, let A be the set of midpoints of the complementary intervals of an arbitrary Cantor subset of ℝ.)

Lemma. If ℜ expands (ℝ, <, +) and has the uniform finiteness property (recall the definition from §1.2) then every discrete definable subset of ℝ is finite.

Proof. Let A ⊆ ℝ be discrete and definable. Assume, toward a contradiction, that A is infinite.

Suppose A is closed. Fix a ∈ A. Then at least one of A ∩ [a, ∞) or A ∩ (−∞, a] is infinite; say the former. Put B = { (x, y) : x, y ∈ A & a ≤ y ≤ x }. Define σ: A → ℝ by σ(x) = min(A ∩ (x, ∞)), that is, σ(x) is the successor of x in A. Then

B_{a} = {a}, B_{σ(a)} = {a, σ(a)}, B_{σ(σ(a))} = {a, σ(a), σ(σ(a))}

and so on, contradicting uniform finiteness.

Now suppose A is not closed; then fr(A) is nonempty and closed (since A is locally closed). The distance function x ↦ d(x, fr(A)): ℝ → ℝ (taken with respect with the sup norm) is continuous and definable. Hence, for each r > 0, { x ∈ A : d(x, fr(A)) ≥ r } is discrete and closed. By the previous case (and uniform finiteness) there exists N ∈ ℕ such that

card{ x ∈ A : d(x, fr(A)) ≥ r } ≤ N

for all r > 0. But then { x ∈ A : d(x, fr(A)) < ϵ } = ∅ for some ϵ > 0, contradicting that fr(A) ≠ ∅. □

9At least, of the first result; see 7.5 of [4] for more evidence. But see Theorem A of [4].

10Yes, and it is not particularly difficult. This was solved independently and in several versions. As far as I know, it was first solved by Tychonievich while still a PhD student of mine; his solution was too short and simple to be publishable on its own. At some point, Fornasiero produced a more abstract version that did not require working over ℝ. Hieronymi produced a more technical version in [25].

Remark. If 𝔐 is an expansion of a densely ordered group (M, <, +) and the least upper bound property holds for definable subsets of M (see [35] for more information) then the lemma holds for 𝔐.

Taken together with [38, Theorem] we have:

Proposition 5.2. If ℜ expands \overline{ℝ} and has the uniform finiteness property, then ℜ^{∘} is o-minimal.^{11}

Question. If ℜ expands \overline{ℝ} and ℜ^{∘} is o-minimal, does ℜ have the uniform finiteness property?

Questions. Let E ⊆ ℝ^{m} be any “natural” mathematical object. Identify and describe the open core of (\overline{ℝ}, E). (Of course, if E is constructible, then this is asking to describe the definable sets of (\overline{ℝ}, E) itself.) Note that any finite sequence E_{1} ⊆ ℝ^{m(1)}, …, E_{l} ⊆ ℝ^{m(l)} may be definably identified with E_{1} × ⋯ × E_{l}.

Some interesting candidates for E include (finite sequences of): infinitely generated proper subgroups of (ℝ, +); noncyclic proper subgroups of (ℝ^{>0}, ·); subrings; subfields; the torsion points of the circle group S^{1} ⊆ ℝ^{2};^{12} rational points of an irreducible algebraic variety;^{13} fractal subsets of the plane;^{14} trajectories of vector fields^{15} (and so on).

Let us consider some concrete cases.

If E is a subfield of ℝ, is (\overline{ℝ}, E)^{∘} equal to either \overline{ℝ} or PH? We have already noted that if E is real closed, then (\overline{ℝ}, E)^{∘} = \overline{ℝ}. On the other hand, if E is either a finite degree algebraic extension of ℚ, or of the form K(α) with α transcendental over a subfield K, then ℤ is definable in (E, +, ·)—see J. Robinson [45] for the former and R. Robinson [46] for the latter—so (\overline{ℝ}, E) = PH.

We know (by Theorems 3.4.1 and 3.4.2) that if α > 0 and E = α^{ℤ}, then (\overline{ℝ}, E) is d-minimal and its own open core. What can be said if E = α^{ℤ} · β^{ℤ} (= { α^{j}β^{k} : j, k ∈ ℤ }) or E = α^{ℤ} × β^{ℤ}, and β ∉ α^{ℚ}? Note that if β ∉ α^{ℚ}, then α^{ℤ} · β^{ℤ} is dense and co-dense in (0, ∞), and is definable in (\overline{ℝ}, α^{ℤ}, β^{ℤ}).^{16} To be fair, I should point out that even the number theory of the set { 3^{m} ± 2^{n} : m, n ∈ ℕ } is not well understood.

Is (\overline{ℝ}, 2^{ℤ}, ℝ_{alg})^{∘} = (\overline{ℝ}, 2^{ℤ})? (I think this is probably true: just amalgamate all relevant proofs in [6] and [11].)^{17}

6. Interdefinability with PH

We have considered several examples of proper reducts of PH. In this section, we consider a few sets that do generate PH over the field.^{18} 6.1. Of course, (\overline{ℝ}, ℚ) = PH, since ℤ is definable in (ℚ, +, ·).

11See [4] for a generalization that does not require working over ℝ.

12See [2] and the last paragraph of [4, §5].

13See [22].

14See [26].

15See [37, 52].

16See [24].

17See [28].

18See [26] for an extremely important update.

Proposition. Let R be a subring of ℝ and (G, +) be a finitely generated subgroup of (R, +) with 1 ∈ G. Then ℤ is definable in (R, +, ·, G).

Proof. The definable set D := { r ∈ R : rG ⊆ G } is a subring of R contained in G. Since G is finitely generated, D is the ring of integers of a number field. By [45], ℤ is definable in (D, +, ·), hence also in (R, +, ·, G). □

Corollary. If (G, +) is a nontrivial finitely generated subgroup of (ℝ, +), then (\overline{ℝ}, G) = PH.^{19}

6.2. “Natural” subsets of natural numbers. We have seen that for certain familiar E ⊆ ℕ (e.g., Fib and \{ α^{n} : n ∈ ℕ \} for α a fixed positive integer), we have (\overline{ℝ}, E) ≠ PH. Let us examine some other cases.

Obviously, (\overline{ℝ}, ℕ) = PH.

If f: ℝ → ℝ is semialgebraic (equivalently, definable in \overline{ℝ}), then either f is ultimately constant or ultimately strictly monotone. Hence, if E = { f(n) : n ∈ ℕ } and is infinite— say, f is an ultimately positive nonconstant polynomial with integer coefficients—then every sufficiently large natural number is definable in (\overline{ℝ}, E), hence ℕ is as well.

If E = \{ n! : n ∈ ℕ \}, then (\overline{ℝ}, E) = PH. (Note that for any A ⊆ ℝ having order type ω, the successor function σ on A is definable in (ℝ, <, A) and the set { σ(x)/x : x ∈ A \ {0} } is definable in (\overline{ℝ}, A).)

By Vinogradov [53], every sufficiently large odd integer is a sum of three prime numbers. It follows easily that (\overline{ℝ}, E) = PH if E is the set of all primes.

Question. Let E ⊆ ℕ and suppose that (\overline{ℝ}, E) is not Borel. Is (\overline{ℝ}, E) = PH?

6.3. (\overline{ℝ}, α^{ℤ}, exp) = PH for any α > 1, since x ↦ log_{α} : (0, ∞) → ℝ is definable in (\overline{ℝ}, exp). More interesting and less trivial:

Proposition. (\overline{ℝ}, ℝ_{alg}, exp) = PH.

Proof. It suffices to show that ℚ is definable in (\overline{ℝ}, ℝ_{alg}, exp). The function t ↦ 2^{t}: ℝ → ℝ is definable in (\overline{ℝ}, exp). By the Gelfond-Schneider theorem (see e.g. Lang [30, pg. 682]), t ∈ ℝ is rational if and only if both t and 2^{t} are algebraic. □

6.4. PH is even obtained as the amalgamation of two o-minimal expansions of ℝ:

Proposition ([47]). There exist functions f, g: ℝ → ℝ such that both (\overline{ℝ}, f) and (\overline{ℝ}, g) admit (finite) C^{∞}-cell decomposition and have field of exponents ℚ, but (\overline{ℝ}, f, g) = PH.

6.5. Consider the vector field

(x, y, z) ↦ (−x^{2}, xy − z, xz + y): ℝ^{3} → ℝ^{3}.

The set T := { (1/t, t cos t, t sin t) : t > 0 } is a trajectory. By intersecting T with the xy-plane and then projecting on the x-axis, we obtain the set

{ 1/(πk) : 0 < k ∈ ℤ }.

Hence, (\overline{ℝ}, T) = PH.

19See [51] for a better result.

Remark. If ℜ expands (ℝ, <, +), defines ℤ, and 1 is ∅-definable, then ℤ is ∅-definable, since ℤ is the unique S ⊆ ℝ such that (0, 1] ∩ S = {1} and x − y ∈ S for all x, y ∈ S.

Part 2

We now proceed to proofs and further technical details. Results may be stated in a preliminary form or in greater generality than is needed for this paper.

Recall that if A ⊆ ℝ^{m+n} ≅ ℝ^{m} × ℝ^{n} and the base space ℝ^{m} is clear from context, then πA denotes the projection of A on the first m coordinates.

BCT is an abbreviation for the Baire category theorem.

7. Lemmas

Fiber Lemma. Let A ⊆ ℝ^{m+n} be definable. Then the definable set

B := { x ∈ ℝ^{m} : cl(A)_{x} ≠ cl(A_{x}) }

is a countable union of definable subsets of ℝ^{m}, each having no interior. If moreover dim A = m, then the definable set

C := { x ∈ ℝ^{m} : dim A_{x} > 0 }

is a countable union of definable subsets of ℝ^{m}, each having no interior.

Proof. Let V be the collection of all boxes in ℝ^{n} with vertices in ℚ^{n}; then

B = ⋃_{V ∈V}{ x ∈ ℝ^{m} : V ∩ cl(A)_{x} ≠ ∅ & V ∩ cl(A_{x}) = ∅ }.

For each V ∈ V, we have

{ x ∈ ℝ^{m} : V ∩ cl(A)_{x} ≠ ∅ & V ∩ cl(A_{x}) = ∅ } ⊆ fr(π((ℝ^{m} × V) ∩ A)).

Frontiers of sets have no interior.

The set C is the union of all sets of the form { x ∈ ℝ^{m} : I ⊆ μA_{x} } where μ ∈ Π(n, 1) and I ⊆ ℝ is an open interval with endpoints in ℚ. Clearly, such a set has no interior (otherwise, dim A > m). □

For each n, let ℜ_{σ}(n) denote the collection of all countable unions of definable subsets of ℝ^{n}. I might say “A is ℜ_{σ}(n)”, or even just “A is ℜ_{σ}”, instead of “A ∈ ℜ_{σ}(n)”.

Easy observations.

• Every open subset of ℝ^{n} is ℜ_{σ}.

• Every countable subset of ℝ^{n} is ℜ_{σ}.

• Every element of ℜ_{σ}(n) is a countable increasing union of bounded definable subsets of ℝ^{n}.

• ℜ_{σ}(n) is closed under taking countable unions and finite intersections.

• If A, B ∈ ℜ_{σ} and B is closed in A, then A \ B ∈ ℜ_{σ}.

• Let f: ℝ^{m} → ℝ^{n} be definable. If A ∈ ℜ_{σ}(m) then f(A) ∈ ℜ_{σ}(n). If B ∈ ℜ_{σ}(n) then f^{−1}(B) ∈ ℜ_{σ}(m). In particular, coordinate projections, as well as the associated fibers, of ℜ_{σ} sets are ℜ_{σ}.

Main Lemma. The following are equivalent:

(1) For all definable A ⊆ ℝ, dim cl(A) = dim A.

(2) Every definable subset of ℝ has interior or is nowhere dense.

(3) Every definable set has interior or is nowhere dense.

(4) For all definable A, dim cl(A) = dim A.

(5) For all m, n and definable A ⊆ ℝ^{m+n}, { x ∈ ℝ^{m} : cl(A)_{x} ≠ cl(A_{x}) } is nowhere dense.

(6) For all m, n and definable A ⊆ ℝ^{m+n}, { x ∈ ℝ^{m} : fr(A)_{x} ≠ fr(A_{x}) } is nowhere dense.

(7) Every definable subset of ℝ has interior or is meager.

(8) Every definable set has interior or is meager.

(9) For all definable A, { x ∈ ℝ^{dim A} : dim A_{x} > 0 } is nowhere dense.

(10) For all definable A, B ⊆ ℝ, dim(A ∪ B) = max{dim A, dim B}.

(11) For all n and definable A, B ⊆ ℝ^{n}, dim(A ∪ B) = max{dim A, dim B}.

(12) Every ℜ_{σ}(1) has interior or is meager.

(13) Every ℜ_{σ} has interior or is meager.

(14) For all m, n and A ∈ ℜ_{σ}(m + n), A has interior if and only if

{ x ∈ ℝ^{m} : A_{x} has interior }

has interior.

(15) For all A ∈ ℜ_{σ}, { x ∈ ℝ^{dim A} : dim A_{x} > 0 } is meager.

(16) For all n and { A_{k} : k ∈ ℕ } ⊆ ℜ_{σ}(n),

dim ⋃_{k∈ℕ} A_{k} = max{ dim A_{k} : k ∈ ℕ }.

Proof. Many of the various implications are obvious, or become so after seeing the key tricks (and there is a marked resemblance to some basic results about F_{σ} sets; see e.g. [38, 1.5]). Hence, I do only a few of these implications and leave the rest to the reader.

2⇒3. Let n ≥ 1 and assume inductively that every definable subset of ℝ^{n} has interior or is nowhere dense. Let A ⊆ ℝ^{n+1} be definable. Suppose that A is somewhere dense, that is, cl(A) has interior. By the Fiber Lemma and the inductive assumptions, { x ∈ ℝ^{n} : A_{x} has interior } has interior. By BCT, there is an open interval I ⊆ ℝ such that { x ∈ ℝ^{n} : I ⊆ A_{x} } is nonmeager (and thus has interior). Then A has interior.

3⇒4. Let A ⊆ ℝ^{n} be definable. Put d = dim cl(A). The result is clear if d = 0. If d = n, then A is somewhere dense, and thus has interior. Suppose now that 0 < d < n. Without loss of generality, assume that the projection of cl(A) on the first d coordinates contains a box U. By the Fiber Lemma, { x ∈ U : cl(A)_{x} ≠ cl(A_{x}) } is nowhere dense, so { x ∈ U : A_{x} ≠ ∅ } has interior.

5⇔3 follows easily from BCT and the Fiber Lemma.

5⇔6 is just symbol chasing.

Next do 7⇒2⇒3⇒8⇒7.

(And so on.) □

Definition. Items 5, 6, 9, 14 and 15 above will be referred to, collectively, as the fiber properties.

By the Main Lemma, every definable subset of ℝ has interior or is nowhere dense if and only if the same is true for every definable set. We use this observation in the sequel without further mention.

Definition. The full dimension of A ⊆ ℝ^{n}, denoted by fdim A, is the pair (d, k), ordered lexicographically, where d = dim A and

k = card{ μ ∈ Π(n, dim A) : int(μA) ≠ ∅ }.

Note that k is independent of d if d ∈ {−∞, 0, n}, so we identify dim and fdim in these cases.

Definition. A set A ⊆ ℝ^{m+n} is π-good (relative to ℜ) if:

• A is definable;

• dim A = m;

• πA is open;

• π(A ∩ U) has interior for every a ∈ A and open neighborhood U of a;

• For all x ∈ πA, dim A_{x} = 0 and cl(A_{x}) = cl(A)_{x}. More generally: A is μ-good (μ ∈ Π(m + n, m)) if there is a permutation σ of coordinates such that μ = π ∘ σ and σ(A) is π-good. Finally, A ⊆ ℝ^{n} is Π-good if it is μ-good for some μ ∈ Π(n, dim A). A collection P of subsets of ℝ^{n} is Π-good if P is a finite collection of Π-good subsets of ℝ^{n}.

Every nonempty open definable subset of ℝ^{n} is Π-good (but ∅ is not Π-good). Every dimension 0 definable subset of ℝ^{n} is Π-good.

Partition Lemma. Suppose every definable set has interior or is nowhere dense. Let A be a finite collection of definable subsets of ℝ^{n}. Then there is a Π-good partition P of ℝ^{n} compatible with A.

Proof. We proceed by induction on (d, k) = max{ fdim A : A ∈ A }, where d ≥ 0 (the result is trivial if d = −∞). It suffices to deal with the case that the elements of A are pairwise disjoint.

Suppose d = 0. Put A′ = A ∪ { fr(A) : A ∈ A }. By the usual tricks, there is a finite partition P_{0} of ⋃ A′, compatible with A′, with each P ∈ P_{0} definable. Put P = P_{0} ∪ {ℝ^{n} \ ⋃ A′}.

Suppose d = n. Put P = { int(A) : A ∈ A & int(A) ≠ ∅ } ∪ P′, where P′ is obtained by applying the inductive assumption to { A \ int(A) : A ∈ A }.

Suppose 0 < d < n. Let A ⊆ ℝ^{n} be definable such that dim A = d and πA has interior. Let Y be the set of all a ∈ A such that π(A ∩ U) has interior for every box U containing a. Note that Y is definable. Let a ∈ A \ Y; then there is a box U with rational vertices such that a ∈ U and π(A ∩ U) has no interior, and thus is nowhere dense. Hence, π(A \ Y) is meager, so fdim(A \ Y) < fdim A. By the fiber properties, the set

S := { x ∈ ℝ^{d} : dim Y_{x} > 0 or cl(Y_{x}) ≠ cl(Y)_{x} }

is nowhere dense. Then P := Y ∩ π^{−1}(int(πA) \ cl(S)) is π-good and fdim(A \ P) < fdim A. (The rest of the proof is routine.) □

Note. The partition P above is obtained canonically if we fix an ordering of the elements of Π(n, d) for each n ∈ ℕ and d ∈ {0, …, n}. For example, if no A ∈ A has interior, then we may always deal first with any A ∈ A such that dim A = n − 1 and the projection of A on the first n − 1 coordinates has interior. (This observation is used later in the proof of Theorem 4.)

8. Proofs

8.1. Proof of Proposition 3.2.

Lemma. Suppose every definable set has interior or is nowhere dense. Let A ⊆ ℝ^{m+n} be definable. Then:

(1) { x ∈ ℝ^{m} : lc(A_{x}) ≠ lc(A)_{x} } is nowhere dense.

(2) For each k ∈ ℕ, { x ∈ ℝ^{m} : (A^{(k)})_{x} ≠ A_{x}^{(k)} } is nowhere dense.

(3) If { x ∈ ℝ^{m} : lc(A_{x}) ≠ ∅ } is somewhere dense, then lc(A) ≠ ∅.

Proof. By the fiber properties, { x ∈ ℝ^{m} : fr(A)_{x} ≠ fr(A_{x}) } is nowhere dense, which in turn yields that { x ∈ ℝ^{m} : cl(fr(A))_{x} ≠ cl(fr(A_{x})) } is nowhere dense. For all x ∈ ℝ^{m}, we have lc(A)_{x} = A_{x} \ cl(fr(A))_{x} and lc(A_{x}) = A_{x} \ cl(fr(A_{x})).

Item 2 follows from 1 by an easy induction on k.

Item 3 is immediate from 1. □

We are now ready to finish the proof of Proposition 3.2. Suppose every dimension 0 definable set has a locally closed point. Then every nonempty definable subset of ℝ has a locally closed closed point, so every definable subset of ℝ has interior or is nowhere dense, which in turn yields that every definable set has interior or is nowhere dense.

Let ∅ ≠ A ⊆ ℝ^{n} be definable; we must show that A^{(1)} is nowhere dense in A. Since lc(A) is open in A, it suffices to show that lc(A) is dense in A. Since lc(U ∩ A) = U ∩ lc(A) for every open U ⊆ ℝ^{n}, it suffices to show lc(A) ≠ ∅. The case dim A = 0 holds by assumption and the result is obvious if A has interior, so suppose 0 < dim A < n. Since σ(lc(A)) = lc(σ(A)) for any permutation σ of coordinates, we may reduce (by the Partition Lemma) to the case that πA is open (where π denotes projecting on the first d coordinates) and dim A_{x} = 0 for all x ∈ πA. Then lc(A_{x}) ≠ ∅ for all x ∈ πA. Apply the lemma. □

8.2. Proof of Theorem 3.2. It suffices to show that the following are equivalent: (1) For every 𝔐 ≡ ℜ, every dimension 0 set definable in 𝔐 is constructible.

(2) For every ∅-definable A ⊆ ℝ^{m+n} there exists N ∈ ℕ such that for all x ∈ ℝ^{m}, if dim A_{x} = 0, then (A_{x})^{(N)} = ∅.

(3) Every ∅-definable set is a finite union of ∅-definable locally closed sets.

(4) Every definable set is constructible.

1⇒2 is a routine compactness argument (using 2.1).

Assume 2. Note that every definable set has interior or is nowhere dense. We proceed by induction on full dimension. Let ∅ ≠ A ⊆ ℝ^{n} be ∅-definable and (d, k) = fdim A. The case d = 0 holds by assumption. If d = n, then A \ int(A) is ∅-definable and dim(A \ int(A)) < dim A. Suppose 0 < d < n. By the Partition Lemma, we may reduce to the case that A is π-good (where π denotes projecting on the first d coordinates). Let N be as guaranteed by the hypothesis. By Lemma 8.1, { x ∈ ℝ^{d} : (A^{(N)})_{x} ≠ ∅ } is nowhere dense. Put

Y = A ∩ π^{−1}(int{ x ∈ ℝ^{d} : (A^{(N)})_{x} = ∅ })

Then Y^{(N)} = ∅ (so Y is constructible) and fdim(A \ Y) < fdim A.

Assume 3. Let A ⊆ ℝ^{n} be definable. Then A = Y_{x} for some m ∈ ℕ, ∅-definable Y ⊆ ℝ^{m+n} and x ∈ ℝ^{m}. Since Y is constructible, and fibers of constructible sets are constructible, A is constructible.

(The converse implications are all easy.) □

8.3. Proof of Theorem 3.3. Suppose every definable subset of ℝ has interior or is nowhere dense.

We already know that every definable set has interior or is nowhere dense.

Let U ⊆ ℝ^{m} be open and f: U → ℝ be definable.

Almost continuity. Let V be the set of points in U such that f is continuous on a box about x. We must show that V is dense in U. Let B ⊆ U be a box. Now, B is the union of the definable sets { x ∈ B : |f(x)| ≤ k }, k ∈ ℕ; by BCT, there exists N ∈ ℕ such that { x ∈ B : |f(x)| ≤ N } is somewhere dense, and thus has interior. So we may assume that f is bounded on B. By the fiber properties, the set

{ x ∈ B : cl(graph(f))_{x} = {f(x)} }

contains a box B′. Then f↾B′ is continuous.

Monotonicity. Suppose m = 1. We must show there is an open definable V ⊆ U such that U \V is nowhere dense, f↾V is continuous, and f is either constant or strictly monotone on each connected component of V. (The proof resembles that of the monotonicity theorem for o-minimal structures, but the setting is different enough to warrant giving some details.) By almost continuity, we may reduce to the case that f is continuous. The sets

V_{1} = { x ∈ U : f is constant on an open interval about x }
V_{2} = { x ∈ U : f is strictly increasing on an open interval about x }
V_{3} = { x ∈ U : f is strictly decreasing on an open interval about x }

are each open and definable, and a routine argument shows that f is either constant or strictly monotone on each connected component of each of these sets, so it suffices to show that U \ (V_{1} ∪ V_{2} ∪ V_{3}) has no interior. Suppose otherwise; then U \ (V_{1} ∪ V_{2} ∪ V_{3}) contains a compact interval I. Since f↾I is continuous and nonconstant, f(I) contains an open interval J. Define g: J → ℝ by g(r) = min(I ∩ f^{−1}{r}). Now, g is injective, so by almost continuity there is an open interval J′ ⊆ J such that g maps J′ homeomorphically onto an open interval I′ ⊆ I. But then f↾I′ is strictly monotone; contradiction.

Almost C^{p}-smoothness. Assume ℜ expands \overline{ℝ}. We must show there is an open definable V ⊆ U such that U \ V has no interior and f↾V is C^{p}. We proceed by induction on p ≥ 0. We have already established the case p = 0. Assume the result holds for a certain p ≥ 0; we show it holds for p + 1. By the inductive assumption, we reduce to the case that f is C^{p}.

Suppose m = 1. By monotonicity, we may assume that f^{(p)} is monotone on each connected component of U. By the Lebesgue differentiability theorem (e.g., Royden [48, Ch. 5]), the set

{ x ∈ U : f^{(p)} is not differentiable at x }

is null, hence nowhere dense. Now apply almost continuity.

Suppose m > 1. It suffices to show that the set of all x ∈ U such that f is C^{p+1} on a neighborhood of x has interior. Let g be some partial derivative of f of order p; we need only show that the set of all x ∈ U such that g is C^{1} on a box about x has interior. Fix some i ∈ {1, …, m}; for convenience, say i = m. Let πU be the projection of U on the first m−1 coordinates and μU be the projection on the last coordinate. By the case m = p = 1, for each u ∈ πU there is an open interval I(u) ⊆ μU such that x_{m} ↦ g(u, x_{m}) : I(u) → ℝ is differentiable. By BCT, there is an open interval I ⊆ μU such that the set

{ u ∈ πU : x_{m} ↦ g(u, x_{m}): I → ℝ is differentiable }

is nonmeager, so there is a box B ⊆ πU such that ∂g/∂x_{m} exists at all x ∈ B × I. By repeating the argument for i = 1, …, m−1, we obtain a box B′ ⊆ B such that the gradient of g exists at all x ∈ B′. By almost continuity (and standard facts), g is C^{1} on some box contained in B′. □

Remark. Perhaps arguments of Laskowski and Steinhorn [31] could be modified to show that almost C^{1}-smoothness holds without the assumption that ℜ defines multiplication.

8.4. A stronger version of Proposition 3.4.

Definition. For A ⊆ ℝ^{n}, μ ∈ Π(n, d) and p ∈ ℕ, let reg_{μ}^{p}(A) denote the set of all a ∈ A such that, for some open neighborhood U about a, μ↾(A∩U) maps A∩U C^{p}-diffeomorphi-cally onto some open V ⊆ ℝ^{d}. For μ = π, this just means that A ∩ U = graph(f) for some C^{p} map f: V → ℝ^{n−d}. Note that reg_{μ}^{0}(A) is definable, open in A, and a C^{0}-submanifold of ℝ^{n} of dimension d; similarly for reg_{μ}^{p}(A) if ℜ expands \overline{ℝ}.

Lemma. Suppose every definable subset of ℝ has interior or is nowhere dense. Let A ⊆ ℝ^{m+n} be definable such that { x ∈ ℝ^{m} : isol(A_{x}) ≠ ∅ } has interior. Then reg_{π}^{0}(A) ≠ ∅. If ℜ expands \overline{ℝ}, then this holds for each reg_{π}^{p}(A).

Proof. For each x ∈ ℝ^{m} such that isol(A_{x}) ≠ ∅, there exist y ∈ A_{x} and a box V (with rational vertices) about y such that V ∩ A_{x} = {y}. By BCT, there is a box V ⊆ ℝ^{n} such that { x ∈ ℝ^{m} : card(V ∩ A_{x}) = 1 } is somewhere dense, and thus contains a box U. Define f: U → ℝ^{n} by letting f(x) be the unique element of V ∩A_{x}. By Theorem 3.3, there is a box B ⊆ U such that f↾B is continuous (C^{p} if ℜ expands \overline{ℝ}). Then graph(f↾B) is contained in reg_{π}^{0}(A) (and in reg_{π}^{p}(A) if ℜ expands \overline{ℝ}). □

Proposition. Suppose every dimension 0 definable subset of ℝ has an isolated point. Let A be a finite collection of definable subsets of ℝ^{n}. Then there is a Π-good partition P of ℝ^{n}, compatible with A, such that P \ reg_{μ}^{0}(P) is nowhere dense in P for every projection μ and P ∈ P such that P is μ-good. If moreover ℜ expands \overline{ℝ}, then this holds with “reg_{μ}^{p}(P)”in place of “reg_{μ}^{0}(P)”.

Proof. First, note that every definable set has interior or is nowhere dense. By the Partition Lemma, it suffices to show that if P ⊆ ℝ^{n} is π-good, then P \ reg_{π}^{0}(P) is nowhere dense in P. The result is trivial if dim P = n (since P is open). An easy induction on n handles the case dim P = 0 (note that reg_{π}^{p}(P) = isol(P) if dim P = 0). For 0 < dim P < n, apply the lemma. □

8.5. Proof of Theorem 3.4.1.

Lemma. The following are equivalent:

(1) ℜ is d-minimal.

(2) For every m and definable A ⊆ ℝ^{m+1} there exists N ∈ ℕ such that for every x ∈ ℝ^{m}, A_{x} either has interior or is a union of N discrete sets.

(3) For every m, n and definable A ⊆ ℝ^{m+n} there exists N ∈ ℕ such that for every x ∈ ℝ^{m}, either dim A_{x} > 0 or A_{x} is a union of N discrete sets.

Proof. (1)⇒(2) is a routine compactness argument (using 2.3).

(2)⇒(3) is an easy induction on n.

Assume (3). Let 𝔐 ≡ ℜ and S ⊆ M be definable in 𝔐. Then there exist m ∈ ℕ, x ∈ M^{m} and A ⊆ M^{m+1}, ∅-definable in 𝔐, such that S = A_{x}. Since 𝔐 ≡ ℜ, S either has interior or is a finite union of discrete sets. Hence, ℜ is d-minimal. □

We now begin the proof proper.

Let n ∈ ℕ and A be a finite collection of definable subsets of ℝ^{n}. We show that there is a finite partition of ℝ^{n} into special C^{0}-submanifolds, each of which is definable and compatible with A. By the Partition Lemma and Proposition 8.4, it suffices to consider the case that A is a Π-good partition of ℝ^{n} such that A \ reg_{μ}^{0}(A) is nowhere dense in A for every projection μ and A ∈ A such that A is μ-good. For the open A ∈ A, there is nothing further to do. Every dimension 0 definable set is a finite disjoint union of discrete definable sets, so the dimension 0 sets in A are disposed of as well. It suffices now to show that if A ∈ A with 0 < d := dim A < n, then there is a definable M ⊆ A such that M is a C^{0}-submanifold and fdim(A \ M) < fdim(A). By permuting coordinates, it suffices to consider the case that A is π-good, where π is the projection on the first d coordinates. Since there exists N ∈ ℕ such that A is the disjoint union of the sets { (x, y) ∈ A : y ∈ isol(A_{x}^{[k]}) } (k = 0, …, N), we may reduce to the case that, in addition to the above data, each A_{x} is discrete.

Let S be the (definable) open set of x ∈ πA such that, for some box U about x, for every y ∈ A_{x} there is a bounded box V ⊆ ℝ^{n−d} about y with card(A_{z} ∩ V) = 1 for every z ∈ U. Note that A ∩ π^{−1}(U) ⊆ reg_{π}^{0}(A)—since cl(A_{x}) = cl(A)_{x} for all x ∈ πA; compare with the proof of almost continuity in Theorem 3.3—so A ∩ π^{−1}(S) is a special C^{0}-submanifold. It suffices now to show that S is dense in int(πA) (since then fdim(A \ π^{−1}(S)) < fdim A). Let B ⊆ πA be a box. Each A_{x} is discrete, so (by BCT) there exist J ⊆ ℕ and a pairwise disjoint collection (V_{j})_{j∈J} of bounded boxes in ℝ^{n−d} such that the (not necessarily definable) set

S′ := { x ∈ B : A_{x} ⊆ ⋃_{j∈J} V_{j} & ∀j ∈ J, card(A_{x} ∩ V_{j}) = 1 }

is nonmeager.^{20} By shrinking B, we reduce to the case that S′ is dense in B. By further shrinking B, we may assume that cl(reg_{π}^{0}(A))_{x} = cl(reg_{π}^{0}(A)_{x}) for all x ∈ B. Since reg_{π}^{0}(A) is dense in A, we have cl(A_{x}) = cl(reg_{π}^{0}(A)_{x}) for all x ∈ B; then (x, y) ∈ reg_{π}^{0}(A) for every x ∈ B and y ∈ A_{x} (since each A_{x} is discrete). By density of S′ in B, we have card(A_{x} ∩ V_{j}) = 1 for all j ∈ J and x ∈ B. Hence, B ⊆ S.

(We have established the C^{0} version.)

Suppose that ℜ expands \overline{ℝ} and let p ∈ ℕ. In order to obtain the C^{p} statement, replace “reg_{π}^{0}” by “reg_{π}^{p}” in the above proof prior to the point of defining the set S. Let T be the set of all x ∈ πA such that A ∩ π^{−1}(U) ⊆ reg_{π}^{p}(A) for some box U about x. We need only show that T is dense in S. Let B ⊆ S be a box. After shrinking B, there is a countable set J and continuous definable maps ϕ_{j}: B → ℝ such that A ∩ π^{−1}(B) = ⋃_{j∈J} graph(ϕ_{j}). By Theorem 3.3, each ϕ_{j} is C^{p} off a nowhere dense definable subset of B. Then B \ T is meager, hence nowhere dense. □

20As pointed out to me by A. Fornasiero, this assertion is unfounded, because BCT has been applied to a potentially uncountable family. This invalidates the rest of the proof, but there is a repair due to A. Thamrongthanyalak ([50]) for the case that ℜ expands (ℝ, <, +) and all sets in A are bounded. Hence, if moreover ℜ defines a bijection between a bounded interval and an unbounded interval, then the repair also holds. In particular, the repair holds if ℜ expands \overline{ℝ}.

8.6. Proof of Theorem 3.4.2. Let α > 1 and ℜ be an o-minimal expansion of \overline{ℝ} having field of exponents ℚ. We show that (ℜ, α^{ℤ}) is d-minimal.

First, we have:

Proposition (cf. [6, Theorem I]). Th(ℜ, α^{ℤ}) is axiomatized over Th(ℜ) by axioms expressing:

• the cut of α in ℚ

• α^{ℤ} is a multiplicative subgroup of (0, ∞)

• α^{ℤ} ∩ (1, α] = {α}

• for every t > 0 there exists g ∈ α^{ℤ} such that g ≤ t < αg.

Remark. If α is ∅-definable in ℜ then the axioms for the cut of α are unnecessary.

Outline of the proof of the Proposition. Let L ⊇ {<, +, −, ·, 0, 1} be a first-order language such that ℜ is an L-structure. By adding a constant, we may assume that α is ∅-definable. By expanding ℜ by all ∅-definable functions, we reduce to the case that Th(ℜ) admits QE and has a universal axiomatization as an L-structure, and that L has no relation symbols other than <.

For t > 0, let ⌊t⌋ = max((0, t] ∩ α^{ℤ}). For t ≤ 0, put ⌊t⌋ = 0. Note that ⌊ ⌋ is ∅-definable in (ℜ, α^{ℤ}) and α^{ℤ} is ∅-definable in (ℜ, ⌊ ⌋).

Let L^{∗} be the result of extending L by a new unary function symbol for ⌊ ⌋. Let T be the L^{∗}-theory Th(ℜ) together with axioms expressing:

• x ≤ 0 → ⌊x⌋ = 0

• 1 ≤ x < α → ⌊x⌋ = 1
• ⌊α⌋ = α
• ⌊⌊x⌋y⌋ = ⌊x⌋⌊y⌋
• x > 0 → ⌊x⌋ ≤ x < α⌊x⌋

It suffices now to show T = Th(ℜ, ⌊ ⌋). Since (𝔓, ⌊ ⌋) embeds into every model of T, where 𝔓 is the prime submodel of ℜ, it suffices to show T admits QE; the proof is a routine modification of known results, so I provide only a brief sketch. Note that T is universal and [10, Theorem C] generalizes [34, 1.2]. Combine the technique of [34, 2.2] with the exponential image (so to speak) of the argument in [35, Appendix]. □

We are now ready to finish the proof of the theorem. We work with (ℜ, ⌊ ⌋) instead of (ℜ, α^{ℤ}). Let (𝔐, ⌊ ⌋) ≡ (ℜ, ⌊ ⌋) and A ⊆ M be definable in (𝔐, ⌊ ⌋). We show that A has interior or is a finite union of discrete sets.

Let L_{M}^{∗} be the expansion of the language L^{∗} by constants for elements of M. By QE, it suffices to consider the case that

A = { t ∈ M : τ_{0}(t) = 0, τ_{1}(t) < 0, …, τ_{k}(t) < 0 }

where τ_{0}, …, τ_{k} are unary L_{M}^{∗}-terms. By an easy induction on complexity (cf. [6, Theorem III]) there exist m ∈ ℕ, a function f: M^{m+1} → M definable in 𝔐, and E ⊆ M such that:

• E is definable and a finite union of discrete sets;

• If 0 ≤ i ≤ k and (a, b) ⊆ M \ E, then there exists x ∈ M^{m} such that τ_{i}(t) = f(x, t)

for all t ∈ (a, b). Now, 𝔐 is o-minimal (since 𝔐 ≡ ℜ), so for any interval (a, b) ⊆ M∪{±∞} and x_{0}, …, x_{k} ∈ M^{m}, the set

{ t ∈ (a, b) : f(x_{0}, t) = 0, f(x_{1}, t) < 0, …, f(x_{k}, t) < 0 }

either has interior or is finite. Then either A has interior or A \ E is discrete. Hence, either A has interior or is a finite union of discrete sets. □

Remark. By Theorems 3.4.2 and 4, if ℜ is an o-minimal expansion of \overline{ℝ} having field of exponents ℚ, then (ℜ, α^{ℤ}) admits countable C^{p}-decomposition. But more can be said: Since T is universal and admits QE, every function f: ℝ^{n} → ℝ definable in (ℜ, α^{ℤ}) is given piecewise by L_{ℝ}^{∗}-terms. With a little more work, the proof (below) of Theorem 4 can be modified to show that the cells of the decompositions can be taken to be ℜ-cells. Moreover, if ℜ admits C^{∞} (or analytic) decomposition, then the cells can be taken to be C^{∞} (or analytic) cells. In particular, every set definable in (\overline{ℝ}, α^{ℤ}) is a countable disjoint union of analytic semialgebraic cells, and every set definable in (ℝ_{an}, α^{ℤ}) is a countable disjoint union of analytic, globally subanalytic cells (see e.g. [13] for a definition of ℝ_{an}). The details are left to a possible future paper (or to the reader as an exercise).

8.7. Proof of Theorem 4. First, we dispose of some preliminaries.

For ϵ > 0 and x ∈ ℝ^{n}, B(x, ϵ) denotes the cube centered at x with side length 2ϵ.

For A, B ⊆ ℝ, write A ≅ B if A and B are order-isomorphic. For X ⊆ ℝ we have:

• X ≅ ℕ iff X is discrete, min X exists, max X does not exist, and X is closed in the interval (min X, sup X).

• X ≅ −ℕ iff X is discrete, max X exists, min X does not exist, and X is closed in (inf X, max X).

• X ≅ ℤ iff X is discrete, neither min X nor max X exist, and X is closed in (inf X, sup X).

• X is finite iff X is discrete, closed and bounded. Hence, if A ⊆ ℝ^{n+1}, then the following sets are definable in (ℝ, <, A):

{ x ∈ ℝ^{n} : A_{x} ≅ ℕ }
{ x ∈ ℝ^{n} : A_{x} ≅ −ℕ }
{ x ∈ ℝ^{n} : A_{x} ≅ ℤ }
{ x ∈ ℝ^{n} : A_{x} is finite }

For −∞ ≤ a < b ≤ +∞, put

midpt(a, b) = \begin{cases}(a + b)/2 & if a, b ∈ ℝ \\ 0 & if a = −∞ and b = +∞ \\ a + 1 & if a ∈ ℝ and b = +∞ \\ b − 1 & if a = −∞ and b ∈ ℝ. \end{cases}

For U ⊆ ℝ open, let midpts(U) be the set of all points midpt(a, b), where (a, b) is a connected component of U. Note that if A ⊆ ℝ, then bd(A) ∪ midpts(int(A)) is closed, has no interior, and is definable in (ℝ, <, +, A).

We now begin the proof proper. Suppose ℜ expands (ℝ, <, +) and is d-minimal. We show that ℜ admits countable decomposition (and that the C^{p} version holds if ℜ expands \overline{ℝ}). We proceed by induction on n ≥ 1 and (d, e) := max{ fdim(πA) : A ∈ A } to show that if A is a finite collection of definable subsets of ℝ^{n}, then there is a countable decomposition of ℝ^{n} compatible with A.

Suppose n = 1. Each A ∈ A has countable boundary (since bd(A) is a finite union of discrete sets), so the collection of the connected components of the sets

⋃_{A∈A} bd(A), ℝ \ ⋃_{A∈A} bd(A)

is a countable decomposition of ℝ compatible with A.

Let n > 1 and assume the result holds for all m ≤ n; we show the result holds for n + 1. Suppose d = 0. Inductively, there is a countable decomposition C of ℝ^{n} compatible with πA := { πA : A ∈ A }. Then { C × ℝ : C ∈ C, C ⊈ ⋃ πA }, together with the connected components of the sets

{x} × ⋃_{A∈A} bd(A_{x}), ℝ \ ({x} × ⋃_{A∈A} bd(A_{x}))

(x ∈ ⋃ πA) is a countable decomposition of ℝ^{n+1} compatible with A.

Suppose d > 0. Put

Y = ⋃_{A∈A}{ (x, t) ∈ ℝ^{n+1} : t ∈ bd(A_{x}) ∪ midpts(int(A_{x})) }.

We need only find a countable decomposition of ℝ^{n+1} compatible with Y (since it will be compatible with A). Each Y_{x} is closed and has no interior. By d-minimality, there exists N ∈ ℕ such that Y_{x}^{[N]} = ∅ for all x ∈ ℝ^{n}. We proceed now by induction on N ≥ 1.

Suppose N = 1. Then each Y_{x} is closed and discrete, so πY is equal the union of the following definable sets:

S_{1} := { x ∈ ℝ^{n} : Y_{x} ≅ ℕ }
S_{2} := { x ∈ ℝ^{n} : Y_{x} ≅ −ℕ }
S_{3} := { x ∈ ℝ^{n} : 0 ∈ Y_{x} ≅ ℤ }
S_{4} := { x ∈ ℝ^{n} : 0 ∉ Y_{x} ≅ ℤ }
S_{5} := { x ∈ ℝ^{n} : Y_{x} is finite and nonempty }.

For each l = 1, …, 4, Y ∩ π^{−1}(S_{l}) is a countable union of graphs of definable functions S_{l} → ℝ, as we now show. Define (f_{1,j}: S_{1} → ℝ)_{j∈ℕ} (by induction):

f_{1,0}(x) = min Y_{x}
f_{1,j+1}(x) = min(Y_{x} ∩ (f_{1,j}(x), ∞)).

Define (f_{2,j}: S_{2} → ℝ)_{j∈−ℕ} by:

f_{2,0}(x) = max Y_{x}
f_{2,j−1}(x) = max(Y_{x} ∩ (−∞, f_{2,j}(x))).

Define (f_{3,j}: S_{3} → ℝ)_{j∈ℤ} by letting f_{3,0} be the 0 map on S_{3} and then combining the previous arguments. Define (f_{4,j}: S_{4} → ℝ)_{j∈ℤ} by f_{4,0}(x) = min(Y_{x} ∩ (0, ∞)); again finish by combining previous arguments.

We now consider the special case d = n (that is, πY has interior). By arguing as in §8.5,^{21} there is a definable open S ⊆ ℝ^{n} such that πY \ S has no interior and Y ∩ π^{−1}(S) is a π-special C^{0}-submanifold. Inductively, there is a countable decomposition C of ℝ^{n} compatible with {S_{1} ∩ S, …, S_{5} ∩ S}. Note that if C ∈ C is contained in S_{5} ∩ S, then Y ∩π^{−1}(C) is a finite disjoint union of graphs of continuous functions C → ℝ, each of which is definable (by the constant finite cardinality of the fibers). Hence, if C ∈ C is contained in (S_{1} ∪⋯∪S_{5})∩S, then every connected component of either π^{−1}(C)∩Y or π^{−1}(C)\Y is a cell, compatible with Y, that projects onto C. Then there is a countable decomposition D_{1} of ℝ^{n+1} compatible with Y ∩ π^{−1}(S) such that if D ∈ D_{1} and πD ∩ (ℝ^{n} \ S) ≠ ∅, then D = πD ×ℝ. Since πY \S has no interior, there is (inductively) a countable decomposition D_{2} of ℝ^{n+1}, compatible with Y \ π^{−1}(S), such that if D ∈ D_{2} and πD ∩ S ≠ ∅, then D = πD × ℝ. Hence,

D := { D ∈ D_{1} : πD ⊆ S } ∪ { D ∈ D_{2} : πD ⊆ ℝ^{n} \ S }

is a countable decomposition of ℝ^{n+1} compatible with Y (hence also with A).

The proof for the case 0 < d < n is a minor modification. Let μ ∈ Π(n, d) be such that (μ ∘ π)(Y) has interior. By arguing as in §8.5, there is a definable open S ⊆ ℝ^{d} such that (μ ∘ π)(Y) \ S has no interior and Y ∩ (μ ∘ π)^{−1}(S) is a (μ ∘ π)-special C^{0}-submanifold of ℝ^{n+1}. Inductively, there is a countable decomposition C of ℝ^{n} compatible with {S_{1} ∩ μ^{−1}(S), …, S_{5} ∩μ^{−1}(S)}. If C ∈ C is contained in any of S_{1} ∩μ^{−1}(S), …, S_{5} ∩μ^{−1}(S), then every connected component of either π^{−1}(C) ∩ Y or π^{−1}(C) \ Y is a cell, compatible with Y, that projects onto C. Then there is a countable decomposition D_{1} of ℝ^{n+1} compatible with Y ∩ (μ ∘ π)^{−1}(S)) such that if D ∈ D_{1} and πD ∩ (ℝ^{n} \ μ^{−1}(S)) ≠ ∅, then D = πD × ℝ. Since fdim(πY \ μ^{−1}(S)) < fdim(πY), there is (inductively) a countable decomposition D_{2} of ℝ^{n+1}, compatible with Y \ (μ ∘ π)^{−1}(S), such that if D ∈ D_{2} and πD ∩ μ^{−1}(S) ≠ ∅, then D = πD × ℝ. Hence,

D := { D ∈ D_{1} : πD ⊆ μ^{−1}(S) } ∪ { D ∈ D_{2} : πD ⊆ ℝ^{n} \ μ^{−1}(S) }

is a countable decomposition of ℝ^{n+1} compatible with Y.

We have finished the case N = 1. Having done it in detail, we now concentrate on the remaining main ideas of the proof, leaving more routine details to the reader.

For A ⊆ ℝ^{n} and f, g: A → ℝ ∪ {±∞}, put

(f, g) = { (x, t) ∈ A × ℝ : f(x) < t < g(x) }.

21But this refers to the flawed part of the argument, so more precisely, as in the repaired proof in [50].

Suppose N > 0 and Y_{x}^{[N+1]} = ∅ for all x ∈ ℝ^{n}. We do the details only of the case d = n. (As before, the case 0 < d < n is a minor modification.) Put

W = { (x, t) ∈ ℝ^{n+1} : t ∈ isol(Y_{x}) }
Z = { (x, t) ∈ ℝ^{n+1} : t ∈ Y_{x}^{[1]} }.

Then Y is the disjoint union of W and Z. For every x ∈ ℝ^{n}: W_{x} = isol(Y_{x}); Z_{x} ⊆ fr(W_{x}); Z_{x} is closed; and Z_{x}^{[N]} = ∅. Put

W′ = { (x, t) ∈ W : t ∈ midpts(ℝ \ Z_{x}) }
S_{0} = { x ∈ πW′ : ∃ϵ > 0, W ∩ π^{−1}(B(x, ϵ)) is a π-special C^{0}-submanifold }
T_{0} = { x ∈ πW : ∃ϵ > 0, W ∩ π^{−1}(B(x, ϵ)) is a π-special C^{0}-submanifold }

There exist definable S, T such that S is dense-open in S_{0} and T is dense-open in T_{0}. By the inductive assumption on N, there is a countable decomposition D of ℝ^{n+1} compatible with {Z, Z ∩ π^{−1}(S), Z ∩ π^{−1}(T)}. Let C ∈ πD be a cell contained in T. Note that either C ⊆ S or C ⊆ T \ S. Every connected component of Z ∩ π^{−1}(C) is a non-open cell that projects onto C. Since W ∩ π^{−1}(T) is a π-special C^{0}-submanifold and C is simply connected, there is a countable family (ϕ_{j}: C → ℝ)_{j∈J} of continuous functions (J some index set) such that W ∩ (C × ℝ) is the disjoint union of the graphs of the ϕ_{j}; the only remaining non-routine work is to show that these functions are definable. Fix one ϕ. Since Z ∩π^{−1}(C) is a disjoint union of graphs of continuous functions C → ℝ, we have exactly three cases to consider:

(1) ϕ(x) > t for all x ∈ C and t ∈ Z_{x}.

(2) ϕ(x) < t for all x ∈ C and t ∈ Z_{x}.

(3) For every x ∈ C, both max(Z_{x} ∩ (−∞, ϕ(x))) and min(Z_{x} ∩ (ϕ(x), ∞)) exist (recall that Z_{x} is closed).

Suppose Case 1 holds. Put h(x) = max Z_{x} for x ∈ C. Note that h is definable and h(x) + 1 = midpt(h(x), ∞) for all x ∈ C. There exists K ⊆ J such that W ∩ (h, ∞) = ⋃_{j∈K} graph(ϕ_{j}). We have five subcases:

(i) K is finite (then certainly each ϕ_{j} with j ∈ K is definable, and we are done).

(ii) K ≅ ℕ (iii) K ≅ −ℕ (iv) K ≅ ℤ and h(x) + 1 ∈ W_{x} for all x ∈ C.

(v) K ≅ ℤ and h(x) + 1 ∉ W_{x} for all x ∈ C. If (ii) holds, then min(W_{x} ∩ (h(x), ∞)) exists for all x ∈ C. Hence, each ϕ_{j} lying strictly above h is definable by induction (as in the case N = 1). Subcase (iii) is similar (but note also that h(x) = inf W_{x} for all x ∈ C). Assume (iv) or (v) holds. For ease of notation, take K = ℤ and, if j, k ∈ ℤ with j < k, then ϕ_{j} < ϕ_{k}. After re-indexing, we have either ϕ_{0} = h + 1 or ϕ_{0} < h + 1 < ϕ_{1} (definitely the latter if C ⊆ T \ S). In either case, ϕ_{0} is definable. Again, we define all ϕ_{j} with j ∈ K by induction.

Case 2 is handled by an easy modification.

For Case 3, define g, h: C → ℝ by:

g(x) = max(Z_{x} ∩ (−∞, ϕ(x)))
h(x) = min(Z_{x} ∩ (ϕ(x), ∞)).

It is not clear from their definitions that g and h are definable—we do not yet know if ϕ is definable—but they are: their graphs are contained in Z and thus are cells. Note that midpt(g(x), h(x)) = (g(x) + h(x))/2 for all x ∈ C. The rest of the argument is a routine modification of that for Case 1.

(We have now finished the proof of the C^{0} version of the theorem.) If ℜ expands \overline{ℝ}, then countable C^{p}-decomposition is obtained just by replacing “C^{0}” (or

“continuous”, as the case may be) with “C^{p}”. □

References

1. O. Belegradek, F. Wagner, and Y. Peterzil, Quasi-o-minimal structures, Journal of Symbolic Logic 65 (2000), 1115–1132.

2. O. Belegradek and B. Zilber, The model theory of the field of reals with a subgroup of the unit circle, Journal of the London Mathematical Society. Second Series 78 (2008), no. 3, 563–579.

3. J. Bochnak, M. Coste, and M.-F. Roy, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge), vol. 36, Springer-Verlag, 1998.

4. A. Dolich, C. Miller, and C. Steinhorn, Structures having o-minimal open core, Transactions of the American Mathematical Society 362 (2010), 1371–1411.

5. R. Dougherty and C. Miller, Definable boolean combinations of open sets are boolean combinations of open definable sets, Illinois Journal of Mathematics 45 (2001), 1347–1350.

6. L. van den Dries, The field of reals with a predicate for the powers of two, Manuscripta Mathematica 54 (1985), 187–195.

7. , A generalization of the Tarski-Seidenberg theorem, and some nondefinability results, Bulletin of the American Mathematical Society (New Series) 15 (1986), 189–193.

8. , On the elementary theory of restricted elementary functions, Journal of Symbolic Logic 53 (1988), 796–808.

9. , o-Minimal structures, Logic: From Foundations to Applications, Oxford Science Publications, Oxford University Press, 1996, pp. 137–185.

10. , T -convexity and tame extensions. II, Journal of Symbolic Logic 62 (1997), 14–34.

11. , Dense pairs of o-minimal structures, Fundamenta Mathematicae 157 (1998), 61–78.

12. , Tame topology and o-minimal structures, London Mathematical Society Lecture Note Series, vol. 248, Cambridge University Press, 1998.

13. L. van den Dries and C. Miller, Geometric categories and o-minimal structures, Duke Mathematical Journal 84 (1996), 497–540.

14. L. van den Dries and P. Speissegger, The real field with convergent generalized power series, Transactions of the American Mathematical Society 350 (1998), 4377–4421.

15. , The field of reals with multisummable series and the exponential function, Proceedings of the London Mathematical Society (3) 81 (2000), 513–565.

16. G. Edgar and C. Miller, Hausdorff dimension, analytic sets and transcendence, Real Analysis Exchange 27 (2001/02), 335–339.

17. , Borel subrings of the reals, Proceedings of the American Mathematical Society 131 (2003), 1121–1129.

18. A. Fornasiero, P. Hieronymi, and E. Walsberg, How to avoid a compact set, preprint, arXiv:1612.00785.

19. H. Friedman, K. Kurdyka, C. Miller, and P. Speissegger, Expansions of the real field by open sets: definability versus interpretability, Journal of Symbolic Logic 75 (2010), 1311–1325.

20. H. Friedman and C. Miller, Expansions of o-minimal structures by sparse sets, Fundamenta Mathematicae 167 (2001), 55–64.

21. H. Friedman and C. Miller, Expansions of o-minimal structures by fast sequences, Journal of Symbolic Logic 70 (2005), 410–418.

22. A. Günaydın and P. Hieronymi, The real field with the rational points of an elliptic curve, Fundamenta Mathematicae 211 (2011), no. 1, 15–40.

23. F. Hausdorff, Set theory, 4th English ed., Chelsea, 1991.

24. P. Hieronymi, Defining the set of integers in expansions of the real field by a closed discrete set, Proceedings of the American Mathematical Society 138 (2010), no. 6, 2163–2168.

25. , Expansions of subfields of the real field by a discrete set, Fundamenta Mathematicae 215 (2011), no. 2, 167–175.

26. P. Hieronymi and C. Miller, Metric dimensions and tameness in expansions of the real field, preprint, arXiv:1510.00964.

27. A. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, 1995.

28. M. Khani, The field of reals with a predicate for the real algebraic numbers and a predicate for the integer powers of two, Archive for Mathematical Logic 54 (2015), no. 7-8, 885–898.

29. K. Kuratowski, Topology, vol. 1, Academic Press, 1966.

30. S. Lang, Algebra, 2nd ed., Addison-Wesley, 1984.

31. M. Laskowski and C. Steinhorn, On o-minimal expansions of Archimedean ordered groups, Journal of Symbolic Logic 60 (1995), 817–831.

32. D. Macpherson, Notes on o-minimality and variations, Model Theory, Algebra, and Geometry, Mathematical Sciences Research Institute Publications, vol. 39, Cambridge University Press, 2000, pp. 97–130.

33. L. Mathews, Cell decomposition and dimension functions in first-order topological structures, Proceedings of the London Mathematical Society (3) 70 (1995), 1–32.

34. C. Miller, Expansions of the real field with power functions, Annals of Pure and Applied Logic 68 (1994), 79–94.

35. , Expansions of dense linear orders with the intermediate value property, Journal of Symbolic Logic 66 (2001), 1783–1790.

36. , Avoiding the projective hierarchy in expansions of the real field by sequences, Proceedings of the American Mathematical Society 134 (2006), 1483–1493.

37. , Expansions of o-minimal structures on the real field by trajectories of linear vector fields, Proceedings of the American Mathematical Society 139 (2011), no. 1, 319–330.

38. C. Miller and P. Speissegger, Expansions of the real line by open sets: o-minimality and open cores, Fundamenta Mathematicae 162 (1999), 193–208.

39. C. Miller and A. Thamrongthanyalak, D-minimal expansions of the real field have the c^{p} zero set property, preprint, available at www.math.osu/ miller.

40. C. Miller and J. Tyne, Expansions of o-minimal structures by iteration sequences, Notre Dame Journal of Formal Logic 47 (2006), 93–99.

41. J. Oxtoby, Measure and category, 2nd ed., Graduate Texts in Mathematics, vol. 2, Springer-Verlag, 1980.

42. A. Pillay, First order topological structures and theories, Journal of Symbolic Logic 52 (1987), 763–778.

43. A. Pillay and C. Steinhorn, Definable sets in ordered structures. I, Transactions of the American Mathematical Society 295 (1986), 565–592.

44. A. Robinson, A note on topological model theory, Fundamenta Mathematicae 81 (1974), 159–171.

45. J. Robinson, The undecidability of algebraic rings and fields, Proceedings of the American Mathematical Society 10 (1959), 950–957.

46. R. Robinson, The undecidability of pure transcendental extensions of real fields, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 10 (1964), 275–282.

47. J.-P. Rolin, P. Speissegger, and A. Wilkie, Quasianalytic Denjoy-Carleman classes and o-minimality, Journal of the American Mathematical Society 16 (2003), 751–777.

48. H. Royden, Real analysis, 3rd ed., Macmillan, 1988.

49. M. Shiota, Geometry of subanalytic and semialgebraic sets, Progress in Mathematics, vol. 150, Birkhäuser, 1997.

50. A. Thamrongthanyalak, Michael’s selection theorem in d-minimal expansions of the real field, in preparation.

51. M. Tychonievich, Defining additive subgroups of the reals from convex subsets, Proceedings of the American Mathematical Society 137 (2009), no. 10, 3473–3476.

52. , The set of restricted complex exponents for expansions of the reals, Notre Dame Journal of Formal Logic 53 (2012), no. 2, 175–186.

53. I. Vinogradov, The representation of an odd number as a sum of three primes, Doklady Akademii Nauk SSSR 16 (1937), 139–142 (in Russian).

Department of Mathematics, The Ohio State University, 231 West 18th Avenue, Columbus, Ohio 43210, USA

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