# Interpretations of syntactic fragments of theories of fields

Sylvy Anscombe and Arno Fehm  Université Paris Cité and Sorbonne Université,
CNRS, IMJ-PRG, F-75013 Paris, France<EMAIL_ADDRESS>Institut für
Algebra, Technische Universität Dresden, 01062 Dresden, Germany  arno.fehm@tu-
dresden.de

###### Abstract.

We set up general machinery to study interpretations of fragments of theories.
We then apply this to existential fragments of theories of fields, and
especially of henselian valued fields. As an application we prove many-one
reductions between various existential theories of fields. In particular we
exhibit several theories of fields many-one equivalent to the existential
theory of $\mathbb{Q}$.

##  1\. Introduction

The notion of an interpretation of one structure $N$ in a language
$\mathfrak{L}_{1}$ in another structure $M$ in a language $\mathfrak{L}_{2}$
is well established in contemporary model theory. Usually this refers to an
isomorphism between $N$ and a definable quotient inside $M$, cf. [Hod93,
Hod97, Poi00, Mar02]. For example, every field interprets every linear
algebraic group over it (even definably so, i.e. without the need to pass to a
quotient), and every valued field interprets its value group and its residue
field. The main importance of this notion of interpretation derives from the
fact that many properties (like stability, or decidability) are transferred
from the interpreting structure $M$ to the interpreted structure $N$.

There seems to be less agreement on what an interpretation of an
$\mathfrak{L}_{1}$-theory $T_{1}$ in an $\mathfrak{L}_{2}$-theory $T_{2}$ is.
Older definitions seem to be of little use nowadays, as Hodges remarks in his
discussion in [Hod93, §5.4]. One possible notion relates to that of a uniform
interpretation $\Gamma$ of the models of $T_{1}$ in the models of $T_{2}$, in
the sense that there is one $\mathfrak{L}_{2}$-formula $\delta_{\Gamma}$ and
for every unnested atomic $\mathfrak{L}_{1}$-formula $\varphi$ a corresponding
$\mathfrak{L}_{2}$-formula $\varphi_{\Gamma}$ such that for every $M\models
T_{2}$ there exists $N\models T_{1}$ and a surjective map
$f_{\Gamma}:\delta_{\Gamma}(M)\rightarrow N$ such that

$N\models\varphi(f_{\Gamma}(a_{1}),\dots,f_{\Gamma}(a_{m}))\;\Longleftrightarrow\;M\models\varphi_{\Gamma}(a_{1},\dots,a_{m}),\quad
a_{1},\dots,a_{m}\in\delta_{\Gamma}(M),$

so that $f_{\Gamma}$ induces an $\mathfrak{L}_{1}$-isomorphism
$\delta_{\Gamma}(M)/E_{\Gamma}\cong N$ (where $E_{\Gamma}$ is the equivalence
relation defined by the $\mathfrak{L}_{2}$-formula assigned to the
$\mathfrak{L}_{1}$-formula $x_{1}=x_{2}$), and thus an interpretation of $N$
in $M$. Many variants of this are discussed in the above mentioned [Hod93,
§5.4].

Such a uniform interpretation yields in particular the following two things: A
class function $\sigma:{\rm Mod}(T_{2})\rightarrow{\rm Mod}(T_{1})$ assigning
to every model $M$ of $T_{2}$ the model $\sigma
M=\delta_{\Gamma}(M)/E_{\Gamma}$ of $T_{1}$ that the given formulas produce,
and a translation map $\iota:{\rm Sent}(\mathfrak{L}_{1})\rightarrow{\rm
Sent}(\mathfrak{L}_{2})$ from the set of $\mathfrak{L}_{1}$-sentences to the
set of $\mathfrak{L}_{2}$-sentences which are related via

(1.1) $\sigma M\models\varphi\;\Longleftrightarrow\;M\models\iota\varphi$

for every $M\models T_{2}$ and every $\mathfrak{L}_{1}$-sentence $\varphi$. If
the structure map $\sigma$ is surjective (say up to isomorphism, or just up to
elementary equivalence), this then gives in particular an interpretation of
the theory $T_{1}$ in the theory $T_{2}$ in the sense that

(1.2) $T_{1}\models\varphi\;\Longleftrightarrow\;T_{2}\models\iota\varphi.$

In particular, one obtains (assuming moreover that the translation map $\iota$
is computable) a Turing reduction, and more precisely even a many-one
reduction from $T_{1}$ to $T_{2}$, and in fact a whole family of reductions of
$\mathfrak{L}_{1}$-theories extending $T_{1}$ to corresponding
$\mathfrak{L}_{2}$-theories extending $T_{2}$. We remark that there are
important examples where a situation as in (1.1) arises without the existence
of an actual interpretation of structures, like when $\sigma$ assigns to a
field the inverse system of its absolute Galois group.

In this work we want to study interpretations of theories with a focus on
fragments of languages, for example existential fragments, with the goal of
obtaining translation maps as in (1.2) but now with $\varphi$ and
$\iota\varphi$ in this fragment. For example, when the formulas
$\delta_{\Gamma}$, $\varphi_{\Gamma}$ in a uniform interpretation $\Gamma$ are
all say quantifier free, then the translation map $\iota$ will map existential
sentences to existential sentences, thereby giving (many-one) reductions
between existential theories, see for example [Pas22] for foundational work on
interpretations in the context of existential theories. Moreover, one obtains
a monotonicity statement for in this case the existential fragment:

(1.3) $M,M^{\prime}\models T_{2},{\rm Th}_{\exists}(M)\subseteq{\rm
Th}_{\exists}(M^{\prime})\;\Longrightarrow\;{\rm Th}_{\exists}(\sigma
M)\subseteq{\rm Th}_{\exists}(\sigma M^{\prime}).$

We set up a general formalism to deal with such interpretations of fragments,
which for applicability still works with a structure map $\sigma$ but
accommodates for the fact that when requiring (1.1) only for certain sentences
(like existential sentences), asking for an actual interpretation of the whole
structure $\sigma M$ in $M$ is certainly way more than necessary, and in fact
there are many more settings where a translation $\iota$ between fragments of
theories arises without being induced by an interpretation of structures.

One important such setting is that of valued fields, where as mentioned above
every valued field interprets its residue field (in the sense of a uniform
intepretation with $T_{1}$ the theory of fields and $T_{2}$ the theory of
valued fields), but in general the residue field does not interpret the valued
field; however, at least in the context of equicharacteristic henselian valued
fields, the existential theory of the residue field determines the existential
theory of the valued field (this is the main result of [AF16]), and in fact
monotonely so in the sense of (1.3) with the arrow reversed, which in turn
gives an interpretation of the existential theory of the valued field in the
existential theory of the residue field in the sense of (1.1) and (1.2), with
a translation map $\iota$ going in the other direction (which is what we will
call an elimination map). So together one obtains something like a mutual
interpretation of the existential theory of the valued field with the
existential theory of the residue field, without the presence of a mutual
interpretation of structures, and our formalism is designed to deal with such
situations.

After setting up this formalism in Section 2, in Section 3 we apply it to
existential theories of PAC fields and henselian valued fields. One of the
applications to henselian valued fields that we obtain, using and extending
[AF16] and [ADF23], is the following:

######  Theorem 1.1.

Let $R$ be any $\mathfrak{L}_{\rm ring}$-theory of fields.

  1. (a)

The set of existential sentences in the language of rings that hold in every
model of $R$ is many-one equivalent to the set of existential sentences in the
language of valued fields that hold in every equicharacteristic henselian non-
trivially valued field with residue field a model of $R$.

  2. (b)

The same as (a) applies with "nontrivially valued field" replaced by "valued
field with discrete value group and distinguished uniformizer", if consequence
(R4) of resolution of singularities from [ADF23] holds.

  3. (c)

Moreover, the same as (a) applies for every $n$ with "existential sentence"
both times replaced by "finite conjunction of existential prenex sentences
each of which has at most $n$ existential quantifiers".

In the following sections 4-5 we deal with interpretations in the context of
limits of theories, in particular the well-known phenomenon of viewing
characteristic zero theories as limits of positive characteristic theories. As
a concrete example we obtain a list of various theories many-one equivalent to
the existential theory of $\mathbb{Q}$, whose decidability is a famous open
question also known under the name Hilbert’s tenth problem for $\mathbb{Q}$,
see for example [Koe14, Poo03]:

######  Theorem 1.2.

The following theories are many-one equivalent:

  1. (a)

The existential theory of $\mathbb{Q}$ in the language of rings.

  2. (b)

The existential theory of $\mathbb{Q}(\\!(t)\\!)$ in the language of rings.

  3. (c)

The existential theory of $\mathbb{Q}(\\!(t)\\!)$ in the language of valued
fields.

  4. (d)

The existential theory of $\mathbb{Q}(\\!(t)\\!)$ in the language of valued
fields with constant $t$.

  5. (e)

The existential theory of large fields of characteristic zero in the language
of rings.

  6. (f)

The existential theory of large fields in the language of rings.

  7. (g)

The existential theory of fields in the language of rings.

Finally, as another application, we discuss the existential theory of global
fields. Regarding decidability we obtain for example the following:

######  Theorem 1.3.

The following are equivalent:

  1. $(a)$

The existential theory of infinite fields is decidable.

  2. $(b)$

The exixtential theory of $\mathbb{Q}$ is decidable and the existential theory
of $\mathbb{F}_{p}(t)$ is uniformly decidable, i.e. there exists an algorithm
that decides given $p\in\mathbb{P}$ and an existential $\mathfrak{L}_{\rm
ring}$-sentence $\varphi$ whether $\varphi$ holds in $\mathbb{F}_{p}(t)$.

We will further apply this formalism to universal-existential theories of
fields, in particular Laurent series fields and function fields, in the
upcoming work [AF23].

##  2\. Contexts, bridges and arches

In this section we set up our formalism in a completely general setting.
Concrete examples and applications are provided in Section 3.

###  2.1. Interpretations and eliminations

######  Definition 2.1.

A language $\mathfrak{L}$ is a (possibly multi-sorted) first-order language.
We denote by ${\rm Form}(\mathfrak{L})$ the set of $\mathfrak{L}$-formulas,
and by ${\rm Sent}(\mathfrak{L})$ the set of $\mathfrak{L}$-sentences, where
we follow the convention that $\top,\perp\in{\rm Sent}(\mathfrak{L})$ for
every language $\mathfrak{L}$. As usual we call a subset $T\subseteq{\rm
Sent}(\mathfrak{L})$ an $\mathfrak{L}$-theory. We moreover call a subset
$L\subseteq{\rm Sent}(\mathfrak{L})$ which contains $\top$ and $\perp$ and is
closed under $\wedge$ and $\vee$ an $\mathfrak{L}$-fragment. The class of
models of a theory $T$ is denoted ${\rm Mod}(T)$. For an
$\mathfrak{L}$-structure $M$, we denote as usual by ${\rm Th}(M)$ the
$\mathfrak{L}$-theory of $M$, and we write ${\rm Th}_{L}(M)={\rm Th}(M)\cap L$
for any $\mathfrak{L}$-fragment $L$. For an $\mathfrak{L}$-theory $T$ we
denote by $T^{\vdash}$ its deductive closure, and write $T_{L}=T^{\vdash}\cap
L$ for any $\mathfrak{L}$-fragment $L$.

######  Remark 2.2.

We will not make use of this but remark that if $L$ is an
$\mathfrak{L}$-fragment and $T\subseteq L$ a consistent theory that is
"relatively deductively closed" in the sense that $T=T_{L}$, then $T$ is
"relatively complete" in the sense that $T={\rm Th}_{L}(M)$ for some
$\mathfrak{L}$-structure $M$ if and only if whenever $\varphi,\psi\in L$ with
$\varphi\vee\psi\in T$, then $\varphi\in T$ or $\psi\in T$.

######  Remark 2.3.

For a countable language $\mathfrak{L}$, when discussing the computability of
an $\mathfrak{L}$-theory $T$, we will always assume that $\mathfrak{L}$ is
presented in the sense that it comes with a fixed injection mapping the
symbols of $\mathfrak{L}$ to $\mathbb{N}$ (the precise form of which is
irrelevant and will not be given explicitly when $\mathfrak{L}$ is finite). By
a standard Gödel coding, this induces an injection
$\alpha:\mathrm{Form}(\mathfrak{L})\rightarrow\mathbb{N}$, and we always
assume that $\alpha({\rm Form}(\mathfrak{L}))$ is computable. A set of
formulas $T\subseteq{\rm Form}(\mathfrak{L})$ is then computable (or
decidable) respectively computably enumerable if
$\alpha(T)\subseteq\mathbb{N}$ is.

If $\mathfrak{L}_{1}$ and $\mathfrak{L}_{2}$ are two countable languages with
corresponding injections $\alpha_{i}:{\rm
Form}(\mathfrak{L}_{i})\rightarrow\mathbb{N}$, and $T_{i}\subseteq{\rm
Form}(\mathfrak{L}_{i})$, we say that a map $f:T_{1}\rightarrow T_{2}$ is
computable if the induced function
$\alpha_{1}(T_{1})\rightarrow\alpha_{2}(T_{2})$ is. Similarly, we say that
$T_{1}$ is many-one reducible to $T_{2}$, and write $T_{1}\leq_{\rm m}T_{2}$,
if $\alpha_{1}(T_{1})$ is many-one reducible to $\alpha_{2}(T_{2})$, i.e.
there exists a computable function $f:\mathbb{N}\rightarrow\mathbb{N}$ such
that $n\in\alpha_{1}(T_{1})$ if and only if $f(n)\in\alpha_{2}(T_{2})$, see
[Soa16, Definition 1.6.8]. We say that $T_{1}$ and $T_{2}$ are many-one
equivalent, and write $T_{1}\simeq_{\rm m}T_{2}$, if $T_{1}\leq_{\rm m}T_{2}$
and $T_{2}\leq_{\rm m}T_{1}$. We say that $T_{1}$ is Turing reducible to
$T_{2}$, and write $T_{1}\leq_{\rm T}T_{2}$, if $\alpha_{1}(T_{1})$ is Turing
reducible to $\alpha_{2}(T_{2})$, i.e. there exists a Turing machine that
decides $\alpha_{1}(T_{1})$ with an oracle for $\alpha_{2}(T_{2})$, see
[Tur39] and [Pos44, §11]. We say that $T_{1}$ and $T_{2}$ are Turing
equivalent, and write $T_{1}\simeq_{\rm T}T_{2}$, if $T_{1}\leq_{\rm T}T_{2}$
and $T_{2}\leq_{\rm T}T_{1}$. When we write $T_{1}\oplus T_{2}$ on one of the
sides of $\leq_{\rm T}$ or $\leq_{\rm m}$ we mean some standard coding of the
disjoint union, e.g. the set
$2\alpha_{1}(T_{1})\cup(2\alpha_{2}(T_{2})+1)\subseteq\mathbb{N}$.

For the rest of this section let
$\mathfrak{L},\mathfrak{L}_{1},\mathfrak{L}_{2}$ be languages.

######  Definition 2.4.

A pair $(L,T)$ consisting of an $\mathfrak{L}$-fragment $L$ and an
$\mathfrak{L}$-theory $T$ will be called an $\mathfrak{L}$-context. We call an
$\mathfrak{L}$-context $(L_{1},T_{1})$ a subcontext of the
$\mathfrak{L}$-context $(L_{2},T_{2})$ if $L_{1}\subseteq L_{2}$ and
$T_{1}\subseteq T_{2}$. If $C_{1}=(L_{1},T_{1})$ is an
$\mathfrak{L}_{1}$-context and $C_{2}=(L_{2},T_{2})$ an
$\mathfrak{L}_{2}$-context, a translation from $C_{1}$ to $C_{2}$ is a map
$\tau:L_{1}\rightarrow L_{2}$ with

$T_{1}\models\varphi\quad\Longleftrightarrow\quad
T_{2}\models\tau\varphi\quad\mbox{ for all }\varphi\in L_{1}.$

A bitranslation from $C_{1}$ to $C_{2}$ is a pair $(\tau_{1},\tau_{2})$ where
$\tau_{1}$ is a translation from $C_{1}$ to $C_{2}$ and $\tau_{2}$ is a
translation from $C_{2}$ to $C_{1}$ such that

(2.1) $\displaystyle
T_{1}\models\varphi\leftrightarrow\tau_{2}\tau_{1}\varphi$
$\displaystyle\mbox{ for all }\varphi\in L_{1},$ (2.2) $\displaystyle
T_{2}\models\psi\leftrightarrow\tau_{1}\tau_{2}\psi$ $\displaystyle\mbox{ for
all }\psi\in L_{2}.$

The following lemma is immediate from the definitions:

######  Lemma 2.5.

Let $\tau$ be a translation from the context $(L_{1},T_{1})$ to the context
$(L_{2},T_{2})$. Then $(T_{1})_{L_{1}}=\tau^{-1}((T_{2})_{L_{2}})$. If
moreover $L_{1}$, $L_{2}$ and $\tau$ are computable, then
$(T_{1})_{L_{1}}\leq_{\rm m}(T_{2})_{L_{2}}$.

######  Remark 2.6.

For a context $C=(L,T)$, let $[\varphi]_{C}$ denote the equivalence class of
$\varphi\in L$ under the equivalence relation $\sim_{C}$ defined on $L$ by
$\varphi\sim_{C}\varphi^{\prime}$ $:\Leftrightarrow$
$T\models\varphi\leftrightarrow\varphi^{\prime}$. Denote by
$\mathrm{LT}(C)=\\{[\varphi]_{C}\mid\varphi\in L\\}$ the quotient of $L$ by
$\sim_{C}$, which we view as a lattice isomorphic to the sublattice of the
Lindenbaum–Tarski algebra of $T$ generated by the fragment $L$, cf. [Sik69,
Ch. 1, §.1, Example D, p. 5].

Given contexts $C_{1},C_{2}$, a function $\tau:L_{1}\rightarrow L_{2}$ is a
translation from $C_{1}$ to $C_{2}$ if and only if
$\tau^{-1}([\top]_{C_{2}})=[\top]_{C_{1}}$. A pair $(\tau_{1},\tau_{2})$ of
functions $\tau_{1}:L_{1}\rightarrow L_{2}$, $\tau_{2}:L_{2}\rightarrow L_{1}$
satisfies (2.1) if and only if $\tau_{2}\circ\tau_{1}$ fixes each
$\sim_{C_{1}}$-class setwise, i.e.
$\varphi\sim_{C_{1}}\tau_{2}\tau_{1}\varphi$ for all $\varphi\in L_{1}$. In
particular, there exist pairs $(\tau_{1},\tau_{2})$ which are not
bitranslations but both $\tau_{i}$ are translations. Also there exist pairs
$(\tau_{1},\tau_{2})$ satisfying both (2.1) and (2.2) but which are not
bitranslations.

######  Definition 2.7.

A bridge is a triple $B=(C_{1},C_{2},\sigma)$ where each $C_{i}=(L_{i},T_{i})$
is an $\mathfrak{L}_{i}$-context and $\sigma:{\rm Mod}(T_{2})\rightarrow{\rm
Mod}(T_{1})$ is a class function. We write $C_{1}.C_{2}$ for $B$ when $\sigma$
is clear from the context. An interpretation for the bridge $B$ is a map
$\iota:L_{1}\rightarrow L_{2}$ such that

(2.3) $\sigma M\models\varphi\quad\Longleftrightarrow\quad
M\models\iota\varphi\quad\mbox{ for all }\varphi\in L_{1},M\models T_{2},$

and an elimination for $B$ is a map $\epsilon:L_{2}\rightarrow L_{1}$ such
that

(2.4) $\sigma M\models\epsilon\psi\quad\Longleftrightarrow\quad
M\models\psi\quad\mbox{ for all }\psi\in L_{2},M\models T_{2}.$

A bridge $B^{\prime}=(C_{1}^{\prime},C_{2}^{\prime},\sigma^{\prime})$, with
$C_{i}^{\prime}=(L_{i}^{\prime},T_{i}^{\prime})$, extends $B$ if $C_{i}$ is a
subcontext of $C_{i}^{\prime}$, for $i=1,2$, and
$\sigma|_{\mathrm{Mod}(T_{2}^{\prime})}=\sigma^{\prime}$. We denote this by
$B\sqsubseteq B^{\prime}$. Such an extension is a fragment extension if
$T_{i}^{\prime}=T_{i}$, for $i=1,2$; or it is a theory extension if
$L_{i}^{\prime}=L_{i}$, for $i=1,2$.

######  Example 2.8.

Our main example, which we will introduce in all detail in Section 3.1, is
that of valued fields: Here $\mathfrak{L}_{1}$ is the language of rings,
$\mathfrak{L}_{2}$ is some language of valued fields, $T_{2}$ some theory of
valued fields whose residue fields are models of the theory $T_{1}$, and
$\sigma$ maps a valued field to its residue field. As there is a uniform
interpretation of the residue field in the valued field, if $L_{1}$ and
$L_{2}$ are compatible fragments (like all $\mathfrak{L}_{i}$-sentences, or
all existential $\mathfrak{L}_{i}$-sentences), the bridge
$((L_{1},T_{1}),(L_{2},T_{2}),\sigma)$ has an interpretation. If one uses the
usual three-sorted language of valued fields, this interpretation is just
relativizing to the residue field sort.

For of the rest of this section let $C_{i}=(L_{i},T_{i})$, for $i=1,2$, be an
$\mathfrak{L}_{i}$-context, and let $B=(C_{1},C_{2},\sigma)$ be a bridge.

######  Remark 2.9.

