DEFINABLE CHOICE IN D-MINIMAL EXPANSIONS OF ORDERED GROUPS*

CHRIS MILLER

Version: December 15, 2006

A (first-order) theory T extending the theory of dense linear orders without endpoints is d-minimal (short for “discrete-minimal”) if in every model of T:

• The underlying set of the model is definably connected (in the model).

• Every unary (parametrically) definable set either has interior or is a finite union of

discrete sets. The intent is, loosely speaking, to capture the notion of the next best thing to o-mini-

mality for theories whose models may define infinite discrete sets. Note that T is o-minimal if, in the above, “discrete sets” is replaced by “points”.

An expansion of a dense linear order without endpoints is d-minimal if its complete theory is d-minimal. See [FM05, Mil05, MT06] for some examples of structures that are d-minimal but not o-minimal.

The main result of this note extends a useful fact from o-minimality:

Theorem. Let T be a complete d-minimal theory extending the theory of dense ordered groups with a distinguished positive element. Then T has definable Skolem functions and elimination of imaginaries.

Indeed:

Definable Choice. Let ℜ be a d-minimal expansion of a dense ordered group (R, <, +, 0, 1) with 1 > 0. Then:

• If Y ⊆ R^{m+n} is ∅-definable and X is the projection of Y on the first m coordinates, then there is a ∅-definable f: X → R^{n} such that the graph of f is contained in Y.

• If E is a ∅-definable equivalence relation on a ∅-definable X ⊆ R^{m}, then there is a ∅-definable f: X → X such that xEy ⇔ f(x) = f(y) for all x, y ∈ X.

(Of course, the above then holds with “A-definable” in place of “∅-definable” for any A ⊆ R.)

The use of abelian notation is justified: Definable connectedness allows us to work in many respects as if we were over the reals—see e.g. [Mil01] for details—in particular, every definably connected dense ordered group is abelian and divisible.

From now on, ℜ denotes a fixed, but arbitrary, expansion of a dense linear order without endpoints (R, <). Definability is with respect to ℜ. Topological notions are with respect to the usual box topologies. The variables m and n range over ℕ (the non-negative integers).

The definition of d-minimality given above is possibly the easiest to state, but it misses the point somewhat, especially for structures.

*This is not a preprint; please do not refer to it as such.

Proposition 1. ℜ is d-minimal if and only if R is definably connected and for every definable S ⊆ R^{m+1} there exists N ∈ ℕ such that for all x ∈ R^{m} the fiber

S_{x} := { t ∈ R : (x, t) ∈ S }

either has interior or is a union of N (not necessarily distinct) discrete sets.

Proof. It is easy to see that definable connectedness is an elementary property. The rest is a routine compactness argument; cf. [Mil05, §8.5]. □

Note. Under the present definition, d-minimality of structures is trivially preserved under elementary equivalence. One of the remarkable facts about o-minimality is that this artifice is unnecessary: If ℜ is o-minimal—i.e., if every unary definable set is a finite union of points and open intervals—then the same is true of every ℜ′ ≡ ℜ [KPS86]. Open questions: If R is definably connected and every unary definable set either has interior or is a finite union of discrete sets, is ℜ d-minimal? What if ℜ expands an ordered group or field? What if R = ℝ?

Proof of Definable Choice. (Cf. [Dri98, pp. 93–94] and the proof of [Mil05, Theorem 4].) Suppose that ℜ is a d-minimal expansion of a dense ordered group (R, <, +, 0, 1) with 1 > 0. For A ⊆ R, put:

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

If A is ∅-definable, then so are each of the above sets. For each n, let B_{n} be the collection of all nonempty ∅-definable A ⊆ R such that bd(A) is a union of n discrete sets. Note if S ⊆ R^{m+1} is ∅-definable, then { x ∈ R^{m} : S_{x} ∈ B_{n} } is ∅-definable. By the previous proposition (and a routine induction; see [Dri98, pp. 94]), it suffices to show that for every n there exists β_{n}: B_{n} → R such that:

• For every A ∈ B_{n}, β_{n}(A) ∈ int(A) ∪ isol(A);

• For every ∅-definable S ⊆ R^{m+1}, the function

x ↦ β_{n}(S_{x}): { x ∈ R^{m} : S_{x} ∈ B_{n} } → R

is ∅-definable. These requirements will be realized by construction.

First, for each n, put A_{n} = { A ∈ B_{n} : int(A) = ∅ }. Note that A_{0} = ∅. We define functions α_{n}: A_{n} → R by induction on n ≥ 1 such that for every n ≥ 1 and A ∈ A_{n} we have α_{n}(A) ∈ isol(A) and α_{n+1}↾A_{n} = α_{n}.

Suppose n = 1. Then every A ∈ A is nonempty, closed and discrete. Define α_{1} by

α_{1}(A) = \begin{cases}min A, & if inf A ≠ −∞ \\ max A, & if inf A = −∞ and sup A < +∞ \\ min\{ t ∈ A : t ≥ 0 \}, & otherwise. \end{cases}

(The existence of the appropriate maxima and minima follows from definable connectedness; see [Mil01, 1.10].)

Assume the result for a certain n ≥ 1; we show it for n + 1. Let A ∈ A_{n+1}. If A ∈ A_{n}, then put α_{n+1}(A) = α_{n}(A). Suppose that A ∉ A_{n}; then cl(A) \ isol(A) ∈ A_{n}. Inductively, put b = α_{n}(cl(A) \ isol(A)). Now, b is a limit point of isol(A)—but not of A \ isol(A), nota bene—so it is limit point of at least one of (−∞, b) ∩ isol(A) or (b, ∞) ∩ isol(A). If the former, put a = inf{ t < b : (t, b) ∩ A ⊆ isol(A) } and

α_{n+1}(A) = \begin{cases}min\{ t ∈ A : t ≥ b − 1 \}, & if a = −∞ \\ min\{ t ∈ A : 2t ≥ b − a \}, & otherwise. \end{cases}

If b is not a limit point of (−∞, b) ∩ isol(A), then put c = sup{ t > b : (b, t) ∩ A ⊆ isol(A) } and

α_{n+1}(A) = \begin{cases}min\{ t ∈ A : t ≥ b + 1 \}, & if c = ∞ \\ min\{ t ∈ A : 2t ≥ b + a \}, & otherwise. \end{cases}

(We have finished the construction of the functions α_{n}.)

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

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

For U ⊆ R open and definable, put

midpts(U) = { midpt(a, b) : −∞ ≤ a < b ≤ +∞, (a, b) ⊆ U, a, b ∉ U }.

Note that midpts(U) ∈ A_{n+1} if U ∈ B_{n} \ A_{n}. Finally, for n ∈ ℕ and B ∈ B_{n}, put

β_{n}(B) = \begin{cases}α_{n}(B), & B ∈ A_{n} \\ α_{n+1}(midpts(int(B))), & B ∉ A_{n} \end{cases}  □

Corollary 1 (of the proof). If ℜ expands a dense ordered group (R, <, +, 0, 1) with 1 > 0 such that R is definably connected, then for all m, n and ∅-definable S ⊆ R^{m+1}, the function x ↦ β_{n}(S_{x}): { x ∈ R^{m} : S_{x} ∈ B_{n} } → R is ∅-definable.

Corollary 2. For all m, n and S ⊆ ℝ^{m+1}, x ↦ β_{n}(S_{x}): { x ∈ ℝ^{m} : S_{x} ∈ B_{n} } → ℝ is ∅-definable in (ℝ, <, +, 1, S).

References

[Dri98] L. van den Dries, Tame topology and o-minimal structures, London Math. Soc. Lecture Note Ser., vol. 248, Cambridge University Press, Cambridge, 1998.

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

[KPS86] J. Knight, A. Pillay, and C. Steinhorn, Definable sets in ordered structures. II, Trans. Amer. Math. Soc. 295 (1986), 593–605.

[Mil01] C. Miller, Expansions of dense linear orders with the intermediate value property, J. Symbolic Logic 66 (2001), 1783–1790.

[Mil05] , Tameness in expansions of the real field, Logic Colloquium ’01 (Vienna, 2001), Lect. Notes in Logic, vol. 20, Assoc. Symbolic Logic, Urbana, IL, 2005, pp. 281–316.

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

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

E-mail address: miller@math.ohio-state.edu
URL: http://www.math.ohio-state.edu/~miller