\documentclass{amsart}

\title{Model theory $\approx$ tame mathematics}
\author[Dries]{Lou van den Dries}
\date{1998; transcribed into \AmS-\LaTeX\ 2002}

\swapnumbers
\input{../../math/abbreviations.tex}

\begin{document}
\maketitle

\emph{David Pierce transcribed (and slightly edited) these notes from
  slides  written by 
  Lou van den Dries and used in his talk at MSRI, Berkeley,
  California, USA, in 1998.  Images of the slides are
posted at}\\
  \verb+http://www.msri.org/ln/msri/1998/mtf/vddries/+\\

\section{Introduction}

In model theory, we associate to a structure $\str M$ invariants like
$\Th{\str M}$, the \defn{theory of $\str M$}; these invariants have a
logical-combinatorial nature: 
\begin{itemize}
\item
$\str M\mapsto\Th{\str M}$
\item
$\str M\mapsto$ category of definable sets and maps over ${\str M}$
  (or over ${\str M\eq}$)
\item
$\str M\mapsto$ category of definable groups and definable group
  homomorphisms over ${\str M}$ (or over ${\str M\eq})$
\end{itemize}
To use $\Th{\str M}$, say, for the study of $\str M$ it is desirable
that $\Th{\str M}$ can be \emph{effectively} described in practice:
$\Th{\str M}$ should be axiomatizable by \emph{finitely} many axiom
\emph{schemes}.

\begin{example}
$\Th{\C\text{ as ring}}$ is axiomatized by:
\begin{itemize}
\item
field axioms (finite in number)
\item
$\forall x_1\dots x_n\,\exists y\,(y^n+x_1y^{n-1}+\dots +x_n=0)$,
  ($n=1,2,3,\dots$)
\item
$\underbrace{1+\dots+1}_{n\text{ times}}\neq0$, ($n=1,2,3,\dots$)
\end{itemize}
\end{example}

