\documentclass[twoside,a4paper,10pt]{article}
\title{Model-Theory of Fields:\\
Background}

\newcommand{\todaysdate}{2004.10.25}

\author{David Pierce}
\date{\todaysdate}
\pagestyle{myheadings}
 \markboth{David Pierce, \todaysdate}{Model-theory summary, \todaysdate}

% \addtolength{\voffset}{-1.5cm}
% \addtolength{\textheight}{3cm}

\usepackage{amsthm}
\swapnumbers

\input{../../math/format}
\input{../../math/abbreviations}
\input{../../math/article-theorems}
%\renewcommand{\implies}{\Longrightarrow}
%\renewcommand{\iff}{\Longleftrightarrow}
%\DeclareMathOperator{\arity}{arity}
\newcommand{\Bv}[1]{\|#1\|}   % Boolean value
\newcommand{\interp}{\mathfrak{I}}
\renewcommand{\fv}{\operatorname{fv}}

\begin{document}
\maketitle \thispagestyle{empty} 


\emph{These notes} are intended as a quick summary of first-order logic as
used in model-theory and the model-theoretic study of
fields.  I originally wrote them for the algebra study group at METU
in 2002, when we were looking at \cite[ch.\ 6]{MR89b:12010}.  For
less terse accounts, see \cite{MR91c:03026} or
\cite{MR94e:03002} or even \cite{MR99k:03032}. 

My notational conventions are these.  The set of natural numbers is
$\varN$, and each natural number $n$ is
the set $\{0,\dots,n-1\}$ of its predecessors.  In particular, $0$ is
$\emptyset$.  If $I\included \varN$, and $M$ is a set, then
$M^I$ is the set of functions from 
$I$ to $M$.  A typical element of $M^I$ can be written
$(a_i:i\in I)$ or just $\tuple a$ or $\vec a$.

Model-theory begins with the distinctions indicated in the table on
p.~\pageref{table}.
Technical terms in \defn{bold} are not defined further; those that are
\tech{slanted}, will be.

\begin{table}[!b]\label{table}
\caption{Model-theoretic symbols and meanings}
\begin{center}
\begin{tabular}{|r|l|}\hline
  IMAGE & REALITY\\
SYMBOL & INTERPRETATION\\
SYNTAX & SEMANTICS\\ \hline\hline\hline
\tech{signature} $\lang$ & $\str M$, an \tech{$\lang$-structure}\\
\hline\hline  
& OPERATIONS ON $M$: \\ \hline
& \textsc{basic operations:}\\ 
\defn{variable} $v_i$ & $\tuple a\mapsto a_i:M^I\to M$, if $i\in I$\\ 
\defn{constant-symbol} $c$ & $c^{\str M}$, an element of $M$ \\ 
\defn{$n$-ary function-symbol} $f$ & $f^{\str M}:M^n\to M$\\ \hline
\tech{term} $t$ & $t^{\str M}$, a composition of basic operations \\
\hline\hline
LOGICAL SYMBOLS: & FUNCTIONS ON  $\pow{M^I}$\\ \hline
\textsc{connectives:} & \textsc{operations}: \\
$\land$ & $\cap$ \\ 
$\lnot$ & $A\mapsto A\comp$ \\
$\lor$ & $\cup$ \\
$\to$ & $(A,B)\mapsto A\comp\cup B$ \\
$\leftrightarrow$ & $(A,B)\mapsto (A\comp\cup B)\cap (A\cup B\comp)$
 \\ \hline
\textsc{quantifiers:} & \textsc{projections:} \\ 
$\exists v_i$ & $A\mapsto\{(a_j:j\in I\setminus\{i\}):\tuple a\in
A\}$
\\ 
$\forall v_i$ &  $A\mapsto\{(a_j:j\in I\setminus\{i\}):\tuple a\in
A\comp\}\comp$ \\ \hline\hline
& RELATIONS ON $M$:\\ \hline
& \textsc{basic relations:}\\
$=$ & equality\\
\defn{$n$-ary relation-symbol} $R$ & $R^{\str M}$, a subset of $M^n$\\
\hline
\textsc{formulas:} & \textsc{definable relations:} \\ 
\tech{atomic} formula $\alpha$ & $\alpha^{\str M}$, a solution-set\\
\tech{open} formula $\beta$ & $\beta^{\str M}$, a \tech{constructible} set \\ 
\tech{formula} $\phi$ & $\phi^{\str M}$ \\
\tech{sentence} & true or false\\ \hline
$\proves$ & $\models$ \\\hline
$\models$ & $\included$\\ \hline
\end{tabular}
\end{center}
\end{table}


Formally, a \defn{structure} with \defn{signature} $\lang$ can be
defined as a pair $(M,\interp)$, where $M$ is 
a set, and $\interp$ is a
function assigning an interpretation to each
constant-, function- and relation-symbol in $\lang$.  (I may refer to
relation-symbols as \defn{predicates}, and to constant-symbols as
\defn{constants}.)  The set $M$ is
called the \defn{universe} of the structure.  One rarely
refers to $\interp$ explicitly, but one may write the structure as $\str M$
(in a more elaborate font) to indicate the presence of $\interp$.

The signature $\lang_{\mathrm r}$ of (unital) rings and fields is 
$$\{+,-,\cdot,0,1\},$$
where $+$ and $\cdot$ are binary, and $-$ is a unary, function-symbol,
and $0$ and $1$ are constant-symbols.  The signature
$\lang_{\mathrm{or}}$ of ordered rings 
and fields contains also the binary relation-symbol $\leq$.  To
indicate explicitly that the integers are to be thought of as
composing an ordered ring, one might write this structure as
$$(\Z,+^{\Z},-^{\Z},\cdot^{\Z},0^{\Z},1^{\Z},\leq^{\Z}).$$
However, the superscripts are rarely needed; one might write
$(\Z,+,-,\cdot,0,1,\leq)$, or just refer to `the ordered ring $\Z$'.


\defn{Terms} can be defined thus (here $f$ is as in the table):
\begin{mylist}
  \item
Constant-symbols and 
variables are terms. 
\item
If $t_0$, \dots, $t_{n-1}$ are terms, then
so is $ft_0\dots t_{n-1}$. 
\end{mylist}

If $t$ is a term, and $I$ is a subset of $\varN$ containing the
indices of all variables appearing in $t$, then $t^{\str M}$ can be
understood in the obvious way as a function from $M^I$ to $M$.

Informally, letters like $x$, $y$ and $z$ stand for variables.
The definition of `term' uses the so-called Polish notation, which needs no
brackets.  Conventionally, binary symbols are written between their
arguments, so that
$\mathbin{\cdot}\mathbin{+}\mathbin{x}\mathbin{y}\mathbin{z}$ is written
$(x+y)\cdot z$.  The manner of writing terms is not mathematically
important; what is important is that \emph{a term of $\lang$ is an
  unambiguous recipe for constructing a function in each
  $\lang$-structure.} 

For every commutative ring $\str A$, there is a unique homomorphism of
$\Z$ into $\str A$; the image of $\Z$ in $A$ is (the universe of) the
\defn{prime ring}
of $\str A$.  Every element of the prime ring is the interpretation of
a term, namely $-(1+\dots+1)$ or $0$ or $1+\dots +1$.  Then every
polynomial over the prime ring is the interpretation of a term of
$\lang_{\mathrm r}$, and every term has such an interpretation in
$\str A$ (if $A$ is infinite).

If we want to allow arbitrary coefficients from $A$, we introduce them
into the signature.  In general, if $B\included M$, then $\lang(B)$ is
$\lang$ with a new constant-symbol for each element of $B$.

\defn{Atomic} formulas take the form $(t_0=t_1)$ or $Rt_0\dots
t_{n-1}$ (where $R$ is as in the table; the latter formula is in
Polish notation.)  The corresponding interpretations in $\str M$ are
thus: 
\begin{myitem}
  \item
$(t_0=t_1)^{\str M}$ is the inverse image of $\{(a,a):a\in M\}$
 under $(t_0^{\str M},t_1^{\str M})$, and
\item
$(Rt_0\dots t_{n-1})^{\str M}=(t_0^{\str M},\dots,t_{n-1}^{\str
  M})\inv R^{\str M}$.
\end{myitem}
In $\lang_{\mathrm r}$, the atomic formulas correspond to polynomial equations
over a prime ring; the interpretations of the formulas are the
solution-sets of the equations.  In $\lang_{\mathrm{or}}$, some atomic
formulas correspond to inequalities.

In the propositional calculus, the connectives $\land$ and $\lnot$ are
adequate to symbolize every truth-table.  In particular, one has the
equivalences:
$$P\lor Q \sim \lnot P\land\lnot Q;\quad P\to Q \sim \lnot P\lor
Q;\quad P\leftrightarrow Q \sim P\to Q\land Q\to P.$$
I shall use the arrows $\implies$ and $\Iff$ not as formal symbols, but as
abbreviations for ordinary expressions like `implies' and `if and only
if' respectively.

Hence we can define \defn{open} (or \defn{basic}, or
\defn{quantifier-free}) formulas thus.  
\begin{mylist}  
\item
Atomic formulas are
open.  
\item If $\alpha$ is open, then so is $\lnot\alpha$.
\item  If $\alpha$ and $\beta$ are open, then so is
$(\alpha\land\beta)$.  
\end{mylist}

Informally, redundant brackets can be omitted.  (Or one can use Polish
notation.) 

Arbitrary \defn{formulas} are defined as open formulas are, with an
extra provision:  
\begin{mylist}\setcounter{mylist}{3}
\item If $\phi$ is a formula, then so is $(\exists
x\qsep \phi)$ for any variable $x$.
\end{mylist}

For every formula $\phi$, there is a set $\fv(\phi)$ of indices of its
\defn{free variables}, 
given thus:  
\begin{mylist} 
\item
If $\alpha$ is atomic, then $\fv(\alpha)$ is the
set of indices of variables appearing in $\phi$.  
\item
$\fv(\lnot\phi)=\fv(\phi)$.  
\item
$\fv(\phi\land\psi)=\fv(\phi)\cup\fv(\psi)$.  
\item  $\fv(\exists
v_i\qsep\phi)=\fv(\phi)\setminus\{i\}$. 
\end{mylist}

If $\fv(\phi)=n$, then $\phi$ can be written
as $\phi(v_0,\dots,v_{n-1})$, and $\phi^{\str M}$
should be a subset of $M^n$.  Indeed, we define:
\begin{myitem}
\item
$(\lnot\phi)^{\str M}=(\phi^{\str M})\comp$;
  \item
$(\phi\land\psi)^{\str M}=\phi^{\str M}\cap\psi^{\str M}$;
\item
$(\exists v_{i}\qsep\phi)^{\str M}$ is the image of $\phi^{\str M}$
  under $\tuple a\mapsto(a_j:j\in I\setminus\{i\}):M^I\to
  M^{I\setminus\{i\}}$, where $\fv(\phi)\included I$.
\end{myitem}

In $\str M$, the sets \defn{definable over $\emptyset$} are the
interpretations of formulas of $\lang$.  These sets are also called
$0$-definable.  If $B\included M$, then the $B$-definable sets are the
interpretations of formulas of $\lang(B)$.  Usually \defn{definable}
means $M$-definable.

In algebraic geometry, if $\str K$ is a field, then the
\defn{constructible} 
sets of $\str K$ are the sets definable by open formulas of
$\lang_{\mathrm r}(K)$.  Chevalley's Theorem \cite[\S\ssp
  4.4, p.\ 33]{MR53:633} is that, if $K$ is
