\documentclass[%
version=last,%
a5paper,
10pt,%
%headings=small,%
bibliography=totoc,%
twoside,%
reqno,%
cleardoublepage=empty,%
parskip=half,%
draft=true,%
DIV=classic,%
%DIV=12,%
headinclude=false,%
%titlepage=true,%
abstract=true,%
pagesize]
{scrartcl}
\usepackage{hfoldsty,url}
\usepackage[neverdecrease]{paralist}

\usepackage{amsmath,amssymb}

\newcommand{\F}{\mathbb F}
\newcommand{\Q}{\mathbb Q}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\ecmodel}{\models_{\mathrm{ec}}}
\newcommand{\thy}[1]{\mathrm{#1}}
\newcommand{\ACF}{\thy{ACF}}	
\newcommand{\ACFA}{\thy{ACFA}}	
\newcommand{\mDF}{\text{$m$-$\thy{DF}$}} % fields with m derivations
\newcommand{\mpDF}{\text{$(m+1)$-$\thy{DF}$}}  % fields with m+1 derivations
\newcommand{\oneDF}{\text{$1$-$\thy{DF}$}} % fields with one derivation
\newcommand{\oDF}{\text{$\upomega$-$\thy{DF}$}}  % fields with omega-many derivations
%\newcommand{\mDPF}{\text{$m$-$\thy{DPF}$}} % diff. perf. fields with m derivations
\newcommand{\DCF}{\thy{DCF}}           % differentially closed fields
\newcommand{\mDCF}{\text{$m$-$\thy{DCF}$}}  % differentially closed fields
				% with m derivations
\newcommand{\oDCF}{\text{$\upomega$-$\thy{DCF}$}}  % differentially closed fields
				% with omega-many derivations
\newcommand{\mpDCF}{\text{$(m+1)$-$\thy{DCF}$}}  % differentially closed fields
				% with m+1 derivations
\newcommand{\oneDCF}{\text{$1$-$\thy{DCF}$}}  % differentially closed fields
				% with one derivations

\newcommand{\VSp}[1]{\operatorname{VS}_{#1}} % vector-spaces with an
				% n-ary predicate for linear dependence
\newcommand{\VSpst}[1]{{\VSp{#1}}\!^*}      % model-companion for these

\newcommand{\DP}{\thy{DP}}

\newcommand{\LT}[1]{\operatorname{LT}(#1)}
\newcommand{\St}[1]{\operatorname S(#1)}

\newcommand{\size}[1]{\lvert#1\rvert}
\newcommand{\ts}[1]{\operatorname S(#1)}
\newcommand{\Forall}[1]{\forall{#1}\;}
\newcommand{\Exists}[1]{\exists{#1}\;}
\newcommand{\lto}{\Rightarrow}
\newcommand{\liff}{\Leftrightarrow}
\newcommand{\ec}{e.c.}
\newcommand{\lspan}[2]{\operatorname{span}_{#1}(#2)}

\usepackage{upgreek}
\usepackage{mathrsfs}
\newcommand{\sig}{\mathscr S}

\newcommand{\str}[1]{\mathfrak{#1}}
\newcommand{\diag}[1]{\operatorname{diag}(#1)}

\newcommand{\included}{\subseteq}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\theequation}{\fnsymbol{equation}}
\renewcommand{\phi}{\varphi}

\usepackage{bm}
\renewcommand{\vec}[1]{\bm{#1}}

\usepackage{amsthm}
\newtheorem*{theorem}{Theorem}

\begin{document}
\title{Chains of structures\\ and of theories}
\author{David Pierce}
\date{March 20, 2013}
\publishers{Mathematics Department\\
Mimar Sinan Fine Arts University\\
Istanbul\\
\url{dpierce@msgsu.edu.tr}\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}
\maketitle

These are my notes for a 50-minute talk at
Sabanc\i\ University on the date above.  I did not discuss the theorem
of \L o\'s and Tarski on page \pageref{LT}, or the proof of my theorem on
page \pageref{P2009}, or the details of \S\ref{5}.  (Today's date is \today.)

\begin{abstract}
  The union of a chain of fields is a field. The union of a chain of
  vector-spaces with their scalar-fields is still a vector-space, but
  it may have strictly lower dimension than the spaces in the chain. A
  model-theoretic result of the 1950s called the Chang--Los-Suszko
  Theorem relates these observations to the logical form of the
  theories of the structures in the chains. 

Instead of looking at chains of models of a fixed theory, one may
fruitfully look at chains of theories themselves. Such a chain might
consist of the theories of fields equipped with finite numbers of
commuting derivations; or of the theories of vector-spaces with
predicates for linear dependence of finite numbers of vectors. I shall
discuss some results concerning these and other examples. 
\end{abstract}

\tableofcontents

\section{Chains of structures}

Given a chain 
\begin{equation*}
K_0\included K_1\included K_2\included\dots
\end{equation*}
of fields, we know that the union
\begin{equation*}
\bigcup_{n\in\upomega}K_n
\end{equation*}
is also a field.  Likewise for ordered fields, or groups, or vector spaces (given with their scalar fields).

However, in the last case, \emph{dimension} need not be preserved in the union.  Indeed, suppose a field-extension $L/K$ has transcendence-basis $(a_1,a_2,a_3,\dots)$.  Fixing $n$ in $\upomega$, we let
\begin{align*}
K_0&=K,&
K_1&=K(a_1),&
K_2&=K(a_1,a_2),
\end{align*}
and in general, for each $j$ in $\upomega$,
\begin{equation*}
K_j=K(a_1,\dots,a_j);
\end{equation*}
we also let
\begin{gather*}
V_0=\lspan K{1,a_1,\dots,a_n},\\
	V_1=\lspan{K_1}{1,a_1,\dots,a_{n+1}}=\lspan{K_1}{1,a_2,\dots,a_{n+1}},
\end{gather*}
and in general, for each $j$ in $\upomega$,
\begin{equation*}
V_j=\lspan{K_j}{1,a_1,\dots,a_{n+j}}=\lspan{K_j}{1,a_{j+1},\dots,a_{n+j}}
\end{equation*}
Then $V_j$ is a vector-space over $K_j$, and
\begin{gather*}
	\dim_{K_j}(V_j)=n+1,\\
	(V_0,K_0)\included(V_1,K_1)\included(V_2,K_2)\included\dotsb,\\
	L=\bigcup_{j\in\upomega}K_j,\\
	\dim_L\Biggl(\bigcup_{j\in\upomega}V_j\Biggr)=1.
\end{gather*}

\section{Logic of chains of structures}

A \textbf{field} is just a \textbf{model} of the \textbf{theory} of fields in the \textbf{signature}
\begin{equation*}
\{0,1,-,+,{}\cdot{}\}.
\end{equation*}
All but one of the \textbf{axioms} of this theory are \textbf{universal,} for example
\begin{equation*}
\Forall{(x,y,z)}x(yz)=(xy)z.
\end{equation*}
The remaining axiom is \textbf{universal-existential,} or $\forall\exists$:
\begin{equation*}
\Forall x\Exists y(x=0\lor xy=1).
\end{equation*}
The axioms for vector-spaces are no more complex; but the axiom requiring dimension at least $2$ \emph{is} more complex, or at least differently complex; it is $\exists\forall$:
\begin{equation*}
\Exists{(\vec u,\vec v)}\Forall{(x,y)}(\vec u\cdot x+\vec v\cdot y=\bm0\lto x=0\land y=0).
\end{equation*}
This is why dimension need not be preserved in unions:

\begin{theorem}[Chang {[1959]}, \L o\'s \&\ Suszko {[1957]}]
Unions of chains of models of a theory are always models too, if and only if the theory can be axiomatized by $\forall\exists$ sentences.
\end{theorem}

But consider fields now in the signature
\begin{equation*}
\{0,-,+,{}\cdot{}\},
\end{equation*}
without a symbol for $1$.  An embedding of \emph{rings} in this signature need not preserve $1$.  For example, the field $\Q$ embeds in the product ring $\Q\times\Q$ under $x\mapsto(x,0)$; but $(1,0)$ is not the $1$ of $\Q\times\Q$ (it is $(1,1)$).

However, an embedding of rings that happen to be fields must preserve $1$.  Therefore, in the signature $\{0,-,+,{}\cdot{}\}$, the union of a chain of fields is still a field.  Now, the axiom saying that there \emph{is} a $1$ would seem to take the form
\begin{equation*}
\Exists x\Forall y(xy=y).
\end{equation*}
However, this complexity is not required, because of the Chang--\L o\'s-Suszko Theorem.  The axioms for integral domains are universal, the most complex being
\begin{equation*}
\Forall{(x,y)}(xy=0\lto x=0\lor y=0).
\end{equation*}
Replacing the axiom $\Forall x1\cdot x=x$ with the $\forall\exists$ sentence
\begin{equation*}
\Forall{(x,y)}\Exists zxzy=y
\end{equation*}
results in axioms for the theory of fields.

By the way, another \textbf{preservation theorem} is:

\begin{theorem}[\L o\'s {[1955]}, Tarski {[1954]}]\label{LT}
Substructures of models of a theory are always models too, if and only if the theory can be axiomatized by universal sentences.
\end{theorem}

So fields cannot be given universal axioms in the usual signature $\{0,1,-,+,{}\cdot{}\}$, since the substructures of fields (in this signature) are just the integral domains, and not every integral domain is a field.  For example,
\begin{equation*}
(\Z,0,1,-,+,{}\cdot{})\included(\Q,0,1,-,+,{}\cdot{}).
\end{equation*}
Similarly in the signature $\{1,{}\cdot{}\}$, groups cannot be given universal axioms, since for example
\begin{equation*}
(\N,1,{}\cdot{})\included(\Z,1,{}\cdot{}),
\end{equation*}
and the former is not a group.

\section{Chains of theories of vector-spaces}

Also by the Chang--\L o\'s-Suszko Theorem, the axioms for vector-spaces of dimension at least two \emph{cannot} be simplified---unless we enlarge the signature, as by including the \textbf{predicate} $\parallel$ for parallelism.  This will be defined by the axiom
\begin{equation*}
\Forall{(\vec u,\vec v)}\Bigl(\vec u\parallel\vec v\liff\Exists{(x,y)}\bigl(\vec u\cdot x+\vec v\cdot v=\bm0\land\lnot(x=0\land y=0)\bigr)\Bigr),
\end{equation*}
which has the form
\begin{equation*}
\Forall{\vec x}(\phi\liff\Exists{\vec y}\theta),
\end{equation*}
which is equivalent to the $\forall\exists$ sentences
\begin{align*}
\Forall{\vec x}\Exists{\vec y}(\phi&\lto\theta),&
\Forall{(\vec x,\vec y)}(\theta\lto\phi).
\end{align*}
Then having dimension at least $2$ is given by the $\forall\exists$ axiom
  \begin{equation*}
	\Exists{(\vec u,\vec v)}\vec u\parallel\vec v.
\end{equation*}
In the larger signature, every vector-space embeds in a space of dimension exactly $2$.  Indeed, given $L/K$ with $[L:K]\geq3$, we may suppose $(1,a,b)$ in $L^3$ is linearly independent over $K$.  Then the vector-space $(K^3,K)$ embeds in $(L^2,L)$ under
\begin{equation*}
(t,x,y)\mapsto(x-at,y-bt).
\end{equation*}
Every embedding of vector-spaces preserves parallelism.  The present embedding preserves \emph{non}-parallelism: this is a special case of:

\begin{theorem}[P. {[2009]}]\label{P2009}
If $K\included L$, and $(1,a_1,\dots,a_n)$ from $L^{n+1}$ is linearly independent over $K$, then the embedding
\begin{equation*}
(t,x_1,\dots,x_n)\mapsto(x_1-a_1t,\dots,x_n-a_nt)
\end{equation*}
of $(K^{n+1},K)$ in $(L^n,L)$
preserves $n$-ary linear independence.
\end{theorem}

\begin{proof}
Consider $(a_1,\dots,a_n)$ as a row-vector $\vec a$.  Then we can write the given embedding as
\begin{equation*}
(\begin{array}{c|c}
t&\vec x
\end{array})
\mapsto\vec x-t\cdot\vec a,
\end{equation*}
or---if the $n\times n$ identity matrix is $I_n$---as
\begin{equation*}
(\begin{array}{c|c}
t&\vec x
\end{array})
\mapsto
(\begin{array}{c|c}
t&\vec x
\end{array})
\cdot
\left(
\begin{array}{c}
-\vec a\\\hline
I_n
\end{array}
\right).
\end{equation*}
This embedding takes the rows of an $n\times(n+1)$ matrix 
$(\begin{array}{c|c}\vec t&X\end{array})$ over $K$ to the rows of the $n\times n$ matrix
\begin{equation*}
X-\vec t\cdot\vec a.
\end{equation*}
Moreover
\begin{align*}
\det(X-\vec t\cdot\vec a)
&=\det\left(\begin{array}{c|c}1&\vec 0\\\hline\vec t&X-\vec t\cdot\vec a\end{array}\right)\\
&=\det\left(
\left(\begin{array}{c|c}1&\vec a\\\hline\vec t&X\end{array}\right)
\left(\begin{array}{c|c}1&-\vec a\\\hline\vec 0&I_n\end{array}\right)
\right)\\
&=\det\left(\begin{array}{c|c}1&\vec a\\\hline\vec t&X\end{array}\right),
\end{align*}
so that
\begin{align*}
\det(X-\vec t\cdot\vec a)\neq0
&\iff\det\left(\begin{array}{c|c}1&\vec a\\\hline\vec t&X\end{array}\right)\neq0\\
&\implies\operatorname{rank}(\begin{array}{c|c}\vec t&X\end{array})=n;
\end{align*}
the converse holds too since the entries in $X$ and $\vec t$ are from $K$.
\end{proof}
Now, if $1\leq n<\upomega$, let
\begin{compactitem}
\item $\VSp n$ be the theory of vector-spaces with predicates for $k$-ary linear dependence when $2\leq k\leq n$;
\item 
$\VSpst n$ be axiomatized by $\VSp n$, along with
\begin{compactitem}
\item
the space is $n$-dimensional,
\item
the scalar-field is algebraically closed.
\end{compactitem}
\end{compactitem}
In addition, let
\begin{compactitem}
\item
$\VSp{\upomega}=\bigcup_{1\leq n<\upomega}\VSp n$,
\item
$\VSpst{\upomega}$ be axiomatized by $\VSp{\upomega}$, along with
\begin{compactitem}
\item
the space is infinite-dimensional,
\item
the scalar-field is algebraically closed.
\end{compactitem}
\end{compactitem}

Note then
\begin{equation*}
\VSpst{\upomega}\neq\bigcup_{1\leq n<\upomega}\VSpst n
\end{equation*}
(the latter is inconsistent).  However:

\begin{theorem}[P. {[2009]}]
If $1\leq n\leq\upomega$,
the models of $\VSpst n$ are precisely the \textbf{existentially closed} models of $\VSp n$.
\end{theorem}

The existentially closed models of a theory $T$ are just those models $\str M$ such that every quantifier-free formula over $\str M$ soluble in some extension (which is also a model of $T$) is already soluble in $\str M$ itself.

The existentially closed fields are the algebraically closed fields.

By the next-to-last theorem, for every model of $\VSp n$, every equation
\begin{equation*}
\vec a_0\cdot x_0+\dots+\vec a_n\cdot x_n=0
\end{equation*}
over the model (\emph{i.e.}\ with the $\vec a_i$ belonging to the model) has a solution in some extension.

In general, if $T$ and $T^*$ are two theories, in the same signature, such that
\begin{compactenum}[1)]
\item
$T$ has $\forall\exists$ axioms,
\item
the models of $T^*$ are precisely the existentially closed models of $T$,
\end{compactenum}
then $T^*$ is the \textbf{model-companion} of $T$.

So each $\VSpst n$ is the model-companion of $\VSp n$ (if $1\leq
n\leq\upomega$), and $\ACF$ is the model-companion of the theory of fields.

\section{Chains of theories of differential fields}

But model-companions need not exist.  For example, let $\mDF$ be the theory of fields equipped with $m$ commuting \textbf{derivations} $\partial_0$, \dots, $\partial_{m-1}$, so that
\begin{gather*}
\partial_i(x+y)=\partial_ix+\partial_iy,\\
\partial_i(xy)=x\cdot\partial_iy+y\cdot\partial_ix,	
\end{gather*}
and let
\begin{equation*}
\oDF=\bigcup_{m\in\upomega}\mDF.
\end{equation*}
If we require also that the fields have characteristic $0$, the theories become $\mDF_0$ and $\oDF_0$.

\begin{theorem}[A. Robinson {[1959]}]
The theory $\oneDF_0$ has a model-companion, $\oneDCF_0$, the theory of \textbf{differentially closed fields} of characteristic $0$.
\end{theorem}

\begin{theorem}[McGrail {[2000]}]
For each $m$ in $\upomega$, the theory
$\mDF_0$ has a model-companion, $\mDCF_0$.
\end{theorem}

\begin{theorem}[P.\ {[2013?]}]
For each $m$ in $\upomega$, the theory
$\mDF$ has a model-companion, $\mDCF$.
\end{theorem}

\begin{theorem}[Kasal \&\ P.\ {[2013?]}]\mbox{}
\begin{compactenum}
\item
The theory $\oDF$ has no model-companion.
\item
The theory $\oDF_0$ has a model-companion, which is
\begin{equation*}
\bigcup_{m\in\upomega}\mDCF_0.
\end{equation*}
\end{compactenum}
\end{theorem}

\begin{proof}
\begin{asparaenum}
\item
For each $j$ in $\upomega$, the theory $\oDF$ has an existentially closed model such that
\begin{align*}
\F_p(\alpha)&\included K_j,&
\alpha&\notin\F_p{}^{\mathrm{alg}},&
\partial_i\alpha=\begin{cases}
	1,&\text{ if }i=j,\\
	0,&\text{ if }i\neq j.
\end{cases}
\end{align*}
Then $\alpha$ cannot have a $p$th root (since derivatives of $p$th powers are $0$).
In a \textbf{non-principal ultraproduct} of the $K_j$, we have $\partial_i\alpha=0$ for all $i$ in $\upomega$; but $\alpha$ still has no $p$th root; so the ultraproduct is not existentially closed as a model of $\oDF$.
\item
It is enough to show $\mDCF_0\included\mpDCF_0$, so that the theory $\bigcup_{m\in\upomega}\mDCF_0$ is consistent.  This is by a general result noted also by Medvedev (2013?).  If
\begin{align*}
K&\models\mpDF_0,&
K&\included L,&
L&\models\mDF_0,
\end{align*}
it is enough to find $M$ so that
\begin{align*}
M&\models\mpDF_0,&
L&\included M,&
K&\included M.
\end{align*}
This can be done\dots\qedhere
\end{asparaenum}
\end{proof}

\section{Chains of theories}\label{5}

Suppose
\begin{equation*}
  T_0\included T_1\included T_2\included\dotsb,
\end{equation*}
each $T_k$ being a theory with signature $\sig_k$, so that
\begin{equation*}
  \sig_0\included\sig_1\included\sig_2\included\dotsb
\end{equation*}
Medvedev notes
that properties of the $T_k$ that are preserved in
$\bigcup_{k\in\upomega}T_k$ include:
\begin{compactenum}
\item
\textbf{completeness} (containing either $\sigma$ or $\lnot\sigma$,
for all sentences $\sigma$ of the signature)
\item
\textbf{consistency} (having a model),
\item
\textbf{model-completeness} (being one's own model-companion),
\item
\textbf{stability.}
\end{compactenum}
\emph{Not} preserved are
\begin{compactenum}\setcounter{enumi}4
\item
\textbf{companionability} (having a model-companion),
\item
\textbf{$\upomega$-stability,}
\item
\textbf{superstability.}
\end{compactenum}
\begin{asparaenum}
  \item
\emph{Completeness} is preserved, because sentences have finite length, so
that every sentence of
$\bigcup_{k\in\upomega}\sigma_k$ is a sentence of some $\sigma_k$.
\item
That \emph{consistency} is preserved is precisely the Compactness Theorem of
first-order logic.  This fails in second-order logic.  For example,
let $\DP$ (for Dedekind and Peano) be the \emph{second-order} theory of
$(\N,1,+)$. Add a new constant $c$ to the signature, and let $\DP_k$ be
axiomatized by
\begin{equation*}
  \DP\cup\{c\neq1,c\neq1+1,\dots,c\neq\underbrace{1+\dots+1}_k\}.
\end{equation*}
Then $\bigcup_{k\in\upomega}\DP_k$ has no model.
\item
\emph{Model-completeness} is preserved, because (by means of Compactness) it
is equivalent to every formula's being equivalent (\emph{modulo} the
theory in question) to an existential
formula.
\item
\emph{Stability} is a possible property of complete
theories. \emph{In}stability of $T$ is equivalent to the presence of a 
formula $\phi(\vec x,\vec y)$ defining an infinite linear order in
some model of $T$, so that, for all $n$ in $\upomega$, 
\begin{equation*}
T\vdash\Exists{(\vec x_0,\dots,\vec x_n)}\Biggl(\bigwedge_{0\leq i\leq
  j\leq n}\phi(\vec x_i,\vec x_j)\land\bigwedge_{0\leq j<i\leq
  n}\lnot\phi(\vec x_i,\vec x_j)\Biggr). 
\end{equation*}
If $T=\bigcup_{k\in\upomega}T_k$, then these sentences are all in some
$\sig_k$, and then (assuming $T_k$ is complete) $T_k$ will be
instable. 
\item
We have already seen that $\oDF$ is not \emph{companionable,} although
it is the union of the companionable theories $\mDF$.
\item
Fix a complete theory $T$ in a countable signature $\sig$.
For each model $\str M$ of $T$, for each set $A$ of parameters from
$\str M$, we let
\begin{compactitem}
  \item
$\LT A$ be the
Boolean algebra, called a \textbf{Lindenbaum--Tarski algebra,} of
formulas in $\sig$ with parameters from $A$, 
considered \emph{modulo} (equivalence in) $T$;
\item
$\St A$ be the Stone space of $\LT A$ (\emph{i.e.}\ the set of maximal
  ideals, or equivalently of ultrafilters).
\end{compactitem}
If $\kappa$ is an infinite cardinal, and for all $\str M$ and $A$ as above,
\begin{equation*}
  \size A\leq\kappa\implies\size{\St A}\leq\kappa,
\end{equation*}
then $T$ is \textbf{$\kappa$-stable.}  For example, the theory $\ACF$
of algebraically closed fields is $\kappa$-stable for all $\kappa$,
since, if $K\models\ACF$, there is a continuous bijection from $\St K$
to the spectrum of $K[X]$.  

In fact $\upomega$-stability implies $\kappa$-stability for all $\kappa$.

McGrail shows that each $\mDCF_0$ is complete and $\upomega$-stable.
However, for each set $A$ of \emph{differential} constants in a model
of $\oDCF_0$, for each element $\sigma$ of $A^{\upomega}$, the subset
\begin{equation*}
  \{\partial_kx=\sigma(k)\colon k\in\upomega\}
\end{equation*}
of $\LT A$ belongs to a different element of $\St A$, so that the
latter has size $\size A^{\upomega}$.
\item
This shows $\oDCF_0$ is not even \emph{superstable,} that is, not
always $\kappa$-stable when $\kappa\geq2^{\upomega}$, that is,
$\kappa\geq\beth_1$.  For, $\oDCF_0$ is not $\beth_{\upomega}$-stable,
since $\beth_{\upomega}{}^{\upomega}>\beth_{\upomega}$.
\end{asparaenum}
In fact, being stable is equivalent to being $\kappa$-stable for some
$\kappa$. 
\end{document}