In the beginning of the article "Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function", by AJ Wilkie, it is asked for us to consider 2 different expansions of the real nunbers $\mathbb{R}$ as a structure for the language of ordered fields. In both cases, it is considered that the language has, additionally, one unary function symbol to be interpreted as $\exp|_{[0,1]} = \exp \cdot I_{[0,1]}$ in one case and as $e: x \mapsto \exp((1+x^2)^{-1})$ (denote these structures by $\mathcal{A}$ and $\mathcal{B}$, respectively). Then he says that these are essentialy the same, because they have the same definable sets. How can one prove such assertion? He says then that one of them being model complete implies that the other is, too. Why is that the case? I tried proving this by induction on the complexity of formulas, but it proved to be quite complicated.

  • 2
    $\begingroup$ here's a hint: first try to see the more general fact that, for any structure $\mathcal{M}=(M;\dots)$ and any functions $f,g$ on $M$, to show that the expansions $(\mathcal{M};f)$ and $(\mathcal{M};g)$ have the same definable sets it suffices to show that $g$ is definable in the first structure and that $f$ is definable in the second $\endgroup$ Jun 22 at 17:15
  • 2
    $\begingroup$ (to do this formally, your idea of induction on the complexity of formulas is a good one. the only time you'll need to use the hypothesis is in the base case of atomic formulas.) then note that $(1+x^2)^{-1}\in[0,1]$ for every $x\in\mathbb{R}$ and that $x\mapsto(1+x^2)^{-1}$ is injective on $\mathbb{R}_{\geqslant 0}$ $\endgroup$ Jun 22 at 17:16
  • 3
    $\begingroup$ @user480840 Two structures (on the same domain) are said to be "interdefinable" if they have the same definable sets. This is a strengthening of the notion of "bi-interpretable". Rather tautologically, a property is preserved under interdefinability if it is defined just in terms of the definable sets (not, for example, in terms of the syntax used to define them). Eg stability, o-minimality, etc are obviously preserved. Quantifier elimination and model completeness are not. $\endgroup$ Jun 22 at 18:47
  • 1
    $\begingroup$ But if you know something stronger about the syntax of the definitions of atomic formulas, you can show that model completeness is preserved. That's what happens in this example. $\endgroup$ Jun 22 at 18:49
  • 2
    $\begingroup$ @user480840 Unfortunately you can't actually write quantifier-free definitions of either of these functions in terms of the other. But the definition of $e$ in terms of restricted exp is equivalent to both an existential formula and a universal formula, and the same is true the other way around. It's a good exercise to verify this and prove that this is enough to transfer model completeness. $\endgroup$ Jun 24 at 14:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.