A function $\iota:L_{1}\rightarrow L_{2}$ is an interpretation for $B$ if and
only if it is a translation from $(L_{1},\mathrm{Th}_{L_{1}}(\sigma M))$ to
$(L_{2},\mathrm{Th}_{L_{2}}(M))$, for each $M\models T_{2}$. A function
$\varepsilon:L_{2}\rightarrow L_{1}$ is an elimination for $B$ if and only if
it is a translation from $(L_{2},\mathrm{Th}_{L_{2}}(M))$ to
$(L_{1},\mathrm{Th}_{L_{1}}(\sigma M))$, for each $M\models T_{2}$.

######  Remark 2.10.

Let $\tau$ be a translation from $C_{1}$ to $C_{2}$ such that
$T_{1}\models\varphi\leftrightarrow\varphi^{\prime}\implies
T_{2}\models\tau\varphi\leftrightarrow\tau\varphi^{\prime}$, so that $\tau$
induces a map $\mathrm{LT}(C_{1})\rightarrow\mathrm{LT}(C_{2})$. One can show
that if this is a lattice homomorphism, then there exists a class function
$\tilde{\sigma}:\mathrm{Mod}(T_{2})\rightarrow\mathrm{Mod}(T_{1})$ such that
$\tau$ is an interpretation for the bridge $(C_{1},C_{2},\tilde{\sigma})$.

The following two lemmas are immediate from the definitions:

######  Lemma 2.11.

For $i=1,2$ suppose that $C_{i}$ is a subcontext of an
$\mathfrak{L}_{i}$-context $\hat{C}_{i}=(\hat{L}_{i},T_{i})$. Then also
$\hat{B}=(\hat{C}_{1},\hat{C}_{2},\sigma)$ is a bridge, it is a fragment
extension of $B$, and the following holds:

  1. $(a)$

If $\iota$ is an interpretation for $\hat{B}$ and $\iota(L_{1})\subseteq
L_{2}$, then $\iota|_{L_{1}}$ is an interpretation for $B$.

  2. $(b)$

If $\epsilon$ is an elimination for $\hat{B}$ and $\epsilon(L_{2})\subseteq
L_{1}$, then $\epsilon|_{L_{2}}$ is an elimination for $B$.

######  Lemma 2.12.

For $i=1,2$ suppose that $C_{i}$ is a subcontext of an
$\mathfrak{L}_{i}$-context $\check{C}_{i}=(L_{i},\check{T}_{i})$ such that
$\sigma(\mathrm{Mod}(\check{T}_{2}))\subseteq\mathrm{Mod}(\check{T}_{1})$.
Then also $\check{B}=(\check{C}_{1},\check{C}_{2},\check{\sigma})$ is a
bridge, where $\check{\sigma}=\sigma|_{\mathrm{Mod}(\check{T}_{2})}$, and it
is a theory extension of $B$. Moreover, the following holds:

  1. $(a)$

If $\iota$ is an interpretation for $B$, then $\iota$ is an interpretation for
$\check{B}$.

  2. $(b)$

If $\epsilon$ is an elimination for $B$, then $\epsilon$ is an elimination for
$\check{B}$.

######  Definition 2.13.

We consider the following property of the bridge $B$:

  1. (sur)

For all $N\models T_{1}$ there exists $M\models T_{2}$ such that
$\mathrm{Th}_{L_{1}}(N)=\mathrm{Th}_{L_{1}}(\sigma M)$.

######  Lemma 2.14.

  1. $(a)$

For every interpretation $\iota$ for $B$ we have

(2.5) $\displaystyle T_{1}\models\varphi\quad\Longrightarrow\quad
T_{2}\models\iota\varphi,\quad\mbox{ for all }\varphi\in L_{1},$

and if $B$ satisfies (sur), then also

(2.6) $\displaystyle T_{1}\models\varphi\quad\Longleftarrow\quad
T_{2}\models\iota\varphi,\quad\mbox{ for all }\varphi\in L_{1},$

and so then $\iota$ is a translation from $C_{1}$ to $C_{2}$.

  2. $(b)$

For every elimination $\epsilon$ for $B$ we have

(2.7) $\displaystyle T_{1}\models\epsilon\psi\quad\Longrightarrow\quad
T_{2}\models\psi,\quad\mbox{ for all }\psi\in L_{2},$

and if $B$ satisfies (sur), then also

(2.8) $\displaystyle T_{1}\models\epsilon\psi\quad\Longleftarrow\quad
T_{2}\models\psi,\quad\mbox{ for all }\psi\in L_{2},$

and so then $\epsilon$ is a translation from $C_{2}$ to $C_{1}$.

###### Proof.

In both (a) and (b) the implication $\Longrightarrow$ is trivial from the
definition. For $\Longleftarrow$ in (a) let $\varphi\in L_{1}$ with
$T_{2}\models\iota\varphi$. For every $N\models T_{1}$, there exists $M\models
T_{2}$ with $\mathrm{Th}_{L_{1}}(N)=\mathrm{Th}_{L_{1}}(\sigma M)$ by (sur),
thus $M\models\iota\varphi$, hence $\sigma M\models\varphi$, and therefore
$N\models\varphi$. The implication $\Longleftarrow$ for (b) is proven
similarly. ∎

######  Proposition 2.15.

If the bridge $B$ has both an interpretation $\iota$ and an elimination
$\epsilon$, then $(\iota,\epsilon)$ satisfies part (2.2) of the definition a
bitranslation (but $\iota$ and $\epsilon$ need not be translations between
$C_{1}$ and $C_{2}$). If in addition $B$ satisfies (sur), then
$(\iota,\epsilon)$ is a bitranslation between $C_{1}$ and $C_{2}$.

###### Proof.

For $\psi\in L_{2}$, by (2.3) and (2.4) we have for every $M\models T_{2}$
that $M\models\psi$ if and only if $M\models\iota\epsilon\psi$, which shows
(2.2). If $B$ satisfies (sur), then Lemma 2.14(a) and (b) give that $\iota$,
respectively $\epsilon$, is a translation, and for $\varphi\in L_{1}$ and
$N\models T_{1}$ we have

$N\models\varphi\quad\Longleftrightarrow\quad\sigma
M\models\varphi\quad\Longleftrightarrow\quad
M\models\iota\varphi\quad\Longleftrightarrow\quad\sigma
M\models\epsilon\iota\varphi\quad\Longleftrightarrow\quad
N\models\epsilon\iota\varphi,$

where $M$ is some model of $T_{2}$ with
$\mathrm{Th}_{L_{1}}(N)=\mathrm{Th}_{L_{1}}(\sigma M)$, whose existence is
guaranteed by (sur). ∎

######  Definition 2.16.

We consider the following monotonicity property of the bridge $B$:

  1. (mon)

For all $M,M^{\prime}\models T_{2}$ with $\mathrm{Th}_{L_{1}}(\sigma
M)\subseteq\mathrm{Th}_{L_{1}}(\sigma M^{\prime})$ we have
$\mathrm{Th}_{L_{2}}(M)\subseteq\mathrm{Th}_{L_{2}}(M^{\prime})$.

######  Lemma 2.17.

Suppose $\iota$ is an interpretation for $B$. Then for every
$\varphi,\varphi^{\prime}\in L_{1}$,
$T_{2}\models\iota(\varphi\wedge\varphi^{\prime})\leftrightarrow(\iota\varphi\wedge\iota\varphi^{\prime})$
and
$T_{2}\models\iota(\varphi\vee\varphi^{\prime})\leftrightarrow(\iota\varphi\vee\iota\varphi^{\prime})$.

###### Proof.

This is very easy to check. ∎

######  Proposition 2.18.

If $B$ admits an elimination, then it satisfies (mon). Conversely, if $B$
admits an interpretation $\iota$ and satisfies (mon), then it admits an
elimination. In that case, if in addition $L_{1}$ and $L_{2}$ are computable,
$T_{2}$ is computably enumerable and $\iota$ is computable, then $B$ admits a
computable elimination.

###### Proof.

If $\epsilon$ is an elimination for $B$, then for $M,M^{\prime}\models T_{2}$
with ${\rm Th}_{L_{1}}(\sigma M)\subseteq{\rm Th}_{L_{1}}(\sigma M^{\prime})$
we have

$M\models\psi\quad\Longleftrightarrow\quad\sigma
M\models\epsilon\psi\quad\Longrightarrow\quad\sigma
M^{\prime}\models\epsilon\psi\quad\Longleftrightarrow\quad
M^{\prime}\models\psi$

for every $\psi\in L_{2}$, hence ${\rm Th}_{L_{2}}(M)\subseteq{\rm
Th}_{L_{2}}(M^{\prime})$.

Now suppose that $B$ satisfies (mon) and admits an interpretation $\iota$. We
claim that for every $\psi\in L_{2}$ there exists $\varphi\in L_{1}$ with
$T_{2}\models\psi\leftrightarrow\iota\varphi$. Indeed, for every
$M,M^{\prime}\models T_{2}$ with $M\models\psi$ and
$M^{\prime}\not\models\psi$, by (mon) there exists $\alpha\in L_{1}$ with
$\sigma M\models\alpha$ and $\sigma M^{\prime}\not\models\alpha$. Thus
$M\models\iota\alpha$ and $M^{\prime}\not\models\iota\alpha$. Therefore, the
separation lemma [PD11, Lemma 3.1.3] gives that there exist $\alpha_{ij}\in
L_{1}$ such that
$T_{2}\models\psi\leftrightarrow\bigwedge_{i}\bigvee_{j}\iota\alpha_{ij}$. By
Lemma 2.17,
$T_{2}\models\bigwedge_{i}\bigvee_{j}\iota\alpha_{ij}\leftrightarrow\iota(\bigwedge_{i}\bigvee_{j}\alpha_{ij})$.
Thus the choice $\varphi:=\bigwedge_{i}\bigvee_{j}\alpha_{ij}$ satisfies the
claim. By defining $\epsilon\psi$ to be $\varphi$ for any such $\varphi$, we
have $M\models\psi\Leftrightarrow M\models\iota\varphi\Leftrightarrow\sigma
M\models\epsilon\psi$ for any $M\models T_{2}$.

Assume now in addition that $L_{1}$ and $L_{2}$ are computable, $T_{2}$ is
computably enumerable and $\iota$ is computable. Then we can obtain a
computable $\epsilon$ as follows: Fix a computable enumeration
$\varphi_{1},\varphi_{2},\dots$ of $L_{1}$ and a computable enumeration
$P_{1},P_{2},\dots$ of the proofs from $T_{2}$ (here we use $\alpha:{\rm
Form}(\mathfrak{L}_{2})\rightarrow\mathbb{N}$ to obtain an injection from the
set of finite sequences of $\mathfrak{L}_{2}$-formulas into $\mathbb{N}$ in
the usual way). The ordering $\prec$ on $\mathbb{N}\times\mathbb{N}$ defined
by

(2.9)
$\displaystyle(n,m)\prec(n^{\prime},m^{\prime})\;\Longleftrightarrow\;n+m<n^{\prime}+m^{\prime}\vee(n+m=n^{\prime}+m^{\prime}\wedge
m<m^{\prime})$

is computable and has order type $\omega$. Given $\psi\in L_{2}$, by the
previous paragraph there exist $n$ and $m$ such that $P_{n}$ is a proof of
$T_{2}\vdash\psi\leftrightarrow\iota\varphi_{m}$. We take the $\prec$-minimal
such pair $(n,m)$ and define $\epsilon\psi:=\varphi_{m}$. ∎

###  2.2. Extensions of bridges

######  Definition 2.19.

An arch is a triple $A=(B,\hat{B},\iota)$ such that $B\sqsubseteq\hat{B}$ is a
fragment extension, $\iota$ is an interpretation for $\hat{B}$, and
$\iota|_{L_{1}}$ is an interpretation for $B$. We write $B|\hat{B}$ for $A$
when $\iota$ is clear from the context.

######  Example 2.20.

In our main example of valued fields (see Example 2.8), we use arches to
capture the fact that we have an interpretation $\iota$ defined on arbitrary
sentences although the eliminations are usually defined only on existential or
universal sentences (see, for example, Corollary 3.20), but restricting to
existential (or universal) sentences throughout would be too limiting, as we
would like to work for example in the class of valued fields with pseudofinite
residue field, which is axiomatized neither by existential nor by universal
sentences. Most of our applications of arches will involve Corollary 2.23
below.

######  Lemma 2.21.

Suppose that $B$ admits an interpretation $\iota$. Let $R\subseteq L_{1}$ and
write $\check{T}_{1}=T_{1}\cup R$, $\check{T}_{2}=T_{2}\cup\iota R$,
$\check{\sigma}=\sigma|_{{\rm Mod}(\check{T}_{2})}$, and
$\check{C}_{i}=(L_{i},\check{T}_{i})$. Then
$\check{B}=(\check{C}_{1},\check{C}_{2},\check{\sigma})$ is a bridge, it is a
theory extension of $B$, and in particular
$\check{T}_{2}^{\vdash}=(T_{2}\cup\iota(R_{L_{1}}))^{\vdash}=(T_{2}\cup\iota(\check{T}_{1,L_{1}}))^{\vdash}$.
Moreover, if $B$ satisfies (sur), then so does $\check{B}$.

###### Proof.

If $M\models\check{T}_{2}=T_{2}\cup\iota R$, then in particular $\sigma
M\models R$, but also $\sigma M\models T_{1}$ as $B$ is a bridge, hence
$\sigma M\models\check{T}_{1}$, and so $\check{B}$ is a bridge. In particular,
$\sigma M\models\check{T}_{1,L_{1}}$, hence
$\check{T}_{2}^{\vdash}\supseteq(T_{2}\cup\iota(\check{T}_{1,L_{1}}))^{\vdash}$,
and the inclusions
$\check{T}_{2}^{\vdash}\subseteq(T_{2}\cup\iota(R_{L_{1}}))^{\vdash}\subseteq(T_{2}\cup\iota(\check{T}_{1,L_{1}}))^{\vdash}$
are trivial as $R\subseteq L_{1}$. Now suppose that $B$ satisfies (sur), and
let $N\models\check{T}_{1}=T_{1}\cup R$. By (sur) there exists $M\models
T_{2}$ with $\mathrm{Th}_{L_{1}}(N)=\mathrm{Th}_{L_{1}}(\sigma M)$. Since
$R\subseteq L_{1}$, this implies that $\sigma M\models R$, and so
$M\models\iota R$. Therefore $\check{B}$ satisfies (sur). ∎

For the rest of this section $\hat{B}$ will denote a fragment extension of
$B=(C_{1},C_{2},\sigma)$, and we write
$\hat{B}=(\hat{C}_{1},\hat{C}_{2},\sigma)$, with
$\hat{C}_{i}=(\hat{L}_{i},T_{i})$.

######  Proposition 2.22.

Let $A=(B,\hat{B},\iota)$ be an arch where $B$ admits an elimination
$\epsilon$. We suppose that $\hat{B}$ satisfies (sur). Then for each
$R\subseteq\hat{L}_{1}$, $(\iota|_{L_{1}},\epsilon)$ is a bitranslation
between $(L_{1},T_{1}\cup R)$ and $(L_{2},T_{2}\cup\iota R)$.

###### Proof.

Define $\check{T}_{1}=T_{1}\cup R$, $\check{T}_{2}=T_{2}\cup\iota R$. Since
$\sigma(\mathrm{Mod}(\check{T}_{2}))\subseteq\mathrm{Mod}(\check{T}_{1})$,
both $B(R):=((L_{1},\check{T}_{1}),(L_{2},\check{T}_{2}),\check{\sigma})$ and
$\hat{B}(R):=((\hat{L}_{1},\check{T}_{1}),(\hat{L}_{2},\check{T}_{2}),\check{\sigma})$
are bridges, where $\check{\sigma}=\sigma|_{\mathrm{Mod}(\check{T}_{2})}$
(Lemma 2.12). Moreover, $\iota|_{L_{1}}$ is an interpretation for $B(R)$
(Lemmas 2.11(a), 2.12(a)) and also $\epsilon$ is an elimination for $B(R)$
(Lemma 2.12(b)). Furthermore, since $\hat{B}$ satisfies (sur), so does
$\hat{B}(R)$, by Lemma 2.21, which trivially implies that also $B(R)$
satisfies (sur). The claim follows from Proposition 2.15. ∎

######  Corollary 2.23.

Let $A=(B,\hat{B},\iota)$ be an arch. We suppose

  1. $(i)$

$L_{1},L_{2},\hat{L}_{1},\hat{L}_{2}$ are computable, $\iota$ is computable,
and $T_{2}$ is computably enumerable111The computability of $L_{1}$ and
$\hat{L}_{1}$ is to be understood with respect to the same injection
$\alpha_{1}:\mathrm{Form}(\mathfrak{L}_{1})\rightarrow\mathbb{N}$, as in
Remark 2.3; and similarly for $L_{2}$, $\hat{L}_{2}$ and $T_{2}$.,

  2. $(ii)$

$\hat{B}$ satisfies (sur), and

  3. $(iii)$

$B$ satisfies (mon).

Then

  1. (I)

$B$ admits a computable elimination.

  2. (II)

For each $R\subseteq\hat{L}_{1}$, $(T_{1}\cup R)_{L_{1}}\simeq_{\rm
m}(T_{2}\cup\iota R)_{L_{2}}$.

  3. (III)

$\mathrm{Th}_{L_{2}}(M)=(T_{2}\cup\iota\mathrm{Th}_{\hat{L}_{1}}(\sigma
M))_{L_{2}}=(T_{2}\cup\iota\mathrm{Th}_{L_{1}}(\sigma M))_{L_{2}}$, for each
$M\models T_{2}$.

###### Proof.

Since $B$ satisfies (mon) and admits an interpretation, it admits an
elimination $\epsilon$ (Proposition 2.18), which, together with the
computability assumptions, may be taken to be computable.

For $R\subseteq\hat{L}_{1}$, $(\iota|_{L_{1}},\epsilon)$ is a bitranslation
between $(L_{1},T_{1}\cup R)$ and $(L_{2},T_{2}\cup\iota R)$ by Proposition
2.22. Since both $\iota|_{L_{1}}$ and $\epsilon$ are computable, this gives a
many-one equivalence by Lemma 2.5.

For $M\models T_{2}$ the inclusions
$\mathrm{Th}_{L_{2}}(M)\supseteq(T_{2}\cup\iota\mathrm{Th}_{\hat{L}_{1}}(\sigma
M))_{L_{2}}\supseteq(T_{2}\cup\iota\mathrm{Th}_{L_{1}}(\sigma M))_{L_{2}}$ are
trivial. Let $M^{\prime}\models T_{2}\cup\iota\mathrm{Th}_{L_{1}}(\sigma M)$,
so that $\sigma M^{\prime}\models\mathrm{Th}_{L_{1}}(\sigma M)$. Then
$M^{\prime}\models\mathrm{Th}_{L_{2}}(M)$, since $B$ satisfies (mon), which
proves (III). ∎

######  Lemma 2.24.

Let $A=(B,\hat{B},\iota)$ be an arch. Suppose that $\hat{B}$ satisfies (sur),
and that $B$ admits an elimination $\epsilon$. Let $I\neq\emptyset$ and
$R_{i}\subseteq\hat{L}_{1}$, for $i\in I$. Then

$(T_{2}\cup\iota(\bigcap_{i\in I}(T_{1}\cup
R_{i})_{{L}_{1}}))_{L_{2}}=(T_{2}\cup\iota(\bigcap_{i\in I}(T_{1}\cup
R_{i})_{\hat{L}_{1}}))_{L_{2}}=\bigcap_{i\in I}(T_{2}\cup\iota
R_{i})_{L_{2}}.$

In particular, $(T_{2}\cup\iota((T_{1}\cup
R)_{L_{1}}))_{L_{2}}=(T_{2}\cup\iota((T_{1}\cup
R)_{\hat{L}_{1}}))_{L_{2}}=(T_{2}\cup\iota R)_{L_{2}}$ for every
$R\subseteq\hat{L}_{1}$.

###### Proof.

For $R\subseteq\hat{L}_{1}$, we write $\bar{R}=(T_{1}\cup R)_{\hat{L}_{1}}$.
First of all note that $R\subseteq\bar{R}=\bar{\bar{R}}$, as $(T_{1}\cup
R)_{\hat{L}_{1}}\subseteq(T_{1}\cup\bar{R})_{\hat{L}_{1}}\subseteq(T_{1}^{\vdash}\cup(T_{1}\cup
R)^{\vdash})_{\hat{L}_{1}}\subseteq((T_{1}\cup T_{1}\cup
R)^{\vdash})_{\hat{L}_{1}}=(T_{1}\cup R)_{\hat{L}_{1}}$. In particular
$(T_{1}\cup\bar{R})_{{L}_{1}}=(T_{1}\cup R)_{{L}_{1}}$. Moreover,
$(T_{2}\cup\iota R)^{\vdash}=(T_{2}\cup\iota\bar{R})^{\vdash}$, and in
particular, $(T_{2}\cup\iota R)_{L_{2}}=(T_{2}\cup\iota\bar{R})_{L_{2}}$, by
Lemma 2.21 applied to $\hat{B}$. Note that by Lemma 2.21, for any
$R\subseteq\hat{L}_{1}$, $((\hat{L}_{1},T_{1}\cup
R),(\hat{L}_{2},T_{2}\cup\iota R),\sigma|_{\mathrm{Mod}(T_{2}\cup\iota R)})$
is a bridge satisfying (sur). In particular, $((L_{1},T_{1}\cup
R),(L_{2},T_{2}\cup\iota R),\sigma|_{\mathrm{Mod}(T_{2}\cup\iota R)})$ is a
bridge satisfying (sur). By Lemma 2.12(b), $\epsilon$ is an elimination also
for this bridge.

By the first paragraph, we may assume that $R_{i}=\bar{R}_{i}$, for each $i\in
I$. Hence we want to prove that

$(T_{2}\cup\iota(\bigcap_{i\in
I}(R_{i})_{L_{1}}))_{L_{2}}=(T_{2}\cup\iota(\bigcap_{i\in
I}R_{i}))_{L_{2}}=\bigcap_{i\in I}(T_{2}\cup\iota R_{i})_{L_{2}}.$

