21

数理解析研究所講究録
第2079巻 2018年 21-26

Model completeness revisited
Masanori Itai

Departemnt of Mathematical Sciences
Tokai University, Hiratsuka, JapanAbstract

We review two theorems concerning the model completeness; the first one is the real numbers withthe exponentiation and the second one is differential fields admitting quantiher elimination without being
differentially closed.

1Introduction

In model theory analysis of the properties of dcfinable sets is vcry important. If a thcory admits climinationof quantifiers, then definable sets are definable by quantifier free formulas. Hence definabl sets are easy
to handle.

Classical examples of theories admitting elimination of quantifiers are(1) thc first‐order thcory of (\mathbb{R}, +, -, \cdot, <, 0,1) ,(2) the first‐order theory of (\mathbb{C}, +, -, \cdot, 0, ) .
If the theory does not admit elimination of quantifiers, then the next best situation is to bonnd thecomplexity of defining formulas to existential formulas. Those theories are called model complete. In thisnote we discuss two topics concerning model completeness.

2Model completenessThe notion of model completeness is introduced by Abraham Robinson;\bullet\bullet\bullet

In 1950, at ICM, A. Robinson gave a proof to Hilbert Nullstellensatz as an application of modelcompleteness.

He also gave an alternative proof to Hilbert 17th Problem using model completeness.
Non‐standard analysis is also originated by him in early 1960' \mathrm{s}.

First recall the definition. \mathcal{L} is a language, T is a \mathcal{L} ‐theory.

Definition 1 The theoryl T is called model complete if for all models M of T,

T\cup Diagram_{0}(M)as a complete L(M) ‐theory.

Let \mathcal{L} be a first‐order language, T is a \mathcal{L}‐theory.
Theorem 2 The following are equivalent;1.

T is model complete;

2. for all models M and N , if M\subset N then M\prec\neg N ;3. for all models M and N , if M\subset N then M\prec\neg 1N ;4. for every \mathcal{L} ‐formula $\varphi$(x) , there exists an existential \mathcal{L} ‐formula $\psi$(x) such that T \models\forall x( $\varphi$(x) \ovalbox{\t \small REJECT}$\psi$(x))

The following is clear.

Theorem 3 If T admits quantifier elimination then T $\iota$ s model complete.

223

Infinitesimals and T_{\exp}

Tarski proved that Th (\mathbb{R}, +, -, \cdot, <, 0,1) admits elimination of quantifiers, hence the theory is modelcomplete. The structure (\mathbb{R}, +, -, \cdot, <0,1) (denoted R) is a typical example of 0‐minimal structure, i.e.,any definable subset of \mathbb{R} is the union of a finite set and a finite union of intervals.
In 1991 A. Wilkie proved a theorem stating that Th (\mathbb{R}, +, -, \cdot, < 0,1, \exp x) is model comlete whichthen implies the 0 ‐minimality of the theorem. The theorem was a major breakthrough for the subject atthat time. His proof uses infinitesimals.

3.1

Model completeness of T_{\exp}