algebraically closed, then all definable sets of $\str K$ are
constructible. 

A \defn{sentence} is a formula with no free variables.  If $\sigma$ is a
sentence, then $\sigma^{\str M}$ is a subset of $M^{\emptyset}$.  But
$M^{\emptyset}=\{\emptyset\}$, whose subsets are $\emptyset$ and
$\{\emptyset\}$, that is, $0$ and $1$, which can be considered as
\defn{false} and \defn{true} respectively.

If $\sigma^{\str M}=1$, then we write
$$\str M\models\sigma$$
and say that $\str M$ is a \defn{model} of $\sigma$.
In particular, if $\fv(\phi)=\{0\}$, then
$$\str M\models\exists v_0\qsep\phi\Iff \phi^{\str M}\neq\emptyset.$$
If $\Gamma$ is a set of sentences, then the expression 
$$\str M\models\Gamma$$
has the obvious meaning.  If $\str M\models\Gamma\implies\str
M\models\sigma$ for all $\lang$-structures $\str M$, then we write
$$\Gamma\models\sigma$$
and say $\sigma$ is a \defn{logical consequence} of $\Gamma$.
One can define a notion of \tech{formal proof}, and write
$\Gamma\proves\sigma$ (`$\sigma$ is deducible from $\Gamma$')  when
there is a formal proof of $\sigma$ from
$\Gamma$.  \defn{G\"odel's Completeness Theorem} is that the symbols
$\proves$ and $\models$ are interchangeable.

A \defn{theory} is a set of sentences that contains all of its logical
consequences.  If $T$ is a theory, and $\Gamma\models T$, then
$\Gamma$ is a set of \defn{axioms} for $T$.

In $\lang_{\mathrm r}$, the axioms for the (first-order) theory of fields are
standard.  They can be written in \tech{universal} form, except for
the axiom
$$\forall x\qsep\exists y\qsep(x=0\lor xy=1).$$
The theory $\ACF$ of algebraically closed fields has the additional axioms
$$\forall v_0\qsep\forall v_1\dots\forall v_{n-1}\qsep\exists
y\qsep v_0+v_1y+\dots v_{n-1}x^{n-1}+y^n=0.$$
The model-theoretic version of Chevalley's Theorem is that $\ACF$
admits \defn{elimination of quantifiers}, that is, for
all \emph{positive} $n$, for 
every $n$-ary formula $\phi$ of $\lang_{\mathrm r}$, there is an open formula
$\alpha$ such that
$$\ACF\models\forall v_0\dots\forall
v_{n-1}\qsep(\phi\leftrightarrow\alpha).$$  
One method of proof relies on the fact that a model of $\ACF$ is
determined up to isomorphism by its characteristic and its
transcendence-degree. 

\section*{Ultra-products}

Let $(\str M^{(i)}:i\in I)$ be an indexed set of
$\lang$-structures.  We define a product-structure
$$\prod_{i\in I}\str M^{(i)},$$
or $\str M$ for short, as follows.  The universe, $M$, is the product 
$\prod_{i\in I}M^{(i)}$. 
A typical element of this is $(a^{(i)}:i\in I)$, or simply $a$.   
Then each $\str M^{(i)}$ is an $\lang(M)$-structure when we define
$$a^{\str M^{(i)}}=a^{(i)}.$$
For the symbols of $\lang$, let this definition be a notational
convention, so that $s^{(i)}$ means $s^{\str M^{(i)}}$ when
$s\in\lang$. 

If $\sigma$ is a sentence of $\lang(M)$, then its \defn{Boolean
  value}, $\Bv{\sigma}$, is defined to be the set
$$\{i\in I:\str M^{(i)}\models\sigma\}.$$
The map $\sigma\mapsto\Bv{\sigma}$ is a sort of homomorphism:
$\Bv{\sigma\wedge\tau}=\Bv{\sigma}\cap\Bv{\tau}$ and $\Bv{\lnot
    \sigma}=\Bv{\sigma}\comp$. 

Having $M$, we define $\str M$ by:
\begin{myitem}
  \item
$c^{\str M}=(c^{\str M^{(i)}}:i\in I)$,
\item
$f^{\str M}(\tuple a) =(f^{\str
  M^{(i)}}(\tuple a^{(i)}):i\in I)$, 
\item
$\tuple a\in R^{\str M}\Iff
  \Bv{R\tuple a}=I$.
\end{myitem}
Let $\fil F$ be a filter on $I$ (that is, the dual of an ideal of
$\pow{I}$).  Define an equivalence-relation $\sim$ on $M$ by:
$$a\sim b\Iff\Bv{a=b}\in\fil F.$$
(In case $\fil F=\{I\}$, this relation is equality.)  The
\defn{reduced product} $\str M/\fil F$ has universe $M\modsim$, and: 
\begin{myitem}
  \item
$c^{\str M/\fil F}=c^{\str M}\modsim$,
\item
$f^{\str M/\fil F}(\tuple a\modsim) =f^{\str
  M}(\tuple a)\modsim$, 
\item
$(\tuple a\modsim)\in R^{\str M/\fil F}\Iff
  \Bv{R\tuple a}\in\fil F$.
\end{myitem}
The validity of this definition must be checked:  If $\tuple a,\tuple b\in M^n$, then
$$\Bv{a_0=b_0\land\dots\land a_{n-1}=b_{n-1}}\included \Bv{f(\tuple
  a)=f(\tuple b)},$$
so $\tuple a\sim\tuple b\implies f(\tuple a)\sim f(\tuple b)$.  Also,
$$\Bv{a_0=b_0\land\dots\land a_{n-1}=b_{n-1}}\cap\Bv{R\tuple
  a}\included \Bv{R\tuple b},$$
so $\tuple a\sim\tuple b\land\Bv{R\tuple a}\in\fil F\implies
  \Bv{R\tuple b}\in\fil F$.

\begin{lemma*}
  Say $\sigma_e$ ($e<2$) are sentences of $\lang(M)$ such that
$$\str M/\fil F\models\sigma_e\Iff\Bv{\sigma_e}\in\fil F$$
in each case.  Then $\str M/\fil
F\models\sigma_0\wedge\sigma_1\Iff\Bv{\sigma_0\wedge\sigma_1}\in\fil F$.
\end{lemma*}

\begin{proof}
  $\Bv{\sigma_0}\cap\Bv{\sigma_1}=\Bv{\sigma_0\wedge\sigma_1}
  \included\Bv{\sigma_e}$. 
\end{proof}

\begin{lemma*}
  Say $\phi$ is a formula of $\lang(M)$ with one free variable, and
$$\str M/\fil F\models\phi(a)\Iff\Bv{\phi(a)}\in\fil F$$
for all $a$ in $M$.  Then 
$\str M/\fil F\models\exists x\qsep\phi\Iff\Bv{\exists
  x\qsep\phi}\in\fil F$. 
\end{lemma*}

\begin{proof}
  $\Bv{\phi(a)}\included\Bv{\exists x\qsep\phi}$ for all $a$ in $M$.
  Also, there
  $a$ in $M$ such that $\str M^{(i)}\models\phi(a)$ if $\str
  M^{(i)}\models\Exists x\phi$.  Then $\Bv{\phi(a)}=\Bv{\Exists
  x\phi}$. 
\end{proof}

\begin{theorem*}[\L o\'s]
  If $\fil U$ is an ultrafilter on $I$, then
  \begin{equation}\label{eqn}
    \str M/\fil U\models \sigma\Iff\Bv{\sigma}\in\fil U
  \end{equation}
for all sentences $\sigma$ of $\lang(M)$.
\end{theorem*}

\begin{proof}
Since all sentences are constructed from atomic formulas using only
  $\land$, $\exists$ and $\lnot$, it is enough to note that if
  (\ref{eqn}) holds when $\sigma=\theta$, then it holds when
  $\sigma=\lnot\theta$. 
\end{proof}

\begin{corollary*}[Compactness]
  If every finite subset of a theory $T$ has a model, then $T$ has a
  model. 
\end{corollary*}

\begin{proof}
  Let $I$ comprise the finite subsets of $T$.  Each $\Gamma$ in $I$
  determines a filter $(\Gamma)$, namely the set
$$\{\Gamma'\in I:\Gamma\included\Gamma'\}.$$
Any finite collection $\{(\Gamma_0),\dots,(\Gamma_{m-1})\}$ of subsets
of $I$ has intersection containing
$\Gamma_0\cup\dots\cup\Gamma_{m-1}$; so the intersection is
non-empty.  Hence some ultrafilter $\fil U$ on $I$ contains each
$(\Gamma)$.  For each $\Gamma$ in $I$, let $\str M^{(\Gamma)}$ be a
model of $\Gamma$.  If $\sigma\in T$, then
$(\{\sigma\})\included\Bv{\sigma}$, so $\Bv{\sigma}\in\fil U$.
By the theorem of \L o\'s,  $\prod_{\Gamma\in I}\str M^{(\Gamma)}/\fil
U \models T$.
\end{proof}

Let $T$ be the set of sentences of $\lang$ such that
$\Bv{\sigma}\in\fil F$.  If $\fil U$ is an ultrafilter on $I$ that
includes $\fil F$, then
$$\str M/\fil U\models T.$$
Conversely, suppose $\str N\models T$.  The set $\{\Bv{\sigma}:\str
N\models\sigma\}$ is closed under finite intersection.  Also, if $\str
N\models\sigma$, then $\Bv{\sigma}\comp\notin \fil F$.  Hence
$\{\Bv{\sigma}:\str N\models\sigma\}\cup\fil F$ is included in an
ultrafilter $\fil U$, such that
$$\str N\models\sigma\Iff \Bv{\sigma}\in\fil U\Iff \str M/\fil
U\models\sigma$$
for all sentences $\sigma$ of $\lang$.  We write
$$\str N\equiv \str M/\fil U,$$
and say that $\str N$ and $\str M/\fil U$ are \defn{elementarily
  equivalent}. 

\begin{example*}
  Let $T$ be the set of sentences of $\lang_{\mathrm r}$, each of
  which is true in all but finitely many finite fields.  Then
$$\prod_{q\in I}\F_q/\fil U\models T,$$
where $I$ is the set of prime powers, for all non-principal
ultrafilters $\fil U$ on $I$.  Conversely, every model of $T$ is
elementarily equivalent to such an \defn{ultraproduct}.
\end{example*}

\bibliographystyle{plain}
\bibliography{../../math/references}
%\tableofcontents
\end{document}
