# Some model theory of $\operatorname{Th}(\mathbb{N},\cdot)$

Atticus Stonestrom***Email<EMAIL_ADDRESS>
###### Abstract

‘Skolem arithmetic’ is the complete theory $T$ of the multiplicative monoid
$(\mathbb{N},\cdot)$. We give a full characterization of the
$\varnothing$-definable stably embedded sets of $T$, showing in particular
that, up to the relation of having the same definable closure, there is only
one non-trivial one: the set of squarefree elements. We then prove that $T$
has weak elimination of imaginaries but not elimination of finite imaginaries.

###### Acknowledgements

I would first like to thank Jamshid Derakhshan for his constant support and
friendship, and for all of the math he has taught me over the years. I would
also like to thank Alexi Block Gorman and James Hanson for their insights on
Presburger arithmetic, Udi Hrushovski for a helpful discussion of the paper,
and Emil Jeřábek, for his succinct and elegant post on MathOverflow
summarizing a quantifier elimination result for $T$.

Finally, I would especially like to thank Alex Kruckman; his guidance and
patience, not only over the course of this paper, but also during all of these
past months as I have been learning about (neo-)stability theory, are simply
impossible to overstate. I would like to thank him in particular for his great
help in understanding the QE result for $T$, for pointing out an oversight in
the proof of Lemma 3.2, for his observation that Fact B.2 follows from a
theorem of Tarski, and for all of his feedback and encouragement.

##  0 Notation

Throughout, $T$ denotes the complete theory of the multiplicative monoid
$(\mathbb{N},\cdot,1)$, where we use $\mathbb{N}$ to mean the non-zero natural
numbers. Fix $\mathbb{M}$ to be a monster model of $T$: concretely, we
throughout consider $\mathbb{M}$ as a special structure [1] of size
$\beth_{\mu^{+}}(\mu)$, for some suitably large cardinal $\mu$, and we use the
word ‘small’ to refer to subsets of size $<\mu^{+}$. In particular, whenever
we refer to a ‘parameter set $B\subset\mathbb{M}$’, we mean that $B$ is small.
Now, define a formula $v_{1}\mid v_{2}\equiv\exists w(v_{2}=v_{1}\cdot w)$,
meaning ‘$v_{1}$ divides $v_{2}$’, and define further a formula

$\pi(u)\equiv(u\neq 1)\wedge\forall w_{1}\forall w_{2}\left[u\mid(w_{1}\cdot
w_{2})\to(u\mid w_{1}\vee u\mid w_{2})\right],$

meaning ‘$u$ is prime’. We will refer to any realization of $\pi$ as a
‘prime’, and we will denote by $\mathbb{P}$ the set $\pi(\mathbb{M})$ of all
primes of $\mathbb{M}$. All other formulas and notation specific to
$\mathbb{M}$ will be defined where they appear.

We use $\omega$ to refer to the natural numbers including $0$, and restrict
the symbol $\mathbb{N}$ to mean only the substructure
$\mathbb{N}\prec\mathbb{M}$; we instead use $\omega$ when the natural numbers
are employed as an index set. For $n\in\omega$, we use $[n]$ to denote the set
$\\{1,\dots,n\\}$. We use $\subseteq$ for containment and $\subset$ for strict
containment, and $|\overline{a}|$ for the length of a tuple $\overline{a}$.
Given an equivalence relation $E\subseteq\mathbb{M}^{n}\times\mathbb{M}^{n}$,
we write the $E$-equivalence class of a tuple $\overline{a}\in\mathbb{M}^{n}$
as $\overline{a}^{E}$.

We often use ‘partitioned formulas’ of the form
$\phi(\overline{v};\overline{w})$, where $\overline{w}$ represents a parameter
tuple. Given a tuple $\overline{c}\in\mathbb{M}^{|\overline{w}|}$ and a subset
$X\subseteq\mathbb{M}$, we write $\phi(X^{|\overline{v}|};\overline{c})$ to
mean the set of all tuples $\overline{a}\in X^{|\overline{v}|}$ such that
$\mathbb{M}\models\phi(\overline{a};\overline{c})$. Finally, given tuples
$\overline{a}_{1}$ and $\overline{a}_{2}$ and a parameter set
$B\subset\mathbb{M}$, we write $\overline{a}_{1}\equiv_{B}\overline{a}_{2}$ to
mean that
$\operatorname{tp}(\overline{a}_{1}/B)=\operatorname{tp}(\overline{a}_{2}/B)$,
and use $\overline{a}_{1}\equiv\overline{a}_{2}$ to abbreviate
$\overline{a}_{1}\equiv_{\varnothing}\overline{a}_{2}$.

##  1 Introduction

Skolem arithmetic is in many regards a highly pathological theory, lying
firmly in the ‘delta quadrant’ of the model-theoretic universe. For instance,
the formula $v\mid w$ has both the independence property, as it shatters any
small subset of $\mathbb{P}$, and the strict order property, as it induces a
partial ordering on $\mathbb{M}$ without maximal elements. Similarly, model-
theoretic notions of independence behave poorly in the theory; forking and
dividing do not coincide, and in fact types may fork over their domains.†††As
an example, if $r\in\mathbb{M}$ is any squarefree element with infinitely many
prime factors, and $p\in\mathbb{P}$ is one of its prime factors, then
$p\mathop{\mathchoice{\kern 5.71527pt\hbox to0.0pt{\hss$\mathchar
12854\relax$\kern 8.00134pt\hss}\hbox to0.0pt{\hss$\mid$\hss}\lower
3.87495pt\hbox to0.0pt{\hss$\smile$\hss}\kern 5.71527pt\displaystyle{}}{\kern
5.71527pt\hbox to0.0pt{\hss$\mathchar 12854\relax$\kern 8.00134pt\hss}\hbox
to0.0pt{\hss$\mid$\hss}\lower 3.87495pt\hbox to0.0pt{\hss$\smile$\hss}\kern
5.71527pt\textstyle{}}{\kern 5.71527pt\hbox to0.0pt{\hss$\mathchar
12854\relax$\kern 8.00134pt\hss}\hbox to0.0pt{\hss$\mid$\hss}\lower
3.87495pt\hbox to0.0pt{\hss$\smile$\hss}\kern 5.71527pt\scriptstyle{}}{\kern
5.71527pt\hbox to0.0pt{\hss$\mathchar 12854\relax$\kern 8.00134pt\hss}\hbox
to0.0pt{\hss$\mid$\hss}\lower 3.87495pt\hbox to0.0pt{\hss$\smile$\hss}\kern
5.71527pt\scriptscriptstyle{}}}^{f}_{\\{r\\}}r$. Our aim in this paper is to
instead understand what kinds of tame structure appear within $T$. To this
end, we compute the $\varnothing$-definable stably embedded sets of $T$, and
we show that $T$ admits weak elimination of imaginaries.

The paper proceeds as follows. In Section 2 we give a number of constructions
and lemmas that provide the main tools for the rest of the paper. First, in
Section 2.1, we describe a quantifier elimination result for $T$ noted in
unpublished work of Emil Jeřábek; for completeness, we include a proof of this
result in Appendix A. In Section 2.2 we discuss radical, or squarefree,
elements; there is a natural two-to-one correspondence between the
$\mathbb{M}$-definable subsets of $\mathbb{P}$ and the radical elements of
$\mathbb{M}$, which allows us to employ radical elements as a means of coding
definable sets of primes. In Section 2.3 we give a few lemmas on conjugate
tuples, and in Section 2.4 we prove some results on definability; we discuss
in particular a lexicographic ordering on $\mathbb{M}^{n}$ that allows us to
obtain some control over the definable closure of a tuple. Finally, in Section
2.5, we discuss $\varnothing$-definable subsets of $\mathbb{M}$ that are
cofinal with respect to divisibility, and prove that the definable closure of
any such set is all of $\mathbb{M}$.

In Section 3 we investigate the theory’s $\varnothing$-definable stably
embedded sets, a full characterization of which we give in Theorem 3.4. In
short, a $\varnothing$-definable subset $D\subseteq\mathbb{M}^{n}$ is stably
embedded if and only if $\operatorname{dcl}D$ is one of $\\{1\\}$,
$\mathbb{M}$, or the definable closure of the set of radical elements of
$\mathbb{M}$. Thus, up to the relation of having the same definable closure,
the only non-trivial stably embedded subset of $\mathbb{M}$ is the set of
radical elements. Note that, by the results on cofinal sets in Section 2,
every $\varnothing$-definable cofinal subset of $\mathbb{M}$ is stably
embedded.

In Section 4 we investigate the theory’s imaginary elements. We first give an
easy example showing that the theory does not eliminate finite imaginaries;
although any $\mathbb{M}$-definable subset of $\mathbb{P}$ can be coded (by a
suitable radical element), the next simplest case cannot be in general, and
the set $\\{p\cdot q,r\cdot s\\}$ has no canonical parameter for any distinct
primes $p,q,r,s$. With this done, the bulk of the section is then devoted to
showing that $T$ nonetheless does have weak elimination of imaginaries, which
we prove in Theorem 4.9. The approach is to reduce questions about sets
definable over arbitrary parameters to questions about sets definable over
radical tuples, which are generally more tractable; we do this using both
results from Section 2 and the stable embeddedness of the set of radical
elements.

##  2 Lemmas and constructions

###  2.1 Quantifier elimination

Define a formula $\operatorname{pow}_{u}(w)\equiv\pi(u)\wedge\forall
v\left[\pi(v)\wedge(v\mid w)\to(v=u)\right]$, expressing that $u$ is prime and
the only possible prime divisor of $w$. We have the following theorem of
$\mathbb{N}$:

$\mathbb{N}\models\forall u\forall v\big{[}\pi(u)\to\exists
w\bigl{[}\operatorname{pow}_{u}(w)\wedge(w\mid v)\wedge\forall
z\bigl{(}\operatorname{pow}_{u}(z)\wedge(z\mid v)\to(z\mid
w)\bigl{)}\big{]}\big{]}.$

In other words, for every prime $u\in\mathbb{P}$ and every $v\in\mathbb{M}$,
there exists an element $w$ that is the ‘highest power’ of $u$ dividing $v$.
Such a $w$ is unique with this property, and we will denote it by
$v_{u^{\infty}}$, which we call the ‘$u$-part’ of $v$. We also will denote by
$u^{\infty}:=\operatorname{pow}_{u}(\mathbb{M})$ the set of all powers of $u$
in $\mathbb{M}$.

Fix a prime $p\in\mathbb{P}$ and a formula $\phi(\overline{v})$. Define the
‘relativization to $p$’ of $\phi$, denoted $\phi^{p}(\overline{v})$, by
induction. If $\phi$ is atomic, take $\phi^{p}(\overline{v})$ to be the
formula obtained by replacing every instance of $v_{i}$ in $\phi$ with
$v_{i,p^{\infty}}$. Then let relativization to $p$ distribute over Boolean
operations and existential quantification; for example, if
$\phi(\overline{v})$ is of the form $\exists w\psi(\overline{v},w)$, then take
$\phi^{p}(\overline{v})\equiv\exists w\psi^{p}(\overline{v},w)$.

######  Remark 2.1.

The ‘relativization to $p$’ process simply replaces every (free or bound)
instance of a variable in $\phi(\overline{v})$ with its $p$-part. In other
words, $\phi^{p}(\overline{v})$ just expresses that
$\phi(\overline{v}_{p^{\infty}})$ holds in the submonoid $p^{\infty}$ of
$\mathbb{M}$. Note in particular that $\phi^{p}(\overline{v})$ is equivalent
to $\phi^{p}(\overline{v}_{p^{\infty}})$.

Now, given a formula $\phi(\overline{v})$ and a natural number $n\in\omega$,
we can construct a corresponding formula $\exists^{\geqslant
n}u\left[\pi(u)\wedge\phi^{u}(\overline{v})\right]$, which expresses that
there are at least $n$ primes $u$ at which the $u$-relativization of
$\phi(\overline{v})$ holds. In fact, every formula is equivalent modulo $T$ to
a Boolean combination of formulas of this form; this is noted in unpublished
work of Emil Jeřábek, who attributes it to a more general result of Mostowski.
[4] For completeness, we include a self-contained proof of this fact in
Appendix A. To ease the notational strain, we will throughout the paper write
these formulas and their negations as $\phi^{\geqslant n}(\overline{v})$ and
$\phi^{<n}(\overline{v})$, respectively, and use $\phi^{=n}(\overline{v})$ to
mean $\phi^{\geqslant n}(\overline{v})\wedge\phi^{\leqslant n}(\overline{v})$.
We record here only the statement of the main QE result; for a proof see
Appendix A.

######  Theorem A.4.

Any formula $\phi(\overline{v})$ is equivalent to a Boolean combination of
formulas of the form $\theta^{\geqslant m}(\overline{v})$.$\hfill\blacksquare$

###  2.2 Radical elements

For a tuple $\overline{a}$, we write $\sigma(\overline{a})$ to mean
$\left\\{p\in\mathbb{P}:\overline{a}_{p^{\infty}}\neq\overline{1}\right\\}$,
which we call the ‘support’ of $\overline{a}$. Given two tuples
$\overline{a}_{1}$ and $\overline{a}_{2}$, we write
$\overline{a}_{1}\perp\overline{a}_{2}$ to mean that
$\sigma(\overline{a}_{1})\cap\sigma(\overline{a}_{2})=\varnothing$; note that
both $\sigma(\overline{v})$ for a variable tuple $\overline{v}$ and
$\overline{v}_{1}\perp\overline{v}_{2}$ for variable tuples $\overline{v}_{1}$
and $\overline{v}_{2}$ are first-order expressible.

We will call an element $r\in\mathbb{M}$ squarefree, or radical, if
$r_{p^{\infty}}\in\\{1,p\\}$, ie if $p^{2}\nmid r$, for every prime
$p\in\mathbb{P}$. We have the following formula defining radical elements,

$\operatorname{rad}(v)\equiv\forall
u\left[\pi(u)\to(v_{u^{\infty}}=1)\vee(v_{u^{\infty}}=u)\right],$

and the following theorem of $T$: $\mathbb{N}\models\forall
v\exists!w\left[\operatorname{rad}(w)\wedge\sigma(v)=\sigma(w)\right]$. In
other words, for every $a\in\mathbb{M}$, there exists a unique radical element
$r\in\mathbb{M}$ with $\sigma(r)=\sigma(a)$. (Indeed, for an arbitrary natural
number $a\in\mathbb{N}$, the squarefree part of $a$ witnesses this sentence in
$\mathbb{N}$ when $v=a$, which gives the desired result.) We will denote the
element $r$ by $\sqrt{a}$, and we will write
$\sqrt{\mathbb{M}}=\operatorname{rad}(\mathbb{M})$ to mean the set of all
radical elements of $\mathbb{M}$. If one thinks of elements of $\mathbb{M}$ as
coding families of powers of primes, then $\sqrt{a}$ can be thought of as
containing precisely the information of which primes are represented in $a$,
and nothing more. Note that a radical element is completely determined by its
prime support. Conversely, any $\mathbb{M}$-definable set of primes can be
coded by a suitable radical element, in the following way:

######  Lemma 2.2.

For any $\mathbb{M}$-definable set of primes $Q\subseteq\mathbb{P}$, there
exists a radical element $r\in\mathbb{M}$ such that $\sigma(r)$ is one of $Q$
and $\mathbb{P}\setminus Q$.

###### Proof.

Use $\neg_{0}$ denote the string ‘$\neg$’ and $\neg_{1}$ to denote the empty
string. For a fixed formula $\theta(u;\overline{w})$, we show the following:

$\mathbb{N}\models\forall\overline{w}\exists
v\left[\operatorname{rad}(v)\wedge\bigvee_{i=0}^{1}\forall
u\left[\pi(u)\to\big{(}(u\mid
v)\leftrightarrow\neg_{i}\theta(u;\overline{w})\big{)}\right]\right].$

To see this, let $\overline{c}\in\mathbb{N}^{|\overline{w}|}$ be arbitrary,
and consider the set
$P:=\left\\{p\in\mathbb{P}\cap\mathbb{N}:\mathbb{N}\models\theta(p,\overline{c})\right\\}$.
We have two cases; first suppose that $P\subseteq\sigma(\overline{c})$. Then
in particular, since elements of $\mathbb{N}$ have finite support, $P$ is
finite, so taking $v=\prod P\in\mathbb{N}$ and $i=1$ gives the desired result.
Otherwise, suppose there is a prime $p\in P\setminus\sigma(\overline{c})$.
Then, for every $q\in\mathbb{P}\cap\mathbb{N}$ not in $\sigma(\overline{c})$,
there is an automorphism of $\mathbb{N}$ taking $p$ to $q$ and fixing the
(prime factors of) $\overline{c}$, whence $q\in P$. So the complement of $P$
in $\mathbb{P}\cap\mathbb{N}$ is a subset of $\sigma(\overline{c})$, and is
therefore again finite, so taking
$v=\prod\left[(\mathbb{P}\cap\mathbb{N})\setminus P\right]\in\mathbb{N}$ and
$i=0$ gives the desired result. ∎

There is thus a natural two-to-one correspondence from the
$\mathbb{M}$-definable sets of primes onto $\sqrt{\mathbb{M}}$. We can avoid
worrying about complements if we restrict our attention to the
$\mathbb{M}$-definable subsets of $\sigma(\overline{a})$ for some tuple
$\overline{a}$; we will use the notation introduced in the following remark
essentially without mention throughout the rest of the paper.

######  Remark 2.3.

If $Q$ is any $\mathbb{M}$-definable set of primes, and $\overline{a}$ is any
tuple, then there exists a tuple $\overline{a}_{Q}$ such that, for any
$p\in\mathbb{P}$, we have
$\overline{a}_{Q,p^{\infty}}=\overline{a}_{p^{\infty}}$ if $p\in Q$ and
$\overline{a}_{Q,p^{\infty}}=\overline{1}$ if $p\notin Q$. We abbreviate
$\overline{a}_{\mathbb{P}\setminus Q}$ by writing $\overline{a}_{\neg Q}$, and
we abuse notation by writing

$\overline{a}_{Q}=\prod\left\\{\overline{a}_{q^{\infty}}:q\in
Q\right\\}\in\mathbb{M}^{|\overline{a}|}.$

As a particular case, if there exists a tuple $\overline{a}$ such that
$Q\subseteq\sigma(\overline{a})$, then there exists a radical element
$r\in\sqrt{\mathbb{M}}$ with $\sigma(r)=Q$; we similarly abuse notation by
writing $r=\prod Q$.

###  2.3 Conjugates

We collect here a few easy criteria for determining and constructing conjugate
tuples.

######  Lemma 2.4.

Suppose $\overline{a}_{1},\overline{a}_{2}$ and
$\overline{c}_{1},\overline{c}_{2}$ are tuples, and that
$\overline{a}_{1}\perp\overline{c}_{1}$ and
$\overline{a}_{2}\perp\overline{c}_{2}$. If
$\overline{a}_{1}\equiv\overline{a}_{2}$ and
$\overline{c}_{1}\equiv\overline{c}_{2}$, then
$\overline{a}_{1}\overline{c}_{1}\equiv\overline{a}_{2}\overline{c}_{2}$.

###### Proof.

Let $\phi(\overline{v},\overline{w})$ be any formula; by Theorem A.4, we may
assume that $\phi$ is of form $\theta^{\geqslant
n}(\overline{v},\overline{w})$ for some formula $\theta$ and $n\in\omega$.
Suppose that $\theta^{\geqslant n}(\overline{a}_{1},\overline{c}_{1})$ holds;
we will show that $\theta^{\geqslant n}(\overline{a}_{2},\overline{c}_{2})$
does too. If $\mathbb{M}\models\theta^{p}(\overline{1},\overline{1})$ for some
(and hence any) $p\in\mathbb{P}$, then the result is immediate, so assume this
is not the case, and let $p_{1},\dots,p_{n}$ be any distinct primes such that
$\mathbb{M}\models\theta^{p_{i}}(\overline{a}_{1},\overline{c}_{1})$ for each
$i\in[n]$. Since $\mathbb{M}\models\neg\theta^{p}(\overline{1},\overline{1})$
and $\overline{a}_{1}\perp\overline{c}_{1}$, for each $i\in[n]$ precisely one
of $p_{i}\in\sigma(\overline{a}_{1})$ and $p_{i}\in\sigma(\overline{c}_{1})$
holds. Assume without loss of generality that $n^{\prime}\in[n+1]$ is such
that, for any $i\in[n]$, we have $p_{i}\in\sigma(\overline{a}_{1})$ if
$i<n^{\prime}$ and $p_{i}\in\sigma(\overline{c}_{1})$ if $i\geqslant
n^{\prime}$. Also, by the theorem hypotheses, let $f,g$ be any automorphisms
such that $f(\overline{a}_{1})=\overline{a}_{2}$ and
$g(\overline{c}_{1})=\overline{c}_{2}$. Since $\overline{a}_{2}$ and
$\overline{c}_{2}$ are coprime, we have
$\\{f(p_{1}),\dots,f(p_{n^{\prime}-1})\\}\perp\\{g(p_{n^{\prime}}),\dots,g(p_{n})\\}$,
and it thus suffices to show
$\mathbb{M}\models\theta^{f(p_{i})}(\overline{a}_{2},\overline{c}_{2})$ and
$\mathbb{M}\models\theta^{g(p_{j})}(\overline{a}_{2},\overline{c}_{2})$ for
each $i<n^{\prime}$ and $j\geqslant n^{\prime}$. We show the former, as the
latter case is identical; fix $i<n^{\prime}$. Since
$\overline{a}_{1}\perp\overline{c}_{1}$ and
$p_{i}\in\sigma(\overline{a}_{1})$, by Remark 2.1 we have
$\mathbb{M}\models\theta^{p_{i}}(\overline{a}_{1},\overline{1})$; pushing
forward along $f$ tells us
$\mathbb{M}\models\theta^{f(p_{i})}(\overline{a}_{2},\overline{1})$. But
$\overline{a}_{2}\perp\overline{c}_{2}$, and
$f(p_{i})\in\sigma(\overline{a}_{2})$, so again by Remark 2.1 we have
$\mathbb{M}\models\theta^{f(p_{i})}(\overline{a}_{2},\overline{c}_{2})$, as
desired. ∎

######  Lemma 2.5.

Suppose $r_{1},r_{2}\in\sqrt{\mathbb{M}}$. If $\sigma(r_{1})$ and
$\sigma(r_{2})$ are infinite, then $r_{1}\equiv r_{2}$.

###### Proof.

This is essentially an immediate corollary of Theorem A.4; we need only show
that $\theta^{\geqslant n}(r_{1})$ holds if and only if $\theta^{\geqslant
n}(r_{2})$ holds for any formula $\theta$ and $n\in\omega$. But the sentence
$\theta^{p}(1)$ (respectively $\theta^{p}(p)$) holds for some $p\in\mathbb{P}$
if and only if $\theta^{q}(1)$ (respectively $\theta^{q}(q)$) holds for every
$q\in\mathbb{P}$, whence the result follows. ∎

######  Lemma 2.6.

If $\overline{a}$ is any tuple and $B\subset\mathbb{M}$ is any (small)
parameter set, then there exists
$\overline{a}^{\prime}\in\mathbb{M}^{|\overline{a}|}$ a realization of
$\operatorname{tp}(\overline{a})$ such that $\overline{a}^{\prime}\perp B$.

###### Proof.

By compactness, and since $B$ is small, it suffices to replace
$\operatorname{tp}(\overline{a})$ with a single formula
$\phi(\overline{v})\in\operatorname{tp}(\overline{a})$ and to assume that $B$
is finite, say of form $\\{b_{1},\dots,b_{n}\\}$. Now the desired result
follows from the following theorem of $\mathbb{N}$:

$\mathbb{N}\models\forall w_{1}\dots\forall
w_{n}\exists\overline{v}\left[\phi(\overline{v})\wedge\bigwedge_{i\in[n]}\overline{v}\perp
w_{i}\right].$

To see this, let $\overline{e}$ be any realization of $\phi(\overline{v})$ in
$\mathbb{N}$ and $\overline{c}$ any instantiation of $\overline{w}$ in
$\mathbb{N}$. Choose any set of primes $P\subset\mathbb{P}\cap\mathbb{N}$ such
that $|P|=|\sigma(\overline{e})|$ and such that $\sigma(\overline{c})\perp P$,
and let $\overline{e}^{\prime}$ be the image of $\overline{e}$ under any
automorphism of $\mathbb{N}$ taking $\sigma(\overline{e})$ to $P$. Now taking
$\overline{v}=\overline{e}^{\prime}$ gives a realization of
$\phi(\overline{v})$ disjoint from $\overline{c}$, as desired. ∎

The following lemma is convenient when thinking about $\varnothing$-definable
cofinal sets.

######  Lemma 2.7.

Let $a\in\mathbb{M}$, and suppose there exist infinitely many $p\in\mathbb{P}$
such that $a_{p^{\infty}}\neq p^{n}$ for any $n\in\omega$. Then, for any
$c\in\mathbb{M}$, there exists a conjugate $a^{\prime}\equiv a$ such that
$c\mid a^{\prime}$.

###### Proof.

After an automorphism, it suffices to find a realization of
$\operatorname{tp}(c)$ that divides $a$. By compactness, we need only find a
realization of a single formula $\theta(v)\in\operatorname{tp}(c)$ that
divides $a$. Since $\mathbb{M}\models\exists v\theta(v)$, also
$\mathbb{N}\models\exists v\theta(v)$, so let $q_{1}^{k_{1}}\cdot\ldots\cdot
q_{n}^{k_{n}}$ be a realization of $\theta$ in $\mathbb{N}$, where the $q_{i}$
are distinct primes and the $k_{i}\in\omega$. By hypothesis, there exist
primes $p_{1},\dots,p_{n}\in\sigma(a)$ such that $a_{p_{i}^{\infty}}\neq
p_{i}^{k}$ for any $k\in\omega$ and $i\in[n]$. In particular, each
$p_{i}^{k_{i}}$ divides $a_{p_{i}^{\infty}}$, so
$p_{1}^{k_{1}}\cdot\ldots\cdot p_{n}^{k_{n}}$ is a realization of $\theta$
dividing $a$, as desired. ∎

###  2.4 Definability

Given a tuple $\overline{a}\in\mathbb{M}^{n}$, denote its components by
$a_{1}\dots a_{n}$, and define a partial ordering $\preccurlyeq$ on $n$-tuples
by taking $\overline{a}^{1}\preccurlyeq\overline{a}^{2}$ to hold if and only
if $a^{1}_{m}\mid a^{2}_{m}$, where $m\in[n+1]$ is minimal such that
$a^{1}_{m}\neq a^{2}_{m}$. As usual, write
$\overline{a}^{1}\prec\overline{a}^{2}$ to mean that
$\overline{a}^{1}\preccurlyeq\overline{a}^{2}$ and
$\overline{a}^{1}\neq\overline{a}^{2}$. This relation preserves several
properties of divisibility – for example, to check that
$\overline{a}^{1}\preccurlyeq\overline{a}^{2}$ it suffices to show that
$\overline{a}^{1}_{p^{\infty}}\preccurlyeq\overline{a}^{2}_{p^{\infty}}$ for
every $p\in\mathbb{P}$ – but it has the advantage that it descends to a total
ordering on $(p^{\infty})^{n}\subset\mathbb{M}^{n}$ even when $n>1$.

######  Lemma 2.8.

Any non-empty $\mathbb{M}$-definable set $D\subseteq\mathbb{M}^{n}$ has
$\preccurlyeq$-minimal elements: tuples $\overline{d}\in D$ such that, for any
$\overline{e}\in D$, if $\overline{e}\preccurlyeq\overline{d}$ then
$\overline{e}=\overline{d}$.

###### Proof.

Let $\phi(\overline{v};\overline{w})$ be a formula and
$\overline{c}\in\mathbb{M}^{|\overline{w}|}$ a tuple such that
$D=\phi(\mathbb{M}^{n};\overline{c})$. Since, by well-ordering of
$\mathbb{N}$, every non-empty subset of $\mathbb{N}^{n}$ has
$\preccurlyeq$-minimal elements, we have the following theorem of
$\mathbb{N}$,

$\mathbb{N}\models\forall\overline{w}\bigg{[}\exists\overline{v}\phi(\overline{v};\overline{w})\to\exists\overline{v}\left[\phi(\overline{v};\overline{w})\wedge\forall\overline{u}\big{(}\phi(\overline{u};\overline{w})\wedge(\overline{u}\preccurlyeq\overline{v})\to(\overline{u}=\overline{v})\big{)}\right]\bigg{]},$

from which the desired result follows. ∎

The following two lemmas are very useful, giving a degree of control over the
definable closure of a tuple $\overline{c}$; together they imply that any
$\preccurlyeq$-minimal element of a $\overline{c}$-definable set $D$ is
actually definable over $\\{\overline{c}\\}\cup\sqrt{\mathbb{M}}$. Put
differently, the family of $\preccurlyeq$-minimal elements of $D$ can be
parametrized over $\overline{c}$ by a set of radical tuples. Refinements of
this fact, in the form of Lemma 2.15 and Lemma 4.8, play a key role in the
proofs of both of our main results.

######  Lemma 2.9.

Suppose $D\subseteq\mathbb{M}^{n}$ is a $\overline{c}$-definable set, and that
$\overline{d}\in D$ is $\preccurlyeq$-minimal in $D$. Then
$\overline{d}_{p^{\infty}}\in\operatorname{dcl}\\{\overline{c}_{p^{\infty}},p\\}$
for each $p\in\mathbb{P}$.

###### Proof.

Fix $p\in\mathbb{P}$ and suppose that
$\overline{d}_{p^{\infty}}\notin\operatorname{dcl}\\{\overline{c}_{p^{\infty}},p\\}$.
Then, by compactness, we may find some $\overline{q}\in(p^{\infty})^{n}$ such
that $\overline{q}\equiv_{\overline{c}_{p^{\infty}}}\overline{d}_{p^{\infty}}$
and $\overline{q}\prec\overline{d}_{p^{\infty}}$; otherwise
$\overline{d}_{p^{\infty}}$ would be $\preccurlyeq$-minimal in
$(p^{\infty})^{n}$ satisfying some $\overline{c}_{p^{\infty}}$-formula,
contradicting that
$\overline{d}_{p^{\infty}}\notin\operatorname{dcl}\\{\overline{c}_{p^{\infty}},p\\}$.
Now by Lemma 2.4 we have
$\overline{d}_{\neg\\{p\\}}\cdot\overline{q}\equiv_{\overline{c}}\overline{d}$,
whence $\overline{d}_{\neg\\{p\\}}\cdot\overline{q}\in D$, contradicting
$\preccurlyeq$-minimality of $\overline{d}$. ∎

######  Lemma 2.10.

Suppose $\overline{a},\overline{c}$ are tuples such that
$\overline{a}_{p^{\infty}}\in\operatorname{dcl}\\{\overline{c}_{p^{\infty}},p\\}$
for each $p\in\mathbb{P}$. Then $\overline{a}$ is definable over
$\\{\overline{c}\\}\cup\sqrt{\mathbb{M}}$.

###### Proof.

By hypothesis, the following partial type in $u$ is inconsistent:

$\\{\pi(u)\\}\cup\left\\{\phi(\overline{a}_{u^{\infty}},\overline{c}_{u^{\infty}})\to\exists^{>1}\overline{v}\left[\overline{v}\in(u^{\infty})^{n}\wedge\phi(\overline{v},\overline{c}_{u^{\infty}})\right]\right\\}_{\phi}.$

Hence, by compactness, there exist finitely many formulas
$\phi_{1},\dots,\phi_{k}$ such that, for every prime $p\in\mathbb{P}$, one of
$\phi_{i}((p^{\infty})^{n},\overline{c}_{p^{\infty}})=\\{\overline{a}_{p^{\infty}}\\}$
holds for some $i\in[k]$. Now, by Remark 2.3, for each $i\in[k]$ define

$r_{i}=\prod\big{\\{}p\in\sigma(\overline{a}):\phi_{i}((p^{\infty})^{n},\overline{c}_{p^{\infty}})=\\{\overline{a}_{p^{\infty}}\\}\big{\\}}\in\sqrt{\mathbb{M}}.$

Then $\overline{a}$ is definable over $\\{\overline{c},\overline{r}\\}$. ∎

The next lemma says that a set definable over a tuple with support $P_{1}$ and
definable over a tuple with support $P_{2}$ is definable over a tuple with
support $P_{1}\cap P_{2}$. In Section 4 this allows us to show that every
$\mathbb{M}$-definable set is definable over a smallest prime support.

######  Lemma 2.11.

Let $\overline{c}^{1},\overline{c}^{2}$ be any (finite) tuples, and let
$P=\sigma(\overline{c}^{1})\cap\sigma(\overline{c}^{2})$. If
$D\subseteq\mathbb{M}^{n}$ is $\overline{c}^{1}$-definable and
$\overline{c}^{2}$-definable, then $D$ is $\overline{c}^{1}_{P}$-definable.

###### Proof.

Let $f$ be any automorphism fixing $\overline{c}^{1}_{P}$; we will show that
$f$ fixes $D$ setwise. First note that, since
$f(\overline{c}^{1}_{P})=\overline{c}^{1}_{P}$ and
$P\subseteq\sigma(\overline{c}^{1})$, we have $f(P)=P$ and thus
$f(\overline{c}^{1}_{\neg P})\perp P$. In particular, defining
$Q=\sigma(f(\overline{c}_{\neg P}^{1}))\cap\sigma(\overline{c}^{2})$, we have
$Q\perp P$ and $Q\subseteq\sigma(\overline{c}^{2})$, and hence
$Q\perp\overline{c}^{1}$. Thus $f(\overline{c}^{1}_{\neg P})_{Q}\perp
f(\overline{c}_{\neg P}^{1})_{\neg Q}\overline{c}^{1}_{\neg
P}\overline{c}^{1}_{P}$, and so by Lemma 2.4 and Lemma 2.6 we may find an
automorphism $g$ fixing each of the latter three tuples and such that
$g(f(\overline{c}^{1}_{\neg P})_{Q})\perp\overline{c}^{2}$. Since $g$ fixes
$\overline{c}^{1}$, it fixes $D$ setwise, and furthermore we have

$g(f(\overline{c}_{\neg P}^{1}))=g(f(\overline{c}_{\neg P}^{1})_{Q})\cdot
f(\overline{c}_{\neg P}^{1})_{\neg Q},$

whence $g(f(\overline{c}^{1}_{\neg P}))\perp\overline{c}^{2}$; in particular
$g(f(\overline{c}^{1}_{\neg P}))\perp\overline{c}^{1}_{P}$ as well. Thus,
since $g(f(\overline{c}^{1}_{\neg P}))\equiv\overline{c}^{1}_{\neg P}$ and
$\overline{c}^{1}_{\neg P}\perp\overline{c}^{1}_{P}\overline{c}^{2}$, by Lemma
2.4 we may find an automorphism $h$ fixing these latter two tuples and taking
$g(f(\overline{c}^{1}_{\neg P}))$ to $\overline{c}^{1}_{\neg P}$. Since $h$
fixes $\overline{c}^{2}$, it fixes $D$ setwise, so $h\circ g$ fixes $D$
setwise. On the other hand, note that each of $f,g,h$ fix
$\overline{c}^{1}_{P}$, and that $h(g(f(\overline{c}^{1}_{\neg
P})))=\overline{c}^{1}_{\neg P}$ by construction of $h$. In particular,
$h\circ g\circ f$ fixes $\overline{c}^{1}$ and thus fixes $D$ setwise.
Combining these two facts tells us that $f$ fixes $D$ setwise, as desired. ∎

Finally, we record a construction that generalizes the notion of a greatest
common divisor. Since the restriction of $\preccurlyeq$ to
$(p^{\infty})^{n}\subset\mathbb{M}^{n}$ is a total ordering for every
$p\in\mathbb{P}$, if $D\subseteq(p^{\infty})^{n}$ in Lemma 2.8, then $D$ has a
unique $\preccurlyeq$-minimal element, which we denote by
$\min_{\preccurlyeq}(D)$.

######  Lemma 2.12.

Let $D\subseteq\mathbb{M}^{n}$ be a non-empty $\mathbb{M}$-definable set of
$n$-tuples. Then there exists a unique $n$-tuple $\gamma(D)\in\mathbb{M}^{n}$
such that
$\gamma(D)_{p^{\infty}}=\min_{\preccurlyeq}\left\\{\overline{d}_{p^{\infty}}:\overline{d}\in
D\right\\}$ for each $p\in\mathbb{P}$. In particular, we have
$\sigma(\gamma(D))=\bigcap_{\overline{d}\in D}\sigma(\overline{d})$.

###### Proof.

This can be proved exactly as Lemma 2.8, since the desired condition is first-
order expressible and possible for every subset of $\mathbb{N}^{n}$. For the
second part, note that $\overline{1}\preccurlyeq\overline{c}$ for every
$n$-tuple $\overline{c}$. In particular, given $p\in\mathbb{P}$, we have
$\gamma(D)_{p^{\infty}}=\overline{1}$ if and only if there exists some
$\overline{d}\in D$ with $\overline{d}_{p^{\infty}}=\overline{1}$. ∎

Note that $\gamma(D)\preccurlyeq\overline{d}$ for every $\overline{d}\in D$.
If $n=1$, ie if $D\subseteq\mathbb{M}$, then the element
$\gamma(D)\in\mathbb{M}$ is furthermore universal with that property: if
$e\in\mathbb{M}$ is such that $e\preccurlyeq d$, ie $e\mid d$, for every $d\in
D$, then also $e\preccurlyeq\gamma(D)$, ie $e\mid\gamma(D)$. In other words,
in that case, $\gamma(D)$ is precisely the greatest common divisor of $D$.

###  2.5 Cofinal sets

In this section we will consider only $\varnothing$-definable sets of
$1$-tuples. If $D\subseteq\mathbb{M}$ is such, then say that $D$ is cofinal if
it is cofinal with respect to divisibility in $\mathbb{M}$: in other words,
if, for every $c\in\mathbb{M}$, there exists some $d\in D$ such that $c\mid
d$. Fix a cofinal $\varnothing$-definable set $D\subseteq\mathbb{M}$.

######  Lemma 2.13.

We have $\operatorname{dcl}D\supseteq\sqrt{\mathbb{M}}$.

###### Proof.

Fix a radical element $r\in\sqrt{\mathbb{M}}$. By cofinality of $D$, there
exists $d\in D$ such that $r\mid d$. By Lemma 2.6, we may find $e$ a conjugate
of $d_{\neg\sigma(r)}$ such that $e\perp d$. Now by Lemma 2.4 we have
$d=d_{\neg\sigma(r)}\cdot d_{\sigma(r)}\equiv e\cdot d_{\sigma(r)}$, so by
$\varnothing$-definability $e\cdot d_{\sigma(r)}\in D$. But $r$ is now
definable over $\\{d,e\cdot d_{\sigma(r)}\\}$, since its prime factors are
precisely $\sigma(d)\cap\sigma(e\cdot d_{\sigma(r)})$. ∎

We require one fact that we will not prove here. First note that, for any
$p\in\mathbb{P}$, the substructure $p^{\infty}$ of $\mathbb{M}$ is a model of
Presburger arithmetic, since the $p$-adic valuation map induces a monoid
isomorphism between $p^{\infty}\cap\mathbb{N}$ and $(\omega,+)$ whenever
$p\in\mathbb{P}\cap\mathbb{N}$.

######  Fact 2.14.

Let $p\in\mathbb{P}$ and suppose that $q_{1},q_{2}\in p^{\infty}$ are powers
of $p$. If $q_{1}\mid q_{2}$ and $q_{2}$ lies in
$\operatorname{dcl}\\{q_{1},p\\}$, then also
$q_{1}\in\operatorname{dcl}\\{q_{2}\\}$.

###### Proof.

This is a case of ‘exchange’ for Presburger arithmetic; see Example 10 in [2].
∎

######  Lemma 2.15.

We have $\operatorname{dcl}D=\mathbb{M}$.

###### Proof.

Let $c\in\mathbb{M}$. By cofinality of $D$, the $c$-definable set $\\{d\in
D:c\mid d\\}$ is non-empty, and thus by Lemma 2.8 it has a minimal element
$d$. By Lemma 2.9, $d_{p^{\infty}}\in\operatorname{dcl}\\{c_{p^{\infty}},p\\}$
for each $p\in\mathbb{P}$. Since $c\mid d$, also $c_{p^{\infty}}\mid
d_{p^{\infty}}$ for each $p\in\mathbb{P}$, and thus by Fact 2.14
$c_{p^{\infty}}\in\operatorname{dcl}\\{d_{p^{\infty}}\\}$ for each
$p\in\mathbb{P}$. Now by Lemma 2.10, $c$ is definable over
$\\{d\\}\cup\sqrt{\mathbb{M}}$, and since
$\sqrt{\mathbb{M}}\subseteq\operatorname{dcl}D$ by Lemma 2.13, this means that
$c$ is $D$-definable, as desired. ∎

##  3 Stably embedded sets

Recall that a $\varnothing$-definable set $D\subseteq\mathbb{M}^{n}$ is said
to be ‘stably embedded’ if every $\mathbb{M}$-definable subset of $D^{k}$ is
definable with parameters from $D$. [5, p. 136] In this section, we give a
full characterization of the $\varnothing$-definable stably embedded sets of
$T$. Note that, by Lemma 2.15, every cofinal $\varnothing$-definable subset of
$\mathbb{M}$ is stably embedded.

######  Lemma 3.1.

The subset $\sqrt{\mathbb{M}}\subset\mathbb{M}$ is stably embedded.

###### Proof.

Fix a formula $\phi(\overline{v};\overline{w})$ and a tuple
$\overline{c}\in\mathbb{M}^{|\overline{w}|}$, and denote $n=|\overline{v}|$;
we want to show that $\phi(\sqrt{\mathbb{M}}{}^{n};\overline{c})$ is
$\sqrt{\mathbb{M}}$-definable. Thus we will construct a formula
$\psi(\overline{v};\overline{s})$, with parameters $\overline{s}$ from
$\sqrt{\mathbb{M}}$, such that
$\mathbb{M}\models\phi(\overline{r};\overline{c})$ if and only if
$\mathbb{M}\models\psi(\overline{r};\overline{s})$ for any radical $n$-tuple
$\overline{r}$.

By Theorem A.4, we may assume that $\phi(\overline{v};\overline{w})$ is of the
form $\theta^{\geqslant k}(\overline{v};\overline{w})$ for some formula
$\theta(\overline{v};\overline{w})$ and some natural number $k\in\omega$. By
Remark 2.1, $\theta^{\geqslant k}(\overline{r};\overline{c})$ holds if and
only if there are at least $k$ elements $p\in\mathbb{P}$ for which
$\theta^{p}(\overline{r}_{p^{\infty}};\overline{c})$ holds. On the other hand,
if $\overline{r}\in\sqrt{\mathbb{M}}{}^{n}$ is radical, then for any prime $p$
the tuple $\overline{r}_{p^{\infty}}$ is of the form
$p^{{\varepsilon}}:=p^{\varepsilon_{1}}\dots p^{\varepsilon_{n}}$ for some
index tuple $\overline{\varepsilon}\in 2^{n}$. In light of this, for each
index tuple $\overline{\varepsilon}\in 2^{n}$, we define a corresponding new
formula
$\theta_{{\varepsilon}}(u;\overline{w})\equiv\pi(u)\wedge\theta^{u}(u^{\varepsilon_{1}},\dots,u^{\varepsilon_{n}};\overline{w})$.
Then, for any radical tuple $\overline{r}$, we have:

$\mathbb{M}\models\phi(\overline{r};\overline{c})\iff\mathbb{M}\models\theta_{{\varepsilon}}(p;\overline{c})\text{,
where }\overline{r}_{p^{\infty}}=p^{{\varepsilon}},\text{ for at least
}k\text{ elements }p\in\mathbb{P};$

note that the formula $\overline{v}_{u^{\infty}}=u^{{\varepsilon}}$ is first-
order expressible for any $\overline{\varepsilon}\in 2^{n}$.

Now we are in a position to apply Lemma 2.2. For each
$\overline{\varepsilon}\in 2^{n}$, there exists $\neg_{\varepsilon}$ either
the empty string or the string ‘$\neg$’ and a radical element
$s_{\varepsilon}\in\sqrt{\mathbb{M}}$ whose prime support is precisely the set
$\\{p\in\mathbb{P}:\mathbb{M}\models\neg_{{\varepsilon}}\theta_{{\varepsilon}}(p;\overline{c})\\}$.
Now define

$\psi(\overline{v};\overline{s})\equiv\exists^{\geqslant
k}u\left[\pi(u)\wedge\bigwedge_{{\varepsilon}\in
2^{n}}\left[\big{(}\overline{v}_{u^{\infty}}=u^{\varepsilon}\big{)}\to\neg_{\varepsilon}\big{(}u\mid
s_{\varepsilon}\big{)}\right]\right].$

By definition, the condition $u\mid s_{\varepsilon}$ is precisely the
condition that
$\mathbb{M}\models\neg_{{\varepsilon}}\theta_{{\varepsilon}}(u;\overline{c})$.
Thus, for a radical tuple $\overline{r}\in\sqrt{\mathbb{M}}{}^{n}$, the
sentence $\psi(\overline{r};\overline{s})$ says ‘there exist at least $k$
elements $p\in\mathbb{P}$ such that, if $\overline{\varepsilon}\in 2^{n}$ is
such that $\overline{r}_{p^{\infty}}=p^{{\varepsilon}}$, then
$\mathbb{M}\models\theta_{{\varepsilon}}(p;\overline{c})$’. Since every
$\overline{r}_{p^{\infty}}$ will be of form $p^{{\varepsilon}}$ for some
$\overline{\varepsilon}$, and the parameters $s_{\varepsilon}$ all lie in
$\sqrt{\mathbb{M}}$, we are done. ∎

######  Lemma 3.2.

If $D\subseteq\mathbb{M}$ is a $\varnothing$-definable and stably embedded set
of $1$-tuples, and not a subset of $\\{1\\}$, then
$\operatorname{dcl}D\supseteq\sqrt{\mathbb{M}}$.

###### Proof.

Suppose that some $r\in\mathbb{\sqrt{M}}$ is not $D$-definable. First note
that $\sigma(r)$ is infinite, as we have the following: if
$F\subseteq\mathbb{M}$ is any $\varnothing$-definable set that is not a subset
of $\\{1\\}$, then every element decomposable as a product of finitely many
primes is $F$-definable; to see this, it suffices to show that every
$p\in\mathbb{P}$ is $F$-definable. Since $F$ is $\varnothing$-definable, we
have $F\cap\mathbb{N}\nsubseteq\\{1\\}$, so choose any
$a=q_{1}^{k_{1}}\cdot\ldots\cdot q_{n}^{k_{n}}\in
F\cap\mathbb{N}\setminus\\{1\\}$ with the $q_{i}$ distinct primes and the
$k_{i}>0$. We may find automorphisms $g,h$ of $\mathbb{M}$ such that
$g(q_{1})=h(q_{1})=p$, and $g(q_{i})\neq h(q_{j})$ for any $i,j>1$. Then $p$
is $\\{g(a),h(a)\\}$-definable, since it is the only prime dividing both
elements. On the other hand, $F$ is $\varnothing$-definable, so $g(a),h(a)\in
F$, and thus we are done.

So, $r$ has infinitely many prime factors. Now consider the subset $E\subseteq
D$ defined by the formula $\sqrt{v}\mid{r}$. As above, choose any
$a=q_{1}^{k_{1}}\cdot\ldots\cdot q_{n}^{k_{n}}\in
D\cap\mathbb{N}\setminus\\{1\\}$, with the $q_{i}$ distinct primes and the
$k_{i}>0$. Choose any distinct $p_{1},\dots,p_{n}\in\sigma(r)$; then $a$ and
$e:=p_{1}^{k_{1}}\cdot\ldots\cdot p_{n}^{k_{n}}$ are conjugate, and
$\sqrt{e}\mid r$, so $e\in E$. Now we will show that $E$ is not $D$-definable;
indeed, let $\overline{d}\in D^{|\overline{d}|}$ be a finite tuple. Since $r$
is not $D$-definable, there is an automorphism $f$ fixing $\overline{d}$ and
not fixing $r$. Since a radical element is uniquely determined by its prime
factors, we have two cases: either there is a prime $p\mid r$ such that
$f(p)\nmid r$, or there is a prime $p\nmid r$ such that $f(p)\mid r$. By
replacing $f$ with $f^{-1}$ if necessary, we may assume we are in the first
case. Now we may find an automorphism $g$ that swaps $p_{1}$ and $p$ and fixes
$\\{p_{2},\dots,p_{n}\\}\setminus\\{p\\}$; in particular, since $p\mid r$, we
still have $g(e)\in E$. On the other hand, since $p_{1}\mid e$, we have $p\mid
g(e)$ and hence $f(p)\mid f(g(e))$. Since $f(p)\nmid r$, this means
$f(g(e))\notin E$, and thus, since $g(e)\in E$, $f$ does not fix $E$ setwise.
Since $\overline{d}$ was arbitrary, this show that $E$ is not $D$-definable,
whence $D$ is not stably embedded. ∎

For terminological convenience, given a prime $p\in\mathbb{P}$ and an element
$a\in\mathbb{M}$, say that $p$ is ‘non-standard in $a$’ if $a_{p^{\infty}}\neq
p^{n}$ for any $n\in\omega$. Say that $p$ is ‘standard in $a$’ otherwise.

######  Lemma 3.3.

If $D\subseteq\mathbb{M}$ is a $\varnothing$-definable and stably embedded set
of $1$-tuples, and not a subset of $\operatorname{dcl}\sqrt{\mathbb{M}}$, then
$\operatorname{dcl}D=\mathbb{M}$.

###### Proof.

By Lemma 2.15, it suffices to show that $D$ is cofinal, so assume otherwise
for contradiction. By Lemma 2.7, and since $D$ is definable without
parameters, this means that there are only finitely many primes non-standard
in $d$ for any $d\in D$. On the other hand,
$D\nsubseteq\operatorname{dcl}\sqrt{\mathbb{M}}$, so let $d$ be an element of
$D$ outside of $\operatorname{dcl}\sqrt{\mathbb{M}}$; we claim there is at
least one prime non-standard in $d$. Otherwise, by compactness, there exists a
finite bound $n_{0}\in\omega$ such that $d_{p^{\infty}}\mid p^{n_{0}}$ for
every $p\in\mathbb{P}$. By Remark 2.3, there exists a radical element $s_{i}$
with support $\\{p\in\sigma(d):d_{p^{\infty}}=p^{i}\\}$ for each
$i\in[n_{0}]$, and then $d$ is definable over $\overline{s}$, contradicting
that $d\notin\operatorname{dcl}\sqrt{\mathbb{M}}$.

Now choose any element $c\in\mathbb{M}$ such that there are infinitely many
primes non-standard in $c$. We claim that the subset $E\subseteq D$ defined by
the formula $v\mid c$ is not $D$-definable, which will show the desired
result. To see this, let $\overline{d}$ be any finite tuple from $D$. By
construction of $c$, and since there are only finitely many primes non-
standard in each $d_{i}$, there exists a prime $p\in\mathbb{P}$ non-standard
in $c$ but standard in every $d_{i}$.

Now, by the first paragraph, let $d$ be any element of $D$ with at least one
non-standard prime. By the proof of Lemma 2.7 and construction of $c$, there
exists a conjugate $e\equiv d$ such that $e\mid c$ and such that $p$ is non-
standard in $e$. Since $D$ is $\varnothing$-definable, $e\in D$, and hence
$e\in E$. On the other hand, since $p$ is non-standard in $e$, we may find an
element $q\in p^{\infty}$ such that $q\equiv e_{p^{\infty}}$ and such that
$q\nmid c_{p^{\infty}}$. Since $p$ is standard in every $d_{i}$, we then have
$q\equiv_{\overline{d}}e_{p^{\infty}}$, and so by Lemma 2.4 we also have
$e_{\neg\\{p\\}}\cdot q\equiv_{\overline{d}}e$. But $q\nmid c_{p^{\infty}}$,
so $e_{\neg\\{p\\}}\cdot q\notin E$, and hence $E$ is not
$\overline{d}$-definable. Since $\overline{d}$ was arbitrary, $E$ is thus not
$D$-definable, as desired. ∎

######  Theorem 3.4.

A $\varnothing$-definable set $D\subseteq\mathbb{M}^{n}$ is stably embedded if
and only if $\operatorname{dcl}D$ is one of the sets $\\{1\\}$,
$\operatorname{dcl}\sqrt{\mathbb{M}}$, and $\mathbb{M}$.

###### Proof.

The sets $\\{1\\}$ and $\mathbb{M}$ are trivially stably embedded, and
$\sqrt{\mathbb{M}}$ is stably embedded by Lemma 3.1. Hence the backwards
direction follows from Lemma C.2. For the forwards direction, again by Lemma
C.2, we may assume that $n=1$, and then the desired implications are given in
Lemma 3.2 and Lemma 3.3. ∎

##  4 Imaginaries

Let $D\subseteq\mathbb{M}^{n}$ be an $X$-definable set for some finite set
$X\subset\mathbb{M}$. Recall that $X$ is a ‘canonical parameter’ for $D$ if it
is fixed pointwise by every automorphism of $\mathbb{M}$ fixing $D$ setwise,
and that $X$ is an ‘almost canonical parameter’ for $D$ if it is fixed setwise
by every automorphism of $\mathbb{M}$ fixing $D$ setwise.

Further recall that a theory $T$ has ‘elimination of imaginaries’ (EI) if
every $\mathbb{M}$-definable set $D\subseteq\mathbb{M}^{n}$ has a canonical
parameter, ‘elimination of finite imaginaries’ if every finite subset of
$\mathbb{M}^{n}$ has a canonical parameter, and ‘weak elimination of
imaginaries’ (WEI) if every $\mathbb{M}$-definable set
$D\subseteq\mathbb{M}^{n}$ has an almost canonical parameter. [5, p. 139] It
is well-known that, to check EI and WEI, it suffices to assume that $D$ is an
equivalence class of a $\varnothing$-definable equivalence relation
$E\subseteq\mathbb{M}^{m}\times\mathbb{M}^{m}$; indeed, if
$D=\phi(\mathbb{M}^{n};\overline{c})$ for some formula
$\phi(\overline{v};\overline{w})$ and some tuple
$\overline{c}\in\mathbb{M}^{m}$, then we may define the equivalence relation

$E(\overline{w}_{1},\overline{w}_{2})\equiv\forall\overline{v}\left[\phi(\overline{v};\overline{w}_{1})\leftrightarrow\phi(\overline{v};\overline{w}_{2})\right],$

and the equivalence class $\overline{c}^{E}$ will be fixed setwise by
precisely the automorphisms of $\mathbb{M}$ fixing $D$ setwise.

######  Remark 4.1.

By Lemma 2.2, any $\mathbb{M}$-definable subset of $\mathbb{P}$ has a
canonical parameter.

We will show that Skolem arithmetic does not have elimination of finite
imaginaries, but that it does have WEI; we prove the latter result by reducing
the question from $\mathbb{M}$-definable sets to $\sqrt{\mathbb{M}}$-definable
sets, the latter being more tractable.

######  Theorem 4.2.

$T$ does not eliminate finite imaginaries.

###### Proof.

Fix any distinct primes $p_{1},p_{2},q_{1},q_{2}\in\mathbb{P}$, and define
$a=p_{1}\cdot p_{2}$ and $b=q_{1}\cdot q_{2}$. We will show that $\\{a,b\\}$
has no canonical parameter. To see this, suppose that $e\in\mathbb{M}$ is any
element fixed by all automorphisms fixing $\\{a,b\\}$ setwise. Then we claim
that

$e_{p_{1}^{\infty}}\equiv e_{p_{2}^{\infty}}\equiv e_{q_{1}^{\infty}}\equiv
e_{q_{2}^{\infty}}.$

Indeed, the automorphisms of $\mathbb{M}$ fixing $\\{a,b\\}$ setwise are the
disjoint union of those that fix both of $\\{p_{1},p_{2}\\}$ and
$\\{q_{1},q_{2}\\}$ setwise and those that swap the sets $\\{p_{1},p_{2}\\}$
and $\\{q_{1},q_{2}\\}$. In particular, for each
$r,s\in\\{p_{1},p_{2},q_{1},q_{2}\\}$, there is an automorphism fixing
$\\{a,b\\}$ setwise – hence fixing $e$ – and swapping $r$ and $s$, whence the
claim follows. Thus if $X\subset\mathbb{M}$ is any finite subset fixed
pointwise by every automorphism of $\mathbb{M}$ fixing $\\{a,b\\}$ setwise,
then we may find an automorphism fixing $X$ pointwise, swapping $p_{1}$ and
$q_{1}$, and fixing $p_{2}$ and $q_{2}$. This automorphism takes $a$ to
$p_{1}\cdot q_{1}$ and $b$ to $p_{2}\cdot q_{2}$, hence does not fix
$\\{a,b\\}$ setwise, and the result follows. ∎

Now we begin showing that $T$ has WEI; throughout the rest of this section, we
will fix a $\varnothing$-definable equivalence relation
$E\subseteq\mathbb{M}^{n}\times\mathbb{M}^{n}$ and a tuple
$\overline{a}\in\mathbb{M}^{n}$; we will show that $\overline{a}^{E}$ has an
almost canonical parameter. We begin by showing that $\overline{a}^{E}$ is
definable over a smallest prime support. Recall the $n$-tuple
$\gamma(\overline{a}^{E})$ defined in Lemma 2.12, each $p$-part of which is
$\min_{\preccurlyeq}\left\\{\overline{a}^{\prime}_{p^{\infty}}:\overline{a}^{\prime}\in\overline{a}^{E}\right\\}$,
and recall in particular that
$\sigma(\gamma(\overline{a}^{E}))=\bigcap_{\overline{a}^{\prime}\in\overline{a}^{E}}\sigma(\overline{a}^{\prime})$.

######  Lemma 4.3.

There exists $\overline{a}^{\prime}\in\overline{a}^{E}$ such that
$\sigma(\overline{a})\cap\sigma(\overline{a}^{\prime})=\sigma(\gamma(\overline{a}^{E}))$.

###### Proof.

It suffices to show that

$\mathbb{N}\models\forall\overline{v}\exists\overline{v}^{\prime}\left[E(\overline{v},\overline{v}^{\prime})\wedge\left(\sigma(\overline{v})\cap\sigma(\overline{v}^{\prime})=\sigma(\gamma(\overline{v}^{E}))\right)\right],$

so we may assume that $\overline{a}\in\mathbb{N}^{n}$ and that
$E\subseteq\mathbb{N}^{n}\times\mathbb{N}^{n}$. Let
$\overline{a}^{\prime}\in\overline{a}^{E}$ be such that
$|\sigma(\overline{a})\cap\sigma(\overline{a}^{\prime})|$ is minimal possible;
we claim that $\overline{a}^{\prime}$ has the desired property. If not, then
there exists some $\overline{a}^{\prime\prime}\in\overline{a}^{E}$ such that
$\sigma(\overline{a})\cap\sigma(\overline{a}^{\prime})\nsubseteq\sigma(\overline{a}^{\prime\prime})$;
let
$p\in\left(\sigma(\overline{a})\cap\sigma(\overline{a}^{\prime})\right)\setminus\sigma(\overline{a}^{\prime\prime})$,
and let $q\in\mathbb{P}\cap\mathbb{N}$ be any prime not in
$\sigma(\overline{a})\cup\sigma(\overline{a}^{\prime})\cup\sigma(\overline{a}^{\prime\prime})$.
Now we may find an automorphism $f:\mathbb{N}\to\mathbb{N}$ swapping $p$ and
$q$ and fixing all other primes in
$\sigma(\overline{a})\cup\sigma(\overline{a}^{\prime})\cup\sigma(\overline{a}^{\prime\prime})$.
Since $p\notin\sigma(\overline{a}^{\prime\prime})$, $f$ fixes
$\overline{a}^{\prime\prime}$, and hence fixes $\overline{a}^{E}$ setwise. In
particular, $f(\overline{a}^{\prime})\in a^{E}$. But also

$\sigma(\overline{a})\cap\sigma(f(\overline{a}^{\prime}))=\sigma(\overline{a})\cap\sigma(\overline{a}^{\prime})\setminus\\{p\\},$

so this contradicts minimality of
$|\sigma(\overline{a})\cap\sigma(\overline{a}^{\prime})|$, as desired. ∎

######  Corollary 4.4.

$\overline{a}^{E}$ is definable over
$\overline{a}_{\sigma(\gamma(\overline{a}^{E}))}$. Conversely,
$\sigma(\gamma(\overline{a}^{E}))$ is the smallest prime support over which
$\overline{a}^{E}$ is definable; in other words, if $\overline{a}^{E}$ is
$\overline{c}$-definable for some tuple $\overline{c}$, then
$\sigma(\gamma(\overline{a}^{E}))\subseteq\sigma(\overline{c})$.

###### Proof.

First we show the first statement. By Lemma 4.3, we may find an element
$\overline{a}^{\prime}\in a^{E}$ such that
$\sigma(\overline{a})\cap\sigma(\overline{a}^{\prime})=\sigma(\gamma(\overline{a}^{E}))$.
Since $\overline{a}^{E}$ is $\overline{a}^{\prime}$-definable, by Lemma 2.11
$\overline{a}^{E}$ is also
$\overline{a}_{\sigma(\overline{a}^{\prime})}$-definable, and the desired
result follows.

For the second statement, suppose $\overline{c}$ is otherwise, and let
$p\in\sigma(\gamma(\overline{a}^{E}))\setminus\sigma(\overline{c})$. Now let
$q$ be any prime outside of $\sigma(\overline{a})\cup\sigma(\overline{c})$. We
may find an automorphism $f$ that fixes $\overline{c}$ and swaps $p$ and $q$.
Since $f$ fixes $\overline{c}$, it must also fix $\overline{a}^{E}$ setwise.
On the other hand, $p\notin\sigma(f(\overline{a}))$, so since
$p\in\sigma(\gamma(\overline{a}^{E}))$ we have
$f(\overline{a})\notin\overline{a}^{E}$, a contradiction. ∎

The following two lemmas show that every $\sqrt{\mathbb{M}}$-definable set has
an almost canonical parameter; combined with stable embeddedness of
$\sqrt{\mathbb{M}}$, this is enough to show that every $\mathbb{M}$-definable
subset of $\sqrt{\mathbb{M}}{}^{m}$ has an almost canonical parameter.

######  Lemma 4.5.

If $D\subseteq\mathbb{M}^{n}$ is $\sqrt{\mathbb{M}}$-definable, then there
exists a tuple $\overline{r}\in\sqrt{\mathbb{M}}{}^{m}$ over which $D$ is
definable, such that (i) $r_{i}\perp r_{j}$ for each $i\neq j$, and (ii)
$\sigma(\overline{r})$ is the smallest prime support over which $D$ is
definable.

###### Proof.

Suppose $D$ is definable over a $k$-tuple
$\overline{s}\in\sqrt{\mathbb{M}}{}^{k}$. By uniqueness of base $2$
representations, the tuple $\overline{s}$ is interdefinable with the element

$s:=s_{1}\cdot s_{2}^{2}\cdot\ldots\cdot s_{k}^{2^{k-1}}\in\mathbb{M},$

so there exists a formula $\phi(\overline{v};w)$ with
$D=\phi(\mathbb{M}^{n};s)$. As usual, take

$E(w_{1},w_{2})\equiv\forall\overline{v}\left[\phi(\overline{v};w_{1})\leftrightarrow\phi(\overline{v};w_{2})\right].$

By Corollary 4.4, $s^{E}$ and hence $D$ are definable over
$s^{\prime}:=s_{\sigma(\gamma(s^{E}))}$. Since also $s^{\prime}\mid s$, for
every $p\in\sigma(s^{\prime})$ we have $s^{\prime}_{p^{\infty}}=p^{i}$ for
some $i\in[2^{k}-1]$. Thus take $m=2^{k}-1$ and define a radical element
$r_{i}=\prod\left\\{p\in\sigma(s^{\prime}):s^{\prime}_{p^{\infty}}=p^{i}\right\\}$
for each $i\in[m]$; then $s^{\prime}$ is definable over $\overline{r}$,
$r_{i}\perp r_{j}$ for each $i\neq j$, and
$\sigma(\overline{r})=\sigma(s^{\prime})=\sigma(\gamma(s^{E}))$ is the
smallest support over which $D$ is definable, again by Corollary 4.4, so this
gives the desired result. ∎

######  Lemma 4.6.

If $D\subseteq\mathbb{M}^{n}$ is definable over some tuple
$\overline{r}\in\sqrt{\mathbb{M}}{}^{m}$, where the $r_{i}$ satisfy the
conditions of Lemma 4.5 and $m$ is minimal possible, then every automorphism
fixing $D$ setwise permutes the $r_{i}$.

###### Proof.

Let $D=\phi(\mathbb{M}^{n};\overline{r})$ for some formula
$\phi(\overline{v};\overline{w})$, and suppose for contradiction that $\alpha$
is an automorphism fixing $D$ setwise but not permuting the $r_{i}$. Since
$\sigma(\overline{r})$ is the smallest support over which $D$ is definable, we
have $\sigma(\alpha(\overline{r}))=\sigma(\overline{r})$. Since also
$r_{i}\perp r_{j}$ for each $i\neq j$, there must hence be some $k\in[m]$ such
that $\sigma(\alpha(r_{k}))\nsubseteq\sigma(r_{i})$ for any $i\in[m]$. Thus
$\sigma(\alpha(r_{k}))$ has non-empty intersection with at least two of the
$\sigma(r_{i})$; without loss of generality suppose there exists
$q_{l}\in\sigma(\alpha(r_{k}))\cap\sigma(r_{l})$ for each $l\in\\{1,2\\}$. We
will show that $D$ is definable over $\\{r_{1}\cdot
r_{2},r_{3},\dots,r_{m}\\}$, which will contradict minimality of $m$ and hence
give the desired result. First we require the following:

######  Claim 1.

For any finite subsets $P_{1}\subseteq\sigma(r_{1})$ and
$P_{2}\subseteq\sigma(r_{2})$ with $|P_{1}|=|P_{2}|$, there is an automorphism
fixing $D$ setwise, swapping $P_{1}$ and $P_{2}$, and fixing
$\overline{r}_{\neg(P_{1}\cup P_{2})}$.

###### Proof of claim.

Let $i=|P_{l}|$ for $l\in\\{1,2\\}$; we prove the claim by induction on $i$.
The case $i=0$ is trivial, since we may simply take the automorphism to be the
identity. Hence suppose each $|P_{l}|=i+1$, so that
$P_{l}=P_{l}^{\prime}\sqcup\\{p_{l}\\}$ for some $P_{l}^{\prime}\subset P_{l}$
of size $i$. Assume without loss of generality that $q_{l}\notin
P^{\prime}_{l}$ for either $l$, so that if $q_{l}\in P_{l}$ then
$q_{l}=p_{l}$. Now, by the induction hypothesis we may find an automorphism
$f$ that has the desired properties with respect to $P_{1}^{\prime}$ and
$P_{2}^{\prime}$. Since $f$ fixes $\overline{r}_{\neg(P_{1}^{\prime}\cup
P_{2}^{\prime})}$ and $p_{l},q_{l}\notin P_{1}^{\prime}\cup P_{2}^{\prime}$
for either $l\in\\{1,2\\}$, we have $p_{l},q_{l}\in\sigma(f(r_{l}))$ for each
$l\in\\{1,2\\}$. Thus we may first find an automorphism $f^{\prime}$ that
fixes $f(\overline{r})$ and fixes $P_{1}^{\prime}\cup P^{\prime}_{2}$
pointwise, and swaps each $p_{l}$ with each $f(p_{l})$, and then similarly
find an automorphism $g$ that fixes $f(\overline{r})$ and fixes
$P^{\prime}_{1}\cup P^{\prime}_{2}$ pointwise, and swaps each $p_{l}$ with
each $q_{l}$. Since $f$ fixes $D$ setwise, $D$ is $f(\overline{r})$-definable,
so both $f^{\prime}$ and $g$ also fix $D$ setwise. On the other hand,
$q_{1},q_{2}\in\sigma(\alpha(r_{k}))$, so we may find an automorphism $h$
swapping $q_{1}$ and $q_{2}$, fixing $\alpha(\overline{r})$ and
$f(\overline{r})_{\neg\\{q_{1},q_{2}\\}}$, and fixing $P_{1}\cup
P_{2}\setminus\\{q_{1},q_{2}\\}$ pointwise; since $h$ fixes
$\alpha(\overline{r})$, it also fixes $D$ setwise. Thus let
$f^{\prime\prime}=g\circ h\circ g$; we claim that $f^{\prime\prime}\circ
f^{\prime}\circ f$ has the desired properties. Each of $f$, $f^{\prime}$, and
$f^{\prime\prime}$ fix $D$ setwise, so $f^{\prime\prime}\circ f^{\prime}\circ
f$ does too. Since $f^{\prime\prime}$ and $f^{\prime}$ fix $P^{\prime}_{1}\cup
P^{\prime}_{2}$ pointwise, and $f$ swaps $P_{1}^{\prime}$ and
$P_{2}^{\prime}$, $f^{\prime\prime}\circ f^{\prime}\circ f$ swaps
$P^{\prime}_{1}$ and $P_{2}^{\prime}$ too. On the other hand, we have

$\displaystyle(f^{\prime\prime}\circ f^{\prime}\circ f)(p_{l})$
$\displaystyle=(g\circ h\circ g)(f^{\prime}(f(p_{l})))$ $\displaystyle=(g\circ
h\circ g)(p_{l})$ $\displaystyle=(g\circ h)(q_{l})=g(q_{3-l})=p_{3-l}$

for each $l\in\\{1,2\\}$, so that in fact $f^{\prime\prime}\circ
f^{\prime}\circ f$ swaps $P_{1}$ and $P_{2}$. For the final property, note
that $f$ fixes $\overline{r}_{\neg(P_{1}^{\prime}\cup P_{2}^{\prime})}$, and
that $f^{\prime}$ fixes $f(\overline{r})$ and
$P^{\prime}_{1}\cup{P_{2}^{\prime}}$, so that $f^{\prime}$ fixes
$\overline{r}_{\neg(P^{\prime}_{1}\cup P^{\prime}_{2})}$. But $f^{\prime}$
also swaps each $p_{l}$ and each $f(p_{l})$, so in fact $f^{\prime}\circ f$
fixes $\overline{r}_{\neg(P_{1}\cup P_{2})}$. Similarly, $g\circ h\circ g$
fixes $f(\overline{r})_{\neg\\{p_{1},p_{2}\\}}$ and $P^{\prime}_{1}\cup
P^{\prime}_{2}$, and thus fixes $\overline{r}_{\neg(P_{1}\cup P_{2})}$ too, as
desired. ∎

A corollary is that, for any finite subsets
$P_{1},P_{2}\subseteq\sigma(r_{1})\cup\sigma(r_{2})$ with $|P_{1}|=|P_{2}|$,
there is an automorphism fixing $D$ setwise, swapping $P_{1}$ and $P_{2}$, and
fixing $\overline{r}_{\neg(P_{1}\cup P_{2})}$. Now, consider the
$\mathbb{M}$-definable set

$\displaystyle
X:=\big{\\{}r^{\prime}_{1}r^{\prime}_{2}\in\sqrt{\mathbb{M}}{}^{2}:\ $
$\displaystyle r^{\prime}_{1}\cdot r^{\prime}_{2}=r_{1}\cdot
r_{2},r^{\prime}_{1}r^{\prime}_{2}\preccurlyeq r_{1}r_{2},r^{\prime}_{1}\perp
r^{\prime}_{2},$ $\displaystyle\text{ and
}D=\phi(\mathbb{M}^{n};r^{\prime}_{1},r^{\prime}_{2},r_{3},\dots,r_{m})\big{\\}}.$

By Lemma 2.8, $X$ has a $\preccurlyeq$-minimal element
$r^{\prime}_{1}r^{\prime}_{2}$. Since
$r^{\prime}_{1}r^{\prime}_{2}\preccurlyeq r_{1}r_{2}$, we have
$\sigma(r^{\prime}_{1})\subseteq\sigma(r_{1})$; since also
$r_{1}^{\prime}\cdot r_{2}^{\prime}=r_{1}\cdot r_{2}$, we have
$\sigma(r^{\prime}_{2})\supseteq\sigma(r_{2})$ as well.

######  Claim 2.

One of $\sigma(r^{\prime}_{1})$ and $\sigma(r^{\prime}_{2})$ is finite.

###### Proof of claim.

Suppose for contradiction that both sets are infinite. Then, by Claim 1 and
compactness, we may find a $2$-tuple
$r^{\prime\prime}_{1}r^{\prime\prime}_{2}\in\sqrt{\mathbb{M}}{}^{2}$ that is
conjugate to $r_{1}r_{2}$ and such that: (i) $r^{\prime\prime}_{1}\cdot
r^{\prime\prime}_{2}=r_{1}\cdot r_{2}$, (ii)
$D=\phi(\mathbb{M}^{n};r^{\prime\prime}_{1},r^{\prime\prime}_{2},r_{3},\dots,r_{m})$,
and (iii) $P_{l}:=\sigma(r^{\prime}_{l})\cap\sigma(r^{\prime\prime}_{1})$ is
infinite for each $l\in\\{1,2\\}$. Now, choose any $p\in P_{1}$. By Lemma 2.4
and Lemma 2.5, we have

$r^{\prime\prime}_{1,P_{1}}r^{\prime\prime}_{1,P_{2}}\equiv
r^{\prime\prime}_{1,P_{1}\setminus\\{p\\}}r^{\prime\prime}_{1,P_{2}\cup\\{p\\}},$

and we may thus find an automorphism $f$ taking the first tuple to the second
and fixing all of the following tuples:
$r_{1}^{\prime\prime}r_{2}^{\prime\prime}$ and $r_{3}\dots r_{m}$ and
$(r_{1}^{\prime}r_{2}^{\prime})_{\neg\sigma(r^{\prime\prime}_{1})}$. Since $f$
fixes $r^{\prime\prime}_{1}r^{\prime\prime}_{2}r_{3}\dots r_{m}$, by condition
(ii) $f$ fixes $D$ setwise, whence
$D=\phi(\mathbb{M}^{n};f(r^{\prime}_{1}),f(r^{\prime}_{2}),r_{3},\dots,r_{m})$.
Also, $f$ fixes $r_{1}\cdot r_{2}=r^{\prime\prime}_{1}\cdot
r^{\prime\prime}_{2}$, so $f(r^{\prime}_{1})\cdot f(r^{\prime}_{2})=r_{1}\cdot
r_{2}$ as well. On the other hand, $f$ fixes
$\sigma(r_{1}^{\prime})\setminus\sigma(r^{\prime\prime}_{1})$ setwise, and
$f(P_{1})=P_{1}\setminus\\{p\\}$. Thus
$\sigma(f(r^{\prime}_{1}))=\sigma(r^{\prime}_{1})\setminus\\{p\\}$, whence
$f(r^{\prime}_{1})f(r^{\prime}_{2})\prec r^{\prime}_{1}r^{\prime}_{2}$, so
$f(r^{\prime}_{1})f(r^{\prime}_{2})$ lies in $X$ and contradicts
$\preccurlyeq$-minimality of $r^{\prime}_{1}r^{\prime}_{2}$ in $X$. ∎

Now we can show that $D$ is $\\{r_{1}\cdot
r_{2},r_{3},\dots,r_{m}\\}$-definable; to see this, let $f$ be any
automorphism fixing the latter set pointwise. By Claim 2, one of
$\sigma(r^{\prime}_{1})$ and $\sigma(r^{\prime}_{2})$ is finite. If the latter
is finite, then the subset $\sigma(r_{2})\subseteq\sigma(r^{\prime}_{2})$ is
also finite, and by the remark following Claim 1 we can find an automorphism
$g$ that fixes the product $r_{1}\cdot r_{2}$ and the tuple $r_{3}\dots
r_{m}$, fixes $D$ setwise, and takes $\sigma(f(r_{2}))$ to $\sigma(r_{2})$.
Then $g\circ f$ fixes $\overline{r}$, hence fixes $D$ setwise, and so $f$
fixes $D$ setwise as well. The case when $\sigma(r^{\prime}_{1})$ is finite is
nearly identical; by the remark following Claim 1, we can find an automorphism
$g$ that fixes the product $r_{1}\cdot r_{2}$ and the tuple $r_{3}\dots
r_{m}$, fixes $D$ setwise, and takes $\sigma(f(r^{\prime}_{1}))$ to
$\sigma(r^{\prime}_{1})$. Then $g\circ f$ fixes
$r^{\prime}_{1}r^{\prime}_{2}r_{3}\dots r_{m}$, hence fixes $D$ setwise by
definition of $X$, and so $f$ again fixes $D$ setwise. In either case, we have
shown that $D$ is $\\{r_{1}\cdot r_{2},r_{3},\dots,r_{m}\\}$-definable, which
contradicts minimality of $m$ and thus gives the desired result. ∎

######  Corollary 4.7.

Any $\mathbb{M}$-definable subset of $\sqrt{\mathbb{M}}{}^{n}$ has an almost
canonical parameter.

###### Proof.

Let $D\subseteq\sqrt{\mathbb{M}}{}^{n}$ be $\mathbb{M}$-definable. By Lemma
3.1, ie since $\sqrt{\mathbb{M}}$ is stably embedded, $D$ is
$\sqrt{\mathbb{M}}$-definable. Thus, by Lemma 4.5 and Lemma 4.6, $D$ is
definable over some $\overline{r}\in\sqrt{\mathbb{M}}{}^{m}$ such that every
automorphism of $\mathbb{M}$ fixing $D$ setwise permutes the $r_{i}$. So
$\\{r_{1},\dots,r_{m}\\}$ is an almost canonical parameter for $D$, and the
result follows. ∎

Now return to the case where $E\subseteq\mathbb{M}^{n}\times\mathbb{M}^{n}$ is
an arbitrary $\varnothing$-definable equivalence relation of $n$-tuples and
$\overline{a}\in\mathbb{M}^{n}$ is an $n$-tuple. Equipped with Corollary 4.7,
in order to show that $\overline{a}^{E}$ has an almost canonical parameter, we
need only reduce the question to showing that a suitable definable subset of
$\sqrt{\mathbb{M}}{}^{m}$ has an almost canonical parameter. We do this via
the lemmas on definability proven in Section 2.4.

######  Lemma 4.8.

$\overline{a}^{E}$ is definable over
$\left\\{\gamma(\overline{a}^{E})\right\\}\cup\sqrt{\mathbb{M}}$.

###### Proof.

By Lemma 2.8, let $\overline{a}^{\prime}$ be any $\preccurlyeq$-minimal
element of $\overline{a}^{E}$. Since $\overline{a}^{E}$ is
$\overline{a}^{\prime}$-definable, it suffices to show that
$\overline{a}^{\prime}$ is definable over
$\left\\{\gamma(\overline{a}^{E})\right\\}\cup\sqrt{\mathbb{M}}$. Furthermore,
by Lemma 2.10, it suffices for this to show that
$\overline{a}^{\prime}_{p^{\infty}}\in\operatorname{dcl}\left\\{\gamma(\overline{a}^{E})_{p^{\infty}},p\right\\}$
for each $p\in\mathbb{P}$. Thus fix any $p\in\mathbb{P}$. By definition,
$\gamma(\overline{a}^{E})_{p^{\infty}}$ is $\preccurlyeq$-minimal among the
$p$-parts of the elements of $\overline{a}^{E}$, so there exists some
$\overline{a}^{\prime\prime}\in\overline{a}^{E}$ such that
$\gamma(\overline{a}^{E})_{p^{\infty}}=\overline{a}^{\prime\prime}_{p^{\infty}}$.
Now $\overline{a}^{E}$ is $\overline{a}^{\prime\prime}$-definable; since
$\overline{a}^{\prime}$ is $\preccurlyeq$-minimal in $\overline{a}^{E}$, by
Lemma 2.9 we thus have
$\overline{a}^{\prime}_{p^{\infty}}\in\operatorname{dcl}\left\\{\overline{a}^{\prime\prime}_{p^{\infty}},p\right\\}$,
and the result follows. ∎

######  Theorem 4.9.

$T$ has weak elimination of imaginaries.

###### Proof.

We need to show that $\overline{a}^{E}$ has an almost canonical parameter. By
Lemma 4.8, let $\overline{s}\in\sqrt{\mathbb{M}}{}^{m}$ be any radical tuple
such that $\overline{a}^{E}$ is definable over
$\left\\{\gamma(\overline{a}^{E}),\overline{s}\right\\}$, and choose a formula
$\phi(\overline{v};\overline{u},\overline{w})$ such that
$\overline{a}^{E}=\phi(\mathbb{M}^{n};\gamma(\overline{a}^{E}),\overline{s})$.
By Corollary 4.7, the $\mathbb{M}$-definable set

$D:=\left\\{\overline{s}^{\prime}\in\sqrt{\mathbb{M}}{}^{m}:\overline{a}^{E}=\phi(\mathbb{M}^{n};\gamma(\overline{a}^{E}),\overline{s}^{\prime})\right\\}\subseteq\sqrt{\mathbb{M}}{}^{m}$

has an almost canonical parameter $X\subset\mathbb{M}$. $D$ is definable over
$X$, so $\overline{a}^{E}$ is definable over the union
$\left\\{\gamma(\overline{a}^{E})\right\\}\cup X$. On the other hand, every
automorphism of $\mathbb{M}$ that fixes $\overline{a}^{E}$ setwise fixes
$\gamma(\overline{a}^{E})$, hence also fixes $D$ setwise, and hence fixes $X$
setwise as well. So each such automorphism fixes
$\left\\{\gamma(\overline{a}^{E})\right\\}\cup X$ setwise, and this latter set
is thus an almost canonical parameter for $\overline{a}^{E}$. ∎

##  Appendix A Proof of QE

######  Remark A.1.

Following the notation of Jeřábek [4], we will occasionally find it convenient
to write the formula $\phi^{\geqslant n}(\overline{v})$ as
$|S(\overline{v})|\geqslant n$, where $S(\overline{v})$ is the ‘set’, which
depends on $\overline{v}$, of the form
$\left\\{p\in\mathbb{P}:\phi^{p}(\overline{v})\right\\}$. In particular, if
$(S_{i}(\overline{v}))_{i\in I}$ is a family of such ‘sets’, then any Boolean
combination of (finitely many) of the $S_{i}(\overline{v})$ will also be of
that form.

We will prove the desired result in a series of lemmas. Use $\neg_{0}$ to
denote the string ‘$\neg$’ and $\neg_{1}$ to denote the empty string. Also,
given a natural number $k\in\omega$, let $2^{k}$ denote the set of $k$-tuples
whose entries are all $0$ or $1$. We will use $2^{k}_{0}$ to mean
$2^{k}\setminus\\{\overline{0}\\}$.

######  Lemma A.2.

For any formulas $\phi_{i}(\overline{v})$ and $\psi_{j}(\overline{v})$ and any
natural numbers $m_{i},n_{j}\in\omega$, the formula

$\eta(\overline{v})\equiv\bigwedge_{i\in[k]}\phi_{i}^{\leqslant
m_{i}}(\overline{v})\wedge\bigwedge_{j\in[l]}\psi_{j}^{\geqslant
n_{j}}(\overline{v})$

is equivalent to a disjunction of formulas of the form

$\bigwedge_{\alpha\in
I}\theta_{\alpha}^{=m^{\prime}_{\alpha}}(\overline{v})\wedge\bigwedge_{\beta\in
J}\xi_{\beta}^{\geqslant n_{\beta}^{\prime}}(\overline{v})$

such that, at any prime $p$, the family of formulas
$\left\\{\theta_{\alpha}^{p}(\overline{v}),\xi_{\beta}^{p}(\overline{v}):\alpha\in
I,\beta\in J\right\\}$ is pairwise inconsistent.

###### Proof.

First note that $\eta(\overline{v})$ is equivalent to the disjunction

$\bigvee_{m^{\prime}_{1}\leqslant m_{1}}\dots\bigvee_{m^{\prime}_{k}\leqslant
m_{k}}\left[\bigwedge_{i\in[k]}\phi_{i}^{=m^{\prime}_{i}}(\overline{v})\wedge\bigwedge_{j\in[l]}\psi_{j}^{\geqslant
n_{j}}(\overline{v})\right],$

and thus we may assume that $\eta(\overline{v})$ is of form
$\bigwedge_{i\in[k]}\phi_{i}^{=m_{i}}(\overline{v})\wedge\bigwedge_{j\in[l]}\psi_{j}^{\geqslant
n_{j}}(\overline{v})$. Now, for any elements $\overline{\varepsilon}\in
2^{k}_{0}$ and $\overline{\varsigma}\in 2^{l}$, define two kinds of formula:

  1. 1.

Let
$\theta_{\overline{\varepsilon}\overline{\varsigma}}(\overline{v})\equiv\bigwedge_{i\in[k]}\neg_{\varepsilon_{i}}\phi_{i}(\overline{v})\wedge\bigwedge_{j\in[l]}\neg_{\varsigma_{j}}\psi_{j}(\overline{v})$.

  2. 2.

Let
$\xi_{\overline{\varsigma}}(\overline{v})\equiv\bigwedge_{i\in[k]}\neg\phi_{i}(\overline{v})\wedge\bigwedge_{j\in[l]}\neg_{\varsigma_{j}}\psi_{j}(\overline{v})$.

Certainly the family
$\left\\{\theta_{\overline{\varepsilon\varsigma}}^{p}(\overline{v}):\overline{\varepsilon}\in
2^{k}_{0},\overline{\varsigma}\in
2^{l}\right\\}\cup\left\\{\xi_{\overline{\varsigma}}^{p}(\overline{v}):\overline{\varsigma}\in
2^{l}_{0}\right\\}$ is pairwise inconsistent for any prime $p\in\mathbb{P}$.
With this in mind, let $F$ be the set of functions $f:2^{k+l}_{0}\to\omega$
with the following two properties:

  1. 1.

For each $i\in[k]$, we have $m_{i}=\sum_{\overline{\varepsilon\varsigma}\in
2^{k+l}_{0}}\varepsilon_{i}f(\overline{\varepsilon\varsigma})$.

  2. 2.

For each $j\in[l]$, we have $n_{j}=\sum_{\overline{\varepsilon\varsigma}\in
2^{k+l}_{0}}\varsigma_{j}f(\overline{\varepsilon\varsigma})$.

Note that $F$ is finite, since the image of each $f\in F$ is bounded on each
element of $2^{k+l}_{0}$. Indeed, if $\overline{\varepsilon\varsigma}\in
2_{0}^{k+l}$, there is either some $i\in[k]$ such that $\varepsilon_{i}=1$ or
some $j\in[l]$ such that $\varsigma_{j}=1$. In the first case we have
$f(\overline{\varepsilon\varsigma})\leqslant m_{i}$, and in the second case we
have $f(\overline{\varepsilon\varsigma})\leqslant n_{j}$. In particular, the
formula

$\bigvee_{f\in F}\left[\bigwedge_{\overline{\varepsilon}\in
2^{k}_{0},{\overline{\varsigma}}\in
2^{l}}\theta_{\overline{\varepsilon\varsigma}}^{=f(\overline{\varepsilon\varsigma})}(\overline{v})\wedge\bigwedge_{\overline{\varsigma}\in
2^{l}_{0}}\xi_{\overline{\varsigma}}^{\geqslant
f(\overline{0\varsigma})}(\overline{v})\right]$

is well-defined and equivalent to $\eta(\overline{v})$. ∎

######  Corollary A.3.

For any formulas $\phi_{i}(\overline{v},w)$ and $\psi_{j}(\overline{v},w)$ and
any $m_{i},n_{j}\in\omega$, the formula

$\eta(\overline{v})\equiv\exists w\left[\bigwedge_{i\in[k]}\phi_{i}^{\leqslant
m_{i}}(\overline{v},w)\wedge\bigwedge_{j\in[l]}\psi_{j}^{\geqslant
n_{j}}(\overline{v},w)\right]$

is equivalent to a Boolean combination of formulas of the form
$\theta^{\geqslant m}(\overline{v})$.

###### Proof.

By Lemma A.2, and since existential quantification distributes over
disjunction, we may assume that $\eta(\overline{v})\equiv\exists
w\left[\bigwedge_{i\in[k]}\phi_{i}^{=m_{i}}(\overline{v},w)\wedge\bigwedge_{j\in[l]}\psi_{j}^{\geqslant
n_{j}}(\overline{v},w)\right]$ and that, for any $p\in\mathbb{P}$, the family
$\left\\{\phi_{i}^{p}(\overline{v},w),\psi_{j}^{p}(\overline{v},w):i\in[k],j\in[l]\right\\}$
is pairwise inconsistent. (For convenience, call this latter fact $\ast$.)
Consider the following sets of primes:

  1. 1.

$S_{i}(\overline{v}):=\big{\\{}p\in\mathbb{P}:\exists
w\phi_{i}^{p}(\overline{v},w)\big{\\}}$, for each $i\in[k]$.

  2. 2.

$T_{j}(\overline{v}):=\big{\\{}p\in\mathbb{P}:\exists
w\psi_{j}^{p}(\overline{v},w)\big{\\}}$, for each $j\in[l]$.

  3. 3.

$U(\overline{v}):=\left\\{p\in\mathbb{P}:\forall
w\bigvee_{i=1}^{k}\phi_{i}^{p}(\overline{v},w)\right\\}$.

  4. 4.

$V_{i}:=\left\\{p\in\mathbb{P}:\phi_{i}^{p}(\overline{1},1)\right\\}$, for
each $i\in[k]$.

We claim that, for any tuple $\overline{a}\in\mathbb{M}^{|\overline{a}|}$, the
sentence $\eta(\overline{a})$ is equivalent to the following conditions on
these sets:

  1. 1.

For each $i\in[k]$ and $j\in[l]$, there are subsets $P_{i}\subseteq
S_{i}(\overline{a})$ and $Q_{j}\subseteq T_{j}(\overline{a})$ satisfying

    1. (a)

$|P_{i}|=m_{i}$ and $|Q_{j}|=n_{j}$ for each $i\in[k]$, $j\in[l]$.

    2. (b)

$P_{i_{1}}\cap P_{i_{2}}=P_{i_{1}}\cap Q_{j_{1}}=Q_{j_{1}}\cap
Q_{j_{2}}=\varnothing$ for any $i_{1}\neq i_{2}\in[k]$, $j_{1}\neq
j_{2}\in[l]$.

    3. (c)

$U(\overline{a})\subseteq\bigcup_{i\in[k]}P_{i}$.

  2. 2.

$|V_{i}|=0$ for each $i\in[k]$.

By Remark A.1 and Fact B.2, condition ($1$) is equivalent to a Boolean
combination of formulas of the desired form. Clearly condition ($2$) is also
of the desired form, and so this will prove the result.

So, we need only show the equivalence of these conditions. Note that we may
assume $\overline{a}\in\mathbb{N}^{|\overline{a}|}$ and that all the sets
above quantify over $\mathbb{P}\cap\mathbb{N}$ rather than $\mathbb{P}$. First
we show the forward direction. Suppose $\mathbb{N}\models\eta(\overline{a})$
and that $c\in\mathbb{N}$ is a witness. We will show condition ($1$) first.
For each $i\in[k]$, let
$P_{i}=\\{p\in\mathbb{P}\cap\mathbb{N}:\phi_{i}^{p}(\overline{a},c)\\}$. Note
that $P_{i}\subseteq S_{i}(\overline{a})$, with $c$ as a witness of the
defining formula for $S_{i}(\overline{v})$, and that $|P_{i}|=m_{i}$ by
definition of $\eta$. Similarly, by definition of $\eta$, for each $j\in[l]$
we may find a subset
$Q_{j}\subseteq\\{q\in\mathbb{P}\cap\mathbb{N}:\psi_{j}^{q}(\overline{a},c)\\}$
with $|Q_{j}|=n_{j}$. Again, $Q_{j}\subseteq T_{j}(\overline{a})$, with $c$ as
a witness. Thus the $P_{i}$ and $Q_{j}$ satisfy condition ($1$a). That they
also satisfy condition ($1$b) is immediate from fact $\ast$. To see ($1$c),
suppose $p\in U(\overline{a})$; then, instantiating $w$ at $c$, we have
$\mathbb{N}\models\bigvee_{i\in[k]}\phi_{i}^{p}(\overline{a},c)$. By
definition of the $P_{i}$, this means $p$ lies in $P_{i}$ for some $i\in[k]$,
as desired. So, all of the properties needed for condition ($1$) are
satisfied. To see that condition ($2$) holds, fix $i\in[k]$, and let
$q\in\mathbb{P}\cap\mathbb{N}$ be any prime outside
$P_{i}\cup\sigma(c)\cup\sigma(\overline{a})$. Since $q\notin P_{i}$, by
definition we have $\mathbb{N}\models\neg\phi_{i}^{q}(\overline{a},c)$. By
Remark 2.1, this means in particular that
$\mathbb{N}\models\neg\phi_{i}^{q}(\overline{a}_{q^{\infty}},c_{q^{\infty}})$.
But $\overline{a}_{q^{\infty}}=\overline{1}$ and $c_{q^{\infty}}=1$ by
construction of $q$, so we have
$\mathbb{N}\models\neg\phi_{i}^{q}(\overline{1},1)$. Now for any
$p\in\mathbb{P}\cap\mathbb{N}$ there is an automorphism of $\mathbb{N}$ taking
$q$ to $p$, and so we also have
$\mathbb{N}\models\neg\phi_{i}^{p}(\overline{1},1)$. In particular,
$|V_{i}|=0$.

Now we show the backward direction. Suppose that conditions ($1$) and ($2$)
hold, witnessed by the sets $P_{i}$ and $Q_{j}$. We will create a witness $c$
for $\eta(\overline{a})$ by stitching together its $p$-parts in the following
steps:

  1. 1.

Fix $i\in[k]$. For any $p\in P_{i}$, since $p\in S_{i}(\overline{a})$, there
exists $e_{p}\in\mathbb{N}$ such that
$\mathbb{N}\models\phi_{i}^{p}(\overline{a},e_{p})$. By Remark 2.1, we may
replace $e_{p}$ with $e_{p,p^{\infty}}$ and thus assume that is it a power of
$p$. Then let $c_{p^{\infty}}=e_{p}$.

  2. 2.

Similarly, for every $j\in[l]$ and $q\in Q_{j}$, there is $f_{q}$ a power of
$q$ such that $\mathbb{N}\models\psi_{j}^{q}(\overline{a},f_{q})$. Let
$c_{q^{\infty}}=f_{q}$.

  3. 3.

Now suppose $p\in\sigma(\overline{a})$. If $p\in U(\overline{a})$, then, by
condition ($1$c), $p\in P_{i}$ for some $i\in[k]$, and so has been handled in
step $1$. If $p\notin U(\overline{a})$, then by the defining formula of
$U(\overline{v})$ there must exist some $g_{p}\in\mathbb{N}$ such that
$\mathbb{N}\models\bigwedge_{i=1}^{k}\neg\phi_{i}^{p}(\overline{a},g_{p})$.
Again by Remark 2.1, we may assume that $g_{p}$ is a power of $p$, and then
let $c_{p^{\infty}}=g_{p}$.

  4. 4.

Now suppose $p\notin\sigma(\overline{a})$ and that
$p\notin\bigcup_{i\in[k]}P_{i}\cup\bigcup_{j\in[l]}Q_{j}$. Then let
$c_{p^{\infty}}=1$. Note that, by condition ($2$), we have
$\mathbb{N}\models\neg\phi_{i}^{p}(\overline{1},1)$ for any $i\in[k]$. In
particular, since $\overline{a}_{p^{\infty}}=\overline{1}$, by Remark 2.1 we
will have $\mathbb{N}\models\neg\phi_{i}^{p}(\overline{a},c)$.

This is well defined for two reasons. First, all but finitely many of the
$p$-parts of $c$ will be $1$: the primes at which the $p$-part of $c$ are not
$1$ lie either in $\sigma(\overline{a})$, which is finite, or in
$\bigcup_{i\in[k]}P_{i}\cup\bigcup_{j\in[l]}Q_{j}$, which is finite by
condition ($1$a). Second, the $P_{i}$ and the $Q_{j}$ are all pairwise
disjoint by condition ($1$b), and so the primes specified at each stage in the
above steps are all distinct. We claim now that

$\mathbb{N}\models\bigwedge_{i\in[k]}\phi_{i}^{=m_{i}}(\overline{a},c)\wedge\bigwedge_{j\in[l]}\psi_{j}^{\geqslant
n_{j}}(\overline{a},c),$

which will complete the proof. We prove this in two parts.

  1. 1.

Let $j\in[l]$. We claim that
$Q_{j}\subseteq\\{q\in\mathbb{P}\cap\mathbb{N}:\psi_{j}^{q}(\overline{a},c)\\}$.
Since $|Q_{j}|=n_{j}$ by condition ($1$a), this will show
$\mathbb{N}\models\psi_{j}^{\geqslant n_{j}}(\overline{a},c)$, as desired. To
see this, suppose $q\in Q_{j}$. Then by step $2$ we have
$\mathbb{N}\models\psi_{j}^{q}(\overline{a},c_{q^{\infty}})$ and hence
$\mathbb{N}\models\psi_{j}^{q}(\overline{a},c)$, as desired.

  2. 2.

Let $i\in[k]$. We claim that
$P_{i}=\\{p\in\mathbb{P}\cap\mathbb{N}:\phi_{i}^{p}(\overline{a},c)\\}$. Since
$|P_{i}|=m_{i}$ by condition ($1$a), this will show
$\mathbb{N}\models\phi_{i}^{=m_{i}}(\overline{a},c)$, as desired. The
inclusion $\subseteq$ follows from an identical argument as in the above item.
So, we show $\supseteq$. Suppose therefore that some
$p\in\mathbb{P}\cap\mathbb{N}$ does not lie in $P_{i}$. We have four cases; if
$p\in P_{i^{\prime}}$ for some $i^{\prime}\neq i\in[k]$, then by the inclusion
$\subseteq$ we have $\mathbb{N}\models\phi_{i^{\prime}}^{p}(\overline{a},c)$.
Since $\phi_{i^{\prime}}^{p}(\overline{v},w)$ and
$\phi_{i}^{p}(\overline{v},w)$ are inconsistent by $\ast$, this means
$\mathbb{N}\models\neg\phi_{i}^{p}(\overline{a},c)$, as desired. The case when
$p\in Q_{j}$ for some $j\in[l]$ follows similarly, since
$\psi_{j}^{p}(\overline{v},w)$ and $\phi_{i}^{p}(\overline{v},w)$ are again
inconsistent by $\ast$. If $p$ does not lie in any of the $P_{i^{\prime}}$ or
$Q_{j}$, but it is a prime factor of some element of $\overline{a}$, then by
step $3$ we have $c_{p^{\infty}}=g_{p}$ and hence
$\mathbb{N}\models\neg\phi_{i}^{p}(\overline{a},c_{p^{\infty}})$, as desired.
Finally, if $p$ does not lie in any of the $P_{i^{\prime}}$ or $Q_{j}$, and
does not divide any element of $\overline{a}$, then by the remark in step $4$
we have $\mathbb{N}\models\neg\phi_{i}^{p}(\overline{a},c)$.

This concludes the proof. ∎

######  Theorem A.4.

Any formula $\phi(\overline{v})$ is equivalent to a Boolean combination of
formulas of the form $\theta^{\geqslant m}(\overline{v})$.

###### Proof.

Proof by induction on the complexity of $\phi(\overline{v})$. First suppose
that $\phi$ is atomic; then it is of the form $v_{1}^{k_{1}}\dots
v_{n}^{k_{n}}=v_{1}^{l_{1}}\dots v_{n}^{l_{n}}$ for some
$k_{i},l_{i}\in\omega$. Since two elements of $\mathbb{N}$ are equal if and
only if their $p$-parts are equal for all $p\in\mathbb{P}$, and the $p$-part
operation commutes with products, the formula $\phi(\overline{v})$ is
equivalent to $(\neg\phi)^{\leqslant 0}(\overline{v})$, as desired. Now it
suffices to show that, if $\phi(\overline{v},w)$ is a conjunction of formulas
of the form $\theta^{\geqslant m}(\overline{v},w)$ and $\theta^{\leqslant
m}(\overline{v},w)$, then so is $\exists w\phi(\overline{v},w)$. This follows
from Corollary A.3. ∎

##  Appendix B A combinatorial fact

Thank you to Alex Kruckman for his observation that Fact B.2 follows from the
following theorem, and to Jamshid Derakhshan and Angus Macintyre for their
elegant exposition of its proof in Example 1 of the paper [3].

######  Theorem B.1.

The theory of infinite atomic Boolean algebras has quantifier elimination
after expanding its language to include the predicate ‘$v$ has $n$ atoms lying
beneath it’ for every $n\in\omega$.$\hfill\blacksquare$

######  Fact B.2.

Suppose we have natural numbers $m_{i},n_{j}\in\omega$ and sets $S_{i},T_{j}$,
for each $i\in[k]$ and $j\in[l]$, and another set $U$. Then the existence of
subsets $P_{i}\subseteq S_{i}$ and $Q_{j}\subseteq T_{j}$ such that

  1. 1.

$|P_{i}|=m_{i}$ and $|Q_{j}|=n_{j}$ for each $i\in[k]$, $j\in[l]$.

  2. 2.

$P_{i_{1}}\cap P_{i_{2}}=P_{i_{1}}\cap Q_{j_{1}}=Q_{j_{1}}\cap
Q_{j_{2}}=\varnothing$ for any $i_{1}\neq i_{2}\in[k]$, $j_{1}\neq
j_{2}\in[l]$.

  3. 3.

$U\subseteq\bigcup_{i=1}^{k}P_{i}$.

is expressible as a Boolean combination of formulas of the form $|X|\geqslant
m$, where $m\in\omega$ and $X$ is a Boolean combination of the $S_{i}$, the
$T_{j}$, and $U$.$\hfill\blacksquare$

##  Appendix C Definable closures of stably embedded sets

Let $T$ be any complete first-order theory, and let $\mathbb{M}\models T$ be a
monster model in the sense of Section 0. Given a tuple $\overline{w}$ and a
formula $\psi(v)$ in a single variable, use $\psi(\overline{w})$ to abbreviate
the formula $\bigwedge_{i\in[|\overline{w}|]}\psi(w_{i})$.

######  Lemma C.1.

Suppose $D\subseteq\mathbb{M}^{m}$ and $E\subseteq\mathbb{M}^{n}$ are
$\varnothing$-definable, and that $D\subseteq\operatorname{dcl}E$. Then there
is a $\varnothing$-definable surjection from a $\varnothing$-definable set of
tuples of $E$ onto $D$.

###### Proof.

For notational convenience, we assume $m=n=1$; the more general case is
identical. Let $\phi(v)$ and $\psi(v)$ be such that $D=\phi(\mathbb{M})$ and
$E=\psi(\mathbb{M})$. By hypothesis, the following partial type in $v$ is
inconsistent:

$\\{\phi(v)\\}\cup\left\\{\forall\overline{w}\left[\psi(\overline{w})\wedge\theta(v;\overline{w})\to\exists^{>1}u\theta(u;\overline{w})\right]\right\\}_{\theta}.$

Thus, by compactness, there exist formulas
$\theta_{1}(v;\overline{w}_{1}),\dots,\theta_{k}(v;\overline{w}_{k})$ such
that, for every element $d\in D$, there exist some $i\in[k]$ and a tuple
$\overline{e}\in E^{|\overline{w}_{i}|}$ with
$\theta_{i}(D;\overline{e})=\\{d\\}$. Without loss of generality, assume that
the $\overline{w}_{i}$ are all tuples of the same length. For each $i\in[k]$,
define a formula

$\delta_{i}(\overline{w})\equiv\psi(\overline{w})\wedge\exists^{=1}v\theta_{i}(v;\overline{w})\wedge\forall
v\left[\theta_{i}(v;\overline{w})\to\phi(v)\right].$

Now, defining the formula $\delta(\overline{w})\equiv\bigvee_{i\leqslant
k}\delta_{i}(\overline{w})$, we get a $\varnothing$-definable surjection
$g(\overline{w})$ from $\delta(E^{|\overline{w}|})$ onto $D$ by taking
$g(\overline{w})$ to act as $\theta_{i}$ on each
$\delta_{i}(E^{|\overline{w}|})\setminus\bigcup_{j<i}\delta_{j}(E^{|\overline{w}|})$.
∎

We need the following lemma in Section 3:

######  Lemma C.2.

Suppose $D\subseteq\mathbb{M}^{m}$ and $E\subseteq\mathbb{M}^{n}$ are
$\varnothing$-definable, with $\operatorname{dcl}D=\operatorname{dcl}E$. Then
$D$ is stably embedded if and only if $E$ is stably embedded.

###### Proof.

Again suppose $m=n=1$ for convenience, and assume that $E$ is stably embedded.
By Lemma C.1, there is a formula $\delta(\overline{w})$ and a
$\varnothing$-definable surjection $g(\overline{w})$ from
$\delta(E^{|\overline{w}|})$ onto $D$. Let $\xi(\overline{v};\overline{c})$ be
any formula. Since $E$ is stably embedded, the set

$X:=\left\\{\overline{e}_{1}\dots\overline{e}_{k}\in\delta(E^{|\overline{w}|})^{k}:\mathbb{M}\models\xi(g(\overline{e}_{1}),\dots,g(\overline{e}_{k});\overline{c})\right\\}$

is $E$-definable. Since $g$ is surjective, the image of $X$ under $g$ is
precisely $\xi(D^{k};\overline{c})$, and so, since $g$ is
$\varnothing$-definable, $\xi(D^{k};\overline{c})$ is also $E$-definable.
Since $E\subseteq\operatorname{dcl}D$, we are done. ∎

## References

  * [1] John T. Baldwin. How Big Should the Monster Model Be? Logic Without Borders, page 31–50, 2015.
  * [2] Oleg Belegradek, Yaacov Peterzil, and Frank Wagner. Quasi-O-Minimal Structures. Journal of Symbolic Logic, 65(3):1115–1132, 2000.
  * [3] Jamshid Derakhshan and Angus Macintyre. Enrichments of Boolean algebras by Presburger predicates. Fundamenta Mathematicae, 239(1):1–17, 2017.
  * [4] Emil Jeřábek. What are the definable sets in Skolem arithmetic? MathOverflow, Nov 2018.
  * [5] Katrin Tent and Martin Ziegler. A Course in Model Theory. Association for Symbolic Logic, 2012.