\documentclass[a4paper,twoside,11pt,reqno]{amsart}
\title{Model theory and linear algebra}
\author{David Pierce}
\date{\today}
\address{Mathematics Dept, METU, Ankara 06531, Turkey}
\email{dpierce@metu.edu.tr}
\urladdr{http://metu.edu.tr/~dpierce/}

\usepackage{verbatim}

\usepackage{amsthm,amssymb}
\usepackage{pstricks,pst-tree}
\newtheorem*{theorem}{Theorem}
\newtheorem*{corollary}{Corollary}
\theoremstyle{definition}
\newtheorem{parag}{\P}

\newcommand{\str}[1]{\mathfrak{#1}}
%\newcommand{\inv}{^{-1}}
\newcommand{\End}[1]{\operatorname{End}(#1)}
\newcommand{\id}{\operatorname{id}}
\usepackage{bm}
\renewcommand{\vec}[1]{\bm{#1}}
%\newcommand{\vz}{\boldsymbol0}
\renewcommand{\phi}{\varphi}
\newcommand{\liff}{\Leftrightarrow}
\newcommand{\lto}{\Rightarrow}
\renewcommand{\land}{\mathrel{\&}}
\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\Forall}[1]{\forall#1\;}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\newcommand{\stnd}[1]{\mathbb#1}
\newcommand{\N}{\stnd N}
\newcommand{\Z}{\stnd Z}
\newcommand{\Q}{\stnd Q}
\newcommand{\R}{\stnd R}
\newcommand{\C}{\stnd C}
\newcommand{\Ham}{\stnd H}
\newcommand{\F}{\stnd F}
\newcommand{\gpgen}[1]{\langle#1\rangle}
\usepackage{mathrsfs}
\newcommand{\pow}[1]{\mathscr P(#1)}
\newcommand{\Th}[1]{\operatorname{Th}(#1)}
\newcommand{\included}{\subseteq}
\newcommand{\nincluded}{\nsubseteq}
\newcommand{\mi}{\mathbf i}
\newcommand{\mpi}{\uppi}

\usepackage{upgreek}
%\newcommand{\vnn}{\upomega}
\newcommand{\sig}[1]{\mathscr#1}
\newcommand{\PV}{\mathrm{PV}}
\newcommand{\PF}{\mathrm{PF}}
\newcommand{\Tm}[1]{\operatorname{Tm}_{\sig L}(#1)}
%\newcommand{\At}[1]{\operatorname{At}(#1)}
\newcommand{\Fm}[1]{\operatorname{Fm}_{\sig L}(#1)}
%\newcommand{\Sn}[1]{\operatorname{Sn}_{\sig L}(#1)}
\renewcommand{\setminus}{\smallsetminus}
\newcommand{\Qu}{\mathsf Q}
\renewcommand{\emptyset}{\varnothing}
\newcommand{\proves}{\vdash}
\newcommand{\theory}[1]{\operatorname{#1}}
\newcommand{\ACF}{\theory{ACF}}
\newcommand{\RCF}{\theory{RCF}}
\newcommand{\VS}{\theory{VS}}
\newcommand{\diag}[1]{\operatorname{diag}(#1)}
\newcommand{\tp}{^{\mathrm t}}
\renewcommand{\models}{\vDash}
\newcommand{\nmodels}{\nvDash}
\newcommand{\trdeg}[1]{\operatorname{tr-deg}(#1)}

\renewcommand{\theequation}{\fnsymbol{equation}}
\begin{document}
\maketitle

These are notes were written originally in preparation for a talk to
be given on Friday, March 26, 2010, in the Department of Mathematics
and Computer Science at \c Cankaya University, Ankara.  The talk itself is
just a selection.  What is said here about vector spaces is based
mainly on \cite{MR2505433}.

\tableofcontents

\section{History of algebra}

\begin{parag}
In the \emph{Elements} \cite{MR1932864} of Euclid (fl.~300
\textsc{b.c.e.}), Proposition II.5 is,
\begin{quote}
If a straight line be cut into equal and unequal segments, the
rectangle contained by the unequal segments of the whole together with
the square on the straight line between the points of section is equal
to the square on the half. 
\end{quote}
In other words, if a straight line be divided unequally, the rectangle
bounded by the unequal pieces falls short of the square on the half by
the square on the segment between the midpoint and the point of
unequal section.  See Figure~\ref{fig:Euclid}, where
\begin{equation*}
\operatorname{rect.}AD,DB=\operatorname{sq.}AC-\operatorname{sq.}DC.
\end{equation*}
\begin{figure}[ht]
\begin{pspicture}(0,-0.5)(5,2.5)
\psset{unit=0.5cm}
\psline(0,0)(10,0)(10,3)(3,3)
\psline(5,0)(5,5)(0,5)(0,0)
\psline(3,0)(3,5)
\uput[dl](0,0){$A$}
\uput[d](3,0){$D$}
\uput[d](5,0){$C$}
\uput[dr](10,0){$B$}
\end{pspicture}
\caption{}\label{fig:Euclid}
\end{figure}
\end{parag}

\begin{parag}
Consequently,
Muhammad ibn M\=us\=a{} al-Khw\=arizm\=\i{} (\emph{c.}~780--850)
\cite[pp.~525, 544]{Katz} asks,  
\begin{quote}
  what must be the amount of a square, which, when twenty-one dirhams
  are added to it, becomes equal to the equivalent of ten roots of
  that square?  Solution: \dots nine.  Or\dots forty-nine.
\end{quote}
See Figure~\ref{fig:al-Khw}.
In our terms, if 
\begin{equation*}
x^2+21=10x,
\end{equation*}
then
\begin{equation*}
x=\frac{10}2\pm\sqrt{\Bigl(\frac{10}2\Bigr)^2-21}=5\pm\sqrt4=5\pm2=3\text{
  or }7, 
\end{equation*}
so $x^2=9$ or $49$.
\begin{figure}[ht]
\begin{pspicture}(0,-0.5)(5,2.5)
\psset{unit=0.5cm}
\psline(0,0)(10,0)(10,3)(0,3)(0,0)
\psline[linestyle=dashed](5,0)(5,3)
\psline(5,3)(5,5)(0,5)(0,3)
\psline(3,0)(3,5)
\rput(6.5,1.5){$21$}
\rput(1.5,1.5){$x^2$}
\psline{<->}(0,-0.5)(10,-0.5)
\uput[d](5,-0.5){$10$}
\rput(4,4){$4$}
\end{pspicture}
\hfill
\begin{pspicture}(0,-0.5)(5,3.5)
\psset{unit=0.5cm}
\psline(0,0)(10,0)(10,7)(0,7)(0,0)
\psline[linestyle=dashed](5,0)(5,5)(10,5)
\psline(7,0)(7,7)
\psline[linestyle=dashed](5,3)(7,3)
\rput(3.5,3.5){$x^2$}
\rput(8.5,3.5){$21$}
\psline{<->}(0,-0.5)(10,-0.5)
\uput[d](5,-0.5){$10$}
\rput(6,4){$4$}
\end{pspicture}
\caption{}\label{fig:al-Khw}
\end{figure}
\end{parag}

\begin{parag}
Descartes observes in the \emph{Geometry} (1637)
\cite[pp.~4, 5]{Descartes-Geometry}: lines can be 
multiplied to make \emph{lines,} not rectangles.  So, in
Figure~\ref{fig:Descartes}, if
\begin{align*}
  AB&=1,& BD&=a,& BC&=b,
\end{align*}
then
\begin{equation*}
  BE= ab.
\end{equation*}
\begin{figure}[ht]
        \begin{pspicture}(0,-0.3)(3,2.2)
\psset{unit=5mm}
\psline(0,0)(6,0)(1,4)
\psline(1,0)(1.5,3.6)
\psline(3,0)(3.3,2.16)
\uput[d](1,0){$D$}
\uput[d](3,0){$A$}
\uput[dr](6,0){$B$}
\uput[ur](1.5,3.6){$E$}
\uput[ur](3.3,2.16){$C$}
    \end{pspicture}
\caption{}\label{fig:Descartes}
\end{figure}
Descartes's purpose is apparently to use geometry as a model for
field theory. He implicitly shows that the \emph{scalar field} of a
\emph{vector space} (of dimension $2$ or more) can be found in the
space.  
\end{parag}

\section{Vector spaces}

\begin{parag}
A \textbf{vector space} is a triple $(\str V,\str K,*)$, where
\begin{enumerate}
\item
$\str V$ is an abelian group   of \textbf{vectors,}
  \begin{equation*}
  (V,\vec0,\vec-,\vec+);
  \end{equation*}
\item
$\str K$ is a field   of \textbf{scalars,}
  \begin{equation*}
  (K,0,1,-,+,{}\cdot{}); 
  \end{equation*}
\item
$*$ is an \textbf{action} of $\str K$ on $\str V$, that is,
a function from $K\times V$ to $V$ such that
\begin{enumerate}
	\item 
each operation 
\begin{equation*}
\vec v\mapsto x*\vec v
\end{equation*}
 on $V$ is an endomorphism of $\str V$, and 
	\item
	the function
	\begin{equation*}
x\mapsto(\vec v\mapsto x*\vec v)
\end{equation*}
is a ring-homorphism from $\str K$ to $(\End{\str V},\circ)$.
\end{enumerate}
\end{enumerate}
So a vector space is a kind of \textbf{$2$-sorted structure,} with the
\textbf{signature}
\begin{equation*}
  \{\vec0,\vec-,\vec+;0,1,-,+,\cdot;*\}.
\end{equation*}
\end{parag}

\begin{parag}
Descartes's example suggests how, given a vector space $(\str V,\str
K,*)$, where
\begin{equation*}
\dim_{\str K}(\str V)\geq2,
\end{equation*}
we can \textbf{interpret} $\str K$ and its action on $\str V$
\emph{in} $\str V$.
To
do this, we introduce a new symbol $\parallel$ for the
binary relation of \textbf{parallelism} on $V$; this relation is
\emph{defined} by  
\begin{equation*}
\vec u\parallel\vec v\liff\Exists x\Exists y(x*\vec u\vec+y*\vec
v=\vec0\land(x\neq0\lor y\neq0)). 
\end{equation*}
Now let 
\begin{equation*}
M=\{(\vec u,\vec v)\in V\times V\colon\vec u\neq0\land\vec u\parallel\vec v\}.
\end{equation*}
If $(\vec u,\vec v)\in M$, then we can define the element
$[\vec u:\vec v]$ of $K$ by the rule
\begin{equation*}
\vec v=[\vec u:\vec v]*\vec u.
\end{equation*}
So we have a surjection $(\vec u,\vec v)\mapsto[\vec u:\vec v]$ from
$M$ onto $K$.  This induces an equivalence-relation $\sim$ on $M$:
\begin{equation*}
  (\vec u_0,\vec u_1)\sim(\vec v_0,\vec v_1)\iff 
  [\vec u_0,\vec u_1]=[\vec v_0,\vec v_1].
\end{equation*}
We now give $M/\mathord{\sim}$ the structure of $\str K$.  We shall
use the formula
\begin{equation*}
\vec s\nparallel\vec u\land\vec s\parallel\vec t\land\vec
u\parallel\vec v\land\vec s\vec-\vec u\parallel\vec t\vec-\vec v,
\end{equation*}
which we denote by
\begin{equation*}
\Delta(\vec s,\vec t,\vec u,\vec v).
\end{equation*}
See Figure~\ref{fig:Delta}.
\begin{figure}[ht]
        \begin{pspicture}
(0,-0.3)(3,2.1)
\psset{unit=5mm}
\psline(0,0)(6,0)(1,4)
\psline(1,0)(1.5,3.6)
\psline(3,0)(3.3,2.16)
\uput[d](1,0){$\vec t$}
\uput[d](3,0){$\vec s$}
\uput[dr](6,0){$\vec0$}
\uput[ur](1.5,3.6){$\vec v$}
\uput[ur](3.3,2.16){$\vec u$}
    \end{pspicture}
\caption{$\Delta(\vec s,\vec t,\vec u,\vec v)$%
%, that is, $\vec s\nparallel\vec u\land\vec s\parallel\vec t\land\vec
%u\parallel\vec v\land\vec s\vec-\vec u\parallel\vec t\vec-\vec v$
}\label{fig:Delta} 
\end{figure}
To interpret the field $\str K$ in $\str V$, we have to express the
formulas
\begin{align*}
  x&=y,& x+y&=z,& x\cdot y&=z,& x*\vec u&=\vec v
\end{align*}
wholly in terms of vectors.  We do this as follows:
\begin{enumerate}
\item
Equality in $K$, or
\begin{equation}\label{eqn:=}
[\vec s:\vec t]=[\vec u:\vec v],
\end{equation}
is expressed in $\str V$ by
\begin{equation}\label{eqn:='}
\Delta(\vec s,\vec t,\vec u,\vec v)\lor
\Exists{\vec w}\Exists{\vec z}
(\Delta(\vec s,\vec t,\vec w,\vec z)\land
\Delta(\vec w,\vec z,\vec u,\vec v)),
\end{equation}
where the latter condition is shown in Figure~\ref{fig:=}; now we can
use~\eqref{eqn:=} to stand for~\eqref{eqn:='}.
\begin{figure}[t]
        \begin{pspicture}
(0,-0.3)(3,2.5)
%\psgrid
\psset{unit=5mm}
\psline(-1,0)(6,0)(1,4)
\psline(1,0)(1.5,3.6)
\psline(3,0)(3.3,2.16)
\psline(3.3,2.16)(2,0)
\psline(1.5,3.6)(-0.67,0)
\uput[d](1,0){$\vec t$}
\uput[d](3,0){$\vec s$}
\uput[r](6,0){$\vec0$}
\uput[d](2,0){$\vec u$}
\uput[d](-0.67,0){$\vec v$}
\uput[ur](1.5,3.6){$\vec z$}
\uput[ur](3.3,2.16){$\vec w$}
    \end{pspicture}
\caption{$[\vec s:\vec t]=[\vec u:\vec v]$ (one case)}\label{fig:=}
\end{figure}
\item
Addition in $\str K$, or
\begin{equation*}
[\vec u_0:\vec u_1]+[\vec v_0:\vec v_1]=[\vec w_0:\vec w_1],
\end{equation*}
is expressed in $\str V$, as in
Figure~\ref{fig:+}, by
\begin{equation*}
\Exists{\vec z}([\vec u_0:\vec z]=[\vec v_0:\vec v_1]\land
[\vec u_0:\vec u_1\vec+\vec z]=[\vec w_0:\vec w_1].
\end{equation*}
\begin{figure}
        \begin{pspicture}
(-3,-2.5)(3,2.5)
%\psgrid
\psset{unit=5mm}
\psline(-6,0)(6,0)(1,4)
\psline(1,0)(1.5,3.6)
%\psline(3,0)(3.3,2.16)
\psline(3.3,2.16)(2,0)
\psline(1.5,3.6)(-0.67,0)
\uput[d](1,0){$\vec u_1$}
\uput[r](6,0){$\vec0$}
\uput[d](2,0){$\vec u_0$}
\uput[ul](-0.67,0){$\vec z$}
\uput[ur](1.5,3.6){$\vec v_1$}
\uput[ur](3.3,2.16){$\vec v_0$}
\uput[u](-5.67,0){$\vec u_1+\vec z$}
\psline(-5.67,0)(-2,-4)(6,0)
\psline(2,0)(3.26,-1.38)
\uput[d](-2,-4){$\vec w_1$}
\uput[dr](3.26,-1.38){$\vec w_0$}
    \end{pspicture}
\caption{$[\vec u_0:\vec u_1]+[\vec v_0:\vec v_1]=[\vec w_0:\vec
    w_1]$}\label{fig:+} 
\end{figure}
\item
Multiplication in $\str K$, or
\begin{equation*}
[\vec u_0:\vec u_1]\cdot[\vec v_0:\vec v_1]=[\vec w_0:\vec w_1],
\end{equation*}
is expressed in $\str V$, as in Figure~\ref{fig:.}, by
\begin{equation*}
\Exists{\vec z}([\vec u_1:\vec z]=[\vec v_0:\vec v_1]\land
[\vec u_0:\vec z]=[\vec w_0:\vec w_1].
\end{equation*}
\begin{figure}[ht]
        \begin{pspicture}
(-3,-2.5)(3,2.5)
%\psgrid
\psset{unit=5mm}
\psline(-6,0)(6,0)(1,4)
\uput[r](6,0){$\vec0$}
\uput[d](2,0){$\vec u_0$}
\uput[d](-1,0){$\vec u_1$}
\uput[ur](1.5,3.6){$\vec v_1$}
\uput[ur](3.3,2.16){$\vec v_0$}
\uput[u](-5.67,0){$\vec z$}
\psline(-5.67,0)(1.5,3.6)
\psline(-5.67,0)(-2,-4)(6,0)
\uput[d](-2,-4){$\vec w_1$}
\uput[dr](3.26,-1.38){$\vec w_0$}
\psline(2,0)(3.26,-1.38)
\psline(3.3,2.16)(-1,0)
    \end{pspicture}
\caption{$[\vec u_0:\vec u_1]\cdot[\vec v_0:\vec v_1]=[\vec w_0:\vec
    w_1]$}\label{fig:.} 
\end{figure}
\item
Finally, scalar multiplication, or
\begin{equation*}
[\vec u_0:\vec u_1]*\vec v_0=\vec v_1,
\end{equation*}
is expressed in $\str V$ by
\begin{equation*}
[\vec u_0:\vec u_1]=[\vec v_0:\vec v_1]\lor(\vec v_0=\vec0\land\vec
v_1=\vec0). 
\end{equation*}
\end{enumerate}
\end{parag}

\begin{parag}
So one can define a vector space as a pair $(\str V,\parallel_{\str K})$,
where 
\begin{enumerate}
	\item 
	$\str V$ is an abelian group $(V,\vec0,\vec-,\vec+)$, and
	\item
	the binary relation $\parallel$ respects axioms ensuring that
        $\str V$ is acted on by a field, $\str K$.
\end{enumerate}
In this sense, a vector space is a $1$-sorted structure in the
signature
\begin{equation*}
  \{\vec0,\vec-,\vec+,\parallel\}.
\end{equation*}
However, the two notions of a vector space are not entirely
equivalent, and not just because spaces in the latter sense are at
least $2$-dimensional.  The \textbf{substructure} relation differs also.
For example, 
we have 
\begin{equation*}
(\Ham,\R,*)\included(\Ham,\C,*),
\end{equation*}
but
\begin{equation*}
(\Ham,\parallel_{\R})\nincluded(\Ham,\parallel_{\C}),
\end{equation*}
since the relations $\parallel_{\R}$ and $\parallel_{\C}$ do not
agree, even on $\C$ (much less on $\Ham$):
\begin{align*}
1&\nparallel_{\R}\mi,&1&\parallel_{\C}\mi.
\end{align*}
(However, $(\C,\parallel_{\R})\included(\Ham,\parallel_{\C})$.) 
\end{parag}

\begin{parag}
Let $\VS$ be the \textbf{theory} of vector spaces in the original
sense, in the signature
\begin{equation*}
\{\vec0,\vec-,\vec+;0,1,-,+\cdot;*\}.  
\end{equation*}
That is, $\VS$ is the set of \textbf{sentences} of \textbf{first-order
  logic} in the given signature that are true in all vector spaces.
(A logic is first order when all variables stand for individuals, not
sets as such.)
Every \textbf{model} $(\str
V,\str K,*)$ of $\VS$
embeds in a $1$-dimensional model 
\begin{equation*}
(\str L,\str L,*);
\end{equation*}
just let $\str L$ be a field-extension of $\str K$ such that
\begin{equation*}
  [\str L:\str K]\geq\dim_{\str K}\str V,
\end{equation*}
and embed a basis of $(\str V,\str K,*)$ in a basis of $(\str L,\str
K,*)$. 
\end{parag}

\begin{parag}
Let $\VS_2$ be the \textbf{theory} of vector spaces of dimension at
least $2$ in the signature
\begin{equation*}
\{\vec0,\vec-,\vec+,\parallel\}.  
\end{equation*}
Every model embeds in a $2$-dimensional model.
Indeed, suppose $L/K$ is a field-extension, and $a,b\in L$, and
$(a,b,1)$ is linearly independent over $K$.  Then $(K^3,\parallel_K)$
embeds in $(L^2,\parallel_L)$ under 
\begin{equation*}
(x,y,z)\mapsto(x-az,y-bz),  
\end{equation*}
that is,
\begin{equation*}
  \begin{pmatrix}
    x&y&z
  \end{pmatrix}
\mapsto
\begin{pmatrix}
  x&y&z
\end{pmatrix}
\begin{pmatrix}
  1&0\\0&1\\-a&-b
\end{pmatrix}.
\end{equation*}
For, the following are equivalent:
\begin{gather*}
	(x,y,z)\parallel_K(u,v,w),\\
	\begin{aligned}
0&=	\det\begin{pmatrix}
	x&y&z\\u&v&w\\a&b&1
	\end{pmatrix}\\
 &=     \det\left(
	\begin{pmatrix}
	x&y\\u&v
	\end{pmatrix}-
	\begin{pmatrix}
	z\\w
	\end{pmatrix}
	\begin{pmatrix}
	a&b
	\end{pmatrix}
	\right)\\
 &=     \det\left(
        \begin{pmatrix}
          x&y&z\\u&v&w
        \end{pmatrix}
        \begin{pmatrix}
          1&0\\0&1\\-a&-b
        \end{pmatrix}
        \right),
%\\
% &=     \begin{pmatrix}
%	x-az&y-zb\\u-aw&v-bw
%	\end{pmatrix}
	\end{aligned}\\
	(x-az,y-zb)\parallel_L(u-aw,v-bw).
\end{gather*}
We used here the identity
 \begin{equation*}
    \det\left(
    \begin{array}{c|c}
      U & \vec v\tp\\\hline\vec a & 1
    \end{array}\right)
=\det(U-\vec v\tp\cdot\vec a),
  \end{equation*}
which follows from
\begin{equation*}
    \left(
    \begin{array}{c|c}
      U & \vec v\tp\\\hline\vec a & 1
    \end{array}\right)
\cdot
    \left(
    \begin{array}{c|c}
      I & \vec 0\tp\\\hline-\vec a & 1
    \end{array}\right)
=
    \left(
    \begin{array}{c|c}
      U-\vec v\tp\cdot\vec a & \vec v\tp\\\hline\vec 0 & 1
    \end{array}\right).
\end{equation*}
\end{parag}

\section{Model theory (outline)}

\begin{parag}
We have entered \textbf{model theory,} which I define as
\begin{center}
  the study of \textbf{structures} \emph{qu\^a} \textbf{models} of
  \textbf{theories.} 
\end{center}
Examples of structures include
\begin{align*}
&(\str V,\str K,*),&
&(\str V,\parallel_{\str K}),&
&(\Q,<),&
&(\Q,+,\cdot),&
&(\R,+,\cdot,<),&
&(\C,+,\cdot).
\end{align*}
Model theory has also been called
\begin{center}
the geography of \textbf{tame} mathematics.
\end{center}
\emph{Tameness} has no one definition.  However, one measure of tameness is
the \textbf{effective axiomatizability} of the (first-order) theory,
\begin{equation*}
\Th{\str A},
\end{equation*}
of a structure $\str A$. 
\end{parag}

\begin{parag}
In the following, 
\begin{equation*}
\N=\{1,2,3,\dots\}, 
\end{equation*}
and $S$ stands for $x\mapsto
x+1$.  Outer universal quantifiers of sentences are suppressed. 
The structure $(\N,1,S,+)$ is ``tame'', because of:

\begin{theorem}[Presburger, 1929]
$\Th{\N,1,S,+}$ is axiomatized by:
\begin{enumerate}
	\item \label{item:P1}
	$1\neq Sx$;
	\item\label{item:P2}
	$Sx=Sy\lto x=y$;
	\item\label{item:P3}
	$x+1=Sx$;
	\item\label{item:P4}
	$x+(y+1)=(x+y)+1$;
	\item
	the \textbf{first-order induction axioms:}
	for each formula $\phi(x)$,
	\begin{equation*}
\phi(1)\land\Forall x(\phi(x)\lto\phi(Sx))\lto\Forall \phi(x).
\end{equation*}
\end{enumerate}
\end{theorem}
\end{parag}

\begin{parag}
  An arbitrary theory $T$ is \textbf{complete} if
  \begin{equation*}
    T\proves\sigma\text{ or }T\proves\lnot\sigma
  \end{equation*}
for all sentences $\sigma$ of the signature of $T$.  The theory
\emph{of} a structure is automatically complete.
Then Presburger's
theorem is that a particular theory given by axioms is complete.
\end{parag}

\begin{parag}
By contrast, $(\N,1,S,+,\cdot)$ is
``wild'', by \textbf{G\"odel's Incompleteness Theorem:} 

\begin{theorem}[G\"odel, 1931 \cite{Goedel-incompl}]
$\Th{\N,1,S,+,\cdot}$ cannot be effectively axiomatized.
\end{theorem}
\end{parag}

\begin{parag}
Even though $\Th{\N,1,S,+}$ can be (effectively) completely
axiomatized in first-order logic, the axioms do not determine
$(\N,1,S,+)$ (up to isomorphism), as we shall see.  However,
$(\N,1,S)$ is characterized (up to isomorphism) by its satisfaction of
the axioms identified by Dedekind (1888) \cite{MR0159773} and Peano
(1889) \cite{Peano}, namely 
Presburger's~\eqref{item:P1} and~\eqref{item:P2}--- 
\begin{align*}
1&\neq Sx,&
Sx=Sy&\lto x=y,
\end{align*}
---along with the \textbf{second-order induction axiom:} the sentence
\begin{equation*}
1\in X\land\Forall t(t\in X\lto St\in X)\lto\Forall tt\in X.
\end{equation*}
\end{parag}

\begin{parag}
That $(\N,1,S)$ satisfies (second-order) induction means $\N$ is the
\emph{smallest}
set that contains $1$ and is closed under $S$.  Another way to say
this is that $\N$ has a \textbf{recursive definition:}
\begin{enumerate}
\item 
$1\in\N$,
\item
if $x\in\N$, then $Sx\in\N$.
\end{enumerate}
This, \emph{together with} the other
two axioms~\eqref{item:P1} and~\eqref{item:P2}, is logically
equivalent to the validity of 
recursive definitions of operations on $\N$: operations such
as addition, given by Presburger's~\eqref{item:P3}
and~\eqref{item:P4}---
\begin{align*}
x+1&=Sx,&
x+(y+1)&=(x+y)+1
\end{align*}
---, or multiplication, given by
\begin{align*}
x\cdot1&=x,&
x\cdot(y+1)&=x\cdot y+x,
\end{align*}
or exponentiation, given by
\begin{align}\label{eqn:exp}
x^1&=x,&
x^{y+1}&=x^y\cdot x.
\end{align}
In particular, despite G\"odel's Incompleteness Theorem,
$(\N,1,S,+,\cdot)$ \emph{can} be completely characterized, in a sense,
in second-order logic. 
\end{parag}

\begin{parag}
From Peano on, some people have not recognized that the possibility of
defining a set recursively does not, by itself, allow functions
\emph{on} the set to be defined recursively.
Addition and multiplication \emph{are} justified by induction alone, as is
shown implicitly in Landau's \emph{Foundations of Analysis} (1929)
\cite{MR12:397m}; but exponentiation is not: 

\begin{theorem}[Dyer-Bennet, 1940 \cite{MR0001234}; P., 2009]
If $n\in\N$, then $(\Z/(n),1,S)$ satisfies (second-order) induction; but
it admits exponentiation defined as in~\eqref{eqn:exp} if and only if
$n\in\{1,2,6,42,1806\}$. 
\end{theorem}
\end{parag}

\section{Model theory (detail)}

\begin{parag}
That induction does not always imply recursion can be seen
in the development of logic itself.  I now review this development in detail.
To be precise then, a \textbf{structure} is one or more disjoint sets called
\textbf{sorts,} together with some (or no) distinguished 
\begin{enumerate}
\item
\textbf{operations:} functions from finite products of sorts to one sort;
\item
\textbf{constants:} operations taking no arguments;
\item
\textbf{relations:} subsets of finite products of the sorts.
\end{enumerate}
If $G$ is a group, and $f$ is the function $X\mapsto\gpgen X$ that converts a subset of $G$ into the subgroup that it generates, then the pair
\begin{equation*}
(G,f)
\end{equation*}
is \emph{not} a structure, although the quadruple
\begin{equation*}
(G,\pow G,\in,f)
\end{equation*}
 is a (two-sorted) structure. 
\end{parag}

\begin{parag}
A structure has a \textbf{signature,} namely a set of \textbf{symbols}
for the distinguished operations (including constants) and relations.
So the signature of 
$(\str V,\str K,*)$ is 
\begin{equation*}
\{\vec0,\vec-,\vec+,0,1,-,+,\cdot,*\}.
\end{equation*}
The symbols `know' which sorts their arguments are from.  The symbols
are called \textbf{non-logical,} to distinguish them from
\textbf{logical symbols,} namely, 
\begin{enumerate}
	\item 
	\textbf{Boolean connectives:} $\lnot$, $\land$, $\lor$, $\lto$, $\liff$, \dots;
	\item
	\textbf{quantifiers:} $\exists$ and $\forall$;
	\item
	\textbf{punctuation:} $($ and $)$;
	\item
	the sign of \textbf{equality,} $=$;
	\item
	\textbf{variables.}
\end{enumerate}
In \textbf{first-order logic,} each variable is required to range only
over the elements of a particular sort, and not (for example) over the
\emph{subsets} of a sort.  In talking about $(\str V,\str K,*)$, we
let boldface variables like $\vec u$ range over $V$; and plainface
variables like $x$, over $K$. 
\end{parag}

\begin{parag}
From logical and non-logical symbols, one builds up \textbf{formulas}
that refer to structures of a particular signature.  The construction
will be discussed later.  \emph{All formulas here will be first-order,
  unless otherwise specified.}  A formula may have \textbf{free
  variables;} if it does not, then the formula is a \textbf{sentence.}
A sentence is either \textbf{true} or \textbf{false} in a structure
(with a suitable signature); if the sentence $\sigma$ is true in the
structure $\str A$, we write 
\begin{equation*}
\str A\models\sigma;
\end{equation*}
we may say also that $\str A$ \textbf{satisfies} $\sigma$.
For example,
\begin{gather*}
\Q\models\Forall x\Exists y(x=0\lor x\cdot y=1),\\
\Z\nmodels\Forall x\Exists y(x=0\lor x\cdot y=1).
\end{gather*}
A set of sentences of some signature is a \textbf{theory.}  If $T$ is
a theory, and all of its elements are true in $\str A$, then $\str A$
is a \textbf{model} of $T$.  If $\sigma$ is a sentence that is true in
every model of $T$, then $\sigma$ is a \textbf{logical consequence} of
$T$, and we may write 
\begin{equation*}
T\models\sigma.
\end{equation*}
\end{parag}

\begin{parag}
A (first-order) theory $T$ is \textbf{complete} if, for every sentence
$\sigma$ of its signature, either $T\models\sigma$ or
$T\models\lnot\sigma$.  The set of sentences that are true in $\str A$
is the \textbf{theory of} $\str A$, denoted by 
\begin{equation*}
\Th{\str A};
\end{equation*}
it is automatically complete.  If $\Sigma\included T$, and every
sentence of $T$ is a logical consequence of $\Sigma$, then $\Sigma$ is
a set of \textbf{axioms} for $T$.
\end{parag}

\begin{parag}
Given a signature $\sig
L$ and a set $C$ of \textbf{parameters,} we recursively define the set
\begin{equation*}
  \Fm C
\end{equation*}
of first-order \textbf{formulas} of $\sig L$ in $C$.  For each
formula, there is a finite \textbf{tree,} as in Figure~\ref{fig:tree},
\textbf{proving} that the formula is a formula.
\begin{figure}[ht]
\psset{nodesep=2mm}
  \pstree{\TR{$\Exists x\Exists y(x*\vec u\vec+y*\vec v=\vec0\land(x\neq0\lor y\neq0))$}}
         {\pstree{\TR{$\Exists y(x*\vec u\vec+y*\vec v=\vec0\land(x\neq0\lor y\neq0))$}}
                 {\pstree{\TR{$(x*\vec u\vec+y*\vec v=\vec0\land(x\neq0\lor y\neq0))$}}
                         {\TR{$x*\vec u\vec+y*\vec v=\vec0$}
                          \pstree{\TR{$(x\neq0\lor y\neq0)$}}
                                 {\TR{$x\neq0$}
                                  \TR{$y\neq0$}}}}}
  \caption{}\label{fig:tree}
\end{figure}
Moreover, such trees are \emph{unique;} so we can also
recursively define functions on $\Fm C$.  For example, given an $\sig
L$-structure $\str A$ that includes $C$, and given a function $v$ that
assigns values from $\str A$ to the variables used in formulas, we can
determine recursively whether
\begin{equation*}
  \str A\models\phi[v],
\end{equation*}
that is, whether $\phi$ \textbf{true}
in $\str A$ under $v$.
\end{parag}

\begin{parag}
We distinguish some sentences as \textbf{logical axioms.}  Then the
set of \textbf{theorems} is the closure of the set of axioms under
\textbf{detachment} (or \textbf{\emph{modus ponens}},
\begin{equation*}
  (\sigma,(\sigma\lto\tau))\mapsto\tau.
\end{equation*}
Again, for each theorem, there is a finite tree, as in
Figure~\ref{fig:proof},
proving that the theorem is
a theorem.  
\begin{figure}[ht]
\psset{nodesep=2mm}
\pstree{\TR{$\lnot\Exists x\phi$}}  
       {\TR{$\lnot\phi(a)$}
        \pstree{\TR{$(\lnot\phi(a)\lto\lnot\Exists x\phi)$}}
               {\TR{$(\lnot\phi(a)\lto\lnot\phi(b))$}
                \TR{$((\lnot\phi(a)\lto\lnot\phi(b))\lto
(\lnot\phi(a)\lto\lnot\Exists x\phi))$}}}
  \caption{Proof of $\lnot\Exists x\phi$, where $\phi$ is
    $\lnot(x=x\lto x=x)$}\label{fig:proof}
\end{figure}
But now the tree is not unique; so we cannot define
functions recursively on the set of theorems.
These points are elaborated in the following paragraphs.
\end{parag}

\begin{parag}
Let $\PV$ 
be a set of \textbf{propositional variables,} perhaps 
\begin{equation*}
\{P_n\colon n\in\N\}.  
\end{equation*}
The set of \textbf{propositional formulas,} say $\PF$, is the
smallest set that includes $\PV$ and is closed under the operations
\begin{align*}
F&\mapsto\lnot F,& (F,G)&\mapsto (F\land G).
\end{align*}
This just means $\PF$ satisfies induction (with respect to $\PV$ and
these operations).
\end{parag}

\begin{parag}
More is true:
Functions can be defined recursively on $\PF$,
because there is \emph{only one way} to construct a given formula.
For example, suppose $h\colon\PV\to\F_2$ (where $\F_2$ is a
two-element field).  Then $h$ extends uniquely to a function $H$ on
$\PF$ such that 
\begin{align*}
H(\lnot F)&=1+H(F),&
H(F\land G)&=H(F)\cdot H(G).
\end{align*}
A propositional formula $F$ is a \textbf{tautology} if $H(F)=1$ for
all choices of $h$.  
\end{parag}

\begin{parag}
In practice, one uses abbreviations in formulas, as  
\begin{gather*}
(F\lor G)\text{ for }\lnot(\lnot F\land\lnot G),\\
(F\lto G)\text{ for }\lnot F\lor G,\\
(F\liff G)\text{ for }((F\lto G)\land(G\lto F)).
\end{gather*}
\end{parag}

\begin{parag}
Let us now develop first-order logic in a
signature $\sig L$.  For simplicity, we assume $\sig L$ is the signature
of a one-sorted structure; for definiteness, we assume 
\begin{equation*}
\sig L=\{0,-,+,\parallel\}.  
\end{equation*}
Fix a set $X$ of \textbf{individual variables.}  Let $C$ be a set of
\textbf{parameters}---individuals from some $\sig L$-structure $\str
V$.  The set of \textbf{terms} over $C$ is the smallest set
that includes $X$ and is closed under  
\begin{align*}
&c,&
&0,& t&\mapsto-t,&(t,u)&\mapsto(t+u),
\end{align*}
where $c$ ranges over $C$.  Call this set
\begin{equation*}
   \Tm C;
\end{equation*}
by definition, it satisfies induction with respect to $X$ and
the given operations.  
\end{parag}

\begin{parag}
Also, functions can be defined recursively on $\Tm
C$, because there is \emph{only one way} to construct a given term.
For example, if $v\colon X\to V$, then there is a unique function
$\tilde v$ from $\Tm C$ into $V$ that extends $v$ and
satisfies 
\begin{align*}
\tilde v(c)&=c,&
\tilde v(0)&=0,& \tilde v(-t)&=-\tilde v(t),&\tilde v(t+u)&=\tilde
v(t)+\tilde v(u). 
\end{align*}
Here, for example, $t+u$ is a string of symbols; but $\tilde
v(t)+\tilde v(u)$ is the image of $(\tilde v(t),\tilde v(u))$ under
the operation of $+$ on $\str V$.
\end{parag}

\begin{parag}
We now define simultaneously the set $\Fm C$ of \textbf{formulas} over
$C$ and the function assigning to each formula $\phi$ its set
$FV(\phi)$ of \textbf{free variables.} 
\begin{enumerate}
	\item 
	If $t,u\in\Tm C$, then the strings
	\begin{align*}
	t&=u,&t&\parallel u
	\end{align*}
	 are in $\Fm C$, and 
both $FV(t=u)$ and $FV(t\parallel u)$ consist of the variables actually appearing in $t$ or $u$.
\item
$\Fm C$ is closed under $\phi\mapsto\lnot\phi$, and 
\begin{equation*}
FV(\lnot\phi)=FV(\phi).
\end{equation*}
\item
If $\phi$ is in $\Fm C$, and $x\in FV(\phi)$, then $\Exists x\phi$ is in $\Fm C$, and
\begin{equation*}
FV(\Exists x\phi)=FV(\phi)\setminus\{x\}.
\end{equation*}
\item
If $\phi$ and $\psi$ are in $\Fm C$, and no variable occurring \emph{non-freely} in one of them occurs (freely or non-freely) in the other, then $(\phi\land\psi)$ is in $\Fm C$, and \begin{equation*}
FV(\phi\land\psi)=FV(\phi)\cup FV(\psi).
\end{equation*}
\end{enumerate}
Then $\Fm C$ satisfies a kind of induction.  Moreover functions can be
defined recursively on $\Fm C$.  Indeed, if $v\colon X\to V$ as above,
and $\phi$ is a formula, let $\phi[v]$ be the result of replacing each
instance of each \emph{free} variable $x$ in $\phi$ with $v(x)$. 
Then $\phi[v]$ is \textbf{true} in $\str V$, and we write
\begin{equation*}
\str V\models\phi[v],
\end{equation*}
according to the following recursive definition.
\begin{enumerate}
	\item 
	$\str V\models(t=u)[v]$ if and only if
	\begin{equation*}
	\tilde v(t)=\tilde v(u).
	\end{equation*}
	\item 
	$\str V\models(t\parallel u)[v]$ if and only if
	\begin{equation*}
	\tilde v(t)\parallel\tilde v(u)
	\end{equation*}
	\item
	$\str V\models\lnot\phi[v]$ if and only if
	\begin{equation*}
\str V\not\models\phi[v].
\end{equation*}
	\item
		$\str V\models\Exists x\phi[v]$ if and only if
		\begin{equation*}
			\str V\models\phi[v']
			\end{equation*}
			for some $v'$ that agrees with $v$ on $FV(\Exists x\phi)$. 
\end{enumerate}
A formula $\sigma$ is a \textbf{sentence} if $FV(\sigma)=\emptyset$.  In this case, $\sigma[v]$ is just $\sigma$.
If $\sigma$ is true in all $\sig L$-structures that include $C$, then $\sigma$ is \textbf{logically valid,} and we may write simply
\begin{equation*}
\models\sigma.
\end{equation*}
\end{parag}

\begin{parag}
If we use
sentences as propositional variables, then a propositional formula is
also a sentence: if the propositional formula is a tautology, then we
may refer also to the sentence as a \textbf{tautology.}  If
$FV(\phi)=\{x\}$, and $c\in C$, then $\phi(c)$ is the result of
replacing each instance of $x$ in $\phi$ with $c$.  Now we define a
sentence to be a \textbf{logical axiom} if it is: 
\begin{enumerate}
	\item 
a tautology;
	\item
a sentence of one of the forms
	\begin{gather*}
	t=t,\\(t=u \lto u=t),\\((t=u\land u=s) \lto t=s),\\(c=d
        \lto(\phi(c)\lto \phi(d))); 
	\end{gather*}
	\item
	a sentence
	\begin{equation*}
	(\sigma\lto\sigma'), 
	\end{equation*}
	where $\sigma$ and $\sigma'$ are sentences, and we get
        $\sigma'$ from $\sigma$ by replacing each occurrence of $x$
        with $y$; 
	\item
a sentence
\begin{equation*}
(\phi(c)\lto\Exists x\phi(x));
\end{equation*}
\item
a sentence
\begin{equation*}
((\sigma\lto\lnot\phi(c))\lto(\sigma\lto \lnot\Exists x\phi(x))),
\end{equation*}
where $c$ does not occur in $\sigma$.
\end{enumerate}
The set of \textbf{theorems} is the smallest set that contains the
logical axioms and that contains $\tau$ if it contains $\sigma$ and
$(\sigma\lto\tau)$. 
\end{parag}

\begin{parag}
If $\sigma$ is a theorem, we may write
\begin{equation*}
\proves\sigma.
\end{equation*}
Every theorem is valid:
if $\proves\sigma$, then $\models\sigma$.  The converse is \textbf{G\"odel's Completeness Theorem:}

\begin{theorem}[G\"odel, 1930]
If $\models\sigma$, then $\proves\sigma$.
\end{theorem}

A sentence $\sigma$ is \textbf{provable} from a collection $S$
of sentences, and we may write
\begin{equation*}
S\proves \sigma,
\end{equation*}
 if some sentence
\begin{equation*}
\tau_0\land\cdots\land\tau_{n-1}\lto \sigma
\end{equation*}
is a theorem, where $\tau_0$, \dots, $\tau_{n-1}$ are in $S$.

\begin{theorem}[Malcev, 1936]
If $S\models\sigma$, then $S\proves\sigma$.
\end{theorem}

\begin{corollary}[Compactness Theorem]
If every finite subset of $S$ has a model, then $S$ has a model.
\end{corollary}
  
\begin{proof}
If $S$ has no model, then 
\begin{align*}
S&\models0\neq0,&S&\proves0\neq0,&S_0&\proves0\neq0
\end{align*}
for some \emph{finite} subset $S_0$ of $S$; but then $S_0$ has no model.
\end{proof}

Compactness \emph{fails} in second-order logic:  The Dedekind--Peano Axioms, together with
\begin{equation*}
\{c\neq1,c\neq S1,c\neq SS1,c\neq SSS1,\dots\},
\end{equation*}
have no model, although every finite subset does.
\end{parag}

\section{Model theory of fields}

\begin{parag}
Henceforth the logic is first-order.  
If $\str A$ is a structure (of one sort, for simplicity,) in a
signature $\sig L$, and $\phi\in\Fm A$ with free variables from the
list $(x_1,\dots,x_n)$, and $(c_1,\dots,c_n)\in A^n$, then the result
of replacing each free variable $x_k$ in $\phi$ with $c_k$ is denoted
by 
\begin{equation*}
\phi(c_1,\dots,c_n).
\end{equation*}
Then $\phi$ \textbf{defines} in $\str A$ the $n$-ary relation
\begin{equation*}
\{(c_1,\dots,c_n)\in A^n\colon\str A\models\phi(c_1,\dots,c_n)\},
\end{equation*}
which can be denoted by
\begin{equation*}
\phi^{\str A}.
\end{equation*}
A definable \emph{set} is a singulary definable relation.  If $FV(\psi)=\{x_1,\dots,x_n,y\}$, then
\begin{equation*}
(\Exists y\psi)^{\str A}=\pi(\psi^{\str A}),
\end{equation*}
where $\pi$ is the \textbf{projection} given by
\begin{equation*}
\pi(c_1,\dots,c_n,d)=(c_1,\dots,c_n).
\end{equation*}
See Figure~\ref{fig:proj}.
\begin{figure}
  \begin{pspicture}(-0.5,-0.5)(5,4.5)
    \pscircle(2.5,2.5){1.5}
\psline{->}(0,0)(5,0)
\psline{->}(0,0)(0,4)
\uput[dr](5,0){$A^n$}
\uput[ul](0,4){$A$}
\psdots(1,0)(4,0)
\psline[linewidth=0.8mm](1,0)(4,0)
\psline[linestyle=dotted](1,0)(1,2.5)
\psline[linestyle=dotted](4,0)(4,2.5)
\rput(2.5,2.5){$\psi^{\str A}$}
\uput[d](2.5,0){$(\Exists y\psi)^{\str A}$}
\psline{->}(5,3.5)(5,1.5)
\uput[r](5,2.5){$\pi$}
  \end{pspicture}
  \caption{}\label{fig:proj}  
\end{figure}
A theory $T$ admits \textbf{quantifier-elimination} (QE) if, for every
model $\str A$ of $T$, the collection of relations definable by
\emph{quantifier-free} formulas is closed under projection.  Having a
theory with QE is a further measure of tameness.
\end{parag}

\begin{parag}
Let $\ACF$ be the theory of \textbf{algebraically closed fields:}
field theory, together with, for each $n$ in $\N$, 
\begin{equation}\label{eqn:acf}
\Forall{t_1}\cdots\Forall{t_n}\Exists xx^n+t_1x^{n-1}+\dotsb+t_{n-1}x+t_n=0.
\end{equation}
Let $\ACF_0$ be the theory of algebraically closed fields of characteristic $0$, namely $\ACF$ together with, for each prime $p$,
\begin{equation*}
\underbrace{1+\dotsb+1}_p\neq0.
\end{equation*}
Let $\RCF$ be the theory of \textbf{real-closed ordered fields:} the
theory of ordered fields, together with~\eqref{eqn:acf} for each
\emph{odd} $n$ in $\N$, and also
\begin{equation*}
\Forall y\Exists x(y>0\lto y=x^2).
\end{equation*}

\begin{theorem}[Tarski\footnote{According to Hodges
      \cite[p.~85]{MR94e:03002}, Tarski announced these results
  in 1949, publishing the proof the result on $\RCF$ in \cite{MR0044472}.}]
$\ACF$ and $\RCF$ admit QE.
In particular, the definable sets:
\begin{enumerate}
	\item 
	in an algebraically closed field, are the finite and co-finite
        sets; 
	\item
	in a real-closed field, are the finite unions of intervals and
        singletons. 
\end{enumerate}
\end{theorem}
\end{parag}

\begin{parag}

A structure $\str A$ has a \textbf{diagram,} denoted by
\begin{equation*}
  \diag{\str A};
\end{equation*}
this is the set of
quantifier-free sentences with parameters from $A$ that are true in
$\str A$.

\begin{theorem}
  For a theory $T$, the following are equivalent:
  \begin{enumerate}
  \item 
$T$ admits QE;
\item
whenever $\str A\included\str M$ for some model $\str M$ of $T$, and
$\str A$ is finitely generated, the theory
\begin{equation*}
  T\cup\diag{\str A}
\end{equation*}
is complete.
  \end{enumerate}
\end{theorem}
\end{parag}

\begin{parag}
By considering prime fields, we can now conclude:

\begin{theorem}
\mbox{}
\begin{enumerate}
\item
$\Th{\C,+,\cdot}$ is axiomatized by $\ACF_0$.
\item
$\Th{\R,+,\cdot,<}$ is axiomatized by $\RCF$.
\end{enumerate}
\end{theorem}
\end{parag}

\begin{parag}
If $T\cup\diag{\str M}$ is complete whenever $\str M\models T$, then
$T$ is called \textbf{model complete.}\footnote{The definition is due
  to Abraham Robinson.}  So $\ACF$ and $\RCF$ and all
other theories with QE are
model complete.
\end{parag}

\begin{parag}
A theory $T^*$ is a \textbf{model companion} of a theory $T$ (in the
same signature if
\begin{enumerate}
\item 
a model of one embeds in a
  model of the other, that is,
  \begin{equation*}
    T_{\forall}=T^*{}_{\forall};
  \end{equation*}
\item
$T^*$ is model complete.
\end{enumerate}
So $\ACF$ and $\RCF$ are
model companions of the theories of fields and ordered fields,
respectively. 
\end{parag}

\begin{parag}
model companions are useful for the following reason.
Suppose $T^*$ is a model companion of $T$, and
\begin{align*}
  \str M&\models T^*,&\str N&\models T,&\str M&\included\str N.
\end{align*}
Say $\phi$ is quantifier-free, with parameters from $M$, and
\begin{equation*}
  \str N\models\Exists{\vec x}\phi.
\end{equation*}
Then 
\begin{equation*}
  \str M\models\Exists{\vec x}\phi.
\end{equation*}
Indeed, we have $\str N\included\str M'$ for some model $\str M'$ of
$T^*$.
Then $\str M'\models\Exists{\vec x}\phi$, so 
\begin{equation*}
T^*\cup\diag{\str
  M}\models\Exists{\vec x}\phi.
\end{equation*}
\end{parag}

\section{Model theory of vector spaces}

\begin{parag}
Let $\VS_K$ be the theory of vector spaces \emph{over the field}
$\str K$,  in the signature 
\begin{equation*}
\{0,-,+\}\cup\{a*\colon a\in K\}.
\end{equation*}
This theory admits QE.
\end{parag}

\begin{parag}
Let $\VS$ be the theory of vector spaces
over an arbitrary field, in the signature
\begin{equation*}
\{\vec0,\vec-,\vec+,0,-,+,*\}.  
\end{equation*}
This has a model companion, namely the theory of
\emph{one-dimensional} vector spaces over an \emph{algebraically closed} field.
In particular, every space embeds in a one-dimensional space.
\end{parag}

\begin{parag}
Let $\VS^2$ be the theory of vector-spaces of dimension at least $2$:
\begin{equation*}
\VS^2=\VS\cup\{\Exists{\vec u}\Exists{\vec v}\Forall x\Forall y
(x*\vec u+y*\vec v=0\lto x=0\land y=0)\}.
\end{equation*}
This has the same model companion as $\VS$, but
is not \emph{included} in a model complete theory, because the union of a
\textbf{chain} of models of $\VS^2$ need not be a model. 
For example, let 
\begin{align*}
K_n&=\Q(\mpi^{1/2^n}),&L=\bigcup_{n\in\N}K_n&=\Q(\pi,\pi^{1/2},\pi^{1/4},\dots).
\end{align*}
Then $(K_{n+1},K_n)\models\VS_2$, and
\begin{equation*}
(K_{n+1},K_n)\included(K_{n+2},K_{n+1}),
\end{equation*}
but
\begin{equation*}
\bigcup_{n\in\N}(K_{n+1},K_n)=(L,L),
\end{equation*}
a model of $\VS$, but not $\VS^2$.
\end{parag}

\begin{parag}
As before, let $\VS_2$ be the theory of vector spaces of dimension at
least $2$ in the signature 
\begin{equation*}
\{\vec0,\vec-,\vec+,\parallel\}.
\end{equation*}
This has a model companion, namely the theory of $2$-dimensional
vector spaces over an algebraically closed field.   
\end{parag}

\begin{parag}
More generally, if $n\in\N$, let $\VS_n$ be the theory of vector spaces of dimension at least $n$ in the signature
\begin{equation*}
\{\vec0,\vec-,\vec+,\parallel^n\},
\end{equation*}
where $\parallel^n$ stands for the $n$-ary relation of linear dependence.  (If we include the signature of the scalar field, then the space can have any dimension.)
This has a model companion, namely the theory of $n$-dimensional
vector spaces over an algebraically closed field.  
For, if again $K\included L$, and $(a_1,\dots,a_n,1)$, that is, $(\vec a,1)$, is an $(n+1)$-tuple from $L$ that is linearly independent over $K$, then $(K^{n+1},\parallel^n_K)$ embeds in $(L^n,\parallel_L^n)$ under
\begin{equation*}
\vec x\mapsto\vec x\cdot
\left(\begin{array}{c}
I_n\\\hline-\vec a
\end{array}\right).
\end{equation*}
\end{parag}

\begin{parag}
There is an analogy with fields.  Let
\begin{equation*}
  M=K(a_0,\dots,a_n),
\end{equation*}
where $(a_0,\dots,a_n)$ is algebraically independent over $K$.  Then
there is a field $L$ such that $K\included L$, and
\begin{equation*}
  \trdeg{ML/L}=n,
\end{equation*}
but if $(b_1,\dots,b_n)$ from $M$ is algebraically independent over
$K$, then it remains so over $L$.  Indeed, we can take
\begin{equation*}
  L=K(x,y),
\end{equation*}
where $x$ is transcendental over $M$, but
\begin{equation*}
  y=\sum_{k=0}^na_kx^k.
\end{equation*}
\end{parag}

%\bibliographystyle{amsplain}
%\bibliography{../../../TeX/references}

\def\cprime{$'$}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{MR0159773}
Richard Dedekind, \emph{Essays on the theory of numbers. {I}: {C}ontinuity and
  irrational numbers. {II}: {T}he nature and meaning of numbers}, authorized
  translation by Wooster Woodruff Beman, Dover Publications Inc., New York,
  1963. \MR{MR0159773 (28 \#2989)}

\bibitem{Descartes-Geometry}
Descartes, \emph{The geometry of {R}en{\'e} {D}escartes}, Dover Publications,
  Inc., New York, 1954, Translated from the French and Latin by David Eugene
  Smith and Marcia L. Latham, with a facsimile of the first edition of 1637.

\bibitem{MR0001234}
John Dyer-Bennet, \emph{A theorem on partitions of the set of positive
  integers}, Amer. Math. Monthly \textbf{47} (1940), 152--154. \MR{MR0001234
  (1,201b)}

\bibitem{MR1932864}
Euclid, \emph{Euclid's {E}lements}, Green Lion Press, Santa Fe, NM, 2002, All
  thirteen books complete in one volume, the Thomas L. Heath translation,
  edited by Dana Densmore. \MR{MR1932864 (2003j:01044)}

\bibitem{Goedel-incompl}
Kurt G{\"o}del, \emph{On formally undecidable propositions of
  {\emph{{p}rincipia mathematica}} and related systems {I} (1931)}, From Frege
  to G{\"o}del (Jean van Heijenoort, ed.), Harvard University Press, 1976,
  pp.~596--616.

\bibitem{MR94e:03002}
Wilfrid Hodges, \emph{Model theory}, Encyclopedia of Mathematics and its
  Applications, vol.~42, Cambridge University Press, Cambridge, 1993.
  \MR{94e:03002}

\bibitem{Katz}
Victor~J. Katz (ed.), \emph{The mathematics of {E}gypt, {M}esopotamia, {C}hina,
  {I}ndia, and {I}slam: A sourcebook}, Princeton University Press, Princeton
  and Oxford, 2007.

\bibitem{MR12:397m}
Edmund Landau, \emph{Foundations of analysis. {T}he arithmetic of whole,
  rational, irrational and complex numbers}, third ed., Chelsea Publishing
  Company, New York, N.Y., 1966, translated by F. Steinhardt; first edition
  1951; first German publication, 1929. \MR{12,397m}

\bibitem{Peano}
Giuseppe Peano, \emph{The principles of arithmetic, presented by a new method
  (1889)}, From {F}rege to {G}{\"o}del (Jean van Heijenoort, ed.), Harvard
  University Press, 1976, pp.~83--97.

\bibitem{MR2505433}
David Pierce, \emph{Model-theory of vector-spaces over unspecified fields},
  Arch. Math. Logic \textbf{48} (2009), no.~5, 421--436. \MR{MR2505433}

\bibitem{MR0044472}
Alfred Tarski, \emph{A decision method for elementary algebra and geometry},
  University of California Press, Berkeley and Los Angeles, Calif., 1951, 2nd
  ed. \MR{MR0044472 (13,423a)}

\end{thebibliography}


\end{document}