Both inclusions $\subseteq$ are trivial. It remains to show that
$\bigcap_{i\in I}(T_{2}\cup\iota
R_{i})_{L_{2}}\subseteq(T_{2}\cup\iota(\bigcap_{i\in
I}(R_{i})_{L_{1}}))_{L_{2}}$, so let $\varphi\in\bigcap_{i\in
I}(T_{2}\cup\iota R_{i})_{L_{2}}$. For each $i\in I$, $T_{2}\cup\iota
R_{i}\models\varphi$. Since $(({L}_{1},T_{1}\cup
R_{i}),({L}_{2},T_{2}\cup\iota R_{i}),\sigma|_{\mathrm{Mod}(T_{2}\cup\iota
R_{i})})$ satisfies (sur) and has elimination $\epsilon$ for each $i\in I$, we
have $T_{1}\cup R_{i}\models\epsilon\varphi$ by (2.8). Thus
$\epsilon\varphi\in\bigcap_{i\in I}(T_{1}\cup R_{i})_{{L}_{1}}=\bigcap_{i\in
I}(R_{i})_{L_{1}}\subseteq T_{1}\cup\bigcap_{i\in I}(R_{i})_{L_{1}}$. Then
$T_{2}\cup\iota\bigcap_{i\in I}(R_{i})_{L_{1}}\models\varphi$ by (2.7). ∎

For an $\mathfrak{L}$-fragment $L$ write $\neg L=\\{\neg\varphi:\varphi\in
L\\}$ and let $\bar{L}$ be the smallest fragment that contains $L\cup\neg L$.
For a context $C=(L,T)$ let $\bar{C}=(\bar{L},T)$, and for a bridge
$B=(C_{1},C_{2},\sigma)$ let $\bar{B}=(\bar{C}_{1},\bar{C}_{2},\sigma)$.

######  Lemma 2.25.

If $B$ satisfies (mon) then so does $\bar{B}$. In particular, if
$A=(B,\hat{B},\iota)$ is an arch that satisfies the assumptions of Corollary
2.23, with $\neg L_{i}\subseteq\hat{L}_{i}$ for $i=1,2$ and $\iota(\neg
L_{1})\subseteq\neg L_{2}$, then also $(\bar{B},\hat{B},\iota)$ is an arch
that satisfies these assumptions.

###### Proof.

For $M,M^{\prime}\models T_{2}$, ${\rm Th}_{\bar{L}_{1}}(\sigma
M)\subseteq{\rm Th}_{\bar{L}_{1}}(\sigma M^{\prime})$ implies ${\rm
Th}_{{L}_{1}}(\sigma M)\subseteq{\rm Th}_{{L}_{1}}(\sigma M^{\prime})$ and
${\rm Th}_{\neg{L}_{1}}(\sigma M)\subseteq{\rm Th}_{\neg{L}_{1}}(\sigma
M^{\prime})$, equivalently ${\rm Th}_{{L}_{1}}(\sigma M^{\prime})\subseteq{\rm
Th}_{{L}_{1}}(\sigma M)$, hence by (mon) ${\rm Th}_{{L}_{2}}(M)\subseteq{\rm
Th}_{{L}_{2}}(M^{\prime})$ and ${\rm Th}_{{L}_{2}}(M^{\prime})\subseteq{\rm
Th}_{{L}_{2}}(M)$, and therefore ${\rm Th}_{\bar{L}_{2}}(M)={\rm
Th}_{\bar{L}_{2}}(M^{\prime})$, in particular ${\rm
Th}_{\bar{L}_{2}}(M)\subseteq{\rm Th}_{\bar{L}_{2}}(M^{\prime})$. ∎

######  Remark 2.26.

Regarding the consequences of Corollary 2.23 for $(\bar{B},\hat{B},\iota)$, of
course one can easily construct an elimination for $\bar{B}$ from an
elimination for $B$, but it is not clear how to deduce $(T_{1}\cup
R)_{\bar{L}_{1}}\simeq_{\rm m}(T_{2}\cup\iota R)_{\bar{L}_{2}}$ directly from
$(T_{1}\cup R)_{{L}_{1}}\simeq_{\rm m}(T_{2}\cup\iota R)_{{L}_{2}}$.

###  2.3. Weak monotonicity

We conclude this section with a weak variant of (mon) in the context of a
fragment extension:

######  Definition 2.27.

We consider the following property of the fragment extension
$B\sqsubseteq\hat{B}$:

  1. (wm)

For all $M\models T_{2}$ and all $N\models T_{1}$, if
$\mathrm{Th}_{L_{1}}(N)\subseteq\mathrm{Th}_{L_{1}}(\sigma M)$ then there
exists $M^{\prime}\models T_{2}$ with $\mathrm{Th}_{\hat{L}_{1}}(\sigma
M^{\prime})=\mathrm{Th}_{\hat{L}_{1}}(N)$ and
$\mathrm{Th}_{L_{2}}(M^{\prime})\subseteq\mathrm{Th}_{L_{2}}(M)$.

######  Lemma 2.28.

Suppose $\hat{B}$ satisfies (sur) and $B$ satisfies (mon). Then
$B\sqsubseteq\hat{B}$ satisfies (wm).

###### Proof.

Let $M\models T_{2}$ and $N\models T_{1}$ with
$\mathrm{Th}_{L_{1}}(N)\subseteq\mathrm{Th}_{L_{1}}(\sigma M)$. By (sur),
there exists $M^{\prime}\models T_{2}$ with
$\mathrm{Th}_{\hat{L}_{1}}(N)=\mathrm{Th}_{\hat{L}_{1}}(\sigma M^{\prime})$.
In particular $\mathrm{Th}_{L_{1}}(\sigma
M^{\prime})\subseteq\mathrm{Th}_{L_{1}}(\sigma M)$. By (mon), we have
$\mathrm{Th}_{L_{2}}(M^{\prime})\subseteq\mathrm{Th}_{L_{2}}(M)$. ∎

######  Lemma 2.29.

Let $T$ be an $\mathfrak{L}$-theory and let $L$ be an $\mathfrak{L}$-fragment.
Suppose that $M\models T_{L}$. Then there exists $N\models T$ such that
$M\models\mathrm{Th}_{L}(N)$.

###### Proof.

It suffices to show that $T\cup\mathrm{Th}_{(\neg)L}(M)$ is consistent,
because any model $N\models T\cup\mathrm{Th}_{(\neg)L}(M)$ satisfies
$M\models\mathrm{Th}_{L}(N)$. By the compactness theorem, it suffices to show
that $T\cup\mathrm{Th}_{(\neg)L}(M)$ is finitely consistent. Let
$\neg\varphi_{1},\ldots,\neg\varphi_{n}\in\mathrm{Th}_{(\neg)L}(M)$, so then
$M\models\neg\bigvee_{i\leq n}\varphi_{i}$. Since $L$ is a fragment, we have
$\bigvee_{i\leq n}\varphi_{i}\in L$ and so $\neg\bigvee_{i\leq
n}\varphi_{i}\in\mathrm{Th}_{(\neg)L}(M)$. Therefore $\bigvee_{i\leq
n}\varphi_{i}\notin\mathrm{Th}_{L}(M)$, and in particular
$T\not\models\bigvee_{i\leq n}\varphi_{i}$, which proves that
$T\cup\mathrm{Th}_{(\neg)L}(M)$ is finitely consistent. ∎

######  Lemma 2.30.

Let $A=(B,\hat{B},\iota)$ be an arch such that $B\sqsubseteq\hat{B}$ satisfies
(wm). Then for all $R,R^{\prime}\subseteq\hat{L}_{1}$, if $(T_{1}\cup
R)_{L_{1}}\subseteq(T_{1}\cup R^{\prime})_{L_{1}}$ then $(T_{2}\cup\iota
R)_{L_{2}}\subseteq(T_{2}\cup\iota R^{\prime})_{L_{2}}$.

###### Proof.

Let $M\models T_{2}\cup\iota R^{\prime}$. Then $\sigma M\models T_{1}\cup
R^{\prime}$, and in particular $\sigma M\models(T_{1}\cup
R^{\prime})_{L_{1}}$, and so $(T_{1}\cup R)_{L_{1}}\subseteq(T_{1}\cup
R^{\prime})_{L_{1}}\subseteq\mathrm{Th}_{L_{1}}(\sigma M)$. By Lemma 2.29,
there exists $N\models T_{1}\cup R$ such that
$\mathrm{Th}_{L_{1}}(N)\subseteq\mathrm{Th}_{L_{1}}(\sigma M)$. By (wm) there
exists $M^{\prime}\models T_{2}$ with $\mathrm{Th}_{\hat{L}_{1}}(\sigma
M^{\prime})=\mathrm{Th}_{\hat{L}_{1}}(N)$ and
$\mathrm{Th}_{L_{2}}(M^{\prime})\subseteq\mathrm{Th}_{L_{2}}(M)$. Thus $\sigma
M^{\prime}\models R$, whence $M^{\prime}\models T_{2}\cup\iota R$. Therefore
$M\models(T_{2}\cup\iota R)_{L_{2}}$, from which it follows that
$T_{2}\cup\iota R^{\prime}\models(T_{2}\cup\iota R)_{L_{2}}$. ∎

######  Remark 2.31.

To clarify the relation between (mon) and (wm), we remark that with $B$ and
$\hat{B}$ as above and $\hat{B}$ satisfying (sur), one can show that $B$
satisfies (mon) if and only if the pair $\hat{B},B$ satisfies (wm) and in
addition $B$ satisfies the following symmetric weakening of (mon): For all
$M,M^{\prime}\models T_{2}$ with $\mathrm{Th}_{L_{1}}(\sigma
M)=\mathrm{Th}_{L_{1}}(\sigma M^{\prime})$ we have
$\mathrm{Th}_{L_{2}}(M)=\mathrm{Th}_{L_{2}}(M^{\prime})$.

######  Remark 2.32.

Under the assumptions of Corollary 2.23, we have that

  1. (II’)

For each $\mathfrak{L}_{1}$-theory $R^{\prime}$, $(T_{1}\cup
R^{\prime})_{L_{1}}\simeq_{\rm m}(T_{2}\cup\iota((T_{1}\cup
R^{\prime})_{\hat{L}_{1}}))_{L_{2}}$,

which follows from applying Corollary 2.23(II) to $R=(T_{1}\cup
R^{\prime})_{\hat{L}_{1}}$. Similar adaptations can be made to the conclusions
of Proposition 2.22 and Lemmas 2.24 and 2.30 to allow
$\mathfrak{L}_{1}$-theories.

##  3\. Existential theories of fields

In this section we discuss a few examples where the general machinery of the
previous two sections applies, where we restrict to existential fragments.

###  3.1. Existential fragments

######  Definition 3.1.

For a language $\mathfrak{L}$, an $\mathfrak{L}$-formula
$\varphi(x_{1},\ldots,x_{m})$ is existential (resp. universal) if it is of the
form

$\displaystyle\exists y_{1}\ldots\exists
y_{n}\;\psi(x_{1},\ldots,x_{m},y_{1},\ldots,y_{n})$ (resp.
$\displaystyle\forall y_{1}\ldots\forall
y_{n}\;\psi(x_{1},\ldots,x_{m},y_{1},\ldots,y_{n})\text{\large)},$

for some $n\geq 0$ and an $\mathfrak{L}$-formula
$\psi(x_{1},\ldots,x_{m},y_{1},\ldots,y_{n})$ without quantifiers. Note that
the quantifiers appearing in $\varphi$ each range over one of the sorts of
$\mathfrak{L}$. We denote by $\mathrm{Sent}_{\exists}(\mathfrak{L})$,
respectively $\mathrm{Sent}_{\exists_{n}}(\mathfrak{L})$, the smallest
$\mathfrak{L}$-fragment containing all existential $\mathfrak{L}$-sentences,
respectively all existential $\mathfrak{L}$-sentences with at most $n$
quantifiers. Similarly, we denote by $\mathrm{Sent}_{\forall}(\mathfrak{L})$
and $\mathrm{Sent}_{\forall_{n}}(\mathfrak{L})$ the sets defined analogously
with universal sentences.

For an $\mathfrak{L}$-theory $T$, we write
$T_{\exists}=T_{\mathrm{Sent}_{\exists}(\mathfrak{L})}$,
$T_{\exists_{n}}=T_{\mathrm{Sent}_{\exists_{n}}(\mathfrak{L})}$,
$T_{\forall}=T_{\mathrm{Sent}_{\forall}(\mathfrak{L})}$, and
$T_{\forall_{n}}=T_{\mathrm{Sent}_{\forall_{n}}(\mathfrak{L})}$. For an
$\mathfrak{L}$-structure $M$ we also write ${\rm Th}_{\exists}(M)$ for ${\rm
Th}_{\mathrm{Sent}_{\exists}(\mathfrak{L})}(M)$ and so on.

######  Remark 3.2.

The fragments $\mathrm{Sent}_{\exists_{n}}(\mathfrak{L})$ form a chain,
ordered by inclusion, and the union is the fragment
$\mathrm{Sent}_{\exists}(\mathfrak{L})$. Similarly
$\mathrm{Sent}_{\forall}(\mathfrak{L})$ is the union of the chain of fragments
$\mathrm{Sent}_{\forall_{n}}(\mathfrak{L})$. By the definition of a fragment,
a sentence in ${\rm Sent}_{\exists}(\mathfrak{L})$ (respectively, ${\rm
Sent}_{\exists}(\mathfrak{L})$) is obtained from finitely many existential
(respectively, universal) $\mathfrak{L}$-sentences by conjunctions and
disjunctions. We remark that our use of $\exists_{n}$ and $\forall_{n}$ is
very different from the one in [Hod97], where for example an
"$\exists_{1}$-sentence" is an element of what we call ${\rm
Sent}_{\exists}(\mathfrak{L})$.

######  Remark 3.3.

When deciding the existential fragment of a complete $\mathfrak{L}$-theory,
i.e. ${\rm Th}_{\exists}(M)$ for some $\mathfrak{L}$-structure $M$, by
induction on the structure of formulas it suffices to decide which existential
$\mathfrak{L}$-sentences hold in $M$: $\varphi\wedge\psi\in{\rm
Th}_{\exists}(M)$ if and only if $\varphi\in{\rm Th}_{\exists}(M)$ and
$\psi\in{\rm Th}_{\exists}(M)$, and $\varphi\vee\psi\in{\rm Th}_{\exists}(M)$
if and only if $\varphi\in{\rm Th}_{\exists}(M)$ or $\psi\in{\rm
Th}_{\exists}(M)$. (This does not hold in general for possibly incomplete
theories.) The same goes for checking inclusions like ${\rm
Th}_{\exists}(M)\subseteq{\rm Th}_{\exists}(M^{\prime})$ for
$\mathfrak{L}$-structures $M,M^{\prime}$.

######  Definition 3.4.

Let

$\mathfrak{L}_{\mathrm{ring}}=\\{+,\cdot,-,0,1\\}$

be the language of rings, and let

$\displaystyle\mathfrak{L}_{\mathrm{val}}$
$\displaystyle=\\{+^{\mathbf{K}},-^{\mathbf{K}},\cdot^{\mathbf{K}},0^{\mathbf{K}},1^{\mathbf{K}},+^{\mathbf{k}},-^{\mathbf{k}},\cdot^{\mathbf{k}},0^{\mathbf{k}},1^{\mathbf{k}},+^{\mathbf{\Gamma}},<^{\mathbf{\Gamma}},0^{\mathbf{\Gamma}},\infty^{\mathbf{\Gamma}},v,\mathrm{res}\\}$

be the (three-sorted) language of valued fields, with a sort $\mathbf{K}$ for
the field itself, a sort $\mathbf{\Gamma}$ for the value group together with
infinity, and a sort $\mathbf{k}$ for the residue field, as well as symbols
$v$ for the valuation map and $\mathrm{res}$ for the residue map. We denote by
$\mathfrak{L}_{\mathrm{val}}(\varpi)$ the expansion of
$\mathfrak{L}_{\mathrm{val}}$ by a new constant symbol $\varpi$ in the sort
$\mathbf{K}$. A valued field $(K,v)$ gives rise in the usual way to an
$\mathfrak{L}_{\rm val}$-structure

$(K,vK\cup\\{\infty\\},Kv,v,\mathrm{res}),$

where $vK$ is the value group, $Kv$ is the residue field, and $\mathrm{res}$
is the residue map (set to $0\in Kv$ outside the valuation ring). For
notational simplicity, we will usually write $(K,v)$ to refer to the
$\mathfrak{L}_{\rm val}$-structure it induces.

######  Remark 3.5.

Since we are going to use results from [AF16] we should point out that the
definition of $\exists$-sentence used there, namely "logically equivalent to a
formula in prenex normal form with only existential quantifiers" is not
suitable for the arguments about decidability given there nor for our use
here. In fact, in general it is not possible to decide whether a given
sentence is an $\exists$-sentence in that sense: For example, if
$\mathfrak{L}=\\{R\\}$ with a binary predicate symbol $R$, and $T=\emptyset$,
then $T^{\vdash}$ is undecidable since it encodes graph theory (which is
undecidable, see e.g. [FJ08, Corollary 28.5.3]), but $T_{\exists}$ is
trivially decidable, which implies that it is not possible to decide whether a
given sentence $\varphi$ is equivalent to some $\psi\in{\rm
Sent}_{\exists}(\mathfrak{L})$, as such a $\psi$ could be found effectively.
However, this poses no problems for either the results in [AF16] or our
application here, as one can simply replace the definition of
$\exists$-sentence by being an element of what we here call the existential
fragment ${\rm Sent}_{\exists}$, and then everything goes through.

######  Remark 3.6.

We might instead work in a one-sorted language of valued fields
$\mathfrak{L}_{O}=\mathfrak{L}_{\rm ring}\cup\\{O\\}$, where $O$ is a unary
predicate and a valued field $(K,v)$ gives rise to an
$\mathfrak{L}_{O}$-structure by interpreting $O$ by the valuation ring
$\mathcal{O}_{v}$. As there is a uniform biinterpretation $\Gamma$ between the
$\mathfrak{L}_{\rm val}$-structure $(K,v)$ and the
$\mathfrak{L}_{O}$-structure $(K,\mathcal{O}_{v})$ in which each defining
formula $\varphi_{\Gamma}$ (see the introduction) is equivalent modulo the
theory of valued fields to both an existential and a universal formula, all
our results for the fragment ${\rm Sent}_{\exists}(\mathfrak{L}_{\rm val})$
carry over to ${\rm Sent}_{\exists}(\mathfrak{L}_{O})$.

###  3.2. PAC fields

Let $\mathbf{PAC}$ be the $\mathfrak{L}_{\mathrm{ring}}$-theory of PAC fields
and $\mathbf{F}$ the $\mathfrak{L}_{\mathrm{ring}}$-theory of fields. We
denote by $\mathrm{PAC}$ the context
$(\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}}),\mathbf{PAC})$ and accordingly
by $\mathrm{PAC}_{\exists}$ and $\mathrm{PAC}_{\exists_{1}}$ the contexts with
fragments ${\rm Sent}_{\exists}(\mathfrak{L}_{\mathrm{ring}})$ respectively
${\rm Sent}_{\exists_{1}}(\mathfrak{L}_{\mathrm{ring}})$. Similarly, we define
the contexts $\mathrm{F}$, $\mathrm{F}_{\exists}$ and
$\mathrm{F}_{\exists_{1}}$. Further we define the bridge
$\mathrm{PAC}_{\exists_{1}}.\mathrm{PAC}=(\mathrm{PAC}_{\exists_{1}},\mathrm{PAC},{\rm
id})$, and similarly the bridges
$\mathrm{PAC}_{\exists_{1}}.\mathrm{PAC}_{\exists}$,
$\mathrm{F}_{\exists_{1}}.\mathrm{PAC}$,
$\mathrm{F}_{\exists_{1}}.\mathrm{PAC}_{\exists_{1}}$ and
$\mathrm{F}_{\exists_{1}}.\mathrm{PAC}_{\exists}$ (also with
$\sigma=\mathrm{id}$). Together with the interpretation $\iota={\rm id}$, we
thus obtain the arches
$\mathrm{F}_{\exists_{1}}.\mathrm{PAC}_{\exists_{1}}|\mathrm{F}_{\exists_{1}}.\mathrm{PAC}$
and
$\mathrm{PAC}_{\exists_{1}}.\mathrm{PAC}_{\exists}|\mathrm{PAC}.\mathrm{PAC}$.

######  Lemma 3.7.

Let $E,F$ be extensions of a field $K$ with $F$ PAC and $E/K$ separable. We
view $E$ and $F$ as $\mathfrak{L}_{\rm ring}(K)$-structures. If ${\rm
Th}_{\exists_{1}}(E)\subseteq{\rm Th}_{\exists_{1}}(F)$, then ${\rm
Th}_{\exists}(E)\subseteq{\rm Th}_{\exists}(F)$.

###### Proof.

Let $E_{0}=E\cap\bar{K}$. The assumption ${\rm
Th}_{\exists_{1}}(E)\subseteq{\rm Th}_{\exists_{1}}(F)$ implies that there
exists a $K$-embedding of $E_{0}$ into $F$ [FJ08, Lemma 20.6.3], so assume
without loss of generality that $E_{0}\subseteq F$. Since $E/K$ is separable,
$E/E_{0}$ is regular. This implies that $F\otimes_{E_{0}}E$ is an integral
domain [Bou07, Ch. V §17 Proposition 8], and so $L:={\rm
Quot}(F\otimes_{E_{0}}E)$ is a field that is the compositum of the linearly
disjoint extensions $F/E_{0}$ and $E/E_{0}$. In particular, $L/F$ is regular,
so since $F$ is PAC, it is existentially closed in $L$ [FJ08, Proposition
11.3.5]. Thus, for the $\mathfrak{L}_{\rm ring}(K)$-theories we have ${\rm
Th}_{\exists}(F)={\rm Th}_{\exists}(L)\supseteq{\rm Th}_{\exists}(E)$. ∎

