Wilkie's theorem

In mathematics, Wilkie's theorem is a result by Alex Wilkie about the theory of ordered fields with an exponential function, or equivalently about the geometric nature of exponential varieties.

Formulations

In terms of model theory, Wilkie's theorem deals with the language L_exp = (+,−,·,<,0,1,e^x), the language of ordered rings with an exponential function e^x. Suppose φ(x₁,...,x_m) is a formula in this language, then Wilkie's theorem states that there is an integer n ≥ m and polynomials f₁,...,f_r ∈ Z[x₁,...,x_n,e^x₁,...,e^x_n] such that φ(x₁,...,x_m) is equivalent to the existential formula

Thus, while this theory does not have full quantifier elimination, formulae can be put in a particularly simple form. This result proves that the theory of the structure R_exp, that is the real ordered field with the exponential function, is model complete.^[1]

In terms of analytic geometry, the theorem states that any definable set in the above language — in particular the complement of an exponential variety — is in fact a projection of an exponential variety. An exponential variety over a field K is the set of points in Kⁿ where a finite collection of exponential polynomials simultaneously vanish. Wilkie's theorem states that if we have any definable set in an L_exp structure K = (K,+,−,·,0,1,e^x), say X ⊂ K^m, then there will be an exponential variety in some higher dimension Kⁿ such that the projection of this variety down onto K^m will be precisely X.

Gabrielov's theorem

The result can be considered as a variation of Gabrielov's theorem. This earlier theorem, by Andrei Gabrielov, dealt with sub-analytic sets, or the language L_an of ordered rings with a function symbol for each proper analytic function on R^m restricted to the closed unit cube [0,1]^m. Gabrielov's theorem states that any formula in this language is equivalent to an existential one, as above.^[2] Hence the theory of the real ordered field with restricted analytic functions is model complete.

Intermediate results

Gabrielov's theorem applies to the real field with all restricted analytic functions adjoined, whereas Wilkie's theorem removes the need to restrict the function, but only allows one to add the exponential function. As an intermediate result Wilkie asked when the complement of a sub-analytic set could be defined using the same analytic functions that described the original set. It turns out the required functions are the pfaffian functions.^[1] In particular the theory of the real ordered field with restricted, totally defined pfaffian functions is model complete.^[3] Wilkie's approach for this latter result is somewhat different from his proof of Wilkie's theorem, and the result that allowed him to show that the Pfaffian structure is model complete is sometimes known as Wilkie's theorem of the complement.

References