\begin{non}[G\"odel]
$\Th{\Z\text{ as ring}}$ cannot be effectively described in any
  reasonable way.  (But $\Z$ as ordered additive group is tame!)
\end{non}

Since G\"odel we know that the requirement of effective
axiomatizability of $\Th{\str M}$ is a serious constraint on $\str M$,
and this has given rise to the impression (via popular literature)
that there is a very limited scope left for ``positive'' contributions
of logic to mathematics.

\emph{But:} despite G\"odel, mathematical problems, even in apparently
``non-tame'' subjects like number theory, do get solved, often by
ingenious moves into tame territory!  Thus the relevance of \fbox{model
theory $\approx$ tame mathematics}

\begin{example}
The field $\Q$ of rational numbers is not tame (Julia Robinson), but
its completions $\R$, $\Q_2$, $\Q_3$, $\Q_5$, \dots\ are all tame
(Tarski, Ax, Kochen, Er\v sov).  (It is \emph{not known} if the field
$\F_p((t))$ is tame.)
\end{example}

\section{How to show tameness of an infinite structure $\str M$:}  

Find a
set $T$ of ``axioms'' such that $\str M\models T$ and show:
\begin{enumerate}
\item
$T$ admits QE [quantifier-elimination] (and\dots) or:
\item
$T$ is model-complete (and\dots) or:
\item
$T$ is $\kappa$-categorical for some infinite cardinal $\kappa$ or:
\item
\dots.
\end{enumerate}
If any of these methods works, one usually obtains, not only a
complete description of $\Th{\str M}$, but also a lot of positive
information about (the category of) definable sets and maps, such as a
dimension theory for definable sets.

\begin{example}
For $\str M:=(\R,<,0,1,+,-,\cdot)$ we take $T:=\RCF$ (the axioms for
real-closed ordered fields):
\begin{itemize}
\item
axioms for ordered fields
\item
$\forall x\,\exists y\,(x>0\to x=y^2)$
\item
$\forall x_1\dots x_{2n+1}\,\exists
  y\,(y^{2n+1}+x_1y^{2n}+\dots+x_{2n+1}=0)$, $n=1,2,3,\dots$
\end{itemize}
\end{example}

How do we show that $\RCF$ admits QE?

\section{QE test:}  

An $\lang$-theory $T$ admits QE
$\Iff$\\
for any models $\str M$ and $\str N$ of $T$, each $\lang$-embedding
$\str R\to\str N$, where $\str R\included\str M$ and $\str R\neq\str
M$, can be extended to an $\lang$-embedding
$$\str R'\to\str N'$$
from some \emph{strictly larger} $\lang$-substructure $\str R'$ of $\str
M$ into some \emph{elementary} extension $\str N'$ of $\str N$.

To apply this test to $\RCF$, we need to know the following about
ordered domains (Artin \&\ Schreier, 1926):

Let $A$ be an ordered (integral) domain.  Then:
\begin{enumerate}
\item
$A$ has a real closure $A\rc$, \ie\ $A\rc$ is a real closed ordered
  field extending $A$ and algebraic over (the fraction field of) $A$.
\item\label{rcii}
Every embedding $A\to L$ of $A$ into a real closed ordered field $L$
extends (uniquely) to an embedding $A\rc\to L$.
\end{enumerate}

\begin{proof}[Proof that $\RCF$ admits QE]  Let $K$ and $L$ be real
  closed ordered fields, $A$ an ordered sub-ring of $K$ and
  $i:A\to L$ an embedding (of ordered rings).  Assume $A\neq K$.  We
  want to show that $i$ can be extended as required in the QE-test.
  By (\ref{rcii}) above we can reduce to the case that $A$ itself is a
  real closed ordered field.  Take any $b$ in $K\setminus A$.  Then $b$
  determines a cut in $A$, that is,  $U<b<V$ where $U:=\{x\in A:x<b\}$ and
  $V:=\{x\in A:b<x\}$.  Then $i(U)<i(V)$ in $L$.  By passing to a
  suitable elementary extension $L'$ of $L$ we can take an element
  $b'$ of $L'$ such that $i(U)<b'<i(V)$.  Then $i$ extends to an
  embedding $i':A[b]\to L'$ with $i'(b)=b'$.
\end{proof}

Routine consequences:
\begin{enumerate}
\item
$\Th{\R,<,0,1,+,-,\cdot}=\{\text{logical consequences of }\RCF\}$, and
  thus {$\Th{\R,<,0,1,+,-,\cdot}$} is decidable.
\item
$\Q\rc$ (the ordered field of real \emph{algebraic} numbers) is an
  elementary substructure of $(\R,<,0,1,+,-,\cdot)$.
\item
Definable $=$ semi-algebraic (for any real closed ordered field).
\item
If $S$ is a semi-algebraic subset of $\R^{m+n}$, then there is a
semi-algebraic map $f:\pi S\to \R^n$ such that $\Gamma(f)\included S$:
[picture].  (This can be read off directly from the axioms of $\RCF$.)
\end{enumerate}

\section{The field of $p$-adic numbers ($p$ prime):}

Equip $\Q$ with the (non-Archimedean) absolute value given by $\abs
a_p=p^{-e}$, where $a=p^em/n$ with $e,m,n\in\Z$ and $p\nmid mn$.  The
completion of $(\Q,\abs{\cdot}_p)$ is called the field of $p$-adic numbers
and is denoted by $(\Q_p,\abs{\cdot}_p)$.  Its elements are infinite sums
$\sum_{k\in\Z}a_kp^k$ with all $a_k$ in $\{0,1,\dots,p-1\}$, and
$a_k=0$ for all $k$ less than some $k_0$ in $\Z$.

$\Z_p=$ closure of $\Z$ in $\Q_p =\{x\in\Q_p:\abs x_p\leq 1\}$, a
compact sub-ring of $Q_p$.

The pair $(\Q_p,\Z_p)$ is an example of a valued field.

A \emph{valued field} is a pair $(K,V)$ with $K$ a field and $V$ a
valuation-ring of $K$ (\ie\ a sub-ring of $K$ such that $x\in
K\implies x\in V\lor x^{-1}\in V$).

To a valued field $(K,V)$ we associate:
\begin{itemize}
\item
its residue field $k:=V/\maxid V$
\item
its value group $\Gamma:=K^{\times}/V^{\times}$, viewed as an ordered
abelian group with $aV^{\times}\leq bV^{\times}\Iff b/a\in V$.
\end{itemize}

\begin{definition}
We call a valuation-ring $V$ \emph{Henselian} if each polynomial
$X^n+a_1X^{n-1}+ \dots+a_{n-1}X+a_n$ in $V[X]$ such that
$a_{n-1}\notin\maxid V$ and $a_n\in\maxid V$ has a zero in $\maxid V$.
\end{definition}

\begin{examples}
$\Z_p$ is Henselian, $k[[t]]$ is Henselian (for any field $k$).
\end{examples}

\begin{definition}
A \emph{$p$-adically closed field} is a valued field $(K,V)$ such that
$\Char K=0$ and $V$ is Henselian, with $\maxid V=pV$ and $k\cong \F_p$
and $[\Gamma:n\Gamma]=n$ for $n$ equal to $1,2,3,\dots$.
\end{definition}

So $(\Q_p,\Z_p)$ is a $p$-adically closed field.

\begin{theorem}[Kochen, late 1960s]
The theory of $p$-adically closed fields is complete and
model-complete.
\end{theorem}

Kochen used this to characterize rational functions in $\Q_p(X_1,
\dots,X_n)$ that take only values in $Z_p$ for arguments in $Z_p$ (such
as $(X^p-X)/p$).  (``$p$-adic Hilbert's 17th problem'')

\section{Henselian valued fields of equi-characteristic $0$}

Consider \emph{Henselian} valued fields $(K,V)$ of equi-characteristic
$0$, \ie\ $\Char K=\Char k=0$. 

\begin{theorem}[Ax \&\ Kochen, Er\v sov, mid 1960s]
$\Th{K,V}$ is completely determined by the pair $(\Th{k},\Th{\Gamma})$
  ($\Gamma=$ value-group).
\end{theorem}

\begin{proof}
A classical result of Kaplansky's (1940s) is that a valued field
$(K,V)$ of equi-characteristic $0$ can be embedded as a valued field
into the generalized formal power-series field $k((t^{\Gamma}))$
consisting of all formal series
$\sum_{\gamma\in\Gamma}\alpha_{\gamma}t^{\gamma}$ with coefficients
$\alpha_{\gamma}$ in $k$, and with well-ordered support
$\{\gamma\in\Gamma:\alpha_{\gamma}\neq0\}$ (the valuation-ring of
$k((t^{\Gamma}))$ consisting of the series with support included in
$\Gamma^{\geq0}$). 

By adapting suitably the embedding technique of Kaplansky, A \& K and
Er\v sov showed that if $(K_1,V_1)$ and $(K_2,V_2)$ are Henselian
valued fields of equi-characteristic $0$ with $\Th{k_1}=\Th{k_2}$ and
$\Th{\Gamma_1}=\Th{\Gamma_2}$, then $(K_1,V_1)$ and $(K_2,V_2)$ have
isomorphic elementary extensions.  Therefore
$\Th{K_1,V_1}=\Th{K_2,V_2}$.
\end{proof}

\begin{corollary}
Given an elementary statement $\sigma$ about valued fields, there are
elementary statements $\sigma_1,\dots,\sigma_k$ about fields and
elementary statements $\tau_1,\dots,\tau_k$ about ordered groups such
that for \emph{all} Henselian valued fields $(K,V)$ of
equi-characteristic $0$,
$$(K,V)\models \sigma\Iff k\models\sigma_i\land\Gamma\models\tau_i\text{
  for some $i$ in $\{1,\dots,k\}$}.$$
\end{corollary}
Note the \emph{uniformity}: the equivalence holds for all $(K,V)$.
  This has a remarkable consequence:

\section{Consequence for $\Q_p$ and $\F_p((t))$}

Let $\sigma$ be an elementary statement about valued fields.  Then
$$(\Q_p,Z_p)\models\sigma\Iff(\F_p((t)),\F_p[[t]])\models\sigma$$
for all but finitely many primes $p$.

\begin{proof}
By G\"odel's Completeness Theorem, there must be a formal proof of
$$\sigma\leftrightarrow(\sigma_1\land\tau_1)\lor
\dots\lor(\sigma_k\land\tau_k)$$
from the axioms for Henselian valued fields of equi-characteristic
$0$.  But only finitely many of the axioms saying that the fields and
the residue-field have characteristic $0$ can be used in such a
proof.  Thus the equivalence above also holds in $(\Q_p,Z_p)$ and in
$(\F_p((t)),\F_p[[t]])$ for all but finitely many $p$.  Now note that
these two valued fields have the same residue-field and the same
value-group.
\end{proof}

\section{Application}

Serge Lang showed in his thesis (early 1950s) that each homogeneous
polynomial of degree $d$ at least $1$ in more than $d^2$ variables
over $\F_p((t))$ has a non-trivial zero in that field.  Thus, for a
\emph{given} $d$ at least $1$, this statement remains true when we
replace $\F_p((t))$ by $\Q_p$, for all but finitely many $p$.

(Exceptions indeed occur, [Terjanian,] and may depend on $d$.)

What about QE for Henselian valued fields?  There are several results
of the following general nature (P.J. Cohen, V. Weispfenning,
F. Delon, J. Denef, Pas).

Henselian valued fields of equi-characteristic $0$ have (uniformly)
relative QE: field-quantifiers can be \emph{eliminated} at the cost of
introducing quantified variables ranging over the residue-field, and
over the value-group.  (The exact language used here can make a
difference for the applications.)

\begin{example}[Pas]
For the valued field $(\C((t)),\C[[t]])$ we have (full) QE in the
language with 3 sorts of variables: variables ranging over the field
itself, variables ranging over the residue-field $\C$, and variables
ranging over the value-group $\Z$ (viewed as an ordered abelian group
with unary predicates for the sets $n\Z$, where $n=2,3,\dots$);
moreover, these sorts are related in the usual way, except that
instead of the residue-class map $\C[[t]]\to\C$ we consider the
\emph{leading-coefficient map} $\C((t))\to\C$ associating to each
series its leading coefficient.
\end{example}

\end{document}
\emph{Some notes for the lay-person:  A ``structure'' is a set
  equipped with some operations and relations.  For example,
  high-school algebra is largely a study of the structure $\R$ of the real
  numbers.  This structure is the set of real numbers, together with
  the operations of addition and multiplication, and the relation of
  ordering (``less-than'').  Likewise, $\C$ is the set of complex numbers,
  together with addition and multiplication; there is no ordering.  As
  sets equipped with addition and multiplication, both $\R$ and $\C$
  are ``rings''.}