######  Lemma 3.8.

  1. $(a)$

Hypotheses (i)–(iii) of Corollary 2.23 hold for the arch
$\mathrm{PAC}_{\exists_{1}}.\mathrm{PAC}_{\exists}|\mathrm{PAC}.\mathrm{PAC}$.

  2. $(b)$

Hypotheses (i)–(iii) of Corollary 2.23 hold for the arch
$\mathrm{F}_{\exists_{1}}.\mathrm{PAC}_{\exists_{1}}|\mathrm{F}_{\exists_{1}}.\mathrm{PAC}$.

###### Proof.

For (i): The fact that the fragments are computable is clear in both cases.
Just like the theory $\mathbf{F}$, the theory $\mathbf{PAC}$ is computably
enumerable since it has a computable axiomatization, see e.g. [FJ08,
Proposition 11.3.2].

For (ii): In case (a) this is trivial. For (b), for every $K\models\mathbf{F}$
there exists a regular extension $F/K$ which is PAC, by [FJ08, Proposition
13.4.6], so $F\models\mathbf{PAC}$ and ${\rm Th}_{\exists_{1}}({\rm
id}(F))={\rm Th}_{\exists_{1}}(F)={\rm Th}_{\exists_{1}}(K)$.

For (iii): In case (b) this is trivial. For (a), given PAC fields
$M,M^{\prime}$ with ${\rm Th}_{\exists_{1}}(M)\subseteq{\rm
Th}_{\exists_{1}}(M^{\prime})$, we have that ${\rm char}(M)={\rm
char}(M^{\prime})$, so without loss of generality, $M$ and $M^{\prime}$ have
the same prime field $K$. Since $K$ is perfect, Lemma 3.7 then implies that
${\rm Th}_{\exists}(M)\subseteq{\rm Th}_{\exists}(M^{\prime})$. ∎

######  Corollary 3.9.

  1. $(a)$

    1. (I)

$\mathrm{PAC}_{\exists_{1}}.\mathrm{PAC}_{\exists}$ admits a computable
elimination
$\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{ring}})\longrightarrow\mathrm{Sent}_{\exists_{1}}(\mathfrak{L}_{\mathrm{ring}})$.

    2. (II)

For every $R\subseteq\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$,
$(\mathbf{PAC}\cup R)_{\exists_{1}}\simeq_{\rm m}(\mathbf{PAC}\cup
R)_{\exists}$.

    3. (III)

$\mathrm{Th}_{\exists}(K)=(\mathbf{PAC}\cup\mathrm{Th}_{\exists_{1}}(K))_{\exists}$,
for each PAC field $K$.

  2. $(b)$

    1. (II)

For every
$R\subseteq\mathrm{Sent}_{\exists_{1}}(\mathfrak{L}_{\mathrm{ring}})$,
$(\mathbf{F}\cup R)_{\exists_{1}}\simeq_{\rm m}(\mathbf{PAC}\cup
R)_{\exists_{1}}$.

######  Remark 3.10.

Corollary 3.9(a) is already implicit in [vdD91, Prop. 2.2], cf. also [DDF21,
Prop. 4.22] for existential formulas over perfect PAC fields. We could have
defined the bridges $\mathrm{F}_{\exists_{1}}.\mathrm{PAC}_{\exists}$ and
$\mathrm{F}_{\exists_{1}}.\mathrm{PAC}_{\exists_{1}}$ instead of with
$\sigma={\rm id}$ also with $\sigma$ the map that sends a field $K$ to its
algebraic part $K_{\rm alg}$, the relative algebraic closure of the prime
field of $K$ in $K$.

Combining Corollary 3.9(aII) and (bII), we get that $(\mathbf{F}\cup
R)_{\exists_{1}}\simeq_{\rm m}(\mathbf{PAC}\cup R)_{\exists}$ for every
$R\subseteq\mathrm{Sent}_{\exists_{1}}(\mathfrak{L}_{\mathrm{ring}})$. We will
generalize this in Corollary 3.13, using the following lemma that strengthens
Corollary 3.9(bII).

######  Lemma 3.11.

For $R\subseteq{\rm Sent}_{\exists}(\mathfrak{L}_{\rm ring})$,
$(\mathbf{F}\cup R)_{\exists_{1}}=(\mathbf{PAC}\cup R)_{\exists_{1}}$.

###### Proof.

The inclusion $(\mathbf{F}\cup R)_{\exists_{1}}\subseteq(\mathbf{PAC}\cup
R)_{\exists_{1}}$ is trivial. For the other inclusion let
$\varphi\in(\mathbf{PAC}\cup R)_{\exists_{1}}$ and $K\models\mathbf{F}\cup R$.
By [FJ08, Proposition 13.4.6] there exists a regular extension $F/K$ with $F$
PAC. Since $R\subseteq{\rm Sent}_{\exists}(\mathfrak{L}_{\rm ring})$, we have
$F\models\mathbf{PAC}\cup R$, hence $F\models\varphi$. Moreover, since
$\varphi\in{\rm Sent}_{\exists_{1}}(\mathfrak{L}_{\rm ring})$ and $K$ is
algebraically closed in $F$, this implies $K\models\varphi$. ∎

######  Remark 3.12.

We note that $(\mathbf{F}\cup R)_{\exists_{1}}=(\mathbf{PAC}\cup
R)_{\exists_{1}}$ need not hold for arbitrary $R\subseteq{\rm
Sent}(\mathfrak{L}_{\rm ring})$, as the case $R={\rm Th}(K)$ for any non-PAC
field $K$ shows, and one can also see that in general not even
$(\mathbf{F}\cup R)_{\exists_{1}}\simeq_{\rm T}(\mathbf{PAC}\cup
R)_{\exists_{1}}$ must hold.

######  Corollary 3.13.

For $R\subseteq{\rm Sent}_{\exists}(\mathfrak{L}_{\rm ring})$,
$(\mathbf{F}\cup R)_{\exists_{1}}\simeq_{\rm m}(\mathbf{PAC}\cup
R)_{\exists}$.

######  Remark 3.14.

We briefly describe another approach to obtain Corollary 3.13. First we
consider a weakening of the hypothesis (ii) of Corollary 2.23 to the
following:

  1. (ii’)

for every $N\models T_{1}$, there exists $M\models T_{2}$ such that
$\mathrm{Th}_{\hat{L}_{1}}(N)\subseteq\mathrm{Th}_{\hat{L}_{1}}(\sigma M)$ and
$\mathrm{Th}_{L_{1}}(N)=\mathrm{Th}_{L_{1}}(\sigma M)$.

Next one can prove an adaptation of Corollary 2.23: Suppose an arch
$(B,\hat{B},\iota)$ satisfies the hypotheses (i,ii’,iii) of Corollary 2.23.
Then $B$ admits a computable elimination and $(T_{1}\cup R)_{L_{1}}\simeq_{\rm
m}(T_{2}\cup\iota R)_{L_{2}}$, for each $R\subseteq\hat{L}_{1}$. One can show
that $\check{B}$ (defined as in Lemma 2.21) satisfies (sur) using only (ii’)
and not the full strength of (ii). Finally, using again [FJ08, Proposition
13.4.6] one sees that hypotheses (i,ii’,iii) of Corollary 2.23 hold for
$\mathrm{F}_{\exists_{1}}.\mathrm{PAC}_{\exists}|\mathrm{F}_{\exists}.\mathrm{PAC}$.

######  Remark 3.15.

While it is known by work of Cherlin, van den Dries and Macintyre that the
theory of a PAC field is determined by its algebraic part, its degree of
imperfection and the theory of the inverse system of its absolute Galois
group, we see here that for the existential theory only the first of these
three plays a role. If we would restrict our attention to PAC fields that are
for example perfect and $\omega$-free (equivalently, Hilbertian), we could
obtain computable eliminations even for the full theory, but since this is
essentially well known and our focus in this paper are existential theories,
we do not pursue this and only remark that Corollary 3.9(aII) readily applies
to the theory $\mathbf{hPAC}$ of Hilbertian PAC fields, and also Lemma 3.11
holds with $\mathbf{PAC}$ replaced by $\mathbf{hPAC}$ since the quoted [FJ08,
Proposition 13.4.6] actually gives a Hilbertian PAC field $F$.

###  3.3. Equicharacteristic henselian valued fields: $\exists$-theories

We denote by $\mathbf{H}^{e\prime}$ the $\mathfrak{L}_{\mathrm{val}}$-theory
of equicharacterstic henselian nontrivially valued fields, and by
$\mathbf{H}^{e,\varpi}$ (resp., $\mathbf{H}^{e,\varpi}_{0}$) the
$\mathfrak{L}_{\mathrm{val}}(\varpi)$-theory of equicharacteristic (resp.,
equicharacteristic zero) henselian valued fields in which the interpretation
of $\varpi$ is a uniformizer (i.e. an element of minimal positive value). We
define the contexts
$\mathrm{H}^{e\prime}:=(\mathrm{Sent}(\mathfrak{L}_{\mathrm{val}}),\mathbf{H}^{e\prime})$
and
$\mathrm{H}^{e\prime}_{\exists}:=(\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}}),\mathbf{H}^{e\prime})$,
and analogously $\mathrm{H}^{e,\varpi}$ and $\mathrm{H}^{e,\varpi}_{0}$ with
fragment ${\rm Sent}(\mathfrak{L}_{\rm val}(\varpi))$, and
$\mathrm{H}^{e,\varpi}_{\exists}$ and $\mathrm{H}^{e,\varpi}_{0,\exists}$ with
fragment ${\rm Sent}_{\exists}(\mathfrak{L}_{\rm val}(\varpi))$.

We denote by $\mathbf{F}_{0}$ the theory of fields of characteristic zero and
define the contexts
$\mathrm{F}_{0}=(\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}}),\mathbf{F}_{0})$
and analogously $\mathrm{F}_{0,\exists}$. We denote by $\sigma_{\mathbf{k}}$
the map that sends a valued field $(K,v)$ to its residue field $Kv$. Thus by
equipping each with an appropriate restriction of $\sigma_{\mathbf{k}}$ we
have the bridges $\mathrm{F}.\mathrm{H}^{e\prime}$,
$\mathrm{F}_{\exists}.\mathrm{H}^{e\prime}_{\exists}$,
$\mathrm{F}_{0}.\mathrm{H}^{e,\varpi}_{0}$,
$\mathrm{F}_{0,\exists}.\mathrm{H}^{e,\varpi}_{0,\exists}$,
$\mathrm{F}.\mathrm{H}^{e,\varpi}$, and
$\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}$.

######  Definition 3.16.

For an $\mathfrak{L}_{\mathrm{ring}}$-term $t$ we define an
$\mathfrak{L}_{\mathrm{val}}$-term $t_{\mathbf{k}}$ by recursion on the length
of $t$ as follows: for a variable $x$ we let $x_{\mathbf{k}}$ be a variable of
the residue field sort; we let $0_{\mathbf{k}}:=0^{\mathbf{k}}$ and
$1_{\mathbf{k}}:=1^{\mathbf{k}}$; for $t=t_{1}+t_{2}$ we let
$t_{\mathbf{k}}=(t_{1})_{\mathbf{k}}+^{\mathbf{k}}(t_{2})_{\mathbf{k}}$,
similarly for $t=t_{1}-t_{2}$ and $t=t_{1}\cdot t_{2}$. For an
$\mathfrak{L}_{\mathrm{ring}}$-formula $\varphi$ we define an
$\mathfrak{L}_{\mathrm{val}}$-formula $\varphi_{\mathbf{k}}$ by recursion on
the length of $\varphi$ as follows: if
$\varphi=t_{1}\stackrel{{\scriptstyle.}}{{=}}t_{2}$, we let
$\varphi_{\mathbf{k}}=(t_{1})_{\mathbf{k}}\stackrel{{\scriptstyle.}}{{=}}(t_{2})_{\mathbf{k}}$;
if $\varphi=\neg\psi$, we define
$\varphi_{\mathbf{k}}:=\neg\psi_{\mathbf{k}}$; if $\varphi=(\psi\wedge\rho)$,
we define $\varphi_{\mathbf{k}}:=(\psi_{\mathbf{k}}\wedge\rho_{\mathbf{k}})$;
and if $\varphi=\exists x\;\psi$, we define $\varphi_{\mathbf{k}}:=\exists
x\in\mathbf{k}\;\psi_{\mathbf{k}}$. Finally, define
$\iota_{\mathbf{k}}:\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})\longrightarrow\mathrm{Sent}(\mathfrak{L}_{\mathrm{val}})\subseteq\mathrm{Sent}(\mathfrak{L}_{\mathrm{val}}(\varpi))$,
given by $\varphi\longmapsto\varphi_{\mathbf{k}}$.

######  Remark 3.17.

The map $\iota_{\mathbf{k}}$ is an interpretation for the bridge
$(\mathrm{F},\mathrm{VF},\sigma_{\mathbf{k}})$, where $\mathbf{VF}$ is the
$\mathfrak{L}_{\mathrm{val}}$-theory of valued fields, and $\mathrm{VF}$ is
the context $(\mathrm{Sent}(\mathfrak{L}_{\mathrm{val}}),\mathbf{VF})$.
Equipped with the appropriate restrictions of $\iota_{\mathbf{k}}$ we get
arches
$\mathrm{F}_{\exists}.\mathrm{H}^{e\prime}_{\exists}|\mathrm{F}.\mathrm{H}^{e\prime}$,
$\mathrm{F}_{0,\exists}.\mathrm{H}^{e,\varpi}_{0,\exists}|\mathrm{F}_{0}.\mathrm{H}^{e,\varpi}_{0}$
and
$\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}|\mathrm{F}.\mathrm{H}^{e,\varpi}$,
where we use that
$\iota_{\mathbf{k}}(\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{ring}}))\subseteq\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}})\subseteq\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}}(\varpi))$.

######  Remark 3.18.

A field $K$ is large if it is existentially closed in $K(\\!(t)\\!)$, see
[Pop96, BF13, Pop14] for background on large fields. To apply our machinery to
the arch
$\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}|\mathrm{F}.\mathrm{H}^{e,\varpi}$,
more precisely to verify (mon) for
$\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}$, we will work under the
following hypothesis, introduced in [ADF23, §2]:

  1. (R4)

Every large field $K$ is existentially closed in every extension $F/K$ for
which there exists a valuation $v$ on $F/K$ with residue field $Fv=K$.

As discussed in [ADF23, Proposition 2.3], (R4) is a consequence of Local
Uniformization, which is in turn implied by Resolution of Singularities. For a
ring $C$ we also consider the hypothesis (R4)C, which we define as (R4)
restricted to large fields $K$ that admit a ring homomorphism $C\rightarrow
K$. Since (R4) holds when restricted to perfect fields $K$ [ADF23, Remark
2.4], in particular (R4)Q holds.

######  Lemma 3.19.

  1. $(a)$

Hypotheses (i)–(iii) of Corollary 2.23 hold for
$\mathrm{F}_{\exists}.\mathrm{H}^{e\prime}_{\exists}|\mathrm{F}.\mathrm{H}^{e\prime}$.

  2. $(b)$

Hypotheses (i)–(iii) of Corollary 2.23 hold for
$\mathrm{F}_{0,\exists}.\mathrm{H}^{e,\varpi}_{0,\exists}|\mathrm{F}_{0}.\mathrm{H}^{e,\varpi}_{0}$.

  3. $(c)$

Hypotheses (i)–(ii) of Corollary 2.23 hold for
$\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}|\mathrm{F}.\mathrm{H}^{e,\varpi}$,
and if in addition (R4) holds, then so does hypothesis (iii).

###### Proof.

For (i): The fact that the fragments and $\iota_{\mathbf{k}}$ are computable
is clear in both cases. The theories $\mathbf{H}^{e\prime}$ and
$\mathbf{H}^{e,\varpi}$ are computably enumerable since they have computable
axiomatizations, see e.g. [ADF23, Remark 4.8], taking Remark 3.6 into account.

For (ii): let $k$ be a field. Then $(k(\\!(t)\\!),v_{t})$ is an
equicharacteristic henselian nontrivially valued field with residue field $k$,
of which $t$ is a uniformizer. In particular,
$\sigma_{\mathbf{k}}:\mathrm{Mod}(\mathbf{H}^{e,\varpi})\longrightarrow\mathrm{Mod}(\mathbf{F})$
is surjective, and so (ii) follows in both cases.

For (iii) in (a): let $(K,v),(L,w)\models\mathbf{H}^{e\prime}$ and suppose
that $Kv\models\mathrm{Th}_{\exists}(Lw)$. That is
$(K,v)\models\mathbf{H}^{e\prime}\cup\iota_{\mathbf{k}}\mathrm{Th}_{\exists}(Lw)$.
By [AF16, Lemma 6.3]222Alternatively, one may apply Lemma 2.24 taking
$R=\mathrm{Th}(Lw)$.,
$\mathbf{H}^{e\prime}\cup\iota_{\mathbf{k}}\mathrm{Th}_{\exists}(Lw)\models(\mathbf{H}^{e\prime}\cup\iota_{\mathbf{k}}\mathrm{Th}(Lw))_{\exists}$.
By [AF16, Lemma 6.1],
$\mathbf{H}^{e\prime}\cup\iota_{\mathbf{k}}\mathrm{Th}(Lw)\models\mathrm{Th}_{\exists}(L,w)$.
Then $(K,v)\models\mathrm{Th}_{\exists}(L,w)$, and therefore
$\mathrm{F}_{\exists}.\mathrm{H}^{e\prime}_{\exists}$ satisfies (mon).

For (iii) in (c): (R4) implies that
$\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}$ satisfies (mon) by
[ADF23, Proposition 4.11] (again, note Remark 3.6), taking $C$ to be the
subfield $\mathbb{F}(\pi)$ generated by the uniformizer $\pi$ and the prime
subfield $\mathbb{F}$, together with the $\pi$-adic valuation $v_{\pi}$. Note
that the valuation ring of $v_{\pi}$ is excellent.

For (iii) in (b): as for (c) except applying (R4)Q instead of (R4): by [ADF23,
Remark 4.18] we may apply [ADF23, Proposition 4.11] to
$(C,u)=(\mathbb{Q}(\pi),v_{\pi})$, noting that the valuation ring of $v_{\pi}$
is excellent, the separability hypotheses are satisfied in characteristic
zero. ∎

######  Corollary 3.20.

  1. $(a)$

    1. (I)

$\mathrm{F}_{\exists}.\mathrm{H}^{e\prime}_{\exists}$ admits a computable
elimination
$\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}})\longrightarrow\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{ring}})$.

    2. (II)

For every $R\subseteq{\rm Sent}(\mathfrak{L}_{\mathrm{ring}})$,
$(\mathbf{F}\cup R)_{\exists}\simeq_{\rm
m}(\mathbf{H}^{e\prime}\cup\iota_{\mathbf{k}}R)_{\exists}$.

    3. (III)

For every $(K,v)\models\mathbf{H}^{e\prime}$,
$\mathrm{Th}_{\exists}(K,v)=(\mathbf{H}^{e\prime}\cup\iota_{\mathbf{k}}\mathrm{Th}_{\exists}(Kv))_{\exists}$.

  2. $(b)$

    1. (I)

$\mathrm{F}_{0,\exists}.\mathrm{H}^{e,\varpi}_{0,\exists}$ admits a computable
elimination
$\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}}(\varpi))\longrightarrow\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{ring}})$.

    2. (II)

For every $R\subseteq{\rm Sent}(\mathfrak{L}_{\mathrm{ring}})$,
$(\mathbf{F}_{0}\cup R)_{\exists}\simeq_{\rm
m}(\mathbf{H}^{e,\varpi}_{0}\cup\iota_{\mathbf{k}}R)_{\exists}$.

    3. (III)

For every $(K,v,\pi_{K})\models\mathbf{H}^{e,\varpi}_{0}$,
$\mathrm{Th}_{\exists}(K,v,\pi_{K})=(\mathbf{H}^{e,\varpi}_{0}\cup\iota_{\mathbf{k}}\mathrm{Th}_{\exists}(Kv))_{\exists}$.

  3. $(c)$

Suppose (R4).

    1. (I)

$\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}$ admits a computable
elimination
$\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}}(\varpi))\longrightarrow\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{ring}})$.

    2. (II)

For every $R\subseteq{\rm Sent}(\mathfrak{L}_{\mathrm{ring}})$,
$(\mathbf{F}\cup R)_{\exists}\simeq_{\rm
m}(\mathbf{H}^{e,\varpi}\cup\iota_{\mathbf{k}}R)_{\exists}$.

    3. (III)

For every $(K,v,\pi_{K})\models\mathbf{H}^{e,\varpi}$,
$\mathrm{Th}_{\exists}(K,v,\pi_{K})=(\mathbf{H}^{e,\varpi}\cup\iota_{\mathbf{k}}\mathrm{Th}_{\exists}(Kv))_{\exists}$.

######  Remark 3.21.

By Lemma 2.25, Lemma 3.19 and therefore also each of the parts of Corollary
3.20 remains true if we replace each $\exists$ by $\forall/\exists$, denoting,
in each of the respective languages, the set of finite conjunctions and
disjunctions of existential or universal sentences. For example, for every
$R\subseteq{\rm Sent}(\mathfrak{L}_{\mathrm{ring}})$, $(\mathbf{F}\cup
R)_{\forall/\exists}\simeq_{\rm
m}(\mathbf{H}^{e\prime}\cup\iota_{\mathbf{k}}R)_{\forall/\exists}$. Similar
extensions hold for several of the results in the rest of this paper, but we
will not spell them out each time.

Although we have only proved (mon) for the bridge
$\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}$ under the hypothesis
(R4), we are able to prove (wm) unconditionally:

######  Lemma 3.22.

The fragment extension
$\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}\sqsubseteq\mathrm{F}.\mathrm{H}^{e,\varpi}$
satisfies (wm).

###### Proof.

Let $(K,v,\pi)\models\mathbf{H}^{e,\varpi}$ and $k\models\mathbf{F}$ with
$\mathrm{Th}_{\exists}(k)\subseteq\mathrm{Th}_{\exists}(Kv)$. Without loss of
generality, $(K,v,\pi)$ is $|k|^{+}$-saturated, and then so is $Kv$. This
implies that there exists an embedding $\varphi:k\rightarrow Kv$, see [CK90,
Lemma 5.2.1]. By [ADF23, Lemma 4.4] there exists an elementary extension
$(K,v)\prec(K^{*},v^{*})$ with a partial section $\zeta:Kv\rightarrow K^{*}$
of ${\rm res}_{v^{*}}$. The composition $\zeta\circ\varphi:k\longrightarrow
K^{*}$ is an embedding of fields, and moreover is an embedding of valued
fields when $k$ is equipped with the trivial valuation. Mapping $t\mapsto\pi$
and using the universal property of henselisations, we may extend
$\zeta\circ\varphi$ to an embedding of valued fields
$(k(t)^{h},v_{t},t)\longrightarrow(K^{*},v^{*},\pi)$. Thus
$\mathrm{Th}_{\exists}(k(t)^{h},v_{t},t)\subseteq\mathrm{Th}_{\exists}(K^{*},v^{*},\pi_{K})=\mathrm{Th}_{\exists}(K,v,\pi_{K})$.
Note that the residue field of $(k(t)^{h},v_{t},t)$ is $k$, in particular it
is elementarily equivalent to $k$. ∎

###  3.4. Equicharacteristic henselian valued fields: $\exists_{n}$-theories

For $n\geq 0$, we define the contexts
$\mathrm{H}^{e\prime}_{\exists_{n}}:=(\mathrm{Sent}_{\exists_{n}}(\mathfrak{L}_{\mathrm{val}}),\mathbf{H}^{e\prime})$
and
$\mathrm{F}_{\exists_{n}}:=(\mathrm{Sent}_{\exists_{n}}(\mathfrak{L}_{\mathrm{ring}}),\mathbf{F})$,
as well as the bridge
$\mathrm{F}_{\exists_{n}}.\mathrm{H}^{e\prime}_{\exists_{n}}$. As
$\iota_{\mathbf{k}}(\mathrm{Sent}_{\exists_{n}}(\mathfrak{L}_{\mathrm{ring}}))\subseteq\mathrm{Sent}_{\exists_{n}}(\mathfrak{L}_{\mathrm{val}})$,
we obtain an arch
$\mathrm{F}_{\exists_{n}}.\mathrm{H}^{e\prime}_{\exists_{n}}|\mathrm{F}.\mathrm{H}^{e\prime}$.

######  Lemma 3.23.

Let $\mathfrak{L}$ be a language and let $M,N$ be $\mathfrak{L}$-structures.
If $\mathfrak{L}$ contain no constant symbols assume that $n\geq 1$.

  1. $(a)$

$\mathrm{Th}_{\exists}(M)\subseteq\mathrm{Th}_{\exists}(N)$ if and only if
$\mathrm{Th}_{\exists}(M^{\prime})\subseteq\mathrm{Th}_{\exists}(N)$ for every
finitely generated substructure $M^{\prime}\subseteq M$.

  2. $(b)$

$\mathrm{Th}_{\exists_{n}}(M)\subseteq\mathrm{Th}_{\exists_{n}}(N)$ if and
only if $\mathrm{Th}_{\exists}(M^{\prime})\subseteq\mathrm{Th}_{\exists}(N)$
for every substructure $M^{\prime}\subseteq M$ generated by at most $n$
elements.

###### Proof.

Part (a) follows immediately from (b), and the latter is what we prove: For
$\Leftarrow$ let $\varphi\in{\rm Th}_{\exists_{n}}(M)$. Without loss of
generality, $\varphi$ is of the form $\exists
y_{1},\dots,y_{n}\psi(\underline{y})$ with $\psi$ quantifier-free. Then
$M\models\psi(\underline{b})$ for some $\underline{b}\in M^{n}$, and
$\underline{b}$ generates a substructure $M^{\prime}$ of $M$ with
$M^{\prime}\models\varphi$, hence $\varphi\in{\rm
Th}_{\exists_{n}}(M^{\prime})\subseteq{\rm Th}_{\exists_{n}}(N)$.

For $\Rightarrow$, let $M^{\prime}\subseteq M$ be generated by
$a_{1},\dots,a_{n}$, and let $\varphi\in{\rm Th}_{\exists}(M^{\prime})$,
without loss of generality of the form $\exists
y_{1},\dots,y_{m}\psi(\underline{y})$ for some $m$. Then
$M^{\prime}\models\psi(\underline{b})$ for some $b_{1},\dots,b_{m}\in
M^{\prime}$, and $b_{i}=t_{i}(a_{1},\dots,a_{n})$ for an $\mathfrak{L}$-term
$t_{i}$, for each $i$. Thus $\exists
x_{1},\dots,x_{n}\psi(t_{1}(\underline{x}),\dots,t_{m}(\underline{x}))\in{\rm
Th}_{\exists_{n}}(M)\subseteq{\rm Th}_{\exists_{n}}(N)$, and so there are
$c_{1},\dots,c_{n}\in N$ with
$N\models\psi(t_{1}(\underline{c}),\dots,t_{m}(\underline{c}))$, in particular
$\varphi\in{\rm Th}_{\exists}(N)$. ∎

######  Lemma 3.24.

Hypotheses (i)–(iii) of Corollary 2.23 hold for
$\mathrm{F}_{\exists_{n}}.\mathrm{H}^{e\prime}_{\exists_{n}}|\mathrm{F}.\mathrm{H}^{e\prime}$.

###### Proof.

For (i): this is again clear.

For (ii): this is again clear, see Lemma 3.19(a).

For (iii): Let $(K,v),(L,w)\models\mathbf{H}^{e\prime}$ and suppose
$\mathrm{Th}_{\exists_{n}}(Kv)\subseteq\mathrm{Th}_{\exists_{n}}(Lw)$. Without
loss of generality, $(L,w)$ is $\aleph_{0}$-saturated. We will show that ${\rm
Th}_{\exists}(M^{\prime})\subseteq{\rm Th}_{\exists}(L,w)$ for every
$\mathfrak{L}_{\rm val}$-substructure $M^{\prime}$ of $(K,v)$ generated by at
most $n$ elements, which by Lemma 3.23(b) will imply that
$\mathrm{Th}_{\exists_{n}}(K,v)\subseteq\mathrm{Th}_{\exists_{n}}(L,w)$.
Without loss of generality assume that $M^{\prime}$ is generated by at most
$n$ elements in the sort $\mathbf{K}$, in particular
$R_{0}=M^{\prime\mathbf{K}}$ is a ring generated by at most $n$ elements. Let
$E={\rm Frac}(R_{0})$, let $u=v|_{E}$ and note that ${\rm
Th}_{\exists}(M^{\prime})\subseteq{\rm Th}_{\exists}(E,u)$.

First we consider the case that $u$ is trivial. Then $(E,u)$ is isomorphic to
the trivially valued field $(Eu,v_{\mathrm{triv}})$, and this isomorphism
carries $R_{0}$ to a subring of $Eu$, which we denote $R_{0}u$. Indeed,
$R_{0}u$ is a subring of $Kv$ generated by at most $n$ elements, so
$\mathrm{Th}_{\exists}(R_{0}u)\subseteq\mathrm{Th}_{\exists}(Lw)$ by Lemma
3.23(b). As $Lw$ is $\aleph_{0}$-saturated and $R_{0}$ is countable, there
exists an $\mathfrak{L}_{\rm ring}$-embedding $R_{0}u\longrightarrow Lw$
([CK90, Lemma 5.2.1]). This extends to an
$\mathfrak{L}_{\mathrm{ring}}$-embedding
$\eta:Eu=\mathrm{Frac}(R_{0}u)\longrightarrow Lw$, which already shows that
$\mathrm{Th}_{\exists}(Eu)\subseteq\mathrm{Th}_{\exists}(Lw)$. Since
$\eta(Eu)$ is a finitely generated field extension of its prime field, it is
separably generated, so there is an embedding $\zeta:\eta(Eu)\longrightarrow
L$ such that $\mathrm{res}_{w}\circ\zeta=\mathrm{id}_{\eta(Eu)}$, see [AF16,
Lemma 2.3]. It follows that $w$ is trivial on the image of $\eta(Eu)$, thus we
have an $\mathfrak{L}_{\mathrm{val}}$-embedding
$(\eta(Eu),v_{\mathrm{triv}})\longrightarrow(L,w)$. This shows that ${\rm
Th}_{\exists}(E,u)=\mathrm{Th}_{\exists}(Eu,v_{\mathrm{triv}})=\mathrm{Th}_{\exists}(\eta(Eu),v_{\mathrm{triv}})\subseteq\mathrm{Th}_{\exists}(L,w)$.

Second we consider the case that $u$ is nontrivial. Let $\mathbb{F}$ be the
prime field of $Eu$, and let $R\subseteq Eu$ be a finitely generated subring
of $Eu$. The field of fractions $F=\mathrm{Frac}(R)$ is a finitely generated
subfield of $Eu$. Since $u$ is nontrivial,
$\mathrm{trdeg}(F/\mathbb{F})<\mathrm{trdeg}(E/\mathbb{F})\leq n$ by the
Abhyankar inequality [EP05, Theorem 3.4.3]. Since $F/\mathbb{F}$ is separable
and finitely generated, there exists a separating transcendence base
$T\subseteq F$. Thus the field extension $F/\mathbb{F}(T)$ is finite and
separable, and therefore generated by a single element $a$, by the primitive
element theorem. Let $S\subseteq F$ be the subring generated by
$T\cup\\{a\\}$. Then $S$ is a subring of $Kv$ that is generated by at most
$|T|+1\leq n$ elements, and ${\rm Frac}(S)=F$. Thus, by Lemma 3.23(b),
$\mathrm{Th}_{\exists}(S)\subseteq\mathrm{Th}_{\exists}(Lw)$, which as argued
for $R_{0}u$ and $Eu$ in the previous paragraph, implies that
$\mathrm{Th}_{\exists}(F)\subseteq\mathrm{Th}_{\exists}(Lw)$. We have thus
shown that ${\rm Th}_{\exists}(R)\subseteq\mathrm{Th}_{\exists}(Lw)$ for every
finitely generated $\mathfrak{L}_{\rm ring}$-substructure $R$ of $Eu$, which
by Lemma 3.23(a) gives that
$\mathrm{Th}_{\exists}(Eu)\subseteq\mathrm{Th}_{\exists}(Lw)$. Since by Lemma
3.19(a) $\mathrm{F}_{\exists}.\mathrm{H}^{e\prime}_{\exists}$ satisfies (mon),
we have
$\mathrm{Th}_{\exists}(E^{h},u^{h})\subseteq\mathrm{Th}_{\exists}(L,w)$, where
$(E^{h},u^{h})\supseteq(E,u)$ denotes the henselization, which is also of
equal characteristic and has residue field $Eu$. Therefore
$\mathrm{Th}_{\exists}(E,u)\subseteq\mathrm{Th}_{\exists}(L,w)$. ∎

######  Corollary 3.25.

  1. (I)

$\mathrm{F}_{\exists_{n}}.\mathrm{H}^{e\prime}_{\exists_{n}}$ admits a
computable elimination
$\mathrm{Sent}_{\exists_{n}}(\mathfrak{L}_{\mathrm{val}})\longrightarrow\mathrm{Sent}_{\exists_{n}}(\mathfrak{L}_{\mathrm{ring}})$.

  2. (II)

For every $R\subseteq\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$,
$(\mathbf{F}\cup R)_{\exists_{n}}\simeq_{\rm
m}(\mathbf{H}^{e\prime}\cup\iota_{\mathbf{k}}R)_{\exists_{n}}$.

  3. (III)

For every $(K,v)\models\mathbf{H}^{e\prime}$,
$\mathrm{Th}_{\exists_{n}}(K,v)=(\mathbf{H}^{e\prime}\cup\iota_{\mathbf{k}}\mathrm{Th}_{\exists_{n}}(Kv))_{\exists_{n}}$.

######  Proposition 3.26.

$\mathrm{F}_{\exists}.\mathrm{H}^{e\prime}_{\exists}$ admits a computable
elimination
$\epsilon:\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}})\rightarrow\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{ring}})$
that for each $n\in\mathbb{N}$ restricts to an elimination
$\mathrm{Sent}_{\exists_{n}}(\mathfrak{L}_{\mathrm{val}})\rightarrow\mathrm{Sent}_{\exists_{n}}(\mathfrak{L}_{\mathrm{ring}})$
of $\mathrm{F}_{\exists_{n}}.\mathrm{H}^{e\prime}_{\exists_{n}}$.

###### Proof.

This is an adaptation of the proof of Proposition 2.18. We use two uniform
aspects of the computability of the fragments of existential sentences.
Firstly, the function
$e:\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}})\rightarrow\mathbb{N}\cup\\{0\\}$,
$\psi\mapsto\min\\{n\in\mathbb{N}\mid\psi\in\mathrm{Sent}_{\exists_{n}}(\mathfrak{L}_{\mathrm{val}})\\}$
is computable. Secondly, we may fix a computable function
$\mathbb{N}\times\mathbb{N}\rightarrow\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{ring}})$,
$(n,m)\mapsto\varphi_{n,m}$, such that $\varphi_{n,1},\varphi_{n,2},\dots$ is
an enumeration of $\mathrm{Sent}_{\exists_{n}}(\mathfrak{L}_{\mathrm{ring}})$,
for each $n$. We can also fix a computable enumeration $P_{1},P_{2},\dots$ of
the proofs from $\mathbf{H}^{e\prime}$, since the latter is computably
enumerable. By Corollary 3.25(I), given
$\psi\in\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}})$ there exist $l$
and $m$ such that $P_{l}$ is a proof of
$\mathbf{H}^{e\prime}\vdash\psi\leftrightarrow\iota_{\mathbf{k}}\varphi_{e(\varphi),m}$.
We take such pair $(l,m)$ minimial with respect to the ordering (2.9) and
define $\epsilon\psi:=\varphi_{e(\psi),m}$. ∎

Theorem 1.1 follows from Corollaries 3.20(aII,cII) and 3.25(II).

##  4\. Limit theories

By analogy with the notion of characteristic in the theory of fields, we study
extensions of theories defined by a sequence of sentences, including limit
cases.

###  4.1. All, almost all, and uniform

Fix a language $\mathfrak{L}$ and a sequence of $\mathfrak{L}$-sentences
$(\rho_{n})_{n\in\mathbb{N}}$.

######  Definition 4.1.

For any $\mathfrak{L}$-theory $T$, we define

$\displaystyle T_{0}$ $\displaystyle:=$ $\displaystyle(T\cup\\{\rho_{n}\mid
n\in\mathbb{N}\\})^{\vdash}$ $\displaystyle T_{n}$ $\displaystyle:=$
$\displaystyle(T\cup\\{\rho_{1},\ldots,\rho_{n-1},\neg\rho_{n}\\})^{\vdash},\quad
n\in\mathbb{N}$ $\displaystyle T_{>m}$ $\displaystyle:=$
$\displaystyle\bigcap_{n>m}T_{n},\quad m\in\mathbb{N}\cup\\{0\\}$
$\displaystyle T_{\gg 0}$ $\displaystyle:=$
$\displaystyle\bigcup_{m\in\mathbb{N}}\bigcap_{n\geq m}T_{n}$ $\displaystyle
T_{N}$ $\displaystyle:=$ $\displaystyle\\{(\varphi,n)\mid n\in N,\varphi\in
T_{n}\\},\quad N\subseteq\mathbb{N}\cup\\{0\\}.$

For an $\mathfrak{L}$-fragment $L$, by analogy with above we write
$T_{N,L}=T_{N}\cap(L\times(\mathbb{N}\cup\\{0\\}))$.

######  Example 4.2.

We will apply this definition in Section 5 mainly in the case where $T$ is
some theory of (possibly valued) fields and $\rho_{n}$ is a quantifier-free
sentence expressing that the characteristic is not $n$, so that $T_{0}$,
$T_{n}$, $T_{>m}$ and $T_{\gg 0}$ are, respectively, the sets of sentences
true in all models of $T$ of characteristic zero, all models of $T$ of
characteristic $n$, all models of $T$ of characteristic greater than $m$, and
all models of $T$ of sufficiently large positive characteristic.

Note that every model of $T$ is a model of $T_{n}$ for exactly one
$n\in\mathbb{N}\cup\\{0\\}$. The models of $T_{>0}$ and $T_{\gg 0}$ can be
described as follows:

######  Proposition 4.3.

Let $T$ be an $\mathfrak{L}$-theory, and let $M$ be an
$\mathfrak{L}$-structure.

  1. (a)

$M\models T_{>0}$ if and only if $M\equiv\prod_{i\in I}M_{i}/\mathcal{U}$ for
some ultrafilter $\mathcal{U}$ on a set $I$, and $M_{i}\models T_{n_{i}}$ for
some $n_{i}\in\mathbb{N}$.

  2. (b)

$M\models T_{\gg 0}$ if and only if $M\models T_{>0}\cup T_{0}$

###### Proof.

(a): $T_{>0}$ is the common theory of the models of $T_{n}$, for
$n\in\mathbb{N}$, so the implication $\Rightarrow$ follows from [CK90,
Exercise 4.1.18], and $\Leftarrow$ follows from Łoś’s theorem since
$T_{n_{i}}\supseteq T_{>0}$.

(b): $\Rightarrow$ is trivial from the definitions. Suppose $M\models
T_{>0}\cup T_{0}$. Then $M\equiv\prod_{i\in I}M_{i}/\mathcal{U}$, as in $(a)$.
For $l>0$, $M\models\rho_{l}$, therefore by Łoś’s theorem $\\{i\in I\mid
n_{i}=l\\}\notin\mathcal{U}$. Thus for every $m\geq 0$, $\\{i\in I\mid
n_{i}>m\\}\in\mathcal{U}$, and so $M\models T_{>m}$, again by Łoś’s theorem. ∎

######  Proposition 4.4.

Let $T,S$ be $\mathfrak{L}$-theories such that $\neg\rho\in L$ for every
$\rho\in S$. Then

  1. $(a)$

$(T_{L}\cup S)_{L}=(T\cup S)_{L}$.

Consequently, if $\neg\rho_{n}\in L$ for every $n\in\mathbb{N}$, then

  1. $(b)$

$(T_{L})_{0,L}=T_{0,L}$,

  2. $(c)$

$(T_{L})_{n,L}=T_{n,L}$ for every $n\in\mathbb{N}$,

  3. $(d)$

$(T_{L})_{>m,L}=T_{>m,L}$ for every $m\in\mathbb{Z}_{\geq 0}$,

  4. $(e)$

$(T_{L})_{\gg 0,L}=T_{\gg 0,L}$, and

  5. $(f)$

$(T_{L})_{N,L}=T_{N,L}$ for every $N\subseteq\mathbb{N}\cup\\{0\\}$.

###### Proof.

For (a), the inclusion $\subseteq$ is clear since $(T\cup
S)_{L}=(T^{\vdash}\cup S)_{L}$ and $T_{L}\subseteq T^{\vdash}$. Now let
$\varphi\in(T\cup S)_{L}$. Then there exist $\rho_{1},\ldots,\rho_{m}\in S$
such that $T\cup\\{\rho_{1},\ldots,\rho_{m}\\}\vdash\varphi$, and equivalently
$T\vdash(\bigvee_{j=1}^{m}\neg\rho_{j}\big{)}\vee\varphi$. Since
$(\bigvee_{j=1}^{m}\neg\rho_{j}\big{)}\vee\varphi\in L$, we have
$(\bigvee_{j=1}^{m}\neg\rho_{j}\big{)}\vee\varphi\in T_{L}$, in particular
$T_{L}\cup\\{\rho_{1},\ldots,\rho_{m}\\}\vdash\varphi$. Thus
$\varphi\in(T_{L}\cup S)_{L}$, which proves $(a)$. Both (b) and (c) are
special cases of (a), and (d) and (e) follow easily. Finally, (f) follows
directly from (b) and (c). ∎

###  4.2. Turing reductions

We keep notations and definitions from the previous subsection.

######  Proposition 4.5.

Let $T$ be an $\mathfrak{L}$-theory, let $L$ be a computable
$\mathfrak{L}$-fragment with $\rho_{n},\neg\rho_{n}\in L$ for every $n$, and
assume that the function $n\mapsto\rho_{n}$ is computable. Then

  1. $(a)$

$T_{0,L}\leq_{\rm T}T_{L}\oplus T_{>0,L}\oplus T_{\gg 0,L}$, and

  2. $(b)$

if $T_{>0,L}$ and $T_{\gg 0,L}$ are decidable, then $T_{L}\simeq_{\rm
m}T_{0,L}$.

Let in addition $T^{\prime}$ be an $\mathfrak{L}$-theory with
$T^{\prime}_{L}\subseteq T_{L}$ and $T_{\gg 0,L}=T^{\prime}_{\gg 0,L}$. Then

  1. $(c)$

$T_{>0,L}\leq_{\rm T}T_{\gg 0,L}\oplus T^{\prime}_{>0,L}\oplus
T_{\mathbb{N},L}$, and

  2. $(d)$

if $T^{\prime}_{\gg 0,L}$ and $T^{\prime}_{>0,L}$ are decidable, then
$T_{>0,L}\simeq_{\rm T}T_{\mathbb{N},L}$ and $T_{L}\simeq_{\rm T}T_{0,L}\oplus
T_{>0,L}\simeq_{\rm T}T_{\mathbb{N}\cup\\{0\\},L}$.

The rest of this subsection is devoted to the proof of Proposition 4.5, and
for this we will denote333Note that e.g. by $\Sigma_{0}$ we do not mean the
first part of Definition 4.1 applied to $T=\Sigma$, instead $\Sigma_{0}$ is
$(T_{L})_{0,L}$. $\Sigma:=T_{L}$, $\Sigma_{0}:=(T_{L})_{0}\cap L$,
$\Sigma_{n}:=(T_{L})_{n}\cap L$, $\Sigma_{>m}:=(T_{L})_{>m}\cap L$,
$\Sigma_{\gg 0}:=(T_{L})_{\gg 0}\cap L$, $\Sigma_{N}:=\\{(\varphi,n):n\in
N,\varphi\in\Sigma_{n}\\}$. For $\varphi\in L$ and $n\in\mathbb{N}\cup\\{0\\}$
we will (only in this section) denote

$\varphi_{n}\;:=\;\varphi\vee\bigvee_{i=1}^{n}\neg\rho_{i}\;\in L$

where it is understood that $\varphi_{0}=\varphi$.

######  Lemma 4.6.

We have $\Sigma=\Sigma_{0}\cap\Sigma_{>0}$. In particular, if $\Sigma_{>0}$ is
decidable, then $\Sigma\leq_{\rm m}\Sigma_{0}$.

###### Proof.

The inclusion from left to right is trivial. For the converse inclusion, let
$\varphi\in\Sigma_{0}\cap\Sigma_{>0}$. From $\varphi\in\Sigma_{0}$ we see that
$\Sigma\vdash\varphi_{n}$ for some minimal $n$. So if $n>0$, then
$\Sigma\vdash\varphi_{n-1}\vee\neg\rho_{n}$, and
$\varphi\in\Sigma_{>0}\subseteq\Sigma_{n}$ implies that
$\Sigma\vdash\varphi_{n-1}\vee\rho_{n}$, hence $\Sigma\vdash\varphi_{n-1}$,
contradicting the minimality of $n$. Thus $n=0$ and
$\varphi=\varphi_{0}\in\Sigma$. ∎

######  Lemma 4.7.

We have $\Sigma_{0}\leq_{\rm T}\Sigma\oplus\Sigma_{>0}\oplus\Sigma_{\gg 0}$.
Moreover, if $\Sigma_{>0}$ and $\Sigma_{\gg 0}$ are decidable, then
$\Sigma_{0}\leq_{\rm m}\Sigma$.

###### Proof.

Suppose that there are algorithms $A_{\Sigma},A_{\Sigma_{>0}},A_{\Sigma_{\gg
0}}$ to decide the theories $\Sigma,\Sigma_{>0},\Sigma_{\gg 0}$. We outline an
algorithm to decide $\Sigma_{0}$.

  1. —

Input. $\varphi\in L$

  2. —

Step 1. Apply $A_{\Sigma_{\gg 0}}$ to decide whether or not
$\varphi\in\Sigma_{\gg 0}$. If ‘NO’ then in particular we have
$\varphi\notin\Sigma_{0}$, so we output ‘NO’ and finish. If else ‘YES’ then we
continue.

  3. —

Step 2. Since $\varphi\in\Sigma_{\gg 0}$ there exists $m\in\mathbb{N}$ such
that $\varphi\in\bigcap_{n\geq m}\Sigma_{n}$. So since
$\Sigma_{n}\models\neg\rho_{n}$ we obtain
$\varphi_{m}\in\bigcap_{n>0}\Sigma_{n}=\Sigma_{>0}$. Apply $A_{\Sigma_{>0}}$
to $\varphi_{0},\varphi_{1},\dots$ until we find the minimal $m_{0}$ with
$\varphi_{m_{0}}\in\Sigma_{>0}$.

  4. —

Step 3. Apply $A_{\Sigma}$ to decide whether or not
$\varphi_{m_{0}}\in\Sigma$.

     * •

If ‘YES’ then in particular we have $\varphi_{m_{0}}\in\Sigma_{0}$. Since also
$\Sigma_{0}\vdash\bigwedge_{i=1}^{m_{0}}\rho_{i}$, it follows that
$\Sigma_{0}\vdash\varphi$, i.e. $\varphi\in\Sigma_{0}$. We output ‘YES’ and
finish.

     * •

If ‘NO’, on the other hand, then $\varphi_{m_{0}}\notin\Sigma$. Since we
already know $\varphi_{m_{0}}\in\Sigma_{>0}$, it follows from Lemma 4.6 that
$\varphi_{m_{0}}\notin\Sigma_{0}$. Therefore $\varphi\notin\Sigma_{0}$. We
output ‘NO’ and finish. ∎

This proves the Turing reduction. If both $\Sigma_{>0}$ and $\Sigma_{\gg 0}$
are decidable, $A_{\Sigma}$ is the only oracle occurring in the above
algorithm, and it gives the many-one reduction $\Sigma_{0}\leq_{\rm m}\Sigma$.

######  Lemma 4.8.

$\Sigma_{\mathbb{N}}\leq_{\rm m}\Sigma$ and $\Sigma_{\mathbb{N}}\leq_{\rm
m}\Sigma_{>0}$.

###### Proof.

For $\varphi\in L$ and $n\in\mathbb{N}$, let $\psi=\varphi_{n-1}\vee\rho_{n}$.
Then $(\varphi,n)\in\Sigma_{\mathbb{N}}$ if and only if $\psi\in\Sigma$.
Moreover, $\psi\in\Sigma$ if and only if $\psi\in\Sigma_{>0}$. Indeed,
$\Sigma\subseteq\Sigma_{>0}\subseteq\Sigma_{n}$, and $\Sigma\vdash\psi$ if and
only if $\Sigma_{n}\vdash\psi$. ∎

######  Lemma 4.9.

Let $\Sigma^{\prime}\subseteq\Sigma$ with $\Sigma^{\prime}_{\gg 0}=\Sigma_{\gg
0}$. Then $\Sigma_{>0}\leq_{\rm T}\Sigma_{\gg
0}\oplus\Sigma^{\prime}_{>0}\oplus\Sigma_{\mathbb{N}}$.

###### Proof.

Suppose there are algorithms $A_{\Sigma_{\mathbb{N}}}$,
$A_{\Sigma^{\prime}_{>0}}$ and $A_{\Sigma_{\gg 0}}$ to decide
$\Sigma_{\mathbb{N}}$, $\Sigma^{\prime}_{>0}$ and $\Sigma_{\gg 0}$. We outline
an algorithm to decide $\Sigma_{>0}$.

  1. —

Input. $\varphi\in L$.

  2. —

Step 1. Apply $A_{\Sigma_{\gg 0}}$ to decide whether or not
$\varphi\in\Sigma_{\gg 0}$. If ‘NO’ then in particular
$\varphi\notin\Sigma_{>0}$, so we output ‘NO’ and finish. If else ‘YES’ then
we continue.

  3. —

Step 2. Since $\Sigma^{\prime}_{\gg 0}=\Sigma_{\gg 0}\models\varphi$ there
exists $m\in\mathbb{N}$ such that $\Sigma^{\prime}_{n}\models\varphi$ for
every $n\geq m$. In particular, $\Sigma^{\prime}_{n}\models\varphi_{m}$ for
every $n>0$, i.e. $\Sigma^{\prime}_{>0}\models\varphi_{m}$. Apply
$A_{\Sigma^{\prime}_{>0}}$ to $\varphi_{0},\varphi_{1},\dots$ until we find
the minimal $m_{0}$ with $\varphi_{m_{0}}\in\Sigma^{\prime}_{>0}$.

  4. —

Step 3. Since $\Sigma^{\prime}\subseteq\Sigma$ and
$\varphi_{m_{0}}\in\Sigma^{\prime}_{>0}$, also
$\varphi_{m_{0}}\in\Sigma_{>0}$, hence
$\varphi\in\bigcap_{n>m_{0}}\Sigma_{n}$. We now use $A_{\Sigma_{\mathbb{N}}}$
to check if $(\varphi,1),\dots,(\varphi,m_{0})\in\Sigma_{\mathbb{N}}$. If yes
then $\varphi\in\bigcap_{n>0}\Sigma_{n}=\Sigma_{>0}$ and we output ‘YES’,
otherwise we output ‘NO’.∎

###### Proof of Proposition 4.5.

By Proposition 4.4 it suffices to prove statements with $T_{0,L}$ replaced by
$(T_{L})_{0,L}=\Sigma_{0}$, $T_{>0,L}$ replaced by
$(T_{L})_{>0,L}=\Sigma_{>0}$, etc., which we do now:

(a): This is Lemma 4.7.

(b): If $\Sigma_{>0}$ and $\Sigma_{\gg 0}$ are decidable, $\Sigma\leq_{\rm
m}\Sigma_{0}$ follows from Lemma 4.6, and $\Sigma_{0}\leq_{\rm m}\Sigma$ from
Lemma 4.7.

(c): This is Lemma 4.9.

(d): $\Sigma_{>0}\leq_{\rm T}\Sigma_{\mathbb{N}}$ is (c) and
$\Sigma_{>0}\geq_{T}\Sigma_{\mathbb{N}}$ is Lemma 4.8. The reduction
$\Sigma\leq_{\rm T}\Sigma_{0}\oplus\Sigma_{>0}$ is Lemma 4.6, and
$\Sigma\geq_{\mathrm{T}}\Sigma_{>0}$ follows from Lemma 4.8 and (c), and
$\Sigma\oplus\Sigma_{>0}\geq_{\mathrm{T}}\Sigma_{0}$ from (a). Thus
$\Sigma\simeq_{\rm T}\Sigma_{0}\oplus\Sigma_{>0}$. Trivially
$\Sigma_{0}\oplus\Sigma_{>0}\simeq_{\rm T}\Sigma_{\mathbb{N}\cup\\{0\\}}$. ∎

###  4.3. Limit arches

Let $A=(B,\hat{B},\iota)$ be an arch. We write $B=(C_{1},C_{2},\sigma)$ and
$\hat{B}=(\hat{C}_{1},\hat{C}_{2},\sigma)$, where $C_{i}=(L_{i},T_{i})$ is a
subcontext of $\hat{C}_{i}=(\hat{L}_{i},T_{i})$, for $i=1,2$. Let
$(\rho_{n})_{n\in\mathbb{N}}$ be a sequence of $\mathfrak{L}_{1}$-sentences,
with $\rho_{n},\neg\rho_{n}\in L_{1}$ for every $n$. Let
$(\iota\rho_{n})_{n\in\mathbb{N}}$ be the corresponding sequence of
$\mathfrak{L}_{2}$-sentences.

For an $\mathfrak{L}_{1}$-theory $R$, we write
$T_{2}(R)=T_{2}\cup\iota(R_{\hat{L}_{1}})$. We will use the notation
introduced in Definition 4.1, first with $T=R$ and the sentences
$(\rho_{n})_{n\in\mathbb{N}}$, leading to theories $R_{0}$, $R_{n}$, $R_{>m}$,
$R_{\gg 0}$, and second with $T=T_{2}(R)$ and the sentences
$(\iota\rho_{n})_{n\in\mathbb{N}}$, leading to theories $T_{2}(R)_{0}$,
$T_{2}(R)_{n}$, $T_{2}(R)_{>m}$, $T_{2}(R)_{\gg 0}$. In particular we have
theories $T_{1,0}$, $T_{1,n}$, $T_{1,>m}$, $T_{1,\gg 0}$, $T_{2,0}$,
$T_{2,n}$, $T_{2,>m}$, $T_{2,\gg 0}$. We moreover extend one of these
notations to contexts and bridges: For $i=1,2$, let $C_{i,0}=(L_{i},T_{i,0})$
and note that $B_{0}:=(C_{1,0},C_{2,0},\sigma|_{\mathrm{Mod}(T_{2,0})})$ is a
bridge.

######  Remark 4.10.

Note that the deductive closure of $T_{2}(R)$ does not depend on the choice of
interpretation $\iota$: we have $M\models T_{2}(R)$ if and only if $M\models
T_{2}$ and $\sigma M\models R_{\hat{L}_{1}}$. Moreover, if
$R\subseteq\hat{L}_{1}$ then $(T_{2}\cup\iota
R)^{\vdash}=T_{2}(R)^{\vdash}=(T_{2}\cup\iota((T_{1}\cup
R)_{\hat{L}_{1}}))^{\vdash}$ by Lemma 2.21; and if instead $R\supseteq T_{1}$
then again $T_{2}(R)^{\vdash}=(T_{2}\cup\iota((T_{1}\cup
R)_{\hat{L}_{1}})^{\vdash}$.

######  Proposition 4.11.

  1. $(a)$

$(T_{2})^{\vdash}=T_{2}(T_{1})^{\vdash}$.

  2. $(b)$

$T_{2,n}=T_{2}(T_{1,n})^{\vdash}$, for all $n\in\mathbb{N}\cup\\{0\\}$.

  3. $(c)$

If $B$ satisfies (sur) and $B_{0}$ satisfies (mon), then
$(T_{2,>m})_{L_{2}}=T_{2}(T_{1,>m})_{L_{2}}$, for all $m\geq 0$.

  4. $(d)$

If $B$ satisfies (sur) and $B_{0}$ satisfies (mon), then $(T_{2,\gg
0})_{L_{2}}=T_{2}(T_{1,\gg 0})_{L_{2}}$.

###### Proof.

  1. $(a)$

We apply Lemma 2.21 to the bridge $\hat{B}$ and $R=\emptyset$.

  2. $(b)$

Let $n\in\mathbb{N}$. We have assumed that
$\rho_{n},\neg\rho_{n}\in{L}_{1}\subseteq\hat{L}_{1}$, thus
$\iota\rho_{n},\iota\neg\rho_{n}\in\hat{L}_{2}$, since $\iota$ is an
interpretation for $\hat{B}$. For $M\models T_{2}$, we have
$M\models\neg\iota\rho_{n}\Leftrightarrow\sigma
M\models\neg\rho_{n}\Leftrightarrow M\models\iota\neg\rho_{n}$. Thus (*):
$T_{2}\models(\neg\iota\rho_{n}\leftrightarrow\iota\neg\rho_{n})$. Together
with $T_{2}(R)^{\vdash}=(T_{2}\cup\iota((T_{1}\cup
R)_{\hat{L}_{1}}))^{\vdash}$ for
$R=\\{\rho_{1},\dots,\rho_{n-1},\neg\rho_{n}\\}$ by Lemma 2.21, we obtain
$T_{2,n}=T_{2}(T_{1,n})^{\vdash}$, and similarly
$T_{2,0}=T_{2}(T_{1,0})^{\vdash}$.

  3. $(c)$

By (b), for each $n>m$ we have $T_{1,n}\supseteq T_{1,>m}$, and therefore
$T_{2,n}=T_{2}(T_{1,n})^{\vdash}\supseteq T_{2}(T_{1,>m})^{\vdash}$. Thus
$(T_{2,>m})_{L_{2}}\supseteq T_{2}(T_{1,>m})_{L_{2}}$.

Conversely, let $M\models T_{2}(T_{1,>m})$ so that $\sigma
M\models(T_{1,>m})_{\hat{L}_{1}}$. Note that
$T_{1,>m}\models\rho_{1}\wedge\ldots\wedge\rho_{m}$ and
$\rho_{1}\wedge\ldots\wedge\rho_{m}\in L_{1}\subseteq\hat{L}_{1}$. Thus
$\sigma M\models\rho_{1}\wedge\ldots\wedge\rho_{m}$, and therefore also
$M\models\iota\rho_{1}\wedge\ldots\wedge\iota\rho_{m}$ (Lemma 2.17). There are
two cases:

First, if $M\models T_{2,n}$ for some $n>0$, then necessarily $n>m$, and so
$M\models T_{2,>m}$.

Otherwise, in the second case, we have $M\models T_{2,0}$, whence $\sigma
M\models(T_{1,0})_{\hat{L}_{1}}$ by (b). In particular $\sigma
M\models\rho_{n}$, for all $n>0$. Since $\sigma M$ is a model of
$(T_{1,>m})_{\hat{L}_{1}}$, by Lemma 2.29 there exists $N\models T_{1,>m}$
such that $\sigma M\models\mathrm{Th}_{\hat{L}_{1}}(N)$. Since
$\neg\rho_{n}\in L_{1}\subseteq\hat{L}_{1}$ and $\sigma
M\not\models\neg\rho_{n}$, also $N\not\models\neg\rho_{n}$, i.e.
$N\models\rho_{n}$, for all $n>0$. It follows that $N\models T_{1,0}$. Let
$S=T_{1}\cup\\{\rho_{1},\ldots,\rho_{m}\\}$ and write $\sigma_{n}=\rho_{m+n}$,
for $n\in\mathbb{N}$. We apply the notation from Definition 4.1 to the
$\mathfrak{L}_{1}$-theory $S$ and the sequence of $\mathfrak{L}_{1}$-sentences
$(\sigma_{n})_{n\in\mathbb{N}}$. Then $S_{n}=T_{1,m+n}$ for each $n>0$, and so
$S_{>0}=T_{1,>m}$ and $S_{0}=T_{1,0}$. It follows that $N\models S_{>0}\cup
S_{0}$. By Proposition 4.3(a), $N\equiv\prod_{i\in I}H_{i}/\mathcal{U}$ for a
set $I$, an ultrafilter $\mathcal{U}$ on $I$ and $H_{i}\models S_{n_{i}}$ for
some $n_{i}\in\mathbb{N}$. By (sur) for ${B}$, for each $i\in I$ there exists
$K_{i}\models T_{2}$ with
$\mathrm{Th}_{L_{1}}(H_{i})=\mathrm{Th}_{L_{1}}(\sigma K_{i})$. It follows
that $\sigma K_{i}\models S_{n_{i}}$, hence $K_{i}\models T_{2,m+n_{i}}$, for
each $i\in I$, and so $K_{i}\models T_{2,>m}$. Denote $K:=\prod_{i\in
I}K_{i}/\mathcal{U}$. By Łoś’s theorem, $\mathrm{Th}_{L_{1}}(\sigma
K)=\mathrm{Th}_{L_{1}}(\prod_{i\in I}\sigma
K_{i}/\mathcal{U})=\mathrm{Th}_{L_{1}}(N)$. So since $N\models S_{0}$ it
follows that $K\models T_{2,0}\cup T_{2,>m}$. Thus, $\sigma
M\models\mathrm{Th}_{{L}_{1}}(\sigma K)$, in particular
$\mathrm{Th}_{L_{1}}(\sigma K)\subseteq\mathrm{Th}_{L_{1}}(\sigma M)$. Since
$B_{0}$ satisfies (mon), we conclude that
$\mathrm{Th}_{L_{2}}(K)\subseteq\mathrm{Th}_{L_{2}}(M)$.

Therefore, in both cases, $M\models(T_{2,>m})_{L_{2}}$. Thus
$T_{2}(T_{1,>m})\models(T_{2,>m})_{L_{2}}$, and hence
$(T_{2,>m})_{L_{2}}\subseteq T_{2}(T_{1,>m})_{L_{2}}$.

  4. $(d)$

Both $T_{2,\gg 0}$ and $T_{2}(T_{1,\gg 0})$ are unions of chains. Thus

$\displaystyle(T_{2,\gg 0})_{L_{2}}=\bigcup_{m\geq
0}(T_{2,>m})_{L_{2}}\overset{\text{(c)}}{=}\bigcup_{m\geq
0}T_{2}(T_{1,>m})_{L_{2}}=\Big{(}\bigcup_{m\geq
0}T_{2}(T_{1,>m})\Big{)}_{L_{2}}=T_{2}(T_{1,\gg 0})_{L_{2}},$

as required. ∎

##  5\. Existential theories of fields with varying characteristic

Throughout this section we consider the language
$\mathfrak{L}_{1}=\mathfrak{L}_{\mathrm{ring}}$ and we fix the sequence
$(\rho_{n})_{n\in\mathbb{N}}$ defined by writing $\rho_{n}$ for the
quantifier-free $\mathfrak{L}_{\rm ring}$-sentence

$\displaystyle\neg\underbrace{1+\ldots+1}_{n}\dot{=}0,$

for each $n\in\mathbb{N}$. Note that $n\mapsto\rho_{n}$ is computable.

For an arch $A=(B,\hat{B},\iota)$ we write $B=(C_{1},C_{2},\sigma)$ and
$\hat{B}=(\hat{C}_{1},\hat{C}_{2},\sigma)$, where $C_{i}=(L_{i},T_{i})$ is a
subcontext of $\hat{C}_{i}=(\hat{L}_{i},T_{i})$, for $i=1,2$. For all such
arches $A$ considered in this section, $C_{1}$ and $\hat{C}_{1}$ are
$\mathfrak{L}_{1}$-contexts, $L_{1}$ contains the quantifier-free
$\mathfrak{L}_{\mathrm{ring}}$-sentences (thus $\rho_{n},\neg\rho_{n}\in
L_{1}$ for every $n$), $\iota(L_{1})\subseteq L_{2}$, and $B$ satisfies (sur).
Thus we may use the notation from Section 4.3, building on Definition 4.1:
first with an $\mathfrak{L}_{1}$-theory $T=R$ and the sentences
$(\rho_{n})_{n\in\mathbb{N}}$, and second with $T=T_{2}(R)$ and the sentences
$(\iota\rho_{n})_{n\in\mathbb{N}}$.

######  Remark 5.1.

For an $\mathfrak{L}_{1}$-theory $R$ of fields, let $S$ denote either $R$ or
$T_{2}(R)$. Then $S_{n}$ is consistent only if $n$ is prime or $0$; and
$S_{>0}=\bigcap_{p\in\mathbb{P}}S_{p}$ and $S_{\gg
0}=\bigcup_{m\in\mathbb{N}}\bigcap_{p\geq m,p\in\mathbb{P}}S_{p}$. We also
follow the convention from Definition 3.1 to write $S_{\exists}$,
$S_{n,\exists}$, etc., for $S_{L}$, $(S_{n})_{L}$, etc., when $L={\rm
Sent}_{\exists}(\mathfrak{L}_{i})$. Moreover by Proposition 4.4(b,d) and Lemma
4.6 we have $S_{\exists}=\bigcap_{p\in\mathbb{P}\cup\\{0\\}}S_{p,\exists}$.

######  Remark 5.2.

Consider the arch
$A=B|\hat{B}=\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}|\mathrm{F}.\mathrm{H}^{e,\varpi}$
together with the sentences $(\rho_{n})_{n\in\mathbb{N}}$ defined above.
Applying the extended notations of Section 4.3 we have the bridge
$B_{0}=(C_{1,0},C_{2,0},\sigma|_{\mathrm{Mod}((\mathbf{H}^{e,\varpi})_{0})})$
where
$C_{2,0}=(\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}}),(\mathbf{H}^{e,\varpi})_{0})$
and
$(\mathbf{H}^{e,\varpi})_{0}=(\mathbf{H}^{e,\varpi}\cup\\{\iota_{\mathbf{k}}\rho_{n}\mid
n\in\mathbb{N}\\})^{\vdash}$.

In Section 3 we had already defined the theory $\mathbf{H}^{e,\varpi}_{0}$ to
be the theory of equicharacteristic zero henselian valued fields, which is
clearly axiomatized by
$\mathbf{H}^{e,\varpi}\cup\\{\iota_{\mathbf{k}}\rho_{n}\mid
n\in\mathbb{N}\\}$. Thus
$\mathbf{H}^{e,\varpi}_{0}=(\mathbf{H}^{e,\varpi})_{0}$. Similarly we had
defined the contexts
$\mathrm{H}^{e,\varpi}_{0}=(\mathrm{Sent}(\mathfrak{L}_{\mathrm{val}}),\mathbf{H}^{e,\varpi}_{0})$
and
$\mathrm{H}^{e,\varpi}_{0,\exists}=(\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}}),\mathbf{H}^{e,\varpi}_{0})$.
We observe that there is no ambiguity between the notation introduced in
sections 3 and 4.3. In particular, we have
$B_{0}=\mathrm{F}_{0,\exists}.\mathrm{H}^{e,\varpi}_{0,\exists}$.

######  Remark 5.3.

We make use of the following basic facts: If $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ are two classes structures in some language $\mathfrak{L}$,
such that for every $M\in\mathcal{C}_{1}$ there exists $N\in\mathcal{C}_{2}$
with either $N\subseteq M$ or $M\preceq_{\exists}N$, then ${\rm
Th}_{\exists}(\mathcal{C}_{1})\supseteq{\rm Th}_{\exists}(\mathcal{C}_{2})$.
If in addition $\mathcal{C}_{1}\supseteq\mathcal{C}_{2}$, then ${\rm
Th}_{\exists}(\mathcal{C}_{1})={\rm Th}_{\exists}(\mathcal{C}_{2})$. In
particular, if $R_{1},R_{2}$ are two $\mathfrak{L}$-theories such that for
every $M\models R_{1}$ there exists $N\models R_{2}$ with either $N\subseteq
M$ or $M\preceq_{\exists}N$, then $R_{1,\exists}\supseteq R_{2,\exists}$, and
if in addition $R_{1}\subseteq R_{2}$, then $R_{1,\exists}=R_{2,\exists}$.

######  Remark 5.4.

For any theory $T$ of fields we have $T_{\exists}\subseteq
T_{0,\exists},T_{>0,\exists}\subseteq T_{\gg 0,\exists}$ (cf. Proposition
4.3). If $T$ has models of every characteristic, then the sentence $1+1\neq 0$
is in $T_{0,\exists}$ but not in $T_{>0,\exists}$, hence
$T_{\exists}\subsetneqq T_{0,\exists}$ and $T_{>0,\exists}\subsetneqq T_{\gg
0,\exists}$. If $T$ has a model of characteristic zero in which $\mathbb{Q}$
is algebraically closed, then $\exists x(x^{2}=2\vee x^{2}=3\vee x^{2}=6)$ is
in $T_{>0,\exists}$ but not in $T_{0,\exists}$, hence $T_{\exists}\subsetneqq
T_{>0,\exists}$ and $T_{0,\exists}\subsetneqq T_{\gg 0,\exists}$.

###  5.1. Prime fields

Recall that $\mathbf{F}$ denotes the theory of fields. Denote
$\mathbb{F}_{0}=\mathbb{Q}$ and let
$\mathbf{P}=\bigcap_{p\in\mathbb{P}\cup\\{0\\}}{\rm Th}(\mathbb{F}_{p})$ be
the theory of prime fields.

######  Remark 5.5.

Ax proved in [Ax68] that $\mathbf{P}_{>0}$ and $\mathbf{P}_{\gg 0}$ are
decidable [FJ08, Corollary 20.9.6, Theorem 20.9.7]. Moreover, with ${\bf Fin}$
the theory of finite fields and ${\bf Psf}$ the theory of pseudofinite fields
(i.e. the infinite models of the theory of finite fields), Ax’s work also
shows that $\mathbf{Psf}_{0}={\bf Psf}_{\gg 0}=\mathbf{P}_{\gg
0}=\mathbf{Fin}_{\gg 0}$: Indeed, for every $K\models{\bf Psf}_{0}$ there is
an ultrafilter $\mathcal{U}$ on $\mathbb{P}$ such that
$K\equiv\prod_{p\in\mathbb{P}}\mathbb{F}_{p}/\mathcal{U}\models\mathbf{P}_{\gg
0}$ [Ax68, Thm. 8”]. Moreover, every $K\models\mathbf{Fin}_{\gg 0}$ is
elementarily equivalent to an ultraproduct
$\prod_{p\in\mathbb{P}}K_{p}/\mathcal{U}$ with each $K_{p}$ a finite field of
characteristic $p$ (Proposition 4.3), and if $F_{p}$ is any pseudofinite field
in which $K_{p}$ is algebraically closed (which exists by [Ax68, Thm. 7,8]),
then
$\prod_{p\in\mathbb{P}}K_{p}/\mathcal{U}\equiv\prod_{p\in\mathbb{P}}F_{p}/\mathcal{U}\models\mathbf{Psf}_{\gg
0}$ [Ax68, Thm. 4]. Thus, $\mathbf{Psf}_{0}\supseteq\mathbf{P}_{\gg
0}\supseteq\mathbf{Fin}_{\gg 0}\supseteq\mathbf{Psf}_{\gg
0}\supseteq\mathbf{Psf}_{0}$ (cf. Proposition 4.3). Finally, by Weil’s Riemann
hypothesis for curves, $\mathbf{PAC}\subseteq\mathbf{Psf}$ [FJ08, Cor.
20.10.5].

######  Proposition 5.6.

  1. (a)

$\mathbf{F}_{p,\exists}=\mathbf{P}_{p,\exists}={\rm
Th}_{\exists}(\mathbb{F}_{p})$ for all $p\in\mathbb{P}\cup\\{0\\}$,

  2. (b)

$\mathbf{F}_{\exists}=\mathbf{P}_{\exists}$,

  3. (c)

$\mathbf{F}_{>0,\exists}=\mathbf{P}_{>0,\exists}$,

  4. (d)

$\mathbf{F}_{\gg 0,\exists}=\mathbf{P}_{\gg 0,\exists}$.

###### Proof.

For $p\in\mathbb{P}\cup\\{0\\}$, since
$\mathbf{F}_{p}\subseteq\mathbf{P}_{p}\subseteq{\rm Th}(\mathbb{F}_{p})$ and
every $K\models\mathbf{F}_{p}$ is a field of characteristic $p$, hence has
prime field isomorphic to $\mathbb{F}_{p}$, (a) follows from Remark 5.3. This
implies (b) by Remark 5.1, and (c) and (d) follow immediately from (b) and
Proposition 4.4. ∎

######  Corollary 5.7.

  1. $(a)$

$\mathbf{F}_{0,\exists}={\rm Th}_{\exists}(\mathbb{Q})$, and
$\mathbf{F}_{p,\exists}$ is decidable for every $p\in\mathbb{P}$.

  2. $(b)$

$\mathbf{F}_{\exists}\simeq_{\rm m}\mathbf{F}_{0,\exists}$, and
$\mathbf{F}_{\exists_{1}}$ is decidable.

  3. $(c)$

$\mathbf{F}_{>0,\exists}$ is decidable.

  4. $(d)$

$\mathbf{F}_{\gg 0,\exists}$ is decidable.

###### Proof.

Part (a) follows from Proposition 5.6(a) since ${\rm Th}(\mathbb{F}_{p})$ is
decidable. Parts (c) and (d) follow from the decidability of $\mathbf{P}_{>0}$
and $\mathbf{P}_{\gg 0}$ via Proposition 5.6(c,d), and
$\mathbf{F}_{\exists}\simeq_{\rm m}\mathbf{F}_{0,\exists}$ is then a
consequence of Proposition 4.5(b), applied to $T=\mathbf{F}$ and
$L=\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{ring}})$. Similarly, applying
Proposition 4.5(b) to $T=\mathbf{F}$ and
$L=\mathrm{Sent}_{\exists_{1}}(\mathfrak{L}_{\mathrm{ring}})$ shows
$\mathbf{F}_{\exists_{1}}\simeq_{\rm m}\mathbf{F}_{0,\exists_{1}}$, and
$\mathbf{F}_{0,\exists_{1}}={\rm Th}_{\exists_{1}}(\mathbb{Q})$ by Proposition
5.6(a), which is decidable, see e.g. [FJ08, Lemma 19.1.3]. ∎

###  5.2. PAC fields

We easily reobtain the decidability of $\mathbf{PAC}_{\exists}$ and
$\mathbf{PAC}_{p,\exists}$ proven in [FJ08, Section 21.4], and in addition get
the decidability of $\mathbf{PAC}_{>0,\exists}$, and $\mathbf{PAC}_{\gg
0,\exists}$ (which are all distinct, see Remark 5.4).

######  Corollary 5.8.

  1. $(a)$

$\mathbf{PAC}_{p,\exists}$ is decidable for all $p\in\mathbb{P}\cup\\{0\\}$.

  2. $(b)$

$\mathbf{PAC}_{\exists}$, $\mathbf{PAC}_{>0,\exists}$, and $\mathbf{PAC}_{\gg
0,\exists}$ are decidable.

###### Proof.

For (a), by Corollary 3.13 we have $\mathbf{PAC}_{p,\exists}\simeq_{\rm
m}\mathbf{F}_{p,\exists_{1}}=\mathrm{Th}_{\exists_{1}}(\mathbb{F}_{p})$, for
each $p\in\mathbb{P}\cup\\{0\\}$, which is decidable.

For (b), by Corollary 3.9(aII) we have $\mathbf{PAC}_{>0,\exists}\simeq_{\rm
m}\mathbf{PAC}_{>0,\exists_{1}}$ and $\mathbf{PAC}_{\gg 0,\exists}\simeq_{\rm
m}\mathbf{PAC}_{\gg 0,\exists_{1}}$. Considering the arch
$B|\hat{B}=\mathrm{F}_{\exists_{1}}.\mathrm{PAC}_{\exists_{1}}|\mathrm{F}_{\exists_{1}}.\mathrm{PAC}$,
we note that $B$ satisfies (mon) trivially, and $\hat{B}$ satisfies (sur)by
Corollary 3.8(b). Thus
$\mathbf{PAC}_{>0,\exists_{1}}=\mathbf{PAC}(\mathbf{F}_{>0})_{\exists_{1}}$
and $\mathbf{PAC}_{\gg 0,\exists_{1}}=\mathbf{PAC}(\mathbf{F}_{\gg
0})_{\exists_{1}}$ by Proposition 4.11(c,d). By Lemma 2.24,
$\mathbf{PAC}(\mathbf{F}_{>0})_{\exists_{1}}=\mathbf{PAC}(\mathbf{F}_{>0,\exists_{1}})_{\exists_{1}}$,
and by Corollary 3.9(bII), we have
$\mathbf{PAC}(\mathbf{F}_{>0,\exists_{1}})_{\exists_{1}}\simeq_{\rm
m}\mathbf{F}_{>0,\exists_{1}}$ and $\mathbf{PAC}(\mathbf{F}_{\gg
0,\exists_{1}})_{\exists_{1}}\simeq_{\rm m}\mathbf{F}_{\gg 0,\exists_{1}}$,
both of which are decidable. Finally $\mathbf{PAC}_{\exists}\simeq_{\rm
m}\mathbf{F}_{\exists_{1}}$, by Corollary 3.13, which is decidable by
Corollary 5.7(b). ∎

###  5.3. Henselian fields

We use the above notational conventions, applied to the arches
$\mathrm{F}_{\exists}.\mathrm{H}^{e\prime}_{\exists}|\mathrm{F}.\mathrm{H}^{e\prime}$
and
$\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}|\mathrm{F}.\mathrm{H}^{e,\varpi}$,
together with $\mathfrak{L}_{\mathrm{ring}}$-theories
$R=\mathbf{F},\mathbf{P},\mathrm{Th}(\mathbb{F}_{p})$, etc.

######  Proposition 5.9.

  1. $(1)$

    1. $(a)$

$\mathbf{H}^{e\prime}_{p,\exists}=\mathbf{H}^{e\prime}(\mathbf{F}_{p})_{\exists}=\mathbf{H}^{e\prime}(\mathbf{P}_{p})_{\exists}=\mathbf{H}^{e\prime}({\rm
Th}(\mathbb{F}_{p}))_{\exists}=\mathrm{Th}_{\exists}(\mathbb{F}_{p}(\\!(t)\\!),v_{t})$
for all $p\in\mathbb{P}\cup\\{0\\}$,

    2. $(b)$

$\mathbf{H}^{e\prime}_{\exists}=\mathbf{H}^{e\prime}(\mathbf{F})_{\exists}=\mathbf{H}^{e\prime}(\mathbf{P})_{\exists}$,

    3. $(c)$

$\mathbf{H}^{e\prime}_{>0,\exists}=\mathbf{H}^{e\prime}(\mathbf{F}_{>0})_{\exists}=\mathbf{H}^{e\prime}(\mathbf{P}_{>0})_{\exists}$,

    4. $(d)$

$\mathbf{H}^{e\prime}_{\gg 0,\exists}=\mathbf{H}^{e\prime}(\mathbf{F}_{\gg
0})_{\exists}=\mathbf{H}^{e\prime}(\mathbf{P}_{\gg 0})_{\exists}$

  2. $(2)$

    1. $(a)$

$\mathbf{H}^{e,\varpi}_{p,\exists}=\mathbf{H}^{e,\varpi}(\mathbf{F}_{p})_{\exists}=\mathbf{H}^{e,\varpi}(\mathbf{P}_{p})_{\exists}=\mathbf{H}^{e,\varpi}({\rm
Th}(\mathbb{F}_{p}))_{\exists}=\mathrm{Th}_{\exists}(\mathbb{F}_{p}(\\!(t)\\!),v_{t},t)$
for all $p\in\mathbb{P}\cup\\{0\\}$, where for the last equality in case
$p\in\mathbb{P}$ we require (R4),

    2. $(b)$

$\mathbf{H}^{e,\varpi}_{\exists}=\mathbf{H}^{e,\varpi}(\mathbf{F})_{\exists}=\mathbf{H}^{e,\varpi}(\mathbf{P})_{\exists}$,

    3. $(c)$

$\mathbf{H}^{e,\varpi}_{>0,\exists}=\mathbf{H}^{e,\varpi}(\mathbf{F}_{>0})_{\exists}=\mathbf{H}^{e,\varpi}(\mathbf{P}_{>0})_{\exists}$,

    4. $(d)$

$\mathbf{H}^{e,\varpi}_{\gg 0,\exists}=\mathbf{H}^{e,\varpi}(\mathbf{F}_{\gg
0})_{\exists}=\mathbf{H}^{e,\varpi}(\mathbf{P}_{\gg 0})_{\exists}$

###### Proof.

For (1) we consider the arch
$B|\hat{B}=\mathrm{F}_{\exists}.\mathrm{H}^{e\prime}_{\exists}|\mathrm{F}.\mathrm{H}^{e\prime}$,
and for (2) we consider the arch
$B|\hat{B}=\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}|\mathrm{F}.\mathrm{H}^{e,\varpi}$,
just as in Lemma 3.19(a,c). Henceforth we can argue simultaneously in both
cases. The bridge $B_{0}$ satisfies (mon) by Lemma 3.19(a) in case (1) and
Lemma 3.19(b) in case (2) (note for the latter that
$B_{0}=\mathrm{F}_{0,\exists}/\mathrm{H}^{e,\varpi}_{0,\exists}$, as discussed
in Remark 5.2). Thus we may apply Proposition 4.11 to get the first equality
in each subcase. Since $B\sqsubseteq\hat{B}$ satisfies (wm), by Lemma 2.28 and
Lemma 3.19(a) in case (1), and Lemma 3.22 in case (2), we may apply Lemma 2.30
and Proposition 5.6 to deduce the remaining equalities, except for the final
equality in (1a) (respectively, (2a)) for which we apply Corollary 3.20(aIII)
(respectively, Corollary 3.20(bIII,cIII)). ∎

######  Remark 5.10.

Alternatively, in case (1) of Proposition 5.9 we may argue via Lemma 2.24: for
the arch
$\mathrm{F}_{\exists}.\mathrm{H}^{e\prime}_{\exists}|\mathrm{F}.\mathrm{H}^{e\prime}$,
the hypotheses of the lemma hold by Lemma 3.19(a). Then by Proposition 5.6(a),
for every $p\in\mathbb{P}\cup\\{0\\}$, we have
$\mathbf{H}^{e\prime}(\mathbf{F}_{p,\exists})=\mathbf{H}^{e\prime}(\mathbf{P}_{p,\exists})=\mathbf{H}^{e\prime}(\mathrm{Th}_{\exists}(\mathbb{F}_{p}))$.
By three applications of Lemma 2.24, we have
$\mathbf{H}^{e\prime}(\mathbf{F}_{p})_{\exists}=\mathbf{H}^{e\prime}(\mathbf{P}_{p})_{\exists}=\mathbf{H}^{e\prime}(\mathrm{Th}(\mathbb{F}_{p}))_{\exists}$.
Moreover
$(\mathbf{H}^{e\prime}_{p})^{\vdash}=\mathbf{H}^{e\prime}(\mathbf{F}_{p})^{\vdash}$
by Proposition 4.11(b)), and so in particular we have
$\mathbf{H}^{e\prime}_{p,\exists}=\mathbf{H}^{e\prime}(\mathbf{F}_{p})_{\exists}$,
which proves (1a). From this (1b) follows, as

$\displaystyle\mathbf{H}^{e\prime}_{\exists}=\bigcap_{p\in\mathbb{P}\cup\\{0\\}}\mathbf{H}^{e\prime}_{p,\exists}=\bigcap_{p\in\mathbb{P}\cup\\{0\\}}\mathbf{H}^{e\prime}(\mathbf{P}_{p})_{\exists}=\mathbf{H}^{e\prime}(\bigcap_{p\in\mathbb{P}\cup\\{0\\}}\mathbf{P}_{p})_{\exists}=\mathbf{H}^{e\prime}(\mathbf{P})_{\exists},$

where the first and fourth equalities hold by Remark 5.1 and the third
equality holds by by Lemma 2.24. Similarly, Lemma 2.24 gives that

$\mathbf{H}^{e\prime}_{>0,\exists}=\bigcap_{p>0}\mathbf{H}^{e\prime}_{p,\exists}=\bigcap_{p>0}\mathbf{H}^{e\prime}(\mathbf{P}_{p})_{\exists}=\mathbf{H}^{e\prime}(\bigcap_{p>0}\mathbf{P}_{p})_{\exists}=\mathbf{H}^{e\prime}(\mathbf{P}_{>0})_{\exists}$

and

$\mathbf{H}^{e\prime}_{\gg
0,\exists}=\bigcup_{\ell>0}\bigcap_{p>\ell}\mathbf{H}^{e\prime}_{p,\exists}=\bigcup_{\ell>0}\mathbf{H}^{e\prime}(\bigcap_{p>\ell}\mathbf{P}_{p})_{\exists}=\mathbf{H}^{e\prime}(\bigcup_{\ell>0}\bigcap_{p>\ell}\mathbf{P}_{p})_{\exists}=\mathbf{H}^{e\prime}(\mathbf{P}_{\gg
0})_{\exists},$

which proves (1c,d).

For case (2), we consider the arch
$B|\hat{B}=\mathrm{F}_{\exists}.\mathrm{H}^{e,\varpi}_{\exists}|\mathrm{F}.\mathrm{H}^{e,\varpi}$.
Then a similar argument is possible provided that we suppose (R4). Under this
hypothesis, $B$ satisfies (mon). Thus Lemma 2.24 applies and the above proof
goes through mutatis mutandis. The advantage of the proof given above is that
it does not rely on (R4).

######  Corollary 5.11.

  1. $(1)$

    1. $(a)$

$\mathbf{H}^{e\prime}_{0,\exists}\simeq_{\rm m}{\rm
Th}_{\exists}(\mathbb{Q})$, and $\mathbf{H}^{e\prime}_{p,\exists}$ is
decidable for every $p\in\mathbb{P}$.

    2. $(b)$

$\mathbf{H}^{e\prime}_{\exists}\simeq_{\rm
m}\mathbf{H}^{e\prime}_{0,\exists}$.

    3. $(c)$

$\mathbf{H}^{e\prime}_{>0,\exists}$ is decidable.

    4. $(d)$

$\mathbf{H}^{e\prime}_{\gg 0,\exists}$ is decidable.

  2. $(2)$

    1. $(a)$

$\mathbf{H}^{e,\varpi}_{0,\exists}\simeq_{\rm
m}\mathrm{Th}_{\exists}(\mathbb{Q})$, and if (R4) holds then
$\mathbf{H}^{e,\varpi}_{p,\exists}$ is decidable for every $p\in\mathbb{P}$.

    2. $(b)$

If (R4) holds, then $\mathbf{H}^{e,\varpi}_{\exists}\simeq_{\rm
m}\mathbf{H}^{e,\varpi}_{0,\exists}$.

    3. $(c)$

If (R4) holds, then $\mathbf{H}^{e,\varpi}_{>0,\exists}$ is decidable.

    4. $(d)$

$\mathbf{H}^{e,\varpi}_{\gg 0,\exists}$ is decidable.

###### Proof.

Part (1a) (respectively (2a)) for $p=0$ follows from Proposition 5.6(a) and
Corollary 3.20(aII) (respectively Corollary 3.20(bII)) applied to
$R=\emptyset$, and for $p\in\mathbb{P}$ follows from the decidability of
$\mathbf{P}_{p}$ via Proposition 5.9(1a) and Corollary 3.20(aII) (resp.
Proposition 5.9(2a) and Corollary 3.20(cII)). Similarly, (1c,d) (resp. (2c,d)
assuming (R4)) follow from Corollary 5.7(c,d) via Proposition 5.9(1c,d) and
Corollary 3.20(aII) (resp. Proposition 5.9(2c,d) and Corollary 3.20(cII)). To
obtain (2d) as written (i.e. without assuming (R4)) we argue as follows: by
Proposition 5.9(2d), we have $\mathbf{H}^{e,\varpi}_{\gg
0,\exists}=\mathbf{H}^{e,\varpi}(\mathbf{F}_{\gg 0})_{\exists}$, and by
Corollary 3.20(bII) $\mathbf{H}^{e,\varpi}_{0}(\mathbf{F}_{\gg
0})_{\exists}\simeq_{\rm m}\mathbf{F}_{\gg 0,\exists}$, which is decidable by
Corollary 5.7(d). This proves (2d) since
$\mathbf{H}^{e,\varpi}(\mathbf{F}_{\gg
0})=\mathbf{H}^{e,\varpi}_{0}(\mathbf{F}_{\gg 0})$. Furthermore (1c) (resp.
(2c)) is a consequence of Proposition 4.5(b), applied to
$T=\mathbf{H}^{e\prime}$ (resp. $T=\mathbf{H}^{e,\varpi}$) and
$L=\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}})$ (resp.
$L=\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{val}}(\varpi))$), or can
alternatively be deduced from Corollary 5.7(c). ∎

###  5.4. Large fields

Let $\mathbf{L}$ denote the $\mathfrak{L}_{\mathrm{ring}}$-theory of large
fields (cf. Remark 3.18). As every PAC field is large, and every nontrivially
valued henselian field is large [Jar11, Example 5.6.2],
$\mathbf{L}\subseteq\mathbf{PAC}$ and
$\mathbf{L}\subseteq\mathbf{H}^{e\prime}\cap{\rm Sent}(\mathfrak{L}_{\rm
ring})$.

######  Proposition 5.12.

  1. $(a)$

$\mathbf{L}_{p,\exists}=\mathbf{H}^{e\prime}_{p,\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})={\rm
Th}_{\exists}(\mathbb{F}_{p}(\\!(t)\\!))$ for all $p\in\mathbb{P}\cup\\{0\\}$.

  2. $(b)$

$\mathbf{L}_{\exists}=\mathbf{H}^{e\prime}_{\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$.

  3. $(c)$

$\mathbf{L}_{>0,\exists}=\mathbf{H}^{e\prime}_{>0,\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$.

  4. $(d)$

$\mathbf{L}_{\gg 0,\exists}=\mathbf{H}^{e\prime}_{\gg
0,\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$.

###### Proof.

By Proposition 5.9(1a),
$\mathbf{H}^{e\prime}_{p,\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})=\mathrm{Th}_{\exists}(\mathbb{F}_{p}(\\!(t)\\!))$.
As every nontrivially valued henselian field is large, we have
$\mathbf{L}\subseteq\mathbf{H}^{e\prime}$, in particular
$\mathbf{L}_{p,\exists}\subseteq\mathbf{H}^{e\prime}_{p,\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$.
Conversely, if $K\models\mathbf{L}_{p}$, then
$K\prec_{\exists}K(\\!(t)\\!)\models\mathbf{H}^{e\prime}_{p,\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$,
hence
$K\models\mathbf{H}^{e\prime}_{p,\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$,
which proves (a). Then (b) follows via Remark 5.1, and (c) and (d) follow
immediately from (a) and Proposition 4.4. ∎

######  Corollary 5.13.

  1. $(a)$

$\mathbf{L}_{0,\exists}\simeq_{\rm m}{\rm Th}_{\exists}(\mathbb{Q})$, and
$\mathbf{L}_{p,\exists}$ is decidable for every $p\in\mathbb{P}$.

  2. $(b)$

$\mathbf{L}_{\exists}\simeq_{\rm m}\mathbf{L}_{0,\exists}$

  3. $(c)$

$\mathbf{L}_{>0,\exists}$ is decidable.

  4. $(d)$

$\mathbf{L}_{\gg 0,\exists}$ is decidable.

###### Proof.

The decidability of $\mathbf{L}_{>0,\exists}$ and $\mathbf{L}_{\gg 0,\exists}$
follow from Corollary 5.11(1c,d) and Proposition 5.12(c,d). For
$p\in\mathbb{P}\cup\\{0\\}$,
$\mathbf{L}_{p,\exists}=\mathbf{H}^{e\prime}_{p,\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$
by Proposition 5.12(a), and by Corollary 5.11(1a) this is decidable when
$p\in\mathbb{P}$. For the case $p=0$, $\mathbf{L}_{\exists}\simeq_{\rm
m}\mathbf{L}_{0,\exists}$ is a consequence of Proposition 4.5(b), applied to
$T=\mathbf{L}$ and $L=\mathrm{Sent}_{\exists}(\mathfrak{L}_{\mathrm{ring}})$,
and
$\mathbf{L}_{0,\exists}=\mathbf{H}^{e\prime}(\mathrm{Th}(\mathbb{Q}))_{\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$
by Proposition 5.12(a). The latter is many-one equivalent to
$\mathbf{H}^{e\prime}(\mathrm{Th}(\mathbb{Q}))_{\exists}$ since by [AF17,
Corollary 6.2 and Corollary 6.18] there are two
$\mathfrak{L}_{\mathrm{ring}}$-formulas — one existential and one universal —
which each define the valuation ring in every model of
$\mathbf{H}^{e\prime}(\mathrm{Th}(\mathbb{Q}))$. Finally,
$\mathbf{H}^{e\prime}(\mathrm{Th}(\mathbb{Q}))_{\exists}\simeq_{\rm
m}\mathrm{Th}_{\exists}(\mathbb{Q})$ by Corollary 5.9(1a) and Corollary
5.11(1a). ∎

######  Remark 5.14.

We proved both $\mathbf{H}^{e\prime}_{0,\exists}\simeq_{\rm
T}\mathbf{H}^{e\prime}_{\exists}$ and
$\mathbf{H}^{e\prime}_{0,\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})\simeq_{\rm
T}\mathbf{H}^{e\prime}_{\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$
but neither statement seems to imply the other immediately, as there is no
uniform existential (or universal) definition of the valuation ring in models
of $\mathbf{H}^{e\prime}$ (or even
$\mathbf{H}^{e\prime}\cup\iota_{\mathbf{k}}\mathbf{P}$). In particular, we
obtain the somewhat surprising Turing equivalence
$\mathbf{H}^{e\prime}_{\exists}\simeq_{\rm
T}\mathbf{H}^{e\prime}_{\exists}\cap\mathrm{Sent}(\mathfrak{L}_{\mathrm{ring}})$.

######  Remark 5.15.

The statement $\mathbf{L}_{0,\exists}={\rm
Th}_{\exists}(\mathbb{Q}(\\!(t)\\!))$, which is part of Proposition 5.12(a)
was also proven by Sander in [San96, Proposition 2.25]. Sander continues to
remark (with references but without detailed proof) that ${\rm
Th}_{\exists}(\mathbb{Q}(\\!(t)\\!))\leq_{\rm T}{\rm
Th}_{\exists}(\mathbb{Q})$ follows from work of Weispfenning, and he asks in
[San96, Problem 2.26] whether $\mathbf{L}_{0,\exists}$ is decidable. The
statement $\mathbf{L}_{0,\exists}\simeq_{\rm m}{\rm Th}_{\exists}(\mathbb{Q})$
(Corollary 5.13(a)) shows that this question is in fact equivalent to a famous
and still open problem.

###### Proof of Theorem 1.2.

By Corollary 5.9(1a,2a), we have
$\mathrm{Th}_{\exists}(\mathbb{Q}(\\!(t)\\!),v_{t})=\mathbf{H}^{e\prime}(\mathrm{Th}(\mathbb{Q}))_{\exists}$
and
$\mathrm{Th}_{\exists}(\mathbb{Q}(\\!(t)\\!),v_{t},t)=\mathbf{H}^{e,\varpi}(\mathrm{Th}(\mathbb{Q}))_{\exists}$.
By Corollary 5.11(1a,2a) these theories are many-one equivalent to
$\mathrm{Th}_{\exists}(\mathbb{Q})$. Thus (a), (c), and (d) are many-one
equivalent. By Proposition 5.12(a), (b) and (e) are many-one equivalent. By
Corollary 5.7(a,b), (a) and (g) are many-one equivalent. Finally by Corollary
5.13(a,b), (a), (e), and (f) are many-one equivalent. ∎

###  5.5. Global fields

Let $\mathbf{F}^{\infty}$ be the theory of infinite fields and $\mathbf{G}$
the theory of global fields (i.e. finitely generated fields of characteristic
zero and transcendence degree zero, or positive characteristic and
transcendence degree one).

######  Proposition 5.16.

We have $\mathbf{G}_{\exists}=(\mathbf{F}^{\infty})_{\exists}$. Consequently,
$\mathbf{G}_{\gg 0,\exists}=(\mathbf{F}^{\infty})_{\gg 0,\exists}$,
$\mathbf{G}_{p,\exists}=(\mathbf{F}^{\infty})_{p,\exists}={\rm
Th}_{\exists}(\mathbb{F}_{p}(t))$ for every $p\in\mathbb{P}$, and
$\mathbf{G}_{0,\exists}=(\mathbf{F}^{\infty})_{0,\exists}=\mathbf{F}_{0,\exists}={\rm
Th}_{\exists}(\mathbb{Q})$.

###### Proof.

Every global field is infinite. Conversely, let $K$ be an infinite field of
characteristic $p\geq 0$. If $p=0$, then the global field $\mathbb{Q}$ can be
embedded into $K$, and if $p>0$ then the global field $\mathbb{F}_{p}(t)$ can
be embedded into any uncountable elementary extension $K\prec K^{*}$. It
follows that $\mathbf{G}_{\exists}=(\mathbf{F}^{\infty})_{\exists}$ (Remark
5.3). Using Proposition 4.4, we conclude that
$\mathbf{G}_{p,\exists}=(\mathbf{G}_{\exists})_{p,\exists}=((\mathbf{F}^{\infty})_{\exists})_{p,\exists}=(\mathbf{F}^{\infty})_{p,\exists}$
for every $p\in\mathbb{P}\cup\\{0\\}$, similarly $\mathbf{G}_{\gg
0,\exists}=(\mathbf{F}^{\infty})_{\gg 0,\exists}$. As
$(\mathbf{F}^{\infty})_{0}=\mathbf{F}_{0}$, we conclude that
$(\mathbf{F}^{\infty})_{0,\exists}=\mathbf{F}_{0,\exists}$, and
$\mathbf{F}_{0,\exists}={\rm Th}_{\exists}(\mathbb{Q})$ follows from
Proposition 5.6(a). Similarly, $\mathbb{F}_{p}(t)$ is infinite, and if $K$ is
any infinite field of characteristic $p>0$, then $\mathbb{F}_{p}(t)$ can be
embedded into any proper elementary extension $K\prec K^{*}$. ∎

######  Lemma 5.17.

$\mathbf{F}_{\gg 0}=(\mathbf{F}^{\infty})_{\gg 0}$

###### Proof.

Since $\mathbf{F}=\mathbf{F}^{\infty}\cap\mathbf{Fin}$, also $\mathbf{F}_{\gg
0}=(\mathbf{F}^{\infty})_{\gg 0}\cap\mathbf{Fin}_{\gg 0}$. So as
$\mathbf{Fin}_{\gg 0}=\mathbf{Psf}_{\gg 0}$ (Remark 5.5) and
$\mathbf{Psf}\supseteq\mathbf{F}^{\infty}$, in particular $\mathbf{Psf}_{\gg
0}\supseteq(\mathbf{F}^{\infty})_{\gg 0}$, we get that $\mathbf{F}_{\gg
0}=(\mathbf{F}^{\infty})_{\gg 0}\cap\mathbf{Fin}_{\gg
0}=(\mathbf{F}^{\infty})_{\gg 0}$. ∎

######  Remark 5.18.

In particular, using Proposition 5.6(d), Proposition 5.16, and Lemma 5.17 we
obtain $\mathbf{P}_{\gg 0,\exists}=\mathbf{F}_{\gg
0,\exists}=(\mathbf{F}^{\infty})_{\gg 0,\exists}=\mathbf{G}_{\gg 0,\exists}$.
We can also show that all of these theories are equal to $\mathbf{L}_{\gg
0,\exists}$ and to $\mathbf{PAC}_{\gg 0,\exists}$: As
$\mathbb{F}_{p}\subseteq\mathbb{F}_{p}(t)\subseteq\mathbb{F}_{p}(\\!(t)\\!)$,
from Propositions 5.6(a), 5.16 and 5.12(a) we get
$\mathbf{F}_{p,\exists}\subseteq\mathbf{G}_{p,\exists}\subseteq\mathbf{H}^{e\prime}_{p,\exists}\cap{\rm
Sent}(\mathfrak{L}_{\rm ring})$, and therefore

$\mathbf{P}_{\gg 0,\exists}=\mathbf{F}_{\gg 0,\exists}\subseteq\mathbf{G}_{\gg
0,\exists}\subseteq\mathbf{H}^{e\prime}_{\gg 0,\exists}\cap{\rm
Sent}(\mathfrak{L}_{\rm ring})=\mathbf{L}_{\gg
0,\exists}\subseteq\mathbf{PAC}_{\gg 0,\exists}$

using Proposition 5.12(d). By Remark 5.5 we have $\mathbf{PAC}_{\gg
0}\subseteq\mathbf{Psf}_{\gg 0}=\mathbf{Psf}_{0}=\mathbf{P}_{\gg 0}$, and thus
$\mathbf{PAC}_{\gg 0,\exists}=\mathbf{P}_{\gg 0,\exists}$ (although
$\mathbf{PAC}_{\gg 0}\neq\mathbf{P}_{\gg 0}$). Note that $\mathbf{F}_{\gg
0,\exists}\supsetneqq\mathbf{F}_{0,\exists}$, $\mathbf{PAC}_{\gg
0,\exists}\supsetneqq\mathbf{PAC}_{0,\exists}$ and $\mathbf{H}^{e\prime}_{\gg
0,\exists}\supsetneqq\mathbf{H}^{e\prime}_{0,\exists}$, as each of
$\mathbf{F}$, $\mathbf{PAC}$ and $\mathbf{H}^{e\prime}$ has models of
characteristic zero in which $\mathbb{Q}$ is algebraically closed (cf. Remark
5.4).

######  Corollary 5.19.

$\mathbf{G}_{\mathbb{N},\exists}\simeq_{\rm T}\mathbf{G}_{>0,\exists}$ and
$\mathbf{G}_{\mathbb{N}\cup\\{0\\},\exists}\simeq_{\rm
T}\mathbf{G}_{\exists}$.

###### Proof.

It follows from Lemma 5.17 that $\mathbf{F}_{\gg
0,\exists}=(\mathbf{F}^{\infty})_{\gg 0,\exists}$. Therefore, using Corollary
5.7(c,d), Proposition 4.5(d) for $T=\mathbf{F}^{\infty}$,
$T^{\prime}=\mathbf{F}$ and $L={\rm Sent}_{\exists}(\mathfrak{L}_{\rm ring})$
gives that $(\mathbf{F}^{\infty})_{>0,\exists}\simeq_{\rm
T}(\mathbf{F}^{\infty})_{\mathbb{N},\exists}$ and
$(\mathbf{F}^{\infty})_{\exists}\simeq_{\rm
T}(\mathbf{F}^{\infty})_{\mathbb{N}\cup\\{0\\},\exists}$. As
$(\mathbf{F}^{\infty})_{\exists}=\mathbf{G}_{\exists}$ (Proposition 5.16), the
claim follows via Proposition 4.4. ∎

In particular, together with Proposition 5.16 this implies Theorem 1.3.

## Acknowledgements

The authors warmly thank Philip Dittmann for a very careful reading of
preliminary versions and myriad helpful suggestions that improved this work in
many ways.

Part of this is based upon work supported by the National Science Foundation
under Grant No. DMS-1928930 while the authors participated in a program hosted
by the Mathematical Sciences Research Institute in Berkeley, California,
during Summer 2022. S. A. was supported by GeoMod AAPG2019 (ANR-DFG). S. A.
and A. F. were supported by the Institut Henri Poincaré. A. F. was funded by
the Deutsche Forschungsgemeinschaft (DFG) - 404427454.

## References

  * [ADF23] S. Anscombe, P. Dittmann, and A. Fehm.  Axiomatizing the existential theory of $\mathbb{F}_{q}(\\!(t)\\!)$.  Algebra & Number Theory 17(11):2013–2032, 2023.
  * [AF16] S. Anscombe and A. Fehm.  The existential theory of equicharacteristic henselian valued fields.  Algebra & Number Theory 10(3):665–683, 2016.
  * [AF17] S. Anscombe and A. Fehm.  Characterizing diophantine henselian valuation rings and valuation ideals.  Proc. London Math. Soc. (3) 115:293–322, 2017.
  * [AF23] S. Anscombe and A. Fehm.  Universal-existential theories of fields.  Manuscript, 2023.
  * [Ax68] J. Ax.  The elementary theory of finite fields.  Annals of Math. 88(2):239–271, 1968.
  * [BF13] L. Bary-Soroker and A. Fehm.  Open problems in the theory of ample fields.  In Geometric and differential Galois theories, volume 27 of Sémin. Congr., pages 1–11. Soc. Math. France, Paris, 2013.
  * [Bou07] N. Bourbaki.  Algèbre. Chapitres 4 à 7.  Springer, 2007.
  * [CK90] C. C. Chang and H. J. Keisler.  Model theory. Third edition. North-Holland Publishing Co., Amsterdam, 1990.
  * [DDF21] N. Daans, P. Dittmann and A. Fehm.  Existential rank and essential dimension of diophantine sets.  arXiv:2102.06941 [math.NT], 2021.
  * [vdD91] L. van den Dries.  A remark on Ax’s theorem on solvability modulo primes.  Math. Z. 208(1):65–70, 1991.
  * [EP05] A. Engler and A. Prestel.  Valued Fields.  Springer Monographs in Mathematics.  Springer, 2005.
  * [FJ08] M. D. Fried and M. Jarden.  Field arithmetic, 3rd edition, Springer, 2008.
  * [Hod93] W. Hodges.  Model theory. Cambridge University Press, 1993.
  * [Hod97] W. Hodges.  A shorter model theory. Cambridge University Press, 1997.
  * [Jar11] M. Jarden.  Algebraic Patching. Springer, 2011.
  * [Koe14] J. Koenigsmann.  Undecidability in Number Theory.  In: L. van den Dries et al. (eds.), Model Theory in Algebra, Analysis and Arithmetic, Springer, 2014.
  * [Mar02] D. Marker.  Model theory: an introduction, Graduate Texts in Mathematics 217, Springer, New York, 2002.
  * [Pas22] H. Pasten.  Notes on the DPRM property for listable structures.  J. Symb. Log. 87(1):273–312, 2022.
  * [Poi00] B. Poizat.  A Course in Model Theory. Springer, 2000.
  * [Poo03] B. Poonen.  Hilbert’s tenth problem over rings of number theoretic interest.  Lecture Notes, available at http://www-math.mit.edu/~poonen/papers/aws2003.pdf, 2003.
  * [Pop96] F. Pop.  Embedding problems over large fields.  Ann. of Math., 144:1–34, 1996.
  * [Pop14] F. Pop.  Little survey on large fields—old & new.  In: Valuation theory in interaction, EMS Ser. Congr. Rep, 432-463, 2014.
  * [Pos44] E. L. Post.  Recursively enumerable sets of positive integers and their decision problems.  Bull. Amer. Math. Soc., 50:284–316, 1944.
  * [PD11] A. Prestel and C. N. Delzell.  Mathematical Logic and Model Theory. Springer, 2011.
  * [San96] T. Sander.  Effektive algebraische Geometrie über nicht algebraisch abgeschlossenen Körpern.  Dissertation, Dortmund 1996.
  * [Sik69] R. Sikorski.  Boolean algebras. Third edition. Springer, 1969.
  * [Soa16] R. I. Soare.  Turing computability. Springer, 2016.
  * [Tur39] A. Turing.  Systems of logic based on ordinals.  Proc. London Math. Soc., ser. 2 v. 45, pp. 161–228, 1939.