Let T_{\exp} be the theory of (\mathbb{R}, +, \cdots , <, 0,1, \exp x) . From the model completeness of T_{\mathrm{c}\mathrm{x}\mathrm{p} , we get the‐minimality of T_{\mathrm{c}\mathrm{x}\mathrm{p} .

0T_{\exp} does not admit elimination of quantifiers.

\bullet\bullet

However Th (\mathbb{R}, +, \cdot, <, 0,1, \mathrm{e}\mathrm{x}\mathrm{p}, \mathrm{l}\mathrm{o}\mathrm{g}, f \in An) admits elimination of quantifiers, where An denotes
the set of all restricted real analytic functions, [\mathrm{v}\mathrm{D}\mathrm{M}\mathrm{M}].

3.1.1

Quasipolynomials

Definition 4 \mathbb{M}_{0} is a substructure of a model \mathbb{M} of T_{\exp}.
A function M^{n} to M

(x_{1}, \cdots , x_{n})\mapsto P(x_{1}, \cdots , x_{n}, e^{x_{1}}, \cdots , e^{x_{n}})where P is a polynomial in 2n variables with coefficients an M_{0} is called a quasipolynomial with coeficients
in M_{0}.

3.1.2

Key lemma

Suppose:\bullet\mathbb{M}_{0}, \mathbb{M} : models of T_{\exp} with \mathbb{M}_{0}\subseteq \mathbb{M}\bulletM_{0}, M domains ( \mathrm{i}.\mathrm{e}. , underlying sets), respectively

In order to show the model completeness of T_{\exp} ;Lemma 5 it ib sufficicnt to ớhow that for any F : M^{n} \rightarrow M is a quasipolynomial with coefficients inM_{0} , and b\in M^{n} is a non‐singular solution to F(x)=0 , i. e.,F(b)=0 and J_{F}(b)\neq 0
then b\in M_{0}^{n} , where J_{F}(b) is the Jacobian at b.
3.1.3

Gavrielov’s theorem

Theorem 6 (Gabrielov) \tilde{\mathb {R} is the reduct of \mathb {R}_{\mathrm{a}\mathrm{n} such that for each resricted analytic function \tilde{f} in thelanguage,\displayte\frac{ptial^{\sm}f partilx_{j}is also in the language for each j . Then Th (\tilde{\mathb {R} ) rs model complete in the language \mathcal{L}(\tilde{\mathb {R} ) .

Corollary 7 Th (\mathbb{R}_{\mathrm{r}\exp}) is model complete, where rexp means that the exponentiation is restricted to (0,1). It follows that Th (\mathb {R}_{\mathrm{r}\mathrm{c}\mathrm{x}\mathrm{p} ) is 0‐minimal.
3.1.4

Khovanski’s theorem

Theorem 8 (Khovanski) Let f_{1},, f_{m} be quasipolinomials from \mathbb{R}^{n} to \mathbb{R} . Then the regular zero setof f_{1},, f_{m} , i. e., \{x \in \mathbb{R}^{n} : f_{1}(x) =. . . = f_{m}(x) = 0\} , is finite and can bp bounded uniformly in thecomplexity of fís.
\cdots\cdots23

3.2

Outline of the proof of Lemma 5

We show that Lemma 5 is true by contradiction. Infinitesimals play an important role in the proof ofmodel completeness of T_{\exp}.
Recall \mathb {M}_{0}\subseteq \mathb {M}\models T_{\mathrm{c}\mathrm{x}\mathrm{p} . Let

Fin ( \mathbb{M} ) :=\{a\in M : \exists N\in \mathbb{Q}(|a| <N)\},$\mu$(\mathbb{M}):=\{a\in M:\forall q\in \mathbb{Q}_{>0}(|a| <q
Fin ( \mathbb{M} ) is a subring of \mathbb{M} and $\mu$(\mathbb{M}) is the unique maximal ideal of Fin ( \mathbb{M} ) . Hence Fin (\mathbb{M})/ $\mu$(\mathbb{M}) is afield, callcd thc rcsidue field of M. Wc dcfinc a valuation group \{ $\Gamma$, <, +, 0 ) of \mathbb{M} and a valuation map
v : M\rightarrow M\backslash \{0\}\rightarrow $\Gamma$ with the following property. For a, b\in M\backslash \{0\},(i) $\nu$(a. b) = $\nu$ (a) + lノ (b) ;(ii) \displaystyle \mathrm{v}(a+b)\geq\min { \mathrm{v}(a) , lノ(b)};(iii) $\nu$(a)=0 if and only \mathrm{i}\mathrm{f}a\in Fin(\mathbb{M})\backslash $\mu$(\mathbb{M}) .
Properties of the valuation.

\displaytefrc{1}$\vaepsilon} is an infinite. Since $\epsilon$\displayte\cdotfrac{1}$\varepsilon$}=1 , we havev(\displayst le\frac{1} $\varepsilon$}) =-v(\in)\bullet

Let $\varepsilon$ be an infinitesimal. Then,\bullet

Let $\varepsilon$ be an infinitesimal, and a\in Fin(\mathbb{M}) . Then v(a\in)=? ) (a)+\uparrow ) ( $\varepsilon$)=v(\in) .

.

We also use the following inequality:

rank ( \mathbb{M} ) \geq resrank ( \mathbb{M})+\dim_{\mathbb{Q} ( $\Gamma$) ,where resrank(M) denotes the rank of residue field.
(1) First we argue that it is enough to show Lemma 5 in T_{\mathrm{r}\exp} where rexp denotes the exponentialfunction restricted to (0,1) . It is known that T_{\mathrm{r}\exp} is model complete.

(2) We then argue that it is enough to work with b with coordinates b_{1},Fin (M) .

\cdots, b_{n} such that all of b_{i} are in(3) We use infinitesimals i.e., elements in $\mu$(M) to reduce to the previous case. (here we use valuation
theory and the property of“ independence” of infinitesimals)
4

Differential fields

All fields are of characteristic zero. The notion of differential fields was introduced by Ritt in the thirties.
Definition 9 (K, $\delta$) is a differential field if K is a field and $\delta$ is a derivation on\bullet$\delta$(x+y)= $\delta$(x)+ $\delta$(y)\bullet$\delta$(xy)= $\delta$(x)y+x $\delta$(y),.

\bullet

C=\{x\in K : $\delta$(x) =0\} , the field of constants.

\bulletLanguage of differential fields =\{+, -, \cdot, $\delta$, 0, 1\}

4.1

K , i.e., for x, y\in K

Differentially closed fields

Historically it took for a while before reaching the right definition of differentially closed fields.
Definition 10 Let (K, $\delta$) be a differcntial field. The polynomial ringK[X_{1)}\cdots X_{n}, $\delta$(X_{1}), \cdots , $\delta$(X_{n}), \cdots j$\delta$^{m}(X_{1}), \cdots , $\delta$^{m}(X_{n}), ]is called the ring of differential polynomials over K , and denoted K\{X_{1}, \cdots , X_{n}\}.
t renlially closed i\displaystyle\int, \displaystyle \int or any f, g \in K\{X\} with g be
Definition 11 A differentially closed field K is di\displaystyle \iinenonzero, \mathrm{o}\mathrm{r}\mathrm{d}(f) >\mathrm{o}\mathrm{r}\mathrm{d}(g) , there is a\in K such that f(a)=0 and g(a)\neq 0.

244.2

Existentially closed differential fields

Definition 12 Adifferentiall?) closed field K is existentially closedf iffor any f_{1} ,f_{m} \in K\{X_{1}, \cdots , X_{n}\}there is a differental field L\supset K containing a solution to the system of differentail eqauations f_{1}f_{m}=0 , there is already a solution in K.
\cdots=\cdots=

4.3

Basic properties (1)Theorem 13 Let K be a differential field. TFAE.

1.

K is differentially closed.

2.

K is existentailly closed.

3.

K is algebraically closed and for every irreducible algebraic variety V\subseteq K^{n} , if W is an irreducible
subvarity of V^{(1)} such that the projection of W onto V is Zariski dense in V and U is a Zariski open
subset of V , then (x, $\delta$(x)) \in U for some x\in V.

4.4

Basic properties (2)DCF is the theory of differentially closed fields.

Theorem 14 DCF \dot{?}sw ‐stablef admits QE (hence model complete), complete.
Proposition 15 Let K be a differentail field.
K is existentially closed\Leftrightarrow

K is differentially clo\mathcal{S}ed.

Lemma 16 K, L are $\omega$ ‐saturated models of DCF. Assume\bullet\overline{a}\in K, \overline{b}\in L , and k=\mathbb{Q}\langle\overline{a} }, \ell=\mathbb{Q}\{\overline{b}\rangle.

\bullet$\sigma$: k\rightarrow l\dot{?}S an iso such that $\sigma$(\overline{a})=\overline{b}.

Then, for all $\alpha$\in

4.5

K,

there is an extension of $\sigma$ to an iso $\sigma$^{*} from k\langle $\alpha$\rangle into L.

DCF admits QE

Here we show that DCF admits elimination of quantifiers.
Proof:\bullet

Suffices to show: assume

K, L\models DCF,

\bulletk\subseteq K, k\subseteq L, \overline{a}\in k, b\in K,\bullet$\varphi$(v, \overline{w}) is quantifier free, and\bullet

K\models $\varphi$(b,\overline{a}).

Then L\models\exists v $\varphi$(v,\overline{a}) .

WLOG, assume 1) K, L are $\omega$ ‐saturated, 2) k is the diff. field generated by \overline{a} . By the previous lemma

we can find $\beta$\in L such that k\{b\rangle\cong k\langle $\beta$\} . Thus L\models $\varphi$( $\beta$, \overline{a}) . So, L\models\exists v $\varphi$(v, \overline{a}) .

\blacksquare

Let F be an infinite field. The following theorem tells us that the field F being algebraically closed
and the theory of F admitting quantifier elimination are equivalent:
Theorem 17 If F is algebraically closed, then the theory of F admits elimination of quantifiers. Moreover
if the theory of (F, +_{;}\cdot, 0,1) admits elimination of quantifiers, then the field F is algebraically closed.
For differential fields, being differentially closed implies its theory admits qunantifier elimination. So
it is vary natural to consider the following question.

Question 18 Suppose the thcory of a differential field K admits QE . Is it necesary that the differential
field K is differentially closed.

25

4.6

Need to understand strongly minimal sets.

Definition 19 A definable set X i.s strongly minimal if for any definable set Y , either X\cap Y is finite,or X-Y is finite.
Study of geometric properies of strongly minimal sets in differential fields is the key.

4.7

QE, but not differentially closed

First we need.

Proposition 20 (Prop 2.1 of HI)\bulletX\bulletC is a curve of.qenus \geq 1.

is a strongly minimal subset of C with induced trivial geometry on X.

(called strictly minimal)

Y_{b} is a definable family of Kolchin‐closed definable sets of finite differential orde $\gamma$\cdot.
THEN: The set of b such that X is orthogonal to the generic type of Y_{b} is definable.

\bullet4.8

T(X) admmits QE, but not DCF.

By the previous Proposition we may find a curve C and a set X defined over \mathb {Q} . Suppose X is definedby $\varphi$(v) . We define the theory $\Gamma$ 1^{\urcorner}(X) consisting the theory of differential fields, admitting elinimation ofquantifiers but is not differentially closed.

Definition 21 (Definition of T(X) ) The universal part T_{\foral } of T(X) consists of\bullet

DF of charcteristic 0,\bullet

X\bulletX has no solution even in the algebraic closure.

has no solution, i. e., \neg\exists x $\varphi$(x) , andThe rest of T(X) consists of the first‐order data making T_{\foral } to admit QE.

4.9First‐order data making $\tau$_{\foral } to admit QE

Definition 22 (Definition of T(X) continued)\bulletfor each U, W differ ential‐algebraic varieties over\mathbb{Q}, $\pi$ : U\rightarrow W such that U_{b} :=$\pi$^{-1}(b) has finite differential order for each b\in W.

W_{1}=\cdot{ b:U_{b} is iweducible} is a quantifier‐free definable set in DCF\bulletLet p_{b} denote the generic type of U_{b} for b\in W_{1}.

\bullet

W_{2} := { b\in W_{1} : p_{b} is orthogonaltoX} is also quantífier‐free definable by $\theta$(w)\bullet

AXIOM:

4.10\forall w\in W( $\theta$(w)\rightarrow\exists u\in U( $\pi$(u)=w))

Proof goes as follows:\bulletT_{\foral } is consitent and any model of T_{\foral } can be extended to a model of T(X) . Hence T is consistent.

\bulletBy definition of T(X) , T_{\foral } admits QE.

\bulletT(X) is a model completion of T_{\forall}.

\bullet

It follows that T(X) admits QE.

\bulletBy definition, models of T(X) are not differentially closed.

4.11

Zariski geometry and Geometric Mordell‐Lang conjecture

Strongly minimal sets in DCF form Zariski geometries and those Zariski geometries are used for thealternative solution to the geometric Mordell‐Lang conjecture for characteristic zero case.

26

References[HI]

E. Hrushovski and M. Itai, On model complete differential fields, Trans. of the AMS, vol355,
no. 11, 2003

[MT]

A. Marcja and C. Toffalori, A Guide to Classical and Modern Model Theory, Kluwer Academic[Ma]

D. Marker, Khovanski‘s theorem, Algebraic Model Theory, Kluwer Academic Publishers, 1997

[vDMM]

L. van den Dries, A.J. Macintyre, D. Marker, The elementary theory of restricted analytic
fields with exponentiation Ann. of Math. , 140 (1994) pp. 183‐205[Wi14]

A. Wilkie, Lectures on the Model Theory of Real and Complex Exponentiation, Lecture notes
in Mathematics, 2111, pp. 35‐53, Springer, 2014

[Wi96]

A. Wilkie, Model completeness results for expansions of the ordered field of the real numbers
by restricted Pfaffian funclion\mathcal{S} and the exponentil function, J. Am. Math. Soc. 9(4), 1051‐
1094(1996)

Publishers, 2003