O-Minimality

A. J. Wilkie

In the paper [11] Tarski makes the following observation: every subset of the set of real numbers ℝ definable in the ordered ring ⟨ℝ; +,^{.} , 0, 1, <⟩ (which I shall henceforth denote by ℝ̄) is a finite union of open intervals and points. This is certainly an easy consequence of his famous quantifier elimination theorem ([12]) - that every subset of ℝ^{n} definable in ℝ̄ is semi-algebraic, i.e. definable by a quantifier free formula - and must have seemed a relatively unimportant one at the time. However, it turned out to be a remarkable insight. For in the 1980’s van den Dries showed that most of the qualitative geometric and topological finiteness properties enjoyed by the class of semi-algebraic sets actually follow from this observation alone. Indeed, many such properties, e.g. finite cell-decomposition theorems in the continuous category, do not even require the ring structure, although some do, e.g. finite cell-decomposition theorems in the differentiable category and finite triangulation theorems.

The property described in Tarski’s observation is now known as o-minimality and, as was shown by Knight, Pillay and Steinhorn in [7] and [10], it can be fruitfully considered in quite general situations: a structure M = ⟨M, <, ...⟩, where < is a dense, linear order (without endpoints) of the domain M, is called o-minimal if every definable (without parameters) subset of M is a finite union of points and open intervals (with endpoints in M ∪ {±∞}).

It is a suprising and non-obvious fact that o-minimality is preserved under elementary equivalence. This is one of the main results of [7] and is typical of the ”uniformity-in-parameters” that crops up frequently in this subject: it is equivalent to the statement that for any formula ϕ(x_{1}, ..., x_{n}, y) of the language of M, there is a natural number N depending only on ϕ such that the set {bϵM : M ⊧ ϕ[a_{1}, ..., a_{n}, b]} is the union of at most N open intervals and points for any choice of parameters a_{1}, .., a_{n}ϵM.

More generally, one can also deduce from the assumption of o-minimality that there are only finitely many homeomorphism types amongst sets of the form {< b_{1}, ..., b_{r} >}ϵM^{r} : M ⊧ ψ[a_{1}, ..., a_{n}, b_{1}, ..., b_{r}]} as < a_{1}, .., a_{n} > varies over M^{n}, where ψ(x_{1}, ..., x_{n}, y_{1}, .., y_{r}) is a formula of the language of M. (Here, M^{r} is equipped with the product topology and M with the order topology.) Similar results and, indeed, a definitive account of the foundations of the general theory of o-minimality can be found in van den Dries’ recent book [3].

Of course, this general theory is only worthwhile if there are interesting examples (other than ℝ̄ and its reducts) and it is my main aim in this short note to state a result that provides a rich source of o-minimal expansions of ℝ̄.

Let ℝ̃ be any expansion of the real ordered field ℝ̄ with language L̃ say. Call a formula ψ of L̃ tame if there exists a natural number N (depending only on ψ) such that whenever the free variables of ψ are partitioned into two classes, say ψ = ψ(x_{1}, ..., x_{m}, y_{1}, ., y_{r}), then the set {< b_{1}, ..., b_{r} > ϵℝ^{r} : M ⊧ ψ[a_{1}, ..., a_{n}, b_{1}, .., b_{r}]} has at most N connected components for any choice of < a_{1}, ..., a_{n} > ϵℝ^{n}. Then I know of no counterexample to the following

Conjecture

With ℝ̃ as above, if every quantifier free formula of L̃ is tame then ℝ̃ is o-minimal (which, in fact, implies that every formula of L̃ is tame - see [7] again).

I am, however, rather sceptical.

In order to state my result in this direction it is convenient to introduce a unary connective, denoted C, to our language, with truth condition:-

ℝ̃ ⊧ (Cϕ)[a_{1},^{.} .., a_{n}] if and only if < a_{1},^{.} .., a_{n} > lies in the closure (in ℝ^{n}) of the set {< b_{1}, ..., b_{n} > ϵℝ^{n} : ℝ̃ ⊧ ϕ[b_{1}, ..., b_{n}]}.

Clearly C is already definable in L̃ (for interpretations expanding ℝ̄) but the point is that we have the following

Theorem (Wilkie, [14]).

Let ℝ̃ be as above and suppose that every quantifier free formula is tame. Then so is any formula that can be obtained from quantifier free formulas by finitely many applications of conjunction, disjunction, existential quantification and the connective C. Further, if we also assume that ℝ̃ has the form < ℝ̄, F > where F is a collection of infinitely differentiable functions from ℝ^{n} to ℝ (for various n’s), then any formula of L̃ is equivalent (in ℝ̃) to one of this type, and hence (since a connected subset of ℝ is an interval) ℝ̃ is o-minimal.

The reason for proving a theorem of this type was that the tameness condition on the quantifier free definable sets was established for a wide class of examples through the work of Khovanskii ([6], but see also [5] in conjunction with [8]). He showed that it holds for structures of the form < ℝ̄, f_{1}, ..., f_{p} > where f_{1}, ..., f_{p} : ℝ^{n} → ℝ are infinitely differentiable functions (actually, the following implies they are analytic) satisfying a system of partial differential equations of the form

\frac{∂f_{i}}{∂x_{j}} = P_{i},_{j} (x_{1}, ..., x_{n}, f_{1}, ..., f_{i}), 1 ≤ i ≤ p, 1 ≤ j ≤ p,

where each P_{i},_{j} (x_{1}, .., x_{n}, y_{1}, ..., y_{i}) is a polynomial with real coefficients. (The sequence f_{1}, ..., f_{p} is then called a Pfaffian chain on ℝ^{n}).

Thus, by the theorem, these structures are o-minimal.

In particular, ⟨ℝ̄, exp⟩ is o-minimal, where exp(x) = e^{x} is the exponential funtion (take p = n = 1, P_{1},_{1} (x_{1}, y_{1}) = y_{1}). In fact, this result appears in [1] although some of the arguments in that paper are, to my mind, incomplete. However, the main idea there is fundamentally sound and was studied extensively by my student S. Maxwell (see[9]) before I finally adapted it to establish the theorem above. Perhaps I should also mention that in the case of ⟨ℝ̄, exp⟩ we now have better information (see[13]): every definable set is existentially definable (from which o-minimality follows very easily from Khovanskii’s result). However, nothing like this is known for expansion of ℝ̄ by general Pfaffian chains. I conclude with an application of the general uniformity result mentioned earlier. Clearly, if we take M = ℝ̄ then we can deduce that for any n, k there is N = N(n, k) such that there are at most N homeomorphism types of sets of the form P^{−1}(0) where P : ℝ^{n} → ℝ is a real polynomial of total degree at most k. This was actually proved by Hardt (see[4]) before o-minimality came on the scene. Now van den Dries noticed that if we take M = ⟨ℝ̄, exp⟩ then Hardt’s result may be improved by using a trick of Khovanskii’s. Namely, we take the exponents of the variables in P, as well as the coefficients, as parameters - which we can do as long as we bound the number of monomial terms in P. We then obtain the result that for any n, k there is N = N(n, k) such that there are at most N homeomorphism types of sets of the forms P^{−1}(0) where P : ℝ^{n} → ℝ is a real polynomial (of arbitray degree but) which is the sum of at most k monomials (i.e. terms of the form ax_{1}^{q_{1}} ⋯ x_{n}^{q_{n}} for aϵℝ and q_{1}, ..., q_{n}ϵℕ, although, in fact, we could also allow q_{1}, ..., q_{n}ϵℝ). (Remark: for n = 1 this is usually attributed to Descartes).

More recently Coste ([2]) has proved a uniformity result for the homeomorphism types of definable functions in o-minimal structures and this gives a corresponding result for the homeomorphism types of polynomials with a restricted number of monomial terms.

References

[1] J.-Y. Charbonnel, ’Sur certains sous-ensembles de l’espace euclidean’, Ann. Ins. Fourier. Grenoble 41, 3 (1991), 679–717.

[2] M. Coste, ’Topological types of fewnomials’, Preprint 96–39 (1996), University of Rennes.

[3] L. van den Dries, ’Tame topology and o-minimal structures’, LMS Lecture Note Series 248, CUP, (1998)

[4] R. Hardt, ’Semi-algebraic local triviality in semi-algebraic mappings’, Amer.J. Maths. 102 (1980), 291–302.

[5] A. G. Khovanskii, ’On a class of systems of transcendental equations’, Soviet Math. Dokl. 22 (1980), 762–765.

[6] ——, ’Fewnomials’, AMS Translations No. 88, (1991).

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

[8] D. Marker, ’Khovanskii’s Theorem, in ’Algebraic Model Theory’, (B. T. Hart et al. (eds), Toronto, ON). (1997), Kluwer 181–193.

[9] S. Maxwell, ’A general model completeness result for expansions of the real ordered field’, to appear in Annals of Pure and Applied Logic.

[10] A. Pillay and C. Steinhorn, ’Definable sets and ordered structures, I’, Trans. Amer. Math. Soc. 295 (1986), 565–592.

[11] A. Tarski, ’Sur le ensembles definissables de nombres reels’, Fund. Math. 17 (1931), 210–239.

[12] ——, ’A decision method for elementary algebra and geometry’, Second edition revised, Rand Corporation, Berkley and Los Angeles, (1951).

[13] A. J. Wilkie, ’Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function’, J. Amer. Math. Soc. 9, No. 4, (1996), 1051–1094.

[14] ——, ’A general theorem of the complement and some new o-minimal structures’. (Submitted).

A. J. Wilkie

Mathematical Institute University of Oxford 24-29 St. Giles OX1 3LB Oxford England