Abstract

Wilkie 5 397) proved a “theorem of the complement” which implies that in order to establish the o-minimality of an expansion of with C∞ functions it suffices to obtain uniform bounds on the number of connected components of quantifier free definable sets. He deduced that any expansion of with a family of Pfaffian functions is o-minimal. We prove an effective version of Wilkie's theorem of the complement, so in particular given an expansion of the ordered field with finitely many C∞ functions, if there are uniform and computable upper bounds on the number of connected components of quantifier free definable sets, then there are uniform and computable bounds for all definable sets. In such a case the theory of the structure is effectively o-minimal: there is a recursively axiomatized subtheory such that each of its models is o-minimal. This implies the effective o-minimality of any expansion of with Pfaffian functions. We apply our results to the open problem of the decidability of the theory of the real field with the exponential function. We show that the decidability is implied by a positive answer to the following problem ): given a language L expanding the language of ordered rings, if an L-sentence is true in every L-structure expanding the ordered field of real numbers, then it is true in every o-minimal L-structure expanding any real closed field