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

\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}

\usepackage{amsmath,amssymb,amsthm,upgreek,url}
\newcommand{\str}[1]{\mathfrak{#1}}
\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\Forall}[1]{\forall#1\;}
\newcommand{\myforall}{\textbf{for all}}
\newcommand{\myforsome}{\textbf{for some}}
\newcommand{\myif}{\textbf{if}}
\newcommand{\myand}{\textbf{and}}
\newcommand{\mythen}{\textbf{then}}

\newcommand{\lto}{\to}
\newcommand{\liff}{\leftrightarrow}
\newcommand{\Aut}[1][L/K]{\operatorname{Aut}(#1)}
\newcommand{\Fix}[1][G]{\operatorname{Fix}(#1)}
\newcommand{\N}{\mathbb N}
\newcommand{\included}{\subseteq}

\newcommand{\theory}[1]{\mathsf{#1}}
\newcommand{\dcf}{\theory{DCF}}
\newcommand{\df}{\theory{DF}}
\newcommand{\acf}{\theory{ACF}}
\DeclareMathOperator{\diag}{diag}
\newcommand{\proves}{\vdash}
\renewcommand{\models}{\vDash}

\usepackage{bm}

\renewcommand{\emptyset}{\varnothing}
\renewcommand{\phi}{\varphi}
\renewcommand{\theta}{\vartheta}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\setminus}{\smallsetminus}

\newcommand{\inv}{^{-1}}
\newcommand{\pset}{A} % set being permuted
\newcommand{\agp}{G} % acting group
\newcommand{\aset}{P} % acting set (may not be a group)
\newcommand{\myop}[1]{#1\,}
\newcommand{\FGA}{\theory{FGA}}
\newcommand{\GA}{\theory{GA}}
\newcommand{\Trand}{\text{\textit{\sffamily T}}}
\DeclareMathOperator{\sym}{Sym}
\newcommand{\Sym}[1]{\sym(#1)}
\newcommand{\Sn}[1][n]{\mathrm S_{#1}}
\newcommand{\TP}[1]{\mathrm{TP}_{#1}}
\newcommand{\NSOP}[1]{\mathrm{NSOP}_{#1}}

\newcommand{\vr}{\mathfrak O}
\newcommand{\invr}{\mathord{\in}\,\vr}
\newcommand{\maxi}{\mathfrak M}
\newcommand{\inmaxi}{\mathord{\in}\,\maxi}
\newcommand{\autom}{^{%\textstyle
    \sigma}}
\newcommand{\fav}{\theory{FAV}}
\newcommand{\acfa}{\theory{ACFA}}
\newcommand{\acvf}{\theory{ACVF}}


\newtheorem{theorem}{Theorem}
\newtheorem*{porism}{Porism}

\renewcommand{\theequation}{\fnsymbol{equation}}

\begin{document}
\title{A Method for Companionability,\\
  Applied to Group Actions and Valuations%
  \thanks{Joint work, initiated at the Nesin Mathematics Village,
    with Ay\c se Berkman and with
    \"Ozlem Beyarslan, Daniel Max Hoffmann, and G\"onen\c c Onay.
    This is an edited version of the document submitted to,
    and accepted by, the 11th Panhellenic Logic Symposium}}
\author{David Pierce}
\publishers{Mathematics Department\\
Mimar Sinan Fine Arts University\\
\url{dpierce@msgsu.edu.tr}\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}

\maketitle

\begin{abstract}
  A method for finding model companions
  is applied to the theory of group actions
  and to the theory of fields with both an automorphism and a valuation.
  \end{abstract}

\section{The Method}

For every system of ordinary differential polynomial equations
over a differential field of characteristic $0$,
the consistency of the system---%
its solubility in some possibly larger differential field---%
is a first-order function of the parameters of the system.
Abraham Seidenberg \cite{MR0082487} showed this,
and from it,
Abraham Robinson \cite[\S5.5]{MR0153570}
derived
the theory $\dcf_0$ of \textbf{differentially closed fields}
of characteristic $0$,
which is to the theory $\df_0$ of all differential fields of characteristic $0$
as the theory $\acf$ of algebraically closed fields
is to the theory of all fields.

Specifically, $\dcf_0$ is the \emph{model completion} of $\df_0$.
To say what this means,
we denote by $\diag(\str M)$ the \textbf{diagram} of $\str M$,
namely the theory of structures in which $\str M$ embeds
\cite[\S2.1]{MR0153570};
this theory is axiomatized by the atomic and negated atomic sentences,
with parameters, that are true in $\str M$.

A theory $T^*$ is the \textbf{model completion} of a theory $T$
in the same signature \cite[\S4.3]{MR0153570} if
\begin{compactenum}[1)]
\item
$T\included T^*$,
\item
$T^*\cup\diag(\str M)$ is consistent
whenever $\str M\models T$,
\item
$T^*\cup\diag(\str M)$ axiomatizes a complete theory
whenever $\str M\models T$.
\end{compactenum}
When $T$ has the model completion $T^*$,
then immediately,
\begin{compactenum}[1)]
\item
every model of $T^*$ embeds in a model of $T$,
\item
every model of $T$ embeds in a model of $T^*$,
\item
$T^*$ is \textbf{model complete,}
that is, $T^*\cup\diag(\str M)$ is complete
whenever $\str M\models T^*$.
\end{compactenum}
Under these conditions alone,
$T^*$ is called the \textbf{model companion} of $T$
(the notion was introduced by ``Eli Bers'' in 1969
\cite[p.\ 609]{MR91c:03026}).

Given a theory $T$,
we define a \textbf{system} of $T$
to be a conjunction of atomic and negated atomic formulas in the signature of the theory.
$T$ is \textbf{inductive} if axiomatized by $\forall\exists$ sentences,
equivalently, every union of a chain of models is a model.

\begin{theorem}\label{thm:1}
  If it exists,
the model-companion $\Trand\/^*$ of a theory $\Trand$
is axiomatized by $\Trand_{\forall}$ and sentences
\begin{equation*}
\Forall{\bm x}\Forall{\bm y}\Exists{\bm z}\bigl(\theta(\bm x,\bm y)\lto\phi(\bm x,\bm z)\bigr),
\end{equation*}
where
\begin{compactitem}
\item
$\phi$ is a system of atomic and negated atomic formulas,
\item
$\theta$ is from a set $\Theta_{\phi}$ of formulas, and
\item
for all models $\str M$ of $\Trand_{\forall}$
with parameters $\bm a$, 
\begin{center}
$\theta(\bm a,\bm y)$ is soluble in $\str M$ for some $\theta$ in $\Theta_{\phi}$
$\iff$\\
$\phi(\bm a,\bm z)$ is soluble in a model of $\Trand_{\forall}\cup\diag{\str M}$.
\end{center}
\end{compactitem}
\end{theorem}

One can use Compactness to replace $\Theta_{\phi}$ with a single formula.
Also, if $\Trand$ has a model-\emph{completion,}
this single formula can be required to be quantifier-free
(and conversely):
this is what Robinson proved.
Seidenberg
had already shown that $\df$ met the condition on $\Trand$.
It was then observed, first by Blum \cite{MR0491149,MR99g:12006,MR2114160},
that not all systems of $\df$ need be considered.
Especially,
every ordinary differential polynomial equation can be written as
\begin{equation*}
  f(\dots,\delta^jx_i,\dots)=0,
\end{equation*}
where $f$ is an ordinary polynomial;
and this equation
is equivalent to the result
of replacing each derivative with a new variable,
then conjoining the equation of the derivative with the variable:
\begin{equation*}
  f(\dots,x_i^{(j)},\dots)=0
  \land\bigwedge_{i,j}\delta x_i^{(j-1)}=x_i^{(j)}.
\end{equation*}
This approach of isolating the singulary operation $\delta$
is useful for other theories involving singulary operations,
specifically the theories of
\begin{compactenum}[1)]
\item
group actions (in work with Ay\c se Berkman),
\item
  fields with automorphism and valuation
  (in work with \"Ozlem Beyarslan, Daniel Max Hoffmann, G\"onen\c c Onay).
\end{compactenum}
The general result that we use is the following.

\begin{porism}
In the hypothesis of Theorem \ref{thm:1},
it is enough that $\phi(\vec x,\vec y)$ range over
a collection $\Phi$ of systems in the signature of $T$ containing,
\begin{compactenum}[(a)]
\item\myforall\ 
systems $\psi(\vec x,\vec u)$ of $T$,
\item\myforall\ models $\str M$ of $T$,
\item\myforall\ choices $\vec a$ of parameters from $M$,
\end{compactenum}
a system $\phi(\vec x,\vec u,\vec v)$
such that,
\begin{enumerate}[(i)]
  \item
if $\Exists{\vec u}\psi(\vec a,\vec u)$
 is consistent with $T\cup\diag{\str A}$,
 then so is
 $\Exists{\vec u}\Exists{\vec v}\phi(\vec a,\vec u,\vec v)$,
 and
 \item
   $T\cup\diag(\str M)\proves
   \Forall{\vec u}\Forall{\vec v}
   \bigl(\phi(\vec a,\vec u,\vec v)\lto\psi(\vec a,\vec u)\bigr)$.
\end{enumerate}
\end{porism}

\section{Group Actions}

We can understand a \textbf{group action}
as kind of two-sorted structure $(\agp,\pset)$,
equipped with a function
\begin{equation*}
(\xi,y)\mapsto\myop{\xi}y
\end{equation*}
from $\agp\times\pset$ to $\pset$.
The structure should be a model of the theory $\GA$,
which has the following axioms:
\begin{gather*}
	\Forall{\xi}\Exists{\eta}\Forall z(\myop{\xi}\myop{\eta} z=z\land\myop{\eta}\myop{\xi} z=z),\\
	\Forall{\xi}\Forall{\eta}\Exists{\zeta}\Forall v
\myop{\xi}\myop{\eta} v=\myop{\zeta} v,\\
\Exists{\xi}\Forall y\myop{\xi} y=y.
\end{gather*}
In words, if the elements of $\agp$ are called \emph{functions,}
$\GA$ says
\begin{compactenum}[1)]
\item
every function has an inverse,
\item
any two functions have a composite,
\item
there is an identity function.
\end{compactenum}
There are no symbolized operations of actually taking inverses,
forming composites, or being the identity.
The theory $\FGA$ of \textbf{faithful} group actions
is axiomatized by $\GA$ along with
\begin{equation*}
\Forall{\xi}\Forall{\eta}\Exists z(\xi\neq\eta\lto\myop{\xi} z\neq\myop{\eta} z).
\end{equation*}
Of a theory $T$,
its \textbf{universal part} $T_{\forall}$
is the theory axiomatized by the universal sentences in $T$;
this is the theory of all substructures of models of $T$.
Then $T$ and $T_{\forall}$ have the same model companion,
if there is one.
To obtain a model companion for $\GA_{\forall}$,
it is enough to look at systems of equations $\myop{\xi}y=z$
and inequations $z\neq w$.

\begin{theorem}[Berkman, P.]\mbox{}
\begin{compactenum}
\item
$\GA$ and $\FGA$ are not inductive,
but they have the same universal part,
which is axiomatized by
\begin{equation*}
\Forall{\xi}\Forall y\Forall z(y\neq z\lto\myop{\xi} y\neq\myop{\xi} z),
\end{equation*}
meaning all functions are injective.
\item
Each of $\GA$ and $\FGA$ has a model companion, $\GA^*$,
which is axiomatized by $\GA_{\forall}$,
along with
\begin{gather*}
\Forall{\xi}\Forall y\Exists z\myop{\xi} z=y,\\
\Exists x\Exists yx\neq y,\\
	\Forall{\bm x}\Exists{\bm{\xi}}
	\left(\bigwedge_{i<j<n}x_i\neq x_j\lto
\phi_n(\bm{\xi},\bm x)
	\right),\\
	\Forall{\bm{\xi}}\Exists{\bm x}
	\left(\bigwedge_{\substack{(\sigma,\tau)\in\Sym n^2\\\sigma\neq\tau}}\xi_{\sigma}\neq\xi_{\tau}\lto
\phi_n(\bm{\xi},\bm x)
	\right),
\end{gather*}
where
$n$ ranges over $\N$, and $\phi_n(\bm{\xi},\bm x)$
is the formula
\begin{equation*}
	\bigwedge_{i<n}\bigwedge_{\sigma\in\Sym n}\myop{\xi_{\sigma}}x_i=x_{\sigma(i)}.
\end{equation*}
That is,
$\GA^*$ is the theory of those models 
$(\aset,\pset)$ of $\GA_{\forall}$ such that
\begin{compactenum}
\item
the functions on $\pset$ induced by elements of $\aset$ are invertible,
\item
$\pset$ has at least two elements, and
\item
for each $n$ in $\N$,
\begin{compactenum}[(i)]
  \item
each set of $n$ distinct elements of $\pset$
is completely permuted by some $n!$ elements of $\aset$,
and
\item
each set of $n!$ distinct elements of $\aset$
completely permutes some $n$ elements of $\pset$.
\end{compactenum}
\end{compactenum}
\item
$\GA^*$ does not admit full elimination of quantifiers,
so $\GA_{\forall}$ has no model completion.
\item
In the expanded signature with a symbol for the function
\begin{equation*}
(\xi,y)\mapsto\myop{\xi\inv}y,
\end{equation*}
the theory $\GA^{\dag}$ axiomatized by $\GA^*$ with
\begin{equation*}
\Forall{\xi}\Forall y\Forall z(\myop{\xi} y=z\liff y=\myop{\xi\inv} z)
\end{equation*}
admits full elimination of quantifiers.
\item
$\GA^{\dag}$ is complete,
and therefore $\GA^*$ is complete.
\item
$\GA^*$ has $\TP2$.
\item
$\GA^*$ has $\NSOP1$
(by the sufficient condition of Chernikov and Ramsey
\cite[Prop.\ 5.3]{MR3580894}).
\item
$\GA^*$ has a prime model,
in which the orbit of any finite set of points
under any finite set of permutations is finite.
\item
$\GA^*$ has no countable universal model.
\item\sloppy
There is a model $(\aset,\upomega)$ of $\GA^*$
in which the model $(\Sym{\upomega},\upomega)$ of $\FGA$ embeds;
thus every countable model of $\GA^*$ embeds (elementarily)
in $(\aset,\upomega)$.
\end{compactenum}
\end{theorem}

\section{Fields with Automorphism and Valuation}

A \textbf{difference field} is just a field with an automorphism.
The theory of difference fields has a model companion,
called $\acfa$
\cite{MR99c:03046,MR2000f:03109}.
In the signature
\begin{equation*}
\{+,-,0,\times,1,{}\autom,\invr,\inmaxi\},
\end{equation*}
we axiomatize $\fav$
by the field axioms, along with axioms
\begin{gather*}
\Forall x\Forall y\bigl((x+y)\autom=x\autom+y\autom\land
	(x\cdot y)\autom=x\autom\cdot y\autom\bigr),\\
\Forall x\Exists yy\autom=x
\end{gather*}
for a surjective endomorphism
(which for a field is an automorphism),
and axioms
\begin{gather*}
0\in\vr,\\
\Forall x\Forall y(x\in\vr\land y\in\vr\lto -x\in\vr
\land x+y\in\vr\land x\cdot y\in\vr),\\
\Forall x\Exists y(x\notin\vr\lto x\cdot y=1\land y\in\vr)
\end{gather*}
for a valuation ring, and
(for convenience) the axiom
\begin{equation*}
\Forall x\Bigl(x\in\maxi\liff
\Exists y\bigl(x=0\lor(x\cdot y=1\land y\notin\vr)\bigr)\Bigr),
\end{equation*}
or equivalently
\begin{equation*}%\label{eqn:notin-m}
\Forall x\Bigl(x\notin\maxi\liff\Exists y(x\cdot y=1\land y\in\vr)\bigr),
\end{equation*}
for membership in the unique maximal ideal of the valuation ring.
Because both the new predicate and its negation have existential definitions,
the predicate does not affect the existence of a model-companion
\cite[Lem.~1.1, p.\ 427]{MR2505433}.

The theory $\acvf$ of algebraically closed fields
with proper valuation ring
is the model companion of the theory of fields with valuation ring
\cite[\S3.4, pp.\ 47 ff.]{MR0472504}.
This does not make it automatic that $\fav$ has a model companion;
for example,
the theory of difference fields (of arbitrary characteristic)
with a derivation has no model companion
\cite{MR2114160}.
To obtain a model companion for $\fav$,
it is enough to look at systems
\begin{equation*}
  \bigwedge_{f\in I_0}f=0
  \land\bigwedge_{i<m}X_i{}\autom=X_{\tau(i)}
\land\bigwedge_{k\in\kappa}X_k\in\maxi
\land\bigwedge_{\ell\in\lambda}X_{\ell}\in\vr,
\end{equation*}
where
\begin{align*}
  m&\leq n<\upomega,&
  I_0&\included_{\mathrm{fin}}\vr[X_j\colon j<n],&
  \tau&\colon m\rightarrowtail n,&
  \kappa&\included\lambda\included n.
\end{align*}


\begin{theorem}[Beyarslan, Hoffman, Onay, P.]\mbox{}
\begin{compactenum}
\item
The models of $\acfa$
are precisely those difference fields such that
\begin{compactenum}[(a)]
\item\myforall\ $m$ and $n$ in $\upomega$ such that $m\leq n$,
\item\myforall\ injective functions $\tau$ from $m$ into $n$,
\item\myforall\ finite subsets $I_0$ of $K[X_j\colon j<n]$,
\item\myif
  \begin{multline}\label{eqn:(I_0)}
    \text{$I_0$ generates}\\\text{a prime ideal $(I_0)$ of $K[X_j\colon j<n]$,}
  \end{multline}
  \item\myand
    \begin{multline}\label{eqn:f(X)}
\bigl\{f(X_{\tau(i)}\colon i<m)\colon f\in(I_0)\cap K[X_i\colon i<m]\bigr\}\\
=(I_0)\cap K[X_{\tau(i)}\colon i<m],
    \end{multline}
  \item\mythen\
the system
\begin{equation}\label{eqn:df-sys}
\bigwedge_{f\in I_0}f=0\land\bigwedge_{i<m}X_i{}\autom=X_{\tau(i)} 
\end{equation}
has a solution in $K$.
\end{compactenum}
\item
$\fav$ has a model companion, $\fav^*$,
whose models are just those models $(K,\sigma,\vr)$ of $\fav$
in which
\begin{equation*}
  \Exists xx\notin\vr
\end{equation*}
and,
\begin{compactenum}[(a)]
\item\myforall\ $m$ and $n$ in $\upomega$ such that $m\leq n$,
\item\myforall\ injective functions $\tau$ from $m$ into $n$,
\item\myforall\ finite subsets $I_0$ of $\vr[X_j\colon j<n]$,
\item\myforall\ subsets $\lambda$ of $n$ and $\kappa$ of $\lambda$,
\item\myif\
\eqref{eqn:(I_0)}, and \eqref{eqn:f(X)}, and
the set
\begin{equation*}
\maxi\cup I_0\cup\{X_k\colon k\in\kappa\}
\end{equation*}
generates a \emph{proper} ideal of
$\vr\bigl[I_0\cup\{X_{\ell}\colon\ell\in\lambda\}\bigr]$,
\item\mythen\
$K$ contains a common solution to the system \eqref{eqn:df-sys}
and the system
\begin{equation*}
\bigwedge_{\ell\in\lambda}X_{\ell}\in\vr
\land\bigwedge_{k\in\kappa}X_k\in\maxi.
\end{equation*}
\end{compactenum}
\item
$\fav^*\neq\acfa\cup\acvf$.
\end{compactenum}
\end{theorem}

%\bibliographystyle{plain}
%\bibliography{../../references}

\begin{thebibliography}{10}

\bibitem{MR0491149}
Lenore Blum.
\newblock Differentially closed fields: a model-theoretic tour.
\newblock In {\em Contributions to algebra (collection of papers dedicated to
  {E}llis {K}olchin)}, pages 37--61. Academic Press, New York, 1977.

\bibitem{MR91c:03026}
Chen~Chung Chang and H.~Jerome Keisler.
\newblock {\em Model theory}, volume~73 of {\em Studies in Logic and the
  Foundations of Mathematics}.
\newblock North-Holland Publishing Co., Amsterdam, third edition, 1990.
\newblock First edition 1973.

\bibitem{MR2000f:03109}
Zo{\'e} Chatzidakis and Ehud Hrushovski.
\newblock Model theory of difference fields.
\newblock {\em Trans. Amer. Math. Soc.}, 351(8):2997--3071, 1999.

\bibitem{MR3580894}
Artem Chernikov and Nicholas Ramsey.
\newblock On model-theoretic tree properties.
\newblock {\em J. Math. Log.}, 16(2):1650009, 41, 2016.

\bibitem{MR99c:03046}
Angus Macintyre.
\newblock Generic automorphisms of fields.
\newblock {\em Ann. Pure Appl. Logic}, 88(2-3):165--180, 1997.
\newblock Joint AILA-KGS Model Theory Meeting (Florence, 1995).

\bibitem{MR2114160}
David Pierce.
\newblock Geometric characterizations of existentially closed fields with
  operators.
\newblock {\em Illinois J. Math.}, 48(4):1321--1343, 2004.

\bibitem{MR2505433}
David Pierce.
\newblock Model-theory of vector-spaces over unspecified fields.
\newblock {\em Arch. Math. Logic}, 48(5):421--436, 2009.

\bibitem{MR99g:12006}
David Pierce and Anand Pillay.
\newblock A note on the axioms for differentially closed fields of
  characteristic zero.
\newblock {\em J. Algebra}, 204(1):108--115, 1998.

\bibitem{MR0153570}
Abraham Robinson.
\newblock {\em Introduction to model theory and to the metamathematics of
  algebra}.
\newblock North-Holland Publishing Co., Amsterdam, 1963.

\bibitem{MR0472504}
Abraham Robinson.
\newblock {\em Complete theories}.
\newblock North-Holland Publishing Co., Amsterdam, second edition, 1977.
\newblock With a preface by H. J. Keisler, Studies in Logic and the Foundations
  of Mathematics, first published 1956.

\bibitem{MR0082487}
Abraham Seidenberg.
\newblock An elimination theory for differential algebra.
\newblock {\em Univ. California Publ. Math. (N.S.)}, 3:31--65, 1956.

\end{thebibliography}


\end{document}