# Decidability for the theory of modules over a Prüfer domain

Lorna Gregory  Dipartimento di Matematica e Fisica, Università degli Studi
della Campania “Luigi Vanvitelli”, Viale Lincoln 5, 81100 Caserta, Italy
<EMAIL_ADDRESS>
###### Abstract.

In this paper we give elementary conditions completely characterising when the
theory of modules of a Prüfer domain is decidable. Using these results, we
show that the theory of modules of the ring of integer valued polynomials is
decidable.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 Recursive sets
  4. 4 Formalisms
  5. 5 First syntactic reductions
  6. 6 Uniserial modules with finite invariants sentences
  7. 7 Finite modules
  8. 8 Removing $|\nicefrac{{d|x}}{{x=0}}|=D$ and $|\nicefrac{{xb=0}}{{c|x}}|=G$.
  9. 9 Further syntactic reductions
  10. 10 Algorithms for sentences which are not reducible
  11. 11 The main theorem
  12. 12 Integer-valued polynomials

##  1\. Introduction

In this article, we give a complete characterization of when the theory of
modules of a recursive Prüfer domain is decidable.

Prüfer domains are a much studied class of rings, including many classically
important rings and classes of rings. For example, they include Dedekind
domains and hence rings of integers of number fields; Bézout domains and hence
the ring of complex entire functions [Hel40, Thm. 9] and the ring of algebraic
integers [Kap74, Thm. 102]; the ring of integer valued polynomials with
rational coefficients [CC97, VI.1.7] and the real holomorphy ring of a
formally real field [Bec82, 2.16].

Prüfer domains have provided a rich supply of rings for which the decidability
of modules can be determined. The theory of modules of a ring $R$ is said to
be decidable if there is an algorithm which decides whether a given first
order sentence in the language of $R$-modules is true in all $R$-modules.

The first non-trivial example of a ring with decidable theory of modules was
given by Szmielew, [Szm55], who showed that the theory of abelian groups (or
equivalently $\mathbb{Z}$-modules) is decidable. This result was generalised
by Eklof and Fischer, [EF72], to certain Dedekind domains, among them certain
rings of integers, and they showed that, for a (recursive) field $k$ with a
splitting algorithm, the theory of $k[x]$-modules is decidable.

The most recent effort to understand decidability of theories of modules over
Prüfer domains started with a paper, [PPT07], of Puninski, Puninskaya and
Toffalori. They showed that a recursive valuation domain with dense
archimedean value group has decidable theory of modules if and only if its set
of units is recursive. Proving a conjecture in [PPT07], we show in [Gre15]
that an arbitrary recursive valuation domain has decidable theory of modules
if and only if the radical relation $a\in\textnormal{rad}bR$ is recursive.

The theory of modules of Bézout domains of the form $D+XQ[X]\subseteq Q[X]$,
where $D$ is a principal ideal domain with field of fractions $Q$, is shown in
[PT14] to be decidable under certain reasonable effective conditions on $D$.
In particular, it is shown that $\mathbb{Z}+X\mathbb{Q}[X]$ has decidable
theory of modules. The theory of modules of the ring of algebraic integers,
along with some other Bézout domains with Krull dimension $1$, is shown to
have decidable theory of modules in [LTP17].

Work towards characterising when a general Prüfer domain has decidable theory
of modules was started in the articles [GLPT18] and [GLT19], and is finished
in the present one. We will describe the results of these articles whilst
describing the main result of this article.

First a reminder of the setup for proving decidability results for theories of
modules. Thanks to the Baur-Monk theorem, if $R$ is a recursive ring then the
theory of $R$-modules is decidable if and only if there exists an algorithm
which, given
$\nicefrac{{\varphi_{1}}}{{\psi_{1}}},\ldots,\nicefrac{{\varphi_{l}}}{{\psi_{l}}}$
pairs of pp-formulae and intervals
$[n_{1},m_{1}],\ldots,[n_{l},m_{l}]\subseteq\mathbb{N}$ where
$n_{i},m_{i}\in\mathbb{N}\cup\\{\infty\\}$, answers whether there exists an
$R$-module $M$ such that, for all $1\leq i\leq l$,
$\left|\varphi(M)/\psi(M)\right|\in[n_{i},m_{i}]$. The existence of an
algorithm answering this question when $[n_{i},m_{i}]$ are either $[1,1]$ or
$[1,\infty]$ is equivalent to the existence of an algorithm deciding whether
one Ziegler basic open set is contained in a finite union of other Ziegler
basic open sets (for the definition of the Ziegler spectrum see 2.1).

We characterise when the theory of modules of a Prüfer domain $R$ is decidable
in terms of the recursivity of three sets: $\mathrm{DPR}(R)$,
$\mathrm{EPP}(R)$ and $X(R)$. Each of these sets is a subset of
$R^{n}\times\mathbb{N}_{0}^{k}$ for some $n,k\in\mathbb{N}_{0}$. For the sets
$\mathrm{EPP}(R)$ and $X(R)$, we postpone their definitions to section 3 and
in this introduction we instead give some indication of their meaning.

For any commutative ring $R$, the set $\mathrm{DPR}(R)$ is defined as the set
of $(a,b,c,d)\in R^{4}$ such that for all prime ideals
$\mathfrak{p},\mathfrak{q}\lhd R$ with $\mathfrak{p}+\mathfrak{q}\neq R$,
either $a\in\mathfrak{p}$, $b\notin\mathfrak{p}$, $c\in\mathfrak{q}$ or
$d\notin\mathfrak{q}$. This set was introduced in [GLPT18] as a generalisation
of the radical relation $a\in\textnormal{rad}bR$. For a recursive Bézout
domain it is shown there that $\mathrm{DPR}(R)$ is recursive if and only if
there is an algorithm deciding inclusions of Ziegler basic open sets. For
recursive Prüfer domains, analogous sufficient conditions were given for there
to exist an algorithm deciding inclusions of Ziegler basic open sets. Building
heavily on those results, we extend the equivalence given in [GLPT18] for
Bézout domains to all recursive Prüfer domains (see 3.8). As a consequence we
get the following theorem.

Theorem. (See 3.9) Let $R$ be a recursive Prüfer domain such that
$R/\mathfrak{m}$ is infinite for all maximal ideals $\mathfrak{m}$. The theory
of $R$-modules is decidable if and only if $\mathrm{DPR}(R)$ is recursive.

For rings $R$ with a pair of pp-formulae $\nicefrac{{\varphi}}{{\psi}}$ and an
$R$-module $M$ such that $\left|\varphi(M)/\psi(M)\right|$ is finite but not
equal to $1$, in particular for commutative rings with finite non-zero
modules, we need to do more than show that there is an algorithm deciding
inclusions of Ziegler basic open sets.

For any ring $R$, if the theory of $R$-modules is decidable then the theory of
modules of size $n$ is decidable uniformly in $n$. In 3.19, we introduce a set
$\mathrm{EPP}(R)$, whose recursivity, for a recursive Prüfer domain $R$, is
equivalent to the decidability of the theory of $R$-modules of size $n$,
uniformly in $n$. This is proved in Theorem 7.6. The main feature of
$\mathrm{EPP}(R)$ is that it is often easier to check in examples that
$\mathrm{EPP}(R)$ is recursive than it is to check that the theory of modules
of size $n$ is decidable uniformly in $n$.

The set $\mathrm{EPP}(R)$ is a generalisation of $\mathrm{PP}(R)$, which is
defined in [GLT19] and inspired by the characterisation of commutative von
Neumann regular rings with decidable theories of modules given in [PP88]. In
[GLT19], for a recursive Bézout domain $R$, under the condition that for each
maximal ideal $\mathfrak{m}$, $R_{\mathfrak{m}}$ has dense value group, it is
shown that the theory of $R$-modules is decidable if and only if
$\mathrm{DPR}(R)$ and $\mathrm{PP}(R)$ are recursive. Building heavily on
[GLT19], we show, that this result also holds for Prüfer domains.

Theorem 3.12. Let $R$ be a recursive Prüfer domain such that
$R_{\mathfrak{m}}$ has dense value group for all maximal ideals
$\mathfrak{m}$. The theory of $R$-modules is decidable if and only if
$\mathrm{PP}(R)$ and $\mathrm{DPR}(R)$ is recursive.

It follows from this result that the theory of modules of a recursive Prüfer
domain with dense value groups (or infinite residue fields) is decidable if
and only if there is an algorithm deciding inclusions of Ziegler basic open
sets and the theory of finite modules of size $n$ is decidable uniformly in
$n$. The same result for commutative von Neumann regular rings easily follows
from [PP88]. This does not appear to be the case for arbitrary Prüfer domains.

The third set, $X(R)$, captures information about finite Baur-Monk invariants
of the, in some sense intrinsically infinite modules, $R_{\mathfrak{p}}/I$
where $\mathfrak{p}\lhd R$ is a prime ideal and $I\lhd R_{\mathfrak{p}}$.

Main Theorem 11.1. Let $R$ be a recursive Prüfer domain. The theory of
$R$-modules is decidable if and only if the sets $\mathrm{DPR}(R)$,
$\mathrm{EPP}(R)$ and $X(R)$ are recursive.

Our characterisation is such that it can be easily checked for concrete rings.
We illustrate this in section 12 by using our main theorem to show that the
ring of integer valued polynomials with rational coefficients,
$\text{Int}(\mathbb{Z})$, has decidable theory of modules. In order to prove
that $\mathrm{DPR}(\text{Int}(\mathbb{Z}))$,
$\mathrm{EPP}(\text{Int}(\mathbb{Z}))$ and $X(\text{Int}(\mathbb{Z}))$ are
recursive, we use Ax’s result, [Ax68, Thm 17], that the common theory of the
$p$-adic valued fields $\mathbb{Q}_{p}$ as $p$ varies, is decidable.

Section $1$ contains background material and simple preparations for the rest
of the paper. Its main purpose is to make the article as accessible as
possible. We postpone a guide to the proof and discussion of what happens in
each section to subsection 2.4.

When it doesn’t complicate the proofs, we will state some of our intermediate
results for arithmetical rings i.e. commutative rings whose localisations at
prime ideals are valuation rings.

##  2\. Preliminaries

Notation: In this article $\mathbb{N}=\\{1,2,3,\ldots\\}$,
$\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$, $\mathbb{N}_{n}=\\{m\geq n\\}$ for
$n\in\mathbb{N}$ and $\mathbb{P}$ denotes the set of prime natural numbers.
For a ring $R$, let $\textnormal{Mod}\text{-}R$ denote the category of (right)
modules.

###  2.1. Model theory of Modules

For general background on model theory of modules see [Pre88].

Let $R$ be a ring. Let $\mathcal{L}_{R}:=\\{0,+,(\cdot r)_{r\in R}\\}$ be the
language of (right) $R$-modules and $T_{R}$ be the theory of (right)
$R$-modules. A (right) pp-$n$-formula is a formula of the form

$\exists
y_{1},\ldots,y_{l}\bigwedge_{j=1}^{m}\sum_{i=1}^{l}y_{i}r_{ij}+\sum_{i=1}^{n}x_{i}s_{ij}=0$

where $r_{ij},s_{ij}\in R$. For $a\in R$, we write $a|x$ for the
pp-$1$-formula $\exists y\,x=ya$.

The solution set $\varphi(M)$ of a pp-$n$-formula $\varphi$ in an $R$-module
$M$ is a subgroup of $M^{n}$. For $\varphi,\psi$, pp-$n$-formulae and
$M\in\textnormal{Mod}\text{-}R$, we will write $\psi\leq_{M}\varphi$ to mean
that $\psi(M)\subseteq\varphi(M)$. We will write $\psi\leq\varphi$ to mean
that $\psi\leq_{M}\varphi$ for all $M\in\textnormal{Mod}\text{-}R$. After
identifying equivalent pp-$n$-formulae, the set of pp-$n$-formulae,
$\textnormal{pp}_{R}^{n}$, equipped with the order $\leq$ is a lattice.

A pp-$m$-pair will simply mean a pair of pp-$m$-formulae and we will write
$\nicefrac{{\varphi}}{{\psi}}$ for such pairs. We write
$\nicefrac{{\varphi}}{{\psi}}(M)$ for the quotient group
$\varphi(M)/\varphi(M)\cap\psi(M)$. For every $n\in\mathbb{N}$ and pp-pair
$\nicefrac{{\varphi}}{{\psi}}$, there is a sentence, denoted
$\left|\nicefrac{{\varphi}}{{\psi}}\right|\geq n$, in the language of (right)
$R$-modules, which expresses, in every $R$-module $M$, that
$\nicefrac{{\varphi}}{{\psi}}(M)$ has at least $n$ elements. We write
$\left|\nicefrac{{\varphi}}{{\psi}}\right|=n$ for the sentence which
expresses, in every $R$-module $M$, that $\nicefrac{{\varphi}}{{\psi}}(M)$ has
exactly $n$ elements.

######  Theorem 2.1 (Baur-Monk).

Let $R$ be a ring. Every sentence in $\mathcal{L}_{R}$ is equivalent to a
boolean combination of sentences of the form
$\left|\nicefrac{{\varphi}}{{\psi}}\right|\geq n$ where
$\nicefrac{{\varphi}}{{\psi}}$ is a pp-$1$-pair.

An embedding $f:A\rightarrow B$ is pure if for all pp-$1$-formulae $\varphi$
and $m\in A$, $f(m)\in\varphi(B)$ implies $m\in\varphi(A)$. A module $N$ is
pure-injective if for every embedding $f:A\rightarrow B$ and homomorphism
$g:A\rightarrow N$, there exists $h:B\rightarrow N$ such that $h\circ f=g$.

######  Lemma 2.2.

[Pre88, 4.36] Let $R$ be a ring. For all $M\in\textnormal{Mod}\text{-}R$,
there exist indecomposable pure-injective modules
$N_{i}\in\textnormal{Mod}\text{-}R$ for $i\in I$ such that $\oplus_{i\in
I}N_{i}$ is elementary equivalent to $M$.

We say a pure-embedding $i:M\rightarrow N$ with $N$ pure-injective is a pure-
injective hull of $M$ if for every other pure-embedding $g:M\rightarrow K$
where $K$ is pure-injective, there is a pure-embedding $h:N\rightarrow K$ such
that $h\circ i=g$. The pure-injective hull of $M$ is unique up to isomorphism
over $M$ and we will write $H(M)$ for any module $N$ such that the inclusion
of $M$ in $N$ is a pure-injective hull of $M$. Every module is a elementary
substructure of its pure-injective hull [Pre88, 2.27]. So, in particular every
module is elementary equivalent to its pure-injective hull.

The (right) Ziegler spectrum, denoted $\textnormal{Zg}_{R}$, is a topological
space whose points are isomorphism classes of indecomposable pure injective
(right) modules and which has a basis of compact open sets given by

$\left(\nicefrac{{\varphi}}{{\psi}}\right):=\\{N\in\textnormal{pinj}_{R}\ |\
\varphi(N)\supsetneq\varphi(N)\cap\psi(N)\\}$

where $\nicefrac{{\varphi}}{{\psi}}$ range over pp-$1$-pairs.

For each $n\in\mathbb{N}$, Prest gave a lattice anti-isomorphism
$D:\textnormal{pp}_{R}^{n}\rightarrow{}_{R}\textnormal{pp}^{n}$ (see [Pre88,
8.21]). As is standard, we denote its inverse
${}_{R}\textnormal{pp}^{n}\rightarrow\textnormal{pp}_{R}^{n}$ also by $D$. We
don’t recall the full definition of $D$ here but instead note that for all
$a\in R$, $Da|x$ is $ax=0$ and $D(xa=0)$ is $a|x$.

Herzog extended this duality to an isomorphism between the lattice of open
sets of the right and left Ziegler spectra of a ring [Her93, 4.4], and, to a
useful bijection between the complete theories of right and left $R$-modules.

The following proposition is direct consequence of [Her93, 6.6].

######  Proposition 2.3.

Let $R$ be a ring. Let $n,m\in\mathbb{N}$ be such that $n\leq m$ and for
$1\leq i\leq m$, let $N_{i}\in\mathbb{N}$ and let
$\nicefrac{{\varphi_{i}}}{{\psi_{i}}}$ be a pp-pair. For

${\raisebox{1.5pt}{$\chi$}}:=\bigwedge_{i=1}^{n}\left|\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right|=N_{i}\wedge\bigwedge_{i=n+1}^{m}\left|\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right|\geq
N_{i},$

define

$D{\raisebox{1.5pt}{$\chi$}}:=\bigwedge_{i=1}^{n}\left|\nicefrac{{D\psi_{i}}}{{D\varphi_{i}}}\right|=N_{i}\wedge\bigwedge_{i=n+1}^{m}\left|\nicefrac{{D\psi_{i}}}{{D\varphi_{i}}}\right|\geq
N_{i}.$

There exists a right $R$-module satisfying $\chi$ if and only if there exits a
left $R$-module satisfying $D{\raisebox{1.5pt}{$\chi$}}$.

A priori, duality may not appear particularly relevant to an article about
commutative rings. However, its use significantly simplifies some of the
proofs in this paper and, as in [Gre15], the fact that it exchanges formulae
$xb=0$ with $b|x$ allows us to reduce the number of calculations.

###  2.2. Decidability and recursive Prüfer domains

A recursive ring is either a finite ring or a ring $R$ together with a
bijection $\pi:\mathbb{N}\rightarrow R$ such that addition and multiplication
in $R$ induce recursive functions on $\mathbb{N}$ via $\pi$.

Note that if $R$ is a ring and $\pi:\mathbb{N}\rightarrow R$ is a bijection
then $T_{R}$ is recursively axiomatisable with respect to $\pi$ if and only if
$R$ together with $\pi$ is a recursive ring.

When proving decidability results about theories of modules, it is common to
work with an “effectively given” ring rather than just a recursive one.
Usually, a ring of a particular type is called effectively given if $R$ is a
recursive ring and the bijection $\pi$ satisfies some extra conditions which
are equivalent, for that particular type of ring, to Prest’s condition $(D)$
holding (see [Pre88, pg 334]). Recall that a recursive ring satisfies
condition $(D)$ if there is an algorithm which, given
$\varphi,\psi\in\textnormal{pp}_{R}^{1}$ answers whether $\psi\leq\varphi$.
For example, a recursive valuation domain $V$ is said to be effectively given
if the preimage under $\pi$ of the set of units of $V$ is recursive. A
recursive Prüfer domain $R$ is said to be effectively given if the preimage
under $\pi$ of the set of $(a,b)\in R^{2}$ such that $a\in bR$ is recursive.

Whether one works with recursive rings or effectively given ones is largely a
matter of personal taste. For simplicity, we choose to work with recursive
rings.

It was remarked in [GLT19, paragraph before 2.4], that the property that $a\in
bR$ is recursive is never used in [GLPT18] and [GLT19]. Moreover, see [GLT19,
2.4], if $R$ is a recursive Prüfer domain and the set
$\mathrm{DPR}(R)\subseteq R^{4}$ is recursive then $a\in bR$ is recursive. In
particular, even though they are stated for effectively given Prüfer domains,
all results in [GLPT18] and [GLT19] in fact hold for recursive Prüfer domains.

The next theorem is a well-known and easy to prove consequence of the Baur-
Monk Theorem. Note that since $T_{R}$ is recursively axiomatisable when $R$ is
recursive, given a sentence $\chi$ in $\mathcal{L}_{R}$, we can always find,
using a proof algorithm, a sentence ${\raisebox{1.5pt}{$\chi$}}^{\prime}$ as
in the statement of the Baur-Monk theorem which is $T_{R}$-equivalent to
$\chi$.

######  Theorem 2.4.

Let $R$ be a recursive ring. The theory of $R$-modules is decidable if and
only if there is an algorithm which, given a sentence $\chi$ of the form

${\raisebox{1.5pt}{$\chi$}}:=\bigwedge_{i=1}^{n}\left|\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right|=N_{i}\wedge\bigwedge_{i=n+1}^{m}\left|\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right|\geq
N_{i},$

where $N_{i}\in\mathbb{N}$ and $\nicefrac{{\varphi_{i}}}{{\psi_{i}}}$ is a
pp-$1$-pair for $1\leq i\leq m$, answers whether there exists an $R$-module
satisfying $\chi$.

######  Remark 2.5.

Let $R$ be a recursive ring. There is an algorithm deciding inclusions of
Ziegler basic open sets if and only if there is an algorithm which, given a
sentence

${\raisebox{1.5pt}{$\chi$}}:=\bigwedge_{i=1}^{n}\left|\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right|\geq
E_{i}\wedge\bigwedge_{j=1}^{m}\left|\nicefrac{{\sigma_{j}}}{{\tau_{j}}}\right|=1,$

where
$\nicefrac{{\varphi_{i}}}{{\psi_{i}}},\nicefrac{{\sigma_{j}}}{{\tau_{j}}}$ are
pp-$1$-pairs and $E_{i}\in\mathbb{N}$ for $1\leq i\leq n$ and $1\leq j\leq m$,
answers whether there exists an $R$-module satisfying $\chi$.

###### Proof.

There is a module satisfying $\chi$ as in the statement if and only if for
each $1\leq i\leq n$, there exists an indecomposable pure-injective module
$N_{i}$ such that
$N_{i}\in\left(\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right)\backslash\bigcup_{j=1}^{m}\left(\nicefrac{{\sigma_{j}}}{{\tau_{j}}}\right)$.
This is a standard argument. For the forward direction use 2.2. For the
reverse, observe $\oplus_{i=1}^{n}N_{i}^{E_{i}}$ satisfies $\chi$. ∎

###  2.3. Arithmetical rings and Prüfer domains

A commutative ring is arithmetical[1][1][1]This condition is often referred to
as Prüfer in papers on Model Theory of Modules. However, algebraists tend to
use the term Prüfer for the stronger condition that every regular ideal is
invertible. To avoid confusion we choose the term with a unique definition. if
all its localisations at maximal ideals are valuation rings. Equivalently,
[Jen66, Thm 1], a commutative ring $R$ is arithmetical if its lattice of
ideals is distributive. A Prüfer domain is an integral domain which is
arithmetical.

The following is a consequence of [Tug03, 1.3].

######  Lemma 2.6.

If $R$ is an arithmetical ring then for all $a,b\in R$, there exist
$\alpha,r,s\in R$ such that $a\alpha=br$ and $b(\alpha-1)=as$.

Note that if $R$ is a recursive arithmetical ring then there is an algorithm
which, given $a,b\in R$, finds $\alpha,r,s$ satisfying the above equations. We
will frequently use this fact without note.

An $R$-module is pp-uniserial if its lattice of pp-definable subgroups is
totally ordered. Over a commutative ring all pp-definable subgroups are
submodules. Thus, all uniserial modules over a commutative ring are pp-
uniserial.

The lattice of pp-$1$-formulae of a commutative ring is distributive if and
only if it is arithmetical [EH95, 3.1]. Thus, the following is a direct
consequence of [Pun03, 3.3].

######  Lemma 2.7.

Let $R$ be a commutative ring. All indecomposable pure-injective $R$-modules
are pp-uniserial if and only if $R$ is arithmetical.

The endomorphism rings of indecomposable pure-injective modules are local
[Pre09, 4.3.43]. Therefore, if $R$ is a commutative ring and $N$ is an
indecomposable pure-injective module then the set, $\textnormal{Att}N$, of
$r\in R$ acting on $N$ non-bijectively form a prime ideal. Thus, if $N$ is an
indecomposable pure-injective module over a commutative ring $R$ then $N$ may
be equipped with the structure of an $R_{\textnormal{Att}N}$-module. Moreover,
$N$ remains indecomposable and pure-injective as an
$R_{\textnormal{Att}N}$-module. Conversely, if $N$ is an indecomposable pure-
injective $R_{\mathfrak{p}}$-module for some prime ideal $\mathfrak{p}\lhd R$
then the restriction of $N$ to $R$ remains indecomposable and pure-injective.

The following lemma is now an easy consequence of the fact that indecomposable
pure-injective modules over arithmetical rings are pp-uniserial (a proof
appears in [GLT19, 2.8]).

######  Lemma 2.8.

Let $R$ be an arithmetical ring and $N$ an indecomposable pure-injective
$R$-module. The sets

$\textnormal{Div}N:=\\{r\in R\ |\ Nr\subsetneq N\\},$
$\textnormal{Ass}N:=\\{r\in R\ |\ \text{ there exists }m\in
N\backslash\\{0\\}\text{ such that }mr=0\\}$

and

$\textnormal{Att}N:=\textnormal{Div}N\cup\textnormal{Ass}N$

are prime ideals.

######  Lemma 2.9.

Let $R$ be an arithmetical ring and $M\in\textnormal{Mod}\text{-}R$.

  1. (1)

For all $\alpha\in R$, there exist $M_{1},M_{2}\in\textnormal{Mod}\text{-}R$
such that $M_{1}\oplus M_{2}\equiv M$,
$\left|\nicefrac{{x\alpha=0}}{{x=0}}(M_{1})\right|=1$,
$\left|\nicefrac{{x=x}}{{\alpha|x}}(M_{1})\right|=1$,
$\left|\nicefrac{{x(\alpha-1)=0}}{{x=0}}(M_{2})\right|=1$ and
$\left|\nicefrac{{x=x}}{{(\alpha-1)|x}}(M_{2})\right|=1$.

  2. (2)

For all $a,b\in R$, there exist $M_{1},M_{2}\in M$ such that $M_{1}\oplus
M_{2}\equiv M$, $\left|\nicefrac{{ab|x}}{{x=0}}(M_{1})\right|=1$ and
$\left|\nicefrac{{xa=0}}{{b|x}}(M_{2})\right|=1$.

###### Proof.

(1) By 2.2, there exist indecomposable pure-injective $R$-modules $N_{i}$ for
$i\in I$ such that $M\equiv\oplus_{i\in I}N_{i}$. Since
$\textnormal{Att}N_{i}$ is a proper ideal for each $N_{i}$, for all $i\in I$,
either $\alpha\notin\textnormal{Att}N_{i}$ or
$\alpha-1\notin\textnormal{Att}N_{i}$. Let $I_{\alpha}$ be the set of $i\in I$
such that $\alpha\notin\textnormal{Att}N_{i}$ and let
$I_{\alpha-1}=I\backslash I_{\alpha}$. So, for all $i\in I_{\alpha-1}$,
$\alpha-1\notin\textnormal{Att}N_{i}$. For each $\beta\in R$ and $N$
indecomposable pure-injective, $\beta\notin\textnormal{Att}N$ if and only if
$\left|\nicefrac{{x=x}}{{\beta|x}}(N)\right|=1$ and
$\left|\nicefrac{{x\beta=0}}{{x=0}}(M_{1})\right|=1$. Therefore
$\left|\nicefrac{{x=x}}{{\alpha|x}}(\oplus_{i\in I_{\alpha}}N_{i})\right|=1$,
$\left|\nicefrac{{x\alpha=0}}{{x=0}}(\oplus_{i\in I_{\alpha}}N_{i})\right|=1$,
$\left|\nicefrac{{x=x}}{{(\alpha-1)|x}}(\oplus_{i\in
I_{\alpha-1}}N_{i})\right|=1$ and
$\left|\nicefrac{{x(\alpha-1)=0}}{{x=0}}(\oplus_{i\in
I_{\alpha-1}}N_{i})\right|=1$.

(2) For any $L\in\textnormal{Mod}\text{-}R$, $xb=0\geq_{L}a|x$ if and only if
$ab\in\textnormal{ann}_{R}L$. So $\left|\nicefrac{{ab|x}}{{x=0}}(L)\right|=1$
if and only if $xb=0\geq_{L}a|x$. Let $N$ be an indecomposable pure-injective
$R$-module. By 2.7, either $xb=0\geq_{N}a|x$ or $a|x\geq_{N}xb=0$. So either
$\left|\nicefrac{{ab|x}}{{x=0}}(N)\right|=1$ or
$\left|\nicefrac{{xb=0}}{{a|x}}(N)\right|=1$. The proof is now as in $(1)$. ∎

It is easy to see that if $R$ is a commutative ring, $\mathfrak{p}\lhd R$ is a
prime ideal and $M$ is an $R_{\mathfrak{p}}$-module then the restriction to
$R$ of the pure-injective hull of $M$ as an $R_{\mathfrak{p}}$-module is equal
to the pure-injective hull of $M$ as an $R$-module.

Recall that a module is called uniserial if its lattice of submodules form a
chain.

######  Theorem 2.10.

[Zie84] Let $V$ be a valuation domain with field of fractions $Q$. Every
indecomposable pure-injective $V$-module is the pure-injective hull of a
module $J/I$ where $I\subsetneq J\subseteq Q$ are submodules of $Q$.

So, in particular, over a valuation domain, all indecomposable pure-injective
$R$-modules are pure-injective hulls of uniserial modules. It is not known if
all indecomposable pure-injective modules over valuation rings are pure-
injective hulls of uniserial modules (see [EH95, §4]).

######  Lemma 2.11.

Let $R$ be a Prüfer domain. For any sentence
${\raisebox{1.5pt}{$\chi$}}\in\mathcal{L}_{R}$, there exists
$M\in\textnormal{Mod}\text{-}R$ such that $M\models{\raisebox{1.5pt}{$\chi$}}$
if and only if there exist $n\in\mathbb{N}$, prime ideals
$\mathfrak{p}_{i}\lhd R$ and uniserial $R_{\mathfrak{p}_{i}}$-modules $U_{i}$
for $1\leq i\leq n$ such that
$\oplus_{i=1}^{n}U_{i}\models{\raisebox{1.5pt}{$\chi$}}$.

###### Proof.

For any ring $R$, there exists $M\in\textnormal{Mod}\text{-}R$ such that
$M\models{\raisebox{1.5pt}{$\chi$}}$ if and only if there exist
$n\in\mathbb{N}$ and indecomposable pure-injective $R$-modules $N_{i}$ for
$1\leq i\leq n$ such that
$\oplus_{i=1}^{n}N_{i}\models{\raisebox{1.5pt}{$\chi$}}$. The result now
follows from 2.10. ∎

We will frequently use the following easy lemma.

######  Lemma 2.12.

Let $V$ be a valuation domain, $\varphi$ a pp-$1$-formula and $U$ a uniserial
$V$-module. If $\left|U/\varphi(U)\right|$ is finite but not equal to $1$ then
$U\cong V/I$ for some ideal $I\lhd V$.

###### Proof.

Since $U$ is uniserial, so is $U/\varphi(U)$. Therefore, since $U/\varphi(U)$
is finite, there exists $u\in U$ such that $u+\varphi(U)$ generates
$U/\varphi(U)$ as a $V$-module. Since $U/\varphi(U)\neq 0$,
$uR\supseteq\varphi(U)$. Therefore $uR=U$. ∎

We finish this subsection by reviewing material about ideals of valuation
domains.

For any commutative ring $R$, $r\in R$ and ideal $I\lhd R$, define

$(I:r):=\\{a\in R\ |\ ar\in I\\}.$

Note that $(I:r)$ is an ideal of $R$.

######  Definition 2.13.

For $V$ a valuation domain and $I\lhd R$ a proper ideal, define
$I^{\\#}:=\bigcup_{a\notin I}(I:a)$. By convention, we define $V^{\\#}$ to be
the unique maximal ideal of $V$.

Note that this definition agrees with the definition given in [FS01, ChII §4],
that is, for $I\neq 0$, $r\in I^{\\#}$ if and only if $rI\subsetneq I$.

######  Lemma 2.14.

Let $V$ be a valuation domain.

  1. (i)

For any ideal $I\lhd V$, $I^{\\#}$ is a prime ideal.

  2. (ii)

If $\mathfrak{p}\lhd V$ is a prime ideal then
$\mathfrak{p}^{\\#}=\mathfrak{p}$.

  3. (iii)

If $I\lhd V$ and $a\in V\backslash\\{0\\}$ then $(aI)^{\\#}=I^{\\#}$.

  4. (iv)

If $I\lhd V$ and $V/I$ is finite then $I^{\\#}$ is the unique maximal ideal of
$V$.

###### Proof.

The first $3$ statements are in [FS01, II.4]. We prove (iv). If $I=V$ then the
statement follows directly from the definition. Otherwise, $I\subseteq
I^{\\#}$ and hence $V/I^{\\#}$ is also finite. Since $V/I^{\\#}$ is a finite
integral domain, it is a field. Therefore $I^{\\#}$ is maximal. ∎

######  Lemma 2.15.

Let $R$ be a Prüfer domain, $\mathfrak{p}\lhd R$ a prime ideal and $I\lhd
R_{\mathfrak{p}}$. Then, for all $\delta,\gamma\in R$,

  1. (1)

$\left|\nicefrac{{x\delta=0}}{{x=0}}(R_{\mathfrak{p}}/I)\right|=1$ if and only
if $\delta\notin I^{\\#}$ or $I=R_{\mathfrak{p}}$, and,

  2. (2)

$\left|\nicefrac{{x=x}}{{\gamma|x}}(R_{\mathfrak{p}}/I)\right|=1$ if and only
if $\gamma\notin\mathfrak{p}$ or $I=R_{\mathfrak{p}}$.

###### Proof.

(1) For any $\delta\in R$,
$\left|\nicefrac{{x\delta=0}}{{x=0}}(R_{\mathfrak{p}}/I)\right|=1$ if and only
if $(I:\delta)\subseteq I$. Now $(I:\delta)\subseteq I$ if and only if
$I=R_{\mathfrak{p}}$, or, for all $a\notin I$, $\delta a\notin I$. Therefore
$\left|\nicefrac{{x\delta=0}}{{x=0}}(R_{\mathfrak{p}}/I)\right|=1$ if and only
if $\delta\notin I^{\\#}$ or $I=R_{\mathfrak{p}}$.

(2) For any $\gamma\in R$,
$\left|\nicefrac{{x=x}}{{\gamma|x}}(R_{\mathfrak{p}}/I)\right|=1$ if and only
if $\gamma R_{\mathfrak{p}}+I=R_{\mathfrak{p}}$. This is true if and only if
$\gamma\notin\mathfrak{p}$ or $I=R_{\mathfrak{p}}$. ∎

######  Remark 2.16.

Let $b\in R\backslash\\{0\\}$, $\mathfrak{p}\lhd R$ be a prime ideal and
$I\lhd R_{\mathfrak{p}}$ be an ideal. If $R_{\mathfrak{p}}/I$ is finite then
$\left|I/bI\right|=\left|R_{\mathfrak{p}}/bR_{\mathfrak{p}}\right|$.

###### Proof.

Since $b\neq 0$,

$\left|R_{\mathfrak{p}}/I\right|\cdot\left|I/bI\right|=\left|R_{\mathfrak{p}}/bI\right|=\left|R_{\mathfrak{p}}/bR_{\mathfrak{p}}\right|\cdot\left|bR_{\mathfrak{p}}/bI\right|=\left|R_{\mathfrak{p}}/bR_{\mathfrak{p}}\right|\cdot\left|R_{\mathfrak{p}}/I\right|.$

So, since $\left|R/I\right|$ is non-zero,
$\left|I/bI\right|=\left|R_{\mathfrak{p}}/bR_{\mathfrak{p}}\right|$. ∎

We will frequently use the following lemma which becomes particularly useful
when $R$ is a valuation ring because then for all $r\in R$ and $I\lhd R$
either $r\in I$ or $rR\supseteq I$.

######  Lemma 2.17.

Let $R$ be a commutative ring, $r\in R$ and $I\lhd R$. Then $rR\supseteq I$ if
and only there exists $J\lhd R$ such that $I=rJ$.

###### Proof.

The reverse direction is clear. For the forward direction, take $J=(I:r)$. ∎

######  Lemma 2.18.

Let $V$ be a valuation domain, $I,J\lhd V$ and $a\in R\backslash\\{0\\}$. Then
$J\supseteq(I:a)$ if and only $aJ\supseteq I$ or $J=V$.

###### Proof.

$(\Rightarrow)$ Suppose $J\supseteq(I:a)$. Since $V$ is a valuation domain,
either $a\in I$ or $aV\supseteq I$. If $a\in I$ then $J\supseteq(I:a)=V$. So
$J=V$. Suppose $aV\supseteq I$. Take $c\in I$. There exists $b\in V$ such that
$ab=c$. So $b\in(I:a)\subseteq J$. Hence $c=ab\in aJ$ as required.

$(\Leftarrow)$ If $J=V$ then $J\supseteq(I:a)$. So, suppose $aJ\supseteq I$.
Take $c\in(I:a)$. Then $ac\in I\supseteq aJ$. Since $a\neq 0$, $c\in J$.
Therefore $J\supseteq(I:a)$. ∎

###  2.4. Guide to the proof

The reverse direction of the main theorem is proved in 3. That is, we show
that if $T_{R}$ is decidable then $\mathrm{DPR}(R)$, $\mathrm{EPP}(R)$ and
$X(R)$ are recursive (see [GLPT18, 6.4] (or 3.5), 3.18 and 3.22).

The proof of the forward direction of the main theorem has $3$ principal
ingredients.

  1. (A)

Consequences of $\mathrm{DPR}(R)$, $\mathrm{EPP}(R)$ and $X(R)$ being
recursive. (§3 and §7)

  2. (B)

Syntactic reductions. (§4, §5 and §9)

  3. (C)

Semantic input. (§6, §8 and §10)

(A) In section 3 we introduce and analyse the sets $\mathrm{DPR}(R)$,
$\mathrm{EPP}(R)$ and $X(R)$. These sets are chosen to be as simple as
possible so that our theorem is as easy as possible to apply to concrete
rings. For this reason, work needs to be done to obtain more elaborate
consequences of them being recursive.

For each $n\in\mathbb{N}$, a set $\mathrm{DPR}_{n}(R)$ was introduced in
[GLPT18]. We show that, 3.7, for $R$ a recursive arithmetical ring, if
$\mathrm{DPR}(R)$ is recursive then the sets $\mathrm{DPR}_{n}(R)$ are
recursive (uniformly in $n$). Combining this with [GLPT18, 7.1], or more
precisely its proof, we conclude that we can effectively decide inclusions of
Ziegler basic open sets if and only if $\mathrm{DPR}(R)$ is recursive.

In section 7, we investigate the consequences of $\mathrm{EPP}(R)$ being
recursive, and of $\mathrm{EPP}(R)$ and the radical relation being recursive
(which is deployed in section 8). We show that for a recursive Prüfer domain
the theory of $R$-modules of size $n$ is decidable uniformly in $n$ if and
only if $\mathrm{EPP}(R)$ is recursive, 7.6.

In the proof of the forward direction of the main theorem, the set $X(R)$ is
only ever used in section 10.

(B) Given a sentence $\chi$ as in (2.4) (from 2.4) we often produce a finite
set $S$ of tuples of sentences
$({\raisebox{1.5pt}{$\chi$}}_{1},\ldots,{\raisebox{1.5pt}{$\chi$}}_{n})$ with
each ${\raisebox{1.5pt}{$\chi$}}_{i}$ having a “better” form than $\chi$ such
that there exists $M\models{\raisebox{1.5pt}{$\chi$}}$ if and only if there
exist
$({\raisebox{1.5pt}{$\chi$}}_{1},\ldots,{\raisebox{1.5pt}{$\chi$}}_{n})\in S$
and modules $M_{i}$ for $1\leq i\leq n$ with
$M_{i}\models{\raisebox{1.5pt}{$\chi$}}_{i}$. This is roughly what happens in
the proof of [GLT19, 4.1]. Section 4 introduces two important formalisms (and
ideas) which used in combination are key to the proof. Essentially they allow
us to “automate” some reductions similar to those in the proof of [GLPT18,
4.1] which in this article become too complicated to perform entirely by hand.

It is shown in [GLT19, 4.1] that for arithmetical rings[2][2][2]The result is
stated there only for Prüfer domains but the same proof implies the result for
all arithmetical rings (see section 5). it is enough to consider sentences
like (2.4) where the pp-pairs involved are of the form
$\nicefrac{{d|x}}{{x=0}}$ or $\nicefrac{{xb=0}}{{c|x}}$. Section 5 uses the
formalisms in section 4, to show that it is enough to consider sentences like
(2.4) where at most one conjunct of the form
$\left|\nicefrac{{d|x}}{{x=0}}\right|=D$ or
$\left|\nicefrac{{d|x}}{{x=0}}\right|\geq D$ with $D\geq 2$ occurs and where
at most one conjunct of the form $\left|\nicefrac{{xb=0}}{{c|x}}\right|=G$ or
$\left|\nicefrac{{xb=0}}{{c|x}}\right|\geq G$ with $G\geq 2$ and $b,c\neq 0$
occurs.

In section 9 a notion of complexity, called the extended signature, is put on
the set $W$ of sentences as in (2.4) as reduced to in section 5. The set of
extended signatures is equipped with an artinian partial order. The reduction
processes in section 9 terminate at expressions whose extended signatures are
not reducible. Some of the sentences which are not reducible are of a form for
which we can answer whether there exists a module satisfying them, because
there is an algorithm deciding inclusions of Ziegler basic open sets. The
remaining sentences are of a particular simple form and we deal with them in
section 10.

(C) In section 6, for pp-pairs $\nicefrac{{\varphi}}{{\psi}}$ of the form
$\nicefrac{{d|x}}{{x=0}}$, $\nicefrac{{xb=0}}{{c|x}}$ with $b,c\neq 0$ and
$\nicefrac{{x=x}}{{c|x}}$ with $c\neq 0$, we give a description of the
uniserial module $U$ over a valuation domain $V$, such that
$\nicefrac{{\varphi}}{{\psi}}(U)$ is finite but non-zero. Unlike the
descriptions of such modules in [Gre15] and [PPT07], the results we prove do
not depend on whether the value group of $V$ is dense or not. We now describe
how we use semantic input to deal with sentences as in (2.4) with a conjunct
of the form $\left|\nicefrac{{d|x}}{{x=0}}\right|=D$, or of the form
$\left|\nicefrac{{xb=0}}{{c|x}}\right|=G$ where $b,c\neq 0$.

For instance, if $\nicefrac{{d|x}}{{x=0}}(U)$ is finite but non-zero then it
is easy to show that $U\cong V/dI$ for some ideal $I\lhd V$. In view of 2.11,
for $R$ a Prüfer domain, this means that for $\chi$ a sentence as in (2.4),
$D\in\mathbb{N}_{2}$ and $d\in R\backslash\\{0\\}$, there exists
$M\in\textnormal{Mod}\text{-}R$ such that
$M\models\left|\nicefrac{{d|x}}{{x=0}}\right|=D\wedge{\raisebox{1.5pt}{$\chi$}}$
if and only if there exist $h\in\mathbb{N}$, prime ideals
$\mathfrak{p}_{i}\lhd R$ and ideals $I_{i}\lhd R_{\mathfrak{p}_{i}}$ for
$1\leq i\leq h$, and, $M^{\prime}\in\textnormal{Mod}\text{-}R$ with
$\left|\nicefrac{{d|x}}{{x=0}}(M^{\prime})\right|=1$ such that
$\bigoplus_{i=1}^{h}R_{\mathfrak{p}_{i}}/dI_{i}\oplus
M^{\prime}\models\left|\nicefrac{{d|x}}{{x=0}}\right|=D\wedge{\raisebox{1.5pt}{$\chi$}}$.

In section 8, we show that if $\mathrm{EPP}(R)$ and the radical relation are
recursive then there is an algorithm which given $D\in\mathbb{N}$, $d\in
R\backslash\\{0\\}$ and a sentence $\Theta$ as in (2.4), answers whether there
exists a direct sum $\oplus_{i=1}^{h}R_{\mathfrak{p}_{i}}/dI_{i}$ satisfying
$\left|\nicefrac{{d|x}}{{x=0}}\right|=D\wedge\Theta$. This is used in 9.5 to
produce sentences
${\raisebox{1.5pt}{$\chi$}}_{1},\ldots{\raisebox{1.5pt}{$\chi$}}_{n}$ as in
(2.4) such that there exists an $R$-module satisfying
$\left|\nicefrac{{d|x}}{{x=0}}\right|=D\wedge{\raisebox{1.5pt}{$\chi$}}$ if
and only if there exists an $R$-module satisfying
$\left|\nicefrac{{d|x}}{{x=0}}\right|=1\wedge{\raisebox{1.5pt}{$\chi$}}_{i}$
for some $1\leq i\leq n$. The sentences ${\raisebox{1.5pt}{$\chi$}}_{i}$ are
less complex than $\chi$ in a way precisely defined in section 9.

Similar, but slightly more complicated, reductions are made for pp-pairs of
the form $\nicefrac{{xb=0}}{{c|x}}$ where $b,c\neq 0$.

For pp-pairs of the form $\nicefrac{{x=x}}{{c|x}}$ we need to do something
different. It is easy to see, 6.3, that if $U$ is a uniserial module over a
valuation domain $V$ then $\nicefrac{{x=x}}{{c|x}}(U)$ is finite but non-zero
if and only if $U\cong V/cI$ for some $I\lhd V$ or $U$ is finite and
$c\in\textnormal{ann}_{R}U$. However, it does not seem possible, in this case,
to make a reduction as for $\left|\nicefrac{{d|x}}{{x=0}}\right|=D$ and sums
of modules of the form $R_{\mathfrak{p}}/dI$. This is the main reason that we
need to make the syntactic reductions in section 5 and 9. In particular, the
set of sentences that are not reducible in the sense of section 9, contains
only a small number of forms of sentences with a conjunct of the form
$\left|\nicefrac{{x=x}}{{c|x}}\right|=C$. These sentences are considered
individually in section 10.

##  3\. Recursive sets

In this section we consider the sets $\mathrm{DPR}(R)$, $\mathrm{EPP}(R)$ and
$X(R)$. In each case, we show that if $T_{R}$ is decidable then they are
recursive.

###  3.1. The set $\mathrm{DPR}(R)$

In [GLPT18], a family of relations $\mathrm{DPR}_{n}(R)$ were defined.
Although not directly stated there, see [GLPT18, 7.1], it was shown that, for
$R$ a recursive[3][3][3]Recall $R$ recursive and $\mathrm{DPR}(R)$ recursive
imply $R$ is effectively given Prüfer domain, if the sets
$\mathrm{DPR}_{n}(R)$ are recursive (uniformly in $n$) then there is an
algorithm deciding inclusions of finite unions of Ziegler basic open sets.
However, it was not known if this condition was necessary for the existence of
such an algorithm, or even if the decidability of the theory of modules of
Prüfer domain implied that $\mathrm{DPR}_{n}(R)$ is recursive for any $n>1$.
It is a consequence of 3.5 that the existence of an algorithm deciding
inclusions of finite unions of Ziegler basic open sets implies that the sets
$\mathrm{DPR}_{n}(R)$ are recursive (uniformly in $n$).

For a recursive Bézout domain, it was shown that if
$\mathrm{DPR}(R):=\mathrm{DPR}_{1}(R)$ is recursive then there is an algorithm
deciding inclusions of finite unions of Ziegler basic open sets. For Prüfer
domains, it was not known if $\mathrm{DPR}_{1}(R)$ being recursive is
sufficient to imply that there is an algorithm deciding inclusions of finite
unions of Ziegler basic open sets. We show, 3.7, that, for $R$ a Prüfer
domain, $\mathrm{DPR}_{1}(R)$ recursive implies $\mathrm{DPR}_{n}(R)$ is
recursive uniformly in $n$.

######  Definition 3.1.

Let $R$ be a commutative ring.

  * •

For each $l\in\mathbb{N}$, let $\mathrm{DPR}_{l}(R)$ be the set of
$2l+2$-tuples
$(a,b_{1},\ldots,b_{l},c,d_{1},\raisebox{-3.0pt}{$\cdot$},d_{l})\in R^{2l+2}$
such that, for all prime ideals $\mathfrak{p},\mathfrak{q}\lhd R$ with
$\mathfrak{p}+\mathfrak{q}\neq R$, either $a\in\mathfrak{p}$,
$c\in\mathfrak{q}$, $b_{i}\notin\mathfrak{p}$ for some $1\leq i\leq l$ or
$d_{i}\notin\mathfrak{q}$ for some $1\leq i\leq l$.

  * •

Let $\mathrm{DPR}_{*}(R)$ be the set of $4$-tuples $(a,B,c,D)$, where $a,c\in
R$ and $B,D\lhd R$ are finitely generated ideals, such that for all prime
ideals $\mathfrak{p},\mathfrak{q}\lhd R$ with $\mathfrak{p}+\mathfrak{q}\neq
R$, either $a\in\mathfrak{p}$, $c\in\mathfrak{q}$, $B\nsubseteq\mathfrak{p}$
or $D\nsubseteq\mathfrak{q}$.

Note that $(a,b_{1},\ldots,b_{l},c,d_{1},\ldots,d_{l})\in\mathrm{DPR}_{l}(R)$
if and only if

$(a,\sum_{i=1}^{l}b_{i}R,c,\sum_{i=1}^{l}d_{i}R)\in\mathrm{DPR}_{*}(R).$

In the following lemma, for $R$ a commutative ring, $I\lhd R$ an ideal and
$X\subseteq\textnormal{Spec}R$, let $V(I)$ denote the closed set, in the
Zariski topology, of prime ideals $\mathfrak{p}$ such that
$\mathfrak{p}\supseteq I$ and $\overline{X}$ the closure of $X$ in the Zariski
topology.

######  Lemma 3.2.

Let $R$ be a commutative ring, $a\in R$ and $B\lhd R$. Then

$(\textnormal{rad}B:a)=\bigcap_{\begin{subarray}{c}\mathfrak{p}\in\textnormal{Spec}R\\\
\mathfrak{p}\supseteq B,\ a\notin\mathfrak{p}\end{subarray}}\mathfrak{p}.$

Hence,

$V((\textnormal{rad}B:a))=\overline{V(B)\backslash V(aR)}.$

###### Proof.

Suppose $r\in(\textnormal{rad}B:a)$. Then $(ra)^{n}\in B$ for some
$n\in\mathbb{N}$. Let $\mathfrak{p}\lhd R$ be a prime ideal with
$B\subseteq\mathfrak{p}$ and $a\notin\mathfrak{p}$. Then
$r^{n}a^{n}=(ra)^{n}\in\mathfrak{p}$. Therefore $r\in\mathfrak{p}$.

Conversely, suppose that $r\notin(\textnormal{rad}B:a)$ i.e. $(ra)^{n}\notin
B$ for all $n\in\mathbb{N}$. A standard argument using Zorn’s lemma produces a
prime ideal $\mathfrak{p}\lhd R$ such that $\mathfrak{p}\supseteq B$ and
$(ra)^{n}\notin\mathfrak{p}$ for all $n\in\mathbb{N}$. Now
$(ra)^{n}\notin\mathfrak{p}$ implies $r\notin\mathfrak{p}$ and
$a\notin\mathfrak{p}$. So we have proved the first statement. For any
$X\subseteq\textnormal{Spec}R$, $V(\bigcap_{\mathfrak{p}\in
X}\mathfrak{p})=\overline{X}$. Therefore, the second statement follows from
the first. ∎

The following statement with $\mathrm{DPR}(R):=\mathrm{DPR}_{1}(R)$ in place
of $\mathrm{DPR}_{*}(R)$ is proved in [GLPT18, 6.3] for Prüfer domains. We use
3.2 to further extend it to all commutative rings.

######  Proposition 3.3.

Let $R$ be a commutative ring. The following are equivalent for $a,c\in R$ and
$B,D\lhd R$ finitely generated.

  1. (1)

$(a,B,c,D)\in\mathrm{DPR}_{*}(R)$

  2. (2)

$1\in(\textnormal{rad}(B):a)+(\textnormal{rad}(D):c)$

###### Proof.

We prove this proposition topologically.

For all $a,c\in R$ and $B,D\lhd R$,
$1\in(\textnormal{rad}(B):a)+(\textnormal{rad}(D):c)$ if and only if
$V((\textnormal{rad}B:a))\cap V((\textnormal{rad}D:c))=\emptyset$. By 3.2,
$V((\textnormal{rad}B:a))=\overline{V(B)\backslash V(aR)}$ and
$V((\textnormal{rad}D:c))=\overline{V(D)\backslash V(cR)}$. Thus

$1\in(\textnormal{rad}(B):a)+(\textnormal{rad}(D):c)$

if and only if

$\overline{V(B)\backslash V(aR)}\cap\overline{V(D)\backslash
V(cR)}=\emptyset.$

Now, by [DST19, 1.5.4 (i)],

$\overline{V(B)\backslash V(aR)}=\bigcup_{\mathfrak{p}\in V(B)\backslash
V(aR)}V(\mathfrak{p})\ \ \text{ and }\ \ \overline{V(D)\backslash
V(cR)}=\bigcup_{\mathfrak{q}\in V(D)\backslash V(cR)}V(\mathfrak{q}).$

So $1\in(\textnormal{rad}(B):a)+(\textnormal{rad}(D):c)$ if and only if

($\dagger$) $(\bigcup_{\mathfrak{p}\in V(B)\backslash
V(aR)}V(\mathfrak{p}))\cap(\bigcup_{\mathfrak{q}\in V(D)\backslash
V(cR)}V(\mathfrak{q}))=\emptyset.$

Now ($\dagger$ ‣ 3.1) holds if and only if for all prime ideals
$\mathfrak{p},\mathfrak{q}$ such that $a\notin\mathfrak{p}$,
$B\subseteq\mathfrak{p}$, $c\notin\mathfrak{q}$ and $D\subseteq\mathfrak{q}$,
we have $V(\mathfrak{p})\cap V(\mathfrak{q})=\emptyset$ (i.e.
$\mathfrak{p}+\mathfrak{q}=R$). ∎

We refer to the relation $a\in\textnormal{rad}bR$ as the radical relation.

######  Remark 3.4.

Let $R$ be a commutative ring. For $a,b\in R$, $a\in\textnormal{rad}bR$ if and
only if $(a,b,a,b)\in\mathrm{DPR}(R)$. In particular, if $R$ is a recursive
ring and $\mathrm{DPR}(R)$ is recursive then the radical relation is
recursive.

For $R$ a commutative ring and $B,D\lhd R$ finitely generated ideals, let
$xB=0$ denote the pp-formula $\bigwedge_{i=1}^{n}xb_{i}=0$ where
$B=\sum_{i=1}^{n}b_{i}R$ and let $D|x$ denote the pp-formula
$\sum_{i=1}^{n}d_{i}|x$ where $D=\sum_{i=1}^{n}d_{i}R$. Note that, up to
$T_{R}$ equivalence, these formulae don’t depend on the choice of generators
of $B$ and $D$.

The following statement with $\mathrm{DPR}_{*}(R)$ replaced by
$\mathrm{DPR}(R)=\mathrm{DPR}_{1}(R)$ is proved in [GLPT18, 6.4] for Prüfer
domains.

######  Proposition 3.5.

Let $R$ be an arithmetical ring. The following are equivalent for $a,c\in R$
and $B,D\lhd R$ finitely generated ideals.

  1. (1)

$(a,B,c,D)\in\mathrm{DPR}_{*}(R)$

  2. (2)

$\left(\nicefrac{{xB=0}}{{D|x}}\right)\subseteq\left(\nicefrac{{xa=0}}{{x=0}}\right)\cup\left(\nicefrac{{x=x}}{{c|x}}\right)$

###### Proof.

$(1)\Rightarrow(2)$: Suppose $(1)$ holds. By 3.3,
$1\in(\textnormal{rad}B:a)+(\textnormal{rad}D:c)$. Hence there exist $u\in R$
and $n\in\mathbb{N}$ such that $(ua)^{n}\in B$ and $((u-1)c)^{n}\in D$.

Suppose $N\in\left(\nicefrac{{xB=0}}{{D|x}}\right)$. Take $m\in N$ such that
$mb=0$ for all $b\in B$ and $m\notin ND$. So $mu^{n}a^{n}=0$ and $m\notin
N(u-1)^{n}c^{n}$. Since $\text{Att}N$ is a proper ideal, either
$u\notin\text{Att}N$ or $u-1\notin\text{Att}N$. Suppose $u\notin\text{Att}N$.
Then $mu^{n}a^{n}=0$ implies $ma^{n}=0$ and hence
$N\in\left(\nicefrac{{xa^{n}=0}}{{x=0}}\right)=\left(\nicefrac{{xa=0}}{{x=0}}\right)$
as required. Now suppose $u-1\notin\text{Att}N$. Then $N(u-1)^{n}c^{n}=Nc^{n}$
and hence
$N\in\left(\nicefrac{{x=x}}{{c^{n}|x}}\right)=\left(\nicefrac{{x=x}}{{c|x}}\right)$.

$(2)\Rightarrow(1)$: Suppose $(2)$ holds. Note that if
$\left(\nicefrac{{xB=0}}{{D|x}}\right)\subseteq\left(\nicefrac{{xa=0}}{{x=0}}\right)\cup\left(\nicefrac{{x=x}}{{c|x}}\right)$
then, applying Herzog’s duality,
$\left(\nicefrac{{xD=0}}{{B|x}}\right)\subseteq\left(\nicefrac{{xc=0}}{{x=0}}\right)\cup\left(\nicefrac{{x=x}}{{a|x}}\right)$.

Suppose $\mathfrak{p},\mathfrak{q}$ are prime ideals with
$\mathfrak{p}+\mathfrak{q}\neq R$. Further, suppose that
$a\notin\mathfrak{p}$, $B\subseteq\mathfrak{p}$ and $D\subseteq\mathfrak{q}$.
We need to show that $c\in\mathfrak{q}$.

Since $R$ is an arithmetical ring, either $\mathfrak{p}\supseteq\mathfrak{q}$
or $\mathfrak{q}\supseteq\mathfrak{p}$. Suppose
$\mathfrak{p}\supseteq\mathfrak{q}$. Then, again since $R$ is an arithmetical
ring, $R_{\mathfrak{p}}/\mathfrak{q}R_{\mathfrak{p}}$ is uniserial and its
pure-injective hull $N:=H(R_{\mathfrak{p}}/\mathfrak{q}R_{\mathfrak{p}})$ is
indecomposable. Since $D\subseteq\mathfrak{q}$, $xD=0$ is equivalent to $x=x$
in $R_{\mathfrak{p}}/\mathfrak{q}R_{\mathfrak{p}}$ and hence in $N$. Since
$B\subseteq\mathfrak{p}$, $B|x$ is not equivalent to $x=x$ in
$R_{\mathfrak{p}}/\mathfrak{q}R_{\mathfrak{p}}$ and hence in $N$. Thus
$N\in\left(\nicefrac{{xD=0}}{{B|x}}\right)$. Since $a\notin\mathfrak{p}$,
$N\notin\left(\nicefrac{{x=x}}{{a|x}}\right)$ and hence
$N\notin\left(\nicefrac{{xc=0}}{{x=0}}\right)$. Therefore
$c\notin\mathfrak{q}$, for otherwise $xc=0$ is equivalent to $x=0$ in $N$. The
argument when $\mathfrak{q}\supseteq\mathfrak{p}$ is very similar except this
time $N:=H(R_{\mathfrak{q}}/\mathfrak{p}R_{\mathfrak{q}})$ and we use that
$\left(\nicefrac{{xD=0}}{{B|x}}\right)\subseteq\left(\nicefrac{{xc=0}}{{x=0}}\right)\cup\left(\nicefrac{{x=x}}{{a|x}}\right)$.
∎

Thus, for $R$ an arithmetical ring, if there exists an algorithm deciding
inclusions of finite unions of Ziegler basic open sets then
$\mathrm{DPR}_{*}(R)$ is recursive. Combining this with [GLPT18, 7.1] (and its
proof) we get the following theorem.

######  Theorem 3.6.

Let $R$ be a recursive Prüfer domain. There is an algorithm deciding
inclusions of finite unions of Ziegler basic open sets if and only if
$\mathrm{DPR}_{*}(R)$ is recursive. Moreover, if $R/\mathfrak{m}$ is infinite
for every maximal ideal $\mathfrak{m}\lhd R$ then $T_{R}$ is decidable if and
only if $\mathrm{DPR}_{*}(R)$ is recursive.

We finish off the work in [GLPT18] by showing that for $R$ a Prüfer domain, if
$\mathrm{DPR}(R)$ is recursive then $\mathrm{DPR}_{n}(R)$ is recursive
uniformly in $n$ (equivalently $\mathrm{DPR}_{*}(R)$ is recursive).

######  Proposition 3.7.

Let $R$ be a recursive arithmetical ring. If $\mathrm{DPR}(R)$ is recursive
then $\mathrm{DPR}_{n}(R)$ is recursive uniformly in $n$.

###### Proof.

Let $n\in\mathbb{N}_{2}$ and $a,c,b_{1},\ldots,b_{n},d_{1},\ldots,d_{n}\in R$.
Suppose that $\alpha,\beta,r_{1},r_{2},\allowbreak s_{1},\allowbreak s_{2}\in
R$ are such that

$b_{1}\alpha=b_{2}r_{2},\ \ \ \ \ \ b_{2}(\alpha-1)=b_{1}r_{1}$
$d_{1}\beta=d_{2}s_{2}\ \text{ and }\ d_{2}(\beta-1)=d_{1}s_{1}.$

Claim:

$(a,c,b_{1},\raisebox{-3.0pt}{$\cdot$},b_{n},d_{1},\ldots,d_{n})\in\text{DPR}_{n}(R)$

if and only if

  1. (i)

$(a\alpha,c\beta,b_{2},\ldots,b_{n},d_{2},\ldots,d_{n})\in\text{DPR}_{n-1}(R)$,

  2. (ii)

$(a\alpha,c(\beta-1),b_{2},\ldots,b_{n},d_{1},d_{3},\ldots,d_{n})\in\text{DPR}_{n-1}(R)$,

  3. (iii)

$(a(\alpha-1),c\beta,b_{1},b_{3}\ldots,b_{n},d_{2},\ldots,d_{n})\in\text{DPR}_{n-1}(R)$
and

  4. (iv)

$(a(\alpha-1),c(\beta-1),b_{1},b_{3},\ldots,b_{n},d_{1},d_{3},\ldots,d_{n})\in\text{DPR}_{n-1}(R)$.

This claim plus the fact that we can always find appropriate
$\alpha,\beta,r_{1},r_{2},s_{1},s_{2}\in R$ implies the proposition.

To prove the forward direction, we show that $(\star)$ implies $(i)$ and note
that the remaining conditions $(ii)$, $(iii)$, $(iv)$ are the same as $(i)$
but with the roles of $b_{1}$ and $b_{2}$, and of $\alpha$ and $\alpha-1$
interchanged (respectively of $d_{1}$ and $d_{2}$, and of $\beta$ and
$\beta-1$ interchanged).

Let $\mathfrak{p},\mathfrak{q}$ be prime ideals such that
$\mathfrak{p}+\mathfrak{q}\neq R$. Assuming $(\star)$, we need to show that
$a\alpha\in\mathfrak{p}$, $c\beta\in\mathfrak{q}$, $b_{i}\notin\mathfrak{p}$
for some $2\leq i\leq n$ or $d_{i}\notin\mathfrak{q}$ for some $2\leq i\leq
n$.

Now $(\star)$ implies $a\in\mathfrak{p}$, $c\in\mathfrak{q}$,
$b_{i}\notin\mathfrak{p}$ for some $1\leq i\leq n$ or
$d_{i}\notin\mathfrak{q}$ for some $1\leq i\leq n$. So the only problem is
when $b_{1}\notin\mathfrak{p}$ or $d_{1}\notin\mathfrak{q}$. Suppose
$b_{1}\notin\mathfrak{p}$. If $\alpha\in\mathfrak{p}$ then
$a\alpha\in\mathfrak{p}$ as required. So suppose further that
$\alpha\notin\mathfrak{p}$. Then $b_{1}\alpha\notin\mathfrak{p}$ and hence
$b_{2}r_{2}\notin\mathfrak{p}$. So $b_{2}\notin\mathfrak{p}$ as required. The
argument when $d_{1}\notin\mathfrak{q}$ is the same with the roles of $b_{1}$
and $d_{1}$, of $b_{2}$ and $d_{2}$, and of $\alpha$ and $\beta$ interchanged.

We now show that if $(\star)$ is not true then one of $(i),(ii),(iii),(iv)$ is
not true. If $(\star)$ is not true then there exist prime ideals
$\mathfrak{p},\mathfrak{q}$ such that $\mathfrak{p}+\mathfrak{q}\neq R$ and
$a\notin\mathfrak{p}$, $c\notin\mathfrak{q}$, $b_{i}\in\mathfrak{p}$ for all
$1\leq i\leq n$ and $d_{i}\in\mathfrak{q}$ for all $1\leq i\leq n$. For any
proper ideal $I$, either $\alpha\notin I$ or $\alpha-1\notin I$ (respectively
$\beta\notin I$ or $\beta-1\notin I$). Without loss of generality, we may
assume that $\alpha\notin\mathfrak{p}$ and $\beta\notin\mathfrak{q}$. Hence
$a\alpha\notin\mathfrak{p}$, $c\beta\notin\mathfrak{q}$,
$b_{i}\in\mathfrak{p}$ for all $1\leq i\leq n$ and $d_{i}\in\mathfrak{q}$ for
all $1\leq i\leq n$. So
$(a\alpha,c\beta,b_{2},\ldots,b_{n},d_{2},\ldots,d_{n})\notin\text{DPR}_{n-1}(R)$
as required. ∎

Combining this with the results in [GLPT18] we get the following.

######  Theorem 3.8.

Let $R$ be a recursive Prüfer domain. There is an algorithm answering whether
one Ziegler basic open set is contained in a finite union of others if and
only if the relation $\mathrm{DPR}(R)$ is recursive.

######  Corollary 3.9.

Let $R$ be a recursive Prüfer domain. The relation $\mathrm{DPR}(R)$ is
recursive if and only if there is an algorithm which, given a sentence

${\raisebox{1.5pt}{$\chi$}}:=\bigwedge_{i=1}^{n}\left|\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right|\geq
E_{i}\wedge\bigwedge_{j=1}^{m}\left|\nicefrac{{\sigma_{j}}}{{\tau_{j}}}\right|=1,$

where $\varphi_{i},\psi_{i},\sigma_{j},\tau_{j}$ are pp-$1$-formulae and
$E_{i}\in\mathbb{N}$ for $1\leq i\leq n$ and $1\leq j\leq m$, answers whether
there exists an $R$-module $M$ with $M\models{\raisebox{1.5pt}{$\chi$}}$.
Moreover, if $R/\mathfrak{m}$ is infinite for every maximal ideal
$\mathfrak{m}\lhd R$ then $T_{R}$ is decidable if and only if
$\mathrm{DPR}(R)$ is recursive.

###### Proof.

The first statement follows from 3.8 and 2.5.

For any $R$-module $M$ and pp-pair $\nicefrac{{\varphi}}{{\psi}}$,
$\nicefrac{{\varphi}}{{\psi}}(M)$ is an $R$-module. By [GLT19, 3.1], if
$R/\mathfrak{m}$ is infinite for every maximal ideal $\mathfrak{m}\lhd R$ then
the only finite $R$-module is the zero module. So, the second statement
follows from the first by a standard argument using the Baur-Monk theorem. ∎

######  Question 1.

It was shown in [Gre15, 3.2] that, for any commutative ring $R$, if $T_{R}$ is
recursive then the radical relation is recursive. For $R$ an arbitrary
commutative ring, does $T_{R}$ decidable imply $\mathrm{DPR}(R)$, or more
generally $\mathrm{DPR}_{*}(R)$, is recursive?

###  3.2. The sets $\mathrm{PP}(R)$ and $\mathrm{EPP}(R)$

In [GLT19], a family of relations $\mathrm{PP}_{n}(R)$ were introduced. It is
shown, [GLT19, 3.2], that if a recursive Prüfer domain has decidable theory of
modules then $\mathrm{PP}_{n}(R)$ is recursive uniformly in $n$. Conversely,
it was shown that if $R$ is a recursive[4][4][4]It was stated there for
effectively given Prüfer domains. However, recall, if $R$ is a recursive
Prüfer domain with $\mathrm{DPR}(R)$ recursive then $R$ is effectively given.
Prüfer domain such that the value group of each localisation of $R$ at a
maximal ideal is dense then if $\mathrm{DPR}_{n}(R)$ and $\mathrm{PP}_{n}(R)$
are recursive uniformly in $n$ then the theory of $R$-modules is recursive.

######  Definition 3.10.

For $l\in\mathbb{N}$, let $\mathrm{PP}_{l}(R)$ consist of the tuples
$(p,n,c_{1},\ldots,c_{l},d)\in\mathbb{P}\times\mathbb{N}\times R^{l+1}$ such
that there exist positive integers $s,k_{1},\ldots,k_{s}$ and maximal ideals
$\mathfrak{m}_{1},\ldots,\mathfrak{m}_{s}$ of $R$ for which
$n\in\mathrm{Span}_{\mathbb{N}_{0}}\\{k_{1},\ldots,k_{s}\\}$ and for $1\leq
i\leq s$

  1. (1)

$\left|R/\mathfrak{m}_{i}\right|=p^{k_{i}}$,

  2. (2)

$c_{j}\in\mathfrak{m}_{i}$ for $1\leq j\leq l$,

  3. (3)

$d\notin\mathfrak{m}_{i}$.

It is clear that for $R$ a Bézout domain, if $\mathrm{PP}_{1}(R)$ is recursive
then $\mathrm{PP}_{l}(R)$ is recursive uniformly in $l$. This is because
$(p,n,c_{1},\ldots,c_{l},d)\in\mathrm{PP}_{l}(R)$ if and only if
$(p,n,\gcd\\{c_{1},\ldots,c_{l}\\},d)\in\mathrm{PP}_{1}(R)$. However, with a
bit more work one can show this is also true for Prüfer domains.

######  Proposition 3.11.

Let $R$ be a recursive Prüfer domain. If $\mathrm{PP}_{1}(R)$ is recursive
then $\mathrm{PP}_{l}(R)$ is recursive uniformly in $l$.

###### Proof.

We skip this proof as it is very similar to the proof of 3.17. ∎

As a direct consequence of [GLT19, 6.1], [GLT19, 3.2], [GLPT18, 6.4], 3.11 and
3.7, we get the following theorem.

######  Theorem 3.12.

Let $R$ be a recursive Prüfer domain such that for all maximal ideals
$\mathfrak{m}$, the value group of $R_{\mathfrak{m}}$ is dense. The theory of
$R$-modules is decidable if and only if $\mathrm{DPR}(R)$ and $\mathrm{PP}(R)$
are recursive.

We generalise $\mathrm{PP}_{l}(R)$ to $\mathrm{EPP}_{l}(R)$ in order to deal
with Prüfer domains with maximal ideals $\mathfrak{m}$ such that
$R_{\mathfrak{m}}$ is a valuation domain with non-dense value group.

######  Definition 3.13.

For $l\in\mathbb{N}$, let $\mathrm{EPP}_{l}(R)$ consist of tuples

$(p,n;a_{1},\ldots,a_{l};\gamma;e,m)\in\mathbb{P}\times\mathbb{N}_{0}\times
R^{l}\times R\times R\times\mathbb{N}_{0}$

such that there exist $h\in\mathbb{N}_{0}$ and, for $1\leq i\leq h$, prime
ideals $\mathfrak{p}_{i}\lhd R$ and ideals $I_{i}\lhd R_{\mathfrak{p}_{i}}$
such that $\gamma\notin\mathfrak{p}_{i}$ and $a_{1},\ldots,a_{l}\in I_{i}$ for
$1\leq i\leq h$, $|\oplus_{i=1}^{h}R_{\mathfrak{p}_{i}}/I_{i}|=p^{n}$ and
$|\oplus_{i=1}^{h}R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}|=p^{m}$.

We say the sequence $(\mathfrak{p}_{j},I_{j})_{1\leq j\leq h}$ witnesses
$(p,n;a_{1},\ldots,a_{l};\gamma;e,m)\in\mathrm{EPP}_{l}(R)$. By convention,
$(p,0;a_{1},\ldots,a_{l};\gamma;e,0)\in\mathrm{EPP}_{l}(R)$ and the empty
sequence is a witness for it. We will often write $\mathrm{EPP}(R)$ for
$\mathrm{EPP}_{1}(R)$.

######  Remark 3.14.

We may replace prime ideals with maximal ideals in 3.13 without changing the
definition since if $\left|R_{\mathfrak{p}}/eR_{\mathfrak{p}}\right|$ is
finite then either $\mathfrak{p}$ is maximal or
$R_{\mathfrak{p}}=eR_{\mathfrak{p}}$ and if $\left|R_{\mathfrak{p}}/I\right|$
is finite then either $\mathfrak{p}$ is maximal or $I=R_{\mathfrak{p}}$.

The relation $\mathrm{EPP}_{l}(R)$ is an extension of the relation
$\mathrm{PP}_{l}(R)$.

######  Lemma 3.15.

Let $p\in\mathbb{P}$, $n\in\mathbb{N}$ and $c_{1},\ldots,c_{n},d\in R$. Then
$(p,n,c_{1},\ldots,c_{l},d)\in\mathrm{PP}_{l}(R)$ if and only if
$(p,n;c_{1},\ldots,c_{l};d;1,0)\in\mathrm{EPP}_{l}(R)$.

###### Proof.

Suppose $(p,n,c_{1},\ldots,c_{l},d)\in\mathrm{PP}_{l}(R)$. Let
$s\in\mathbb{N}$, $k_{1},\ldots,k_{s}\in\mathbb{N}$ and
$\mathfrak{m}_{1},\ldots,\mathfrak{m}_{s}$ be as in the definition of
$\mathrm{PP}_{l}(R)$. Let $\lambda_{1},\ldots,\lambda_{s}\in\mathbb{N}_{0}$ be
such that $n=\sum_{i=1}^{s}\lambda_{i}k_{i}$. Then $c_{j}\in\mathfrak{m}_{i}$
for $1\leq j\leq l$, $d\notin\mathfrak{m}_{i}$,
$|\oplus_{i=1}^{s}(R_{\mathfrak{m}_{i}}/\mathfrak{m}_{i}R_{\mathfrak{m}_{i}})^{\lambda_{i}}|=p^{n}$
and $|\oplus_{i=1}^{s}(R_{\mathfrak{m}_{i}}/1\cdot
R_{\mathfrak{m}_{i}})^{\lambda_{i}}|=p^{0}$. So
$(p,n;c_{1},\ldots,c_{l};d;1,0)\in\mathrm{EPP}_{l}(R)$.

Suppose $(\mathfrak{m}_{j},I_{j})_{1\leq j\leq s}$ witnesses
$(p,n;c_{1},\ldots,c_{l};d;1,0)\in\mathrm{EPP}_{l}(R)$. For $1\leq i\leq s$,
let $\lambda_{i}\in\mathbb{N}_{0}$ be such that
$|R_{\mathfrak{m}_{i}}/I_{i}|=|R/\mathfrak{m}_{i}|^{\lambda_{i}}$. If
$\lambda_{i}\neq 0$ then $I_{i}\subseteq\mathfrak{m}_{i}R_{\mathfrak{m}_{i}}$
and so $c_{j}\in\mathfrak{m}_{i}$ for $1\leq j\leq l$. For $1\leq i\leq s$,
let $k_{i}$ be such that $|R/\mathfrak{m}_{i}|=p^{k_{i}}$. Now $n=\sum_{i=1,\
\lambda_{i}\neq 0}^{s}\lambda_{i}k_{i}$ and hence
$(p,n,c_{1},\ldots,c_{l},d)\in\mathrm{PP}_{l}(R)$. ∎

If the value group of $R_{\mathfrak{m}}$ is dense then, for all $e\in R$,
$\left|R_{\mathfrak{m}}/eR_{\mathfrak{m}}\right|$ is either $1$ or infinite.
Moreover, $\left|R_{\mathfrak{m}}/eR_{\mathfrak{m}}\right|=1$ if and only if
$e\notin\mathfrak{m}$.

######  Remark 3.16.

Let $R$ be a Prüfer domain such that the value group of $R_{\mathfrak{m}}$ is
dense for all maximal ideals $\mathfrak{m}$. Then
$(p,n;a_{1},\ldots,a_{l};\gamma;e,m)\in\mathrm{EPP}_{l}(R)$ if and only if
$(p,n,a_{1},\ldots,a_{l},\gamma\cdot e)\in\mathrm{PP}_{l}(R)$ and $m=0$.

In particular, if $R$ is a recursive Prüfer domain such that the value group
of $R_{\mathfrak{m}}$ is dense for all maximal ideals $\mathfrak{m}$ then
$\mathrm{EPP}_{l}(R)$ is recursive if and only if $\mathrm{PP}_{l}(R)$ is
recursive.

######  Proposition 3.17.

Let $R$ be a recursive Prüfer domain. If $\mathrm{EPP}_{1}(R)$ is recursive
then $\mathrm{EPP}_{l}(R)$ is recursive uniformly in $l$.

###### Proof.

We show that for all $p\in\mathbb{P}$, $n,m\in\mathbb{N}_{0}$,
$a_{1},\ldots,a_{l},\gamma,e\in R$, if $\alpha,r,s\in R$ are such that
$a_{1}\alpha=a_{2}r$ and $a_{2}(\alpha-1)=a_{1}s$ then
$(p,n;a_{1},\ldots,a_{l};\gamma;e,m)\in\mathrm{EPP}_{l}(R)$ if and only if
there exist $n_{1},n_{2}\in\mathbb{N}_{0}$ and $m_{1},m_{2}\in\mathbb{N}_{0}$
such that $n_{1}+n_{2}=n$, $m_{1}+m_{2}=m$,
$(p,n_{1};a_{2},\ldots,a_{l};\gamma\alpha;e,m_{1})\in\mathrm{EPP}_{l-1}(R)$
and
$(p,n_{2},a_{1},a_{3},\ldots,a_{l},\gamma(\alpha-1);e,m_{2})\in\mathrm{EPP}_{l-1}(R)$.
This is enough since we can always effectively find appropriate $\alpha,r,s\in
R$.

Suppose that $(\mathfrak{p}_{j},I_{j})_{1\leq j\leq s}$ witnesses
$(p,n;a_{1},\ldots,a_{l};\gamma;e,m)\in\mathrm{EPP}_{l}(R)$. For all $1\leq
j\leq s$, either $\alpha\notin\mathfrak{p}_{j}$ or
$\alpha-1\notin\mathfrak{p}_{j}$. By reordering, we may assume that
$\alpha\notin\mathfrak{p}_{j}$ for $1\leq j\leq t$ and
$\alpha-1\notin\mathfrak{p}_{j}$ for $t+1\leq j\leq s$. Let
$n_{1}=\log_{p}\left|\oplus_{i=1}^{t}R_{\mathfrak{p}_{i}}/I_{i}\right|$,
$n_{2}=\log_{p}\left|\oplus_{i=t+1}^{s}R_{\mathfrak{p}_{i}}/I_{i}\right|$,
$m_{1}=\log_{p}\left|\oplus_{i=1}^{t}R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}\right|$
and
$m_{2}=\log_{p}\left|\oplus_{i=t+1}^{s}R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}\right|$.
Now $\alpha\gamma\notin\mathfrak{p}_{j}$ and $a_{2},\ldots,a_{l}\in I_{j}$ for
$1\leq j\leq t$,
$\left|\oplus_{i=1}^{t}R_{\mathfrak{p}_{i}}/I_{i}\right|=p^{n_{1}}$ and
$\left|\oplus_{i=1}^{t}R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}\right|=p^{m_{1}}$.
So
$(p,n_{1};a_{2},\ldots,a_{l};\gamma\alpha;e,m_{1})\in\mathrm{EPP}_{l-1}(R)$.
Similarly,
$(p,n_{2},a_{1},a_{3},\ldots,a_{l},\allowbreak\gamma(\alpha-1);e,m_{2})\in\mathrm{EPP}_{l-1}(R)$.

Conversely, suppose that $n_{1},n_{2},m_{1},m_{2}\in\mathbb{N}_{0}$ are such
that $n_{1}+n_{2}=n$, $m_{1}+m_{2}=m$,
$(p,n_{1};a_{2},\ldots,a_{l};\allowbreak\gamma\alpha;\allowbreak
e,m_{1})\in\mathrm{EPP}_{l-1}(R)$ and
$(p,n_{2},a_{1},a_{3},\ldots,a_{l},\allowbreak\gamma(\alpha-1);e,m_{2})\in\mathrm{EPP}_{l-1}(R)$.
Let $(\mathfrak{p}_{j},I_{j})_{1\leq j\leq t}$ witness
$(p,n_{1};a_{2},\ldots,a_{l};\gamma\alpha;e,m_{1})\allowbreak\in\mathrm{EPP}_{l-1}(R)$
and let $(\mathfrak{p}_{j},I_{j})_{t+1\leq j\leq s}$ witness
$(p,n_{2},a_{1},a_{3},\ldots,a_{l},\allowbreak\gamma(\alpha-1);e,m_{2})\in\mathrm{EPP}_{l-1}(R)$.
Then

$\left|\oplus_{i=1}^{s}R_{\mathfrak{p}_{i}}/I_{i}\right|=\left|\oplus_{i=1}^{t}R_{\mathfrak{p}_{i}}/I_{i}\right|\cdot\left|\oplus_{i=t+1}^{s}R_{\mathfrak{p}_{i}}/I_{i}\right|=p^{n_{1}}p^{n_{2}}=p^{n}$

and

$\left|\oplus_{i=1}^{s}R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}\right|=\left|\oplus_{i=1}^{t}R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}\right|\cdot\left|\oplus_{i=t+1}^{s}R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}\right|=p^{m_{1}}p^{m_{2}}=p^{m}.$

For $1\leq j\leq t$, $\gamma\alpha\notin I_{j}$ and hence $\gamma\notin I_{j}$
and $\alpha\notin I_{j}$. Since $a_{2}\in I_{j}$ and
$\alpha\notin\mathfrak{p}_{j}$, $a_{1}\alpha=a_{2}r\in I_{j}$ implies
$a_{1}\in I_{j}$. Similarly, $\gamma\notin\mathfrak{m}_{j}$ and $a_{2}\in
I_{j}$ for $t+1\leq j\leq s$. Therefore $(\mathfrak{p}_{j},I_{j})_{1\leq j\leq
s}$ witnesses $(p,n;a_{1},\ldots,a_{l};\gamma;e,m)\in\mathrm{EPP}_{l}(R)$. ∎

######  Lemma 3.18.

Let $R$ be a Prüfer domain. If $T_{R}$ is decidable then $\mathrm{EPP}_{1}(R)$
(and hence $\mathrm{EPP}_{l}(R)$ is recursive uniformly in $l$).

###### Proof.

For $p\in\mathbb{P}$, $n,m\in\mathbb{N}_{0}$ and $a,\gamma,e\in R$, let
$\Theta_{(p,n;a;\gamma;e,m)}$ be the $\mathcal{L}_{R}$-sentence

$\left|\nicefrac{{x=x}}{{x=0}}\right|=p^{2m+n}\wedge\left|\nicefrac{{x=x}}{{e|x}}\right|=p^{m}\wedge\left|\nicefrac{{xe=0}}{{e|x}}\right|=1\wedge\left|\nicefrac{{x=x}}{{\gamma|x}}\right|=1\wedge\left|\nicefrac{{e^{2}a|x}}{{x=0}}\right|=1.$

We show that, for $m,n$ not both zero,
$(p,n;a;\gamma;e,m)\in\mathrm{EPP}_{1}(R)$ if and only if there is an
$R$-module satisfying $\Theta_{(p,n;a;\gamma;e,m)}$. Hence the lemma holds.

Suppose $(p,n;a;\gamma;e,m)\in\mathrm{EPP}_{1}(R)$. By definition, there exist
prime ideals $\mathfrak{p}_{1},\ldots\mathfrak{p}_{s}\lhd R$ and ideals
$I_{i}\lhd R_{\mathfrak{p}_{i}}$ such that $\gamma\notin\mathfrak{p}_{j}$ and
$a\in I_{j}$ for $1\leq j\leq s$,
$|\oplus_{i=1}^{s}R_{\mathfrak{p}_{i}}/I_{i}|=p^{n}$ and
$|\oplus_{i=1}^{s}R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}|=p^{m}$. Let
$M:=\oplus_{i=1}^{s}R_{\mathfrak{p}_{i}}/e^{2}I_{i}$. Then $M$ satisfies
$\Theta_{(p,n;a;\gamma;e,m)}$.

Conversely, suppose there exists an $R$-module $M$ satisfying
$\Theta_{(p,n;a;\gamma;e,m)}$. Since $M$ is finite and non-zero, there exist
maximal ideals $\mathfrak{m}_{1},\ldots,\mathfrak{m}_{s}\lhd R$ and proper
ideals $J_{i}\lhd R_{\mathfrak{m}_{i}}$ such that
$\oplus_{i=1}^{s}R_{\mathfrak{m}_{i}}/J_{i}\cong M$. Since $M$ satisfies
$\Theta_{(p,n;a;\gamma;e,m)}$, for $1\leq i\leq s$, $(J_{i}:e)\subseteq
eR_{\mathfrak{m}_{i}}+J_{i}$.

By 2.18, either $eR_{\mathfrak{m}}+J_{i}=R_{\mathfrak{m}_{i}}$ or
$J_{i}\subseteq e^{2}R_{\mathfrak{m}_{i}}+eJ_{i}$. So, either
$e\notin\mathfrak{m}_{i}$, $J_{i}\subseteq e^{2}R_{\mathfrak{m}_{i}}$ or
$J_{i}\subseteq eJ_{i}$. So, for each $1\leq i\leq s$, there exists $I_{i}\lhd
R_{\mathfrak{m}_{i}}$ with $J_{i}=e^{2}I_{i}$.

Since $|e^{2}a|x/x=0(R_{\mathfrak{m}_{i}}/e^{2}I_{i})|=1$, $a\in I_{i}$ and
since $|x=x/\gamma|x(R_{\mathfrak{m}_{i}}/e^{2}I_{i})|=1$,
$\gamma\notin\mathfrak{m}_{i}$. Therefore
$\mathfrak{m}_{1},\ldots,\mathfrak{m}_{s}$ and $I_{i}\lhd
R_{\mathfrak{m}_{i}}$ are such that $a\in I_{i}$ and
$\gamma\notin\mathfrak{m}_{i}$ for $1\leq i\leq s$, and
$|\oplus_{i=1}^{s}R_{\mathfrak{m}_{i}}/I_{i}|=p^{n}$ and
$|\oplus_{i=1}^{s}R_{\mathfrak{m}_{i}}/eR_{\mathfrak{m}_{i}}|=p^{m}$. Hence
$(p,n;a;\gamma;e,m)\in\mathrm{EPP}_{1}(R)$. ∎

The following corollary is a direct consequence of the proof of 3.18. We will
later see, 7.6, that the converse also holds.

######  Corollary 3.19.

If the theory of $R$-modules of size $n$ is decidable uniformly in $n$ then
$\mathrm{EPP}_{1}(R)$ is recursive.

###  3.3. The set $X(R)$

######  Definition 3.20.

Let $X(R)$ be the set of
$(p,n;e,\gamma,a,\delta)\in\mathbb{P}\times\mathbb{N}\times(R\backslash\\{0\\})\times
R^{3}$ such that there exist integers $h\in\mathbb{N}$ and prime ideals
$\mathfrak{p}_{1},\ldots,\mathfrak{p}_{h}$ such that
$\left|\oplus_{i=1}^{h}R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}\right|=p^{n}$
and for $1\leq i\leq h$, $\gamma\notin\mathfrak{m}_{i}$, and, there exists an
ideal $I_{i}\lhd R_{\mathfrak{p}_{i}}$ such that $a\in I_{i}$ and
$\delta\notin(I_{i})^{\\#}$.

It is often easier to check that $X(R)$ is recursive in concrete rings using
the following reformulation.

######  Remark 3.21.

Let
$(p,n;e,\gamma,a,\delta)\in\mathbb{P}\times\mathbb{N}\times(R\backslash\\{0\\})\times
R^{3}$. Then $(p,n;e,\gamma,a,\delta)\in X(R)$ if and only if there exist
$1\leq h\leq n$ and maximal ideals $\mathfrak{m}_{1},\ldots,\mathfrak{m}_{h}$
such that
$\left|\oplus_{i=1}^{h}R_{\mathfrak{m}_{i}}/eR_{\mathfrak{m}_{i}}\right|=p^{n}$,
and, for $1\leq i\leq h$

  1. (1)

$\gamma\notin\mathfrak{m}_{i}$, and,

  2. (2)

either $\delta\notin\mathfrak{m}_{i}$, or, there exists a prime ideal
$\mathfrak{q}_{i}\subseteq\mathfrak{m}_{i}$ such that $a\in\mathfrak{q}_{i}$
and $\delta\notin\mathfrak{q}_{i}$.

###### Proof.

Note that if $\mathfrak{p}_{i}$ in the definition of $X(R)$ is such that
$\left|R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}\right|=1$ then we may drop
$\mathfrak{p}_{i}$ from the sequence of prime ideals witnessing
$(p,n;e,\gamma,a,\delta)\in X(R)$. Therefore, we may assume each
$\mathfrak{p}_{i}$ is maximal and that $1\leq h\leq n$. Now, if $a\in I_{i}$
and $\delta\notin(I_{i})^{\\#}$ then either $I_{i}=R_{\mathfrak{p}_{i}}$ and
$\delta\notin\mathfrak{p}_{i}$, or, $I_{i}\lhd R_{\mathfrak{p}_{i}}$ is a
proper ideal. If $I_{i}$ is a proper ideal then $a\in I_{i}$ implies
$a\in(I_{i})^{\\#}$.

Therefore, if $(p,n;e,\gamma,a,\delta)\in X(R)$ then the conditions in the
statement hold with, $\mathfrak{m}_{i}:=\mathfrak{p}_{i}$, and
$\mathfrak{q}_{i}:=(I_{i})^{\\#}$ if $\delta\in\mathfrak{m}_{i}$. Conversely,
if the conditions in the statement hold for $(p,n;e,\gamma,a,\delta)$ then set
$\mathfrak{p}_{i}:=\mathfrak{m}_{i}$ and, $I_{i}:=R_{\mathfrak{m}_{i}}$ if
$\delta\notin\mathfrak{m}_{i}$ and $I_{i}:=\mathfrak{q}_{i}$ otherwise. ∎

######  Proposition 3.22.

Let $R$ be a Prüfer domain. If $T_{R}$ is decidable then $X(R)$ is recursive.

###### Proof.

Let
$(p,n;e,\gamma,a,\delta)\in\mathbb{P}\times\mathbb{N}\times(R\backslash\\{0\\})\times
R^{3}$. We show that $(p,n;e,\gamma,a,\delta)\in X(R)$ if and only if there
exists an $R$-modules satisfying

${\raisebox{1.5pt}{$\chi$}}:=\left|\nicefrac{{x=x}}{{e|x}}\right|=p^{n}\wedge\left|\nicefrac{{xe=0}}{{e|x}}\right|=1\wedge\left|\nicefrac{{e^{2}a|x}}{{x=0}}\right|=1\wedge\left|\nicefrac{{x=x}}{{\gamma|x}}\right|=1\wedge\left|\nicefrac{{x\delta=0}}{{x=0}}\right|=1.$

First suppose that there exist $h\in\mathbb{N}$ and prime ideals
$\mathfrak{p}_{1},\ldots,\mathfrak{p}_{h}\lhd R$ such that
$\left|\oplus_{i=1}^{h}R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}\right|=p^{n}$
and for $1\leq i\leq h$, $\gamma\notin\mathfrak{p}_{i}$, and, there exists an
ideal $I_{i}\lhd R_{\mathfrak{p}_{i}}$ such that $a\in I_{i}$ and
$\delta\notin(I_{i})^{\\#}$. Then
$\bigoplus_{i=1}^{h}R_{\mathfrak{p}_{i}}/e^{2}I_{i}\models{\raisebox{1.5pt}{$\chi$}}$.

Conversely, suppose there exists an $R$-module satisfying $\chi$. Then, 2.11,
there exists a finite direct sum of modules $U_{i}$ such that
$\oplus_{i=1}^{h}U_{i}\models{\raisebox{1.5pt}{$\chi$}}$ and each $U_{i}$ is
the restriction to $R$ of a uniserial module over $R_{\mathfrak{p}_{i}}$ for
some prime ideal $\mathfrak{p}_{i}\lhd R$. We may assume that $U_{i}/U_{i}e$
is non-zero for each $U_{i}$, for otherwise the direct sum with $U_{i}$
omitted also satisfies $\chi$. Since $U_{i}$ is uniserial as an
$R_{\mathfrak{p}_{i}}$-module and $U_{i}/U_{i}e$ is non-zero and finite,
$U_{i}$ is finitely generated over $R_{\mathfrak{p}_{i}}$. Therefore
$U_{i}\cong R_{\mathfrak{p}_{i}}/J_{i}$ for some ideal $J_{i}\lhd
R_{\mathfrak{p}_{i}}$. Since $|xe=0/e|x(U_{i})|=1$, $(J_{i}:e)\subseteq
J_{i}+eR_{\mathfrak{p}_{i}}$. So, as in 3.18, there exists $I_{i}\lhd
R_{\mathfrak{p}_{i}}$ such that $J_{i}=e^{2}I_{i}$.

Now, since $\oplus_{i=1}^{h}U_{i}\models{\raisebox{1.5pt}{$\chi$}}$,
$\left|\oplus_{i=1}^{h}R_{\mathfrak{p}_{i}}/eR_{\mathfrak{p}_{i}}\right|=p^{n}$,
$e^{2}a\in e^{2}I$ and hence $a\in I$. Moreover, by 2.15,
$\gamma\notin\mathfrak{p}_{i}$ and $\delta\notin I_{i}^{\\#}$. ∎

##  4\. Formalisms

The formalisms introduced in this section will be used throughout the paper to
allow us to make reductions in complexity of certain sets of conditions later
on.

###  4.1. Sets of functions

Let $\Delta$ be a set and $\mathcal{E}$ a set of functions from $\Delta$ to
$\mathbb{N}\cup\\{\infty\\}$ such that if $f,g\in\mathcal{E}$ then $f\cdot
g\in\mathcal{E}$ and such that the function which has constant value $1$ is in
$\mathcal{E}$. Let $n\in\mathbb{N}$, $X,Y\subseteq\Delta$ be finite sets and
let $f:X\rightarrow\mathbb{N}$ and $g:Y\rightarrow\mathbb{N}$.

Define $\Omega_{f,g,n}$ to be the set of all tuples of functions
$(f_{1},\ldots,f_{n},g_{1},\ldots,g_{n})$ where $f_{i}:X\cup(Y\backslash
Y_{i})\rightarrow\mathbb{N}$ and $g_{i}:Y_{i}\rightarrow\mathbb{N}$ are such
that $Y_{i}\subseteq Y$ and

  * •

$\prod_{i=1}^{n}f_{i}(x)=f(x)$ for all $x\in X$,

  * •

$f_{i}(y)<g(y)$ for all $y\in Y\backslash Y_{i}$,

  * •

$g_{i}(y)=g(y)$ for all $y\in Y_{i}$, and

  * •

for all $y\in Y$,

$\left(\prod_{i\text{ with }y\in Y\backslash Y_{i}}f_{i}(y)\cdot\prod_{i\text{
with }y\in Y_{i}}g_{i}(y)\right)\geq g(y).$

The most important instance of this set up in this paper is when $\Delta$ is a
set of pairs $\varphi/\psi$ of pp-$1$-formulae over a ring $R$ and
$\mathcal{E}$ is the set of $R$-modules $M$ viewed as functions on $\Delta$ by
setting $M(\varphi/\psi):=|\varphi(M)/\psi(M)|$.

For $\mathcal{E}_{1},\mathcal{E}_{2}$ sets of functions from $\Delta$ to
$\mathbb{N}\cup\\{\infty\\}$, define $\mathcal{E}_{1}\cdot\mathcal{E}_{2}$ to
be the set of $f:\Delta\rightarrow\mathbb{N}\cup\\{\infty\\}$ such that there
exist $f_{1}\in\mathcal{E}_{1}$ and $f_{2}\in\mathcal{E}_{2}$ such that
$f=f_{1}\cdot f_{2}$.

######  Lemma 4.1.

Let $\mathcal{E}=\prod_{i=1}^{n}\mathcal{E}_{i}$, $X,Y\subseteq\Delta$ be
finite sets and let $f:X\rightarrow\mathbb{N}$ and $g:Y\rightarrow\mathbb{N}$.
There exists $h\in\mathcal{E}$ such that $h(x)=f(x)$ for all $x\in X$ and
$h(y)\geq g(y)$ for all $y\in Y$ if and only if for some
$(f_{1},\ldots,f_{n},g_{1},\ldots,g_{n})\in\Omega_{f,g,n}$ there exist
$h_{i}\in\mathcal{E}_{i}$ for $1\leq i\leq n$ such that $h_{i}(x)=f_{i}(x)$
for all $x\in X\cup(Y\backslash Y_{i})$ and $h_{i}(y)\geq g_{i}(y)$ for all
$y\in Y_{i}$.

###### Proof.

Let $h\in\mathcal{E}$ be such that $h(x)=f(x)$ for all $x\in X$ and $h(y)\geq
g(y)$ for all $y\in Y$. Since $\mathcal{E}=\prod_{i=1}^{n}\mathcal{E}_{i}$,
there exist $h_{i}\in\mathcal{E}_{i}$ for $1\leq i\leq n$ such that
$\prod_{i=1}^{n}h_{i}(x)=h(x)$ for all $x\in\Delta$. For each $1\leq i\leq n$,
let $Y_{i}:=\\{y\ |\ h_{i}(y)\geq g(y)\\}$, let $f_{i}(x)=h_{i}(x)$ for all
$x\in X\cup(Y\backslash Y_{i})$, and let $g_{i}(y)=g(y)$ for all $y\in Y_{i}$.
By definition $\prod_{i=1}^{n}f_{i}(x)=\prod_{i=1}^{n}h_{i}(x)=h(x)=f(x)$ for
all $x\in X$, $f_{i}(y)=h_{i}(y)<g(y)$ for all $y\in Y\backslash Y_{i}$ and
$g_{i}(y)=g(y)$ for all $y\in Y_{i}$. Now if $y\in Y\backslash Y_{i}$ then
$f_{i}(y)=h_{i}(y)$ and if $y\in Y_{i}$ then $g_{i}(y)=g(y)$. Therefore, for
all $y\in Y$, either $y\in Y_{i}$ for some $1\leq i\leq n$ and hence the $4$th
condition holds or $y\notin Y_{i}$ for all $1\leq i\leq n$ and so $g(y)\leq
h(y)=\prod_{i=1}^{n}h_{i}(y)=\prod_{i}f_{i}(y)$. So
$(f_{1},\ldots,f_{n},g_{1},\ldots,g_{n})\in\Omega_{f,g,n}$.

Conversely, suppose $h_{1},\ldots,h_{n}:\Delta\rightarrow\mathbb{N}$ are such
that there exists $(f_{1},\ldots,f_{n},\allowbreak
g_{1},\ldots,g_{n})\in\Omega_{f,g,n}$ with $h_{i}(x)=f_{i}(x)$ for all $x\in
X\cup(Y\backslash Y_{i})$ and $h_{i}(y)\geq g_{i}(y)$ for all $y\in Y_{i}$.
Define $h:\Delta\rightarrow\mathbb{N}$ by $h(x)=\prod_{i=1}^{n}h_{i}(x)$ for
all $x\in\Delta$. Then $h(x)=f(x)$ for all $x\in X$ and $h(y)\geq g(y)$ for
all $y\in Y$ as required. ∎

######  Definition 4.2.

Let $X,Y\subseteq\Delta$ be finite sets and let $f:X\rightarrow\mathbb{N}$ and
$g:Y\rightarrow\mathbb{N}$. Let $g:=\max\\{g(y)\ |\ y\in Y\\}$. Define
$\Theta_{f,g}$ to be the set of pairs of functions $(f^{\prime},g^{\prime})$
such that $f^{\prime}:X\cup(Y\backslash Y^{\prime})\rightarrow\mathbb{N}$,
$g^{\prime}:Y^{\prime}\rightarrow\mathbb{N}$, $f^{\prime}(x)=f(x)$ for all
$x\in X$, $g^{\prime}(y)=g$ for all $y\in Y^{\prime}$ and $g(y)\leq
f^{\prime}(y)<g$ for all $y\in Y\backslash Y^{\prime}$.

######  Remark 4.3.

A function $h\in\mathcal{E}$ is such that $h(x)=f(x)$ for all $x\in X$ and
$h(y)\geq g(y)$ for all $y\in Y$ if and only if there exists
$(f^{\prime},g^{\prime})\in\Theta_{f,g}$ such that $h(x)=f^{\prime}(x)$ for
all $x\in X\cup(Y\backslash Y^{\prime})$ and $h(y)\geq g^{\prime}(y)$ for all
$y\in Y^{\prime}$.

###  4.2. Lattices generated by conditions

Let $W$ be an infinite set. Let $\mathbb{W}$ be the free bounded distributive
lattice generated by $W$[5][5][5]See [Grä11] for the definition of a free
distributive lattice and add a largest and smallest element.. We use $\sqcup$
for the supremum in this lattice and $\sqcap$ for the infimum in this lattice.
Any element of $\mathbb{W}$ may be expressed as $\bigsqcup_{i\in
I}\bigsqcap_{j\in J_{i}}w_{ij}$ where $I$ and $J_{i}$ for $i\in I$ are finite
sets and $w_{ij}\in W$. Moreover, for $v_{k},w_{ij}\in W$,

$\bigsqcap_{k\in K}v_{k}\leq\bigsqcup_{i\in I}\bigsqcap_{j\in J_{i}}w_{ij}$

if and only if there exists $i\in I$ such that

$\bigsqcap_{k\in K}v_{k}\leq\bigsqcap_{j\in J_{i}}w_{ij}$

if and only if there exists $i\in I$ such that

$\\{v_{k}\ |\ k\in K\\}\supseteq\\{w_{ij}\ |\ j\in J_{i}\\}.$

We make the convention that the empty infimum is the largest element $\top$
and the empty supremum is the least element $\bot$.

We call an expression of the form $\bigsqcup_{i\in I}\bigsqcap_{j\in
J_{i}}w_{ij}$, where $w_{ij}\in W$, irredundant if for each $i\in I$,
$w_{ij_{1}}=w_{ij_{2}}$ implies $j_{i}=j_{2}$ and the sets $w_{i}:=\\{w_{ij}\
|\ j\in J_{i}\\}$ for $i\in I$ are pairwise incomparable by inclusion. If
$\bigsqcup_{i\in I}\bigsqcap_{j\in J_{i}}w_{ij}$ and $\bigsqcup_{i\in
I^{\prime}}\bigsqcap_{j\in J^{\prime}_{i}}w^{\prime}_{ij}$ are in irredundant
form then $\bigsqcup_{i\in I}\bigsqcap_{j\in J_{i}}w_{ij}=\bigsqcup_{i\in
I^{\prime}}\bigsqcap_{j\in J^{\prime}_{i}}w^{\prime}_{ij}$ if and only if
there exist bijections $\sigma:I\rightarrow I^{\prime}$ and
$\sigma_{i}:J_{i}\rightarrow J^{\prime}_{\sigma(i)}$ for each $i\in I$ such
that $w_{ij}=w^{\prime}_{\sigma(i),\sigma_{i}(j)}$ for all $i\in I$ and $j\in
I_{i}$.

Given a recursive presentation of $W$ (i.e. a bijection with $\mathbb{N}$),
this presentation of $W$ gives rise to a recursive presentation of
$\mathbb{W}$ (i.e a presentation where the inclusion of $W$ in $\mathbb{W}$ is
recursive and $\sqcup$ and $\sqcap$ are recursive functions).

For any $V\subseteq W$, define $\mathbb{V}$ to be the filter generated by $V$
in $\mathbb{W}$. Note for $w_{ij}\in W$, $\bigsqcup_{i\in I}\bigsqcap_{j\in
J_{i}}w_{ij}\in\mathbb{V}$ if and only if there exists $i\in I$ such that
$w_{ij}\in V$ for all $j\in J_{i}$. So, in particular $\mathbb{V}$ is prime
filter. It follows that $V$ is a recursive subset of $W$ if and only if
$\mathbb{V}$ is a recursive subset of $\mathbb{W}$.

Suppose that $\text{clx}:W\rightarrow\alpha$ where $\alpha$ is a partially
ordered set with the descending chain condition. Let
$\underline{w}\in\mathbb{W}$ and let $\underline{w}=\bigsqcup_{i\in
I}\bigsqcap_{j\in J_{i}}w_{ij}$ be in irredundant form. For $\beta\in\alpha$,
we write $\mathrm{clx}\underline{w}\leq\beta$ if $w_{ij}\leq\beta$ for all
$i\in I$ and $j\in J_{i}$ and $\mathrm{clx}\underline{w}<\beta$ if
$\mathrm{clx}w_{ij}<\beta$ for all $i\in I$ and $j\in J_{i}$. Note that if
$\underline{w}$ is a lattice combination of elements $w_{i}\in W$ for $1\leq
i\leq n$ then $\mathrm{clx}w_{i}\leq\beta$ (respectively
$\mathrm{clx}w_{i}<\beta$) for $1\leq i\leq n$ implies
$\mathrm{clx}\underline{w}\leq\beta$ (respectively
$\mathrm{clx}\underline{w}<\beta$).

######  Remark 4.4.

Let $W$ be an infinite recursively presented set and $V\subseteq W$. Suppose
that $\alpha$ is an artinian recursive partially ordered set,
$\mathrm{clx}:W\rightarrow\alpha$ is recursive and $W_{0}\subseteq W$ is
recursive. Suppose that there is an algorithm which given $w\notin W_{0}$
computes $\underline{w}\in\mathbb{W}$ such that
$\text{clx}\underline{w}<\text{clx}w$ and such that $w\in V$ if and only if
$\underline{w}\in\mathbb{V}$. Then $V$ is a recursive subset of $W$ if and
only if $V\cap W_{0}$ is a recursive subset of $W$.

The precise choice of $W$ and $V$ varies throughout this article.

To illustrate how this setup is used, let $R$ be a recursive ring. Let $W$ be
the set of $\mathcal{L}_{R}$-sentences

$\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
X}\left|\nicefrac{{\varphi}}{{\psi}}\right|=f(\nicefrac{{\varphi}}{{\psi}})\wedge\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
Y}\left|\nicefrac{{\varphi}}{{\psi}}\right|\geq
g(\nicefrac{{\varphi}}{{\psi}})$

where $X,Y$ are finite sets of pp-$1$-pairs, $f:X\rightarrow\mathbb{N}$ and
$g:Y\rightarrow\mathbb{N}$. Let $V$ be the set of $w\in W$ such that there
exists $M\in\textnormal{Mod}\text{-}R$ with $M\models w$. Then, by 2.4,
$T_{R}$ is decidable if and only if $V$ is recursive. Working with
$\mathbb{W}$ and $\mathbb{V}$, rather than $W$ and $V$ directly, allows us to
talk about more than one module at a time. For instance, for
$w_{1},\ldots,w_{n}\in W$, the condition $w_{1}\sqcap\ldots\sqcap
w_{n}\in\mathbb{V}$ says that there exist $R$-modules
$M_{i}\in\textnormal{Mod}\text{-}R$ with $M_{i}\models w_{i}$ for $1\leq i\leq
n$.

##  5\. First syntactic reductions

Recall that, for a recursive ring $R$, in order to show that the theory of
$R$-modules is decidable, it is enough to show that there is an algorithm
which, given a sentence of the form

$\bigwedge_{i=1}^{s}\left|\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right|=F_{i}\wedge\bigwedge_{j=1}^{t}|\nicefrac{{\sigma_{j}}}{{\tau_{j}}}|\geq
G_{j},$

where, for $1\leq i\leq s$ and $1\leq j\leq t$, $\varphi_{i}$, $\psi_{i}$,
$\sigma_{j}$ and $\tau_{j}$ are pp-$1$-formulae and
$F_{i},G_{j}\in\mathbb{N}$, answers whether there exists an $R$-module
satisfying it.

In [GLT19], it was shown that if $R$ is a recursive Prüfer domain then it is
enough to consider sentences where the pairs of pp-$1$-formulae in $(\star)$
are all of the form $\nicefrac{{d|x}}{{x=0}}$ and $\nicefrac{{xb=0}}{{c|x}}$.
The proof of this statement relies on 2.6, [PT15, 2.2] and the fact, by 2.2
and 2.7, that every $R$-module is elementary equivalent to a direct sum of pp-
uniserial modules. This is also true for arithmetical rings, and so, although
not stated in [GLT19], the result, with the same proof, also holds for
arithmetical rings.

######  Theorem 5.1.

[GLT19, 4.1] Let $R$ be a recursive arithmetical ring. If there exists an
algorithm which, given a sentence

${\raisebox{1.5pt}{$\chi$}}:=\bigwedge_{i=1}^{m}\left|\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right|=G_{i}\wedge\bigwedge_{i=m+1}^{n}\left|\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right|\geq
H_{i},$

where $G_{i},H_{i}\in\mathbb{N}$ and $\nicefrac{{\varphi_{i}}}{{\psi_{i}}}$
are pairs of pp-$1$-formulae of the form $\nicefrac{{d|x}}{{x=0}}$ and
$\nicefrac{{xb=0}}{{c|x}}$ for $1\leq i\leq n$, answers whether there exists
$M\in\textnormal{Mod}\text{-}R$ satisfying $\chi$, then $T_{R}$ is decidable.

We call any conjunction of sentences of the form

$\left|\nicefrac{{d|x}}{{x=0}}\right|=1\ \ \ \text{ or }\ \ \
\left|\nicefrac{{xb=0}}{{c|x}}\right|=1$

an auxiliary sentence.

Convention: In the sequel, we will use the symbol $\square$ as a variable
denoting either $=$ or $\geq$ when talking about conjunctions of sentences
like $\left|\nicefrac{{\varphi}}{{\psi}}\right|\square N$. It will be useful
for us to extend this notation so that $\square$ can also be the symbol
$\emptyset$, where $\square$ being $\emptyset$ indicates that
$\left|\nicefrac{{\varphi}}{{\psi}}\right|\square N$ is omitted from the
conjunction. For instance, when $\square_{1}$ is $\emptyset$, the sentence
$\left|\nicefrac{{d|x}}{{x=0}}\right|\square_{1}D\wedge\left|\nicefrac{{xb=0}}{{c|x}}\right|\square_{2}E$
stands for $\left|\nicefrac{{xb=0}}{{c|x}}\right|\square_{2}E$.

In this section we improve [GLT19, 4.1] to prove the following.

######  Theorem 5.2.

Let $R$ be arithmetical ring. If there exists an algorithm which, given a
sentence $\chi$ of the form

$\left|\nicefrac{{d|x}}{{x=0}}\right|\square_{1}D\wedge\left|\nicefrac{{xb=0}}{{c|x}}\right|\square_{2}E\wedge\bigwedge_{i=1}^{m}\left|\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right|=G_{i}\wedge\bigwedge_{i=m+1}^{n}\left|\nicefrac{{\varphi_{i}}}{{\psi_{i}}}\right|\geq
H_{i}\wedge\Xi,$

where $\square_{1},\square_{2}\in\\{\geq,=,\emptyset\\}$, $d,c,b\in
R\backslash\\{0\\}$, $D,E,G_{i},H_{i}\in\mathbb{N}$, $\Xi$ is an auxiliary
sentence and $\nicefrac{{\varphi_{i}}}{{\psi_{i}}}$ are pairs of
pp-$1$-formulae of the form $\nicefrac{{x=x}}{{c^{\prime}|x}}$ and
$\nicefrac{{xb^{\prime}=0}}{{x=0}}$ for $1\leq i\leq n$, answers whether there
exists an $R$-module satisfying $\chi$, then $T_{R}$ is decidable.

######  Definition 5.3.

Let $X,Y$ be finite subsets of pp-pairs of the form $\nicefrac{{d|x}}{{x=0}}$
or $\nicefrac{{xb=0}}{{c|x}}$, $f:X\rightarrow\mathbb{N}$ and
$g:Y\rightarrow\mathbb{N}$ functions. Define
${\raisebox{1.5pt}{$\chi$}}_{f,g}$ to be the sentence

$\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
X}\left|\nicefrac{{\varphi}}{{\psi}}\right|=f(\nicefrac{{\varphi}}{{\psi}})\wedge\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
Y}\left|\nicefrac{{\varphi}}{{\psi}}\right|\geq
g(\nicefrac{{\varphi}}{{\psi}}).$

For the rest of this section, let $W$ be the set of
$\mathcal{L}_{R}$-sentences of the form ${\raisebox{1.5pt}{$\chi$}}_{f,g}$ and
let $V$ be the set of $w\in W$ such that there exists
$M\in\textnormal{Mod}\text{-}R$ with $M\models w$. If $X$ and $Y$ are both
empty then ${\raisebox{1.5pt}{$\chi$}}_{f,g}$ should be read as the true
sentence.

Define $\mathrm{clx}_{1}{\raisebox{1.5pt}{$\chi$}}_{f,g}$ to be

$\left|\\{\nicefrac{{d|x}}{{x=0}}\in X\ |\
f(\nicefrac{{d|x}}{{x=0}})>1\\}\right|+\left|\\{\nicefrac{{d|x}}{{x=0}}\in Y\
|\ g(\nicefrac{{d|x}}{{x=0}})>1\\}\right|$

and $\mathrm{clx}_{2}{\raisebox{1.5pt}{$\chi$}}_{f,g}$ to be

$\displaystyle\left|\\{\nicefrac{{xb=0}}{{c|x}}\in X\ |\
f(\nicefrac{{xb=0}}{{c|x}})>1\text{ and }c,b\neq 0\\}\right|+$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left|\\{\nicefrac{{xb=0}}{{c|x}}\in
Y\ |\ g(\nicefrac{{xb=0}}{{c|x}})>1\text{ and }b,c\neq 0\\}\right|.$

Formally, we extend $\mathrm{clx}_{1}$ and $\mathrm{clx}_{2}$ to
$\bot,\top\in\mathbb{W}$ by setting
$\mathrm{clx}_{1}\bot=\mathrm{clx}_{1}\top=0$ and
$\mathrm{clx}_{2}\bot=\mathrm{clx}_{2}\top=0$. We will use the notation
$\mathrm{clx}_{i}\underline{w}\leq\mathrm{clx}_{i}w$ and
$\mathrm{clx}_{i}\underline{w}<\mathrm{clx}_{i}w$, for $i\in\\{1,2\\}$,
$\underline{w}\in\mathbb{W}$ and $w\in W$ as in subsection 4.2.

######  Remark 5.4.

For all $w_{1},w_{2}\in W$ and $i\in\\{1,2\\}$,

$\mathrm{clx}_{i}(w_{1}\wedge
w_{2})\leq\mathrm{clx}_{i}(w_{1})+\mathrm{clx}_{i}(w_{2}).$

For our purposes, given $w\in W$, we may always assume that $w$ is of the form

${\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi,$

where $f:X\rightarrow\mathbb{N}_{2}$, $g:Y\rightarrow\mathbb{N}_{2}$ with
$X,Y$ finite disjoint sets of pp-pairs of the form $\nicefrac{{d|x}}{{x=0}}$
or $\nicefrac{{xb=0}}{{c|x}}$, and $\Xi$ is an auxiliary sentence.

It is obvious that any ${\raisebox{1.5pt}{$\chi$}}_{f,g}\in W$ may be
rewritten as ${\raisebox{1.5pt}{$\chi$}}_{f^{\prime},g}\wedge\Xi$ where
$f^{\prime}:X^{\prime}\rightarrow\mathbb{N}_{2}$ and $\Xi$ is an auxiliary
sentence. Moreover, for ${\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi\in W$, let
$Y^{\prime}:=\\{\nicefrac{{\varphi}}{{\psi}}\ |\
g(\nicefrac{{\varphi}}{{\psi}})>1\\}$ and $g^{\prime}:=g|_{Y^{\prime}}$. Then
${\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi\in V$ if and only if
${\raisebox{1.5pt}{$\chi$}}_{f,g^{\prime}}\wedge\Xi\in V$. If
$\nicefrac{{\varphi}}{{\psi}}\in X\cap Y$ and
$f(\nicefrac{{\varphi}}{{\psi}})<g(\nicefrac{{\varphi}}{{\psi}})$ then
$T_{R}\models\lnot{\raisebox{1.5pt}{$\chi$}}_{f,g}$. If
$f(\nicefrac{{\varphi}}{{\psi}})\geq g(\nicefrac{{\varphi}}{{\psi}})$ then
${\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi\in V$ if and only if
${\raisebox{1.5pt}{$\chi$}}_{f,g^{\prime}}\wedge\Xi\in V$ where
$g^{\prime}:=g|_{Y\backslash\\{\nicefrac{{\varphi}}{{\psi}}\\}}$. So, given
$w\in W$, we can effectively decide that $w\notin V$ or compute $f,g$ and
$\Xi$ of the required form such that,
$\mathrm{clx}_{1}{\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi\leq\mathrm{clx}_{1}w$,
$\mathrm{clx}_{2}{\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi\leq\mathrm{clx}_{2}w$,
and, $w\in V$ if and only if ${\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi\in V$.

######  Remark 5.5.

Let $X,Y$ be disjoint finite sets of pp-pairs of the form $d|x/x=0$ or
$xb=0/c|x$, $f:X\rightarrow\mathbb{N}$ and $g:Y\rightarrow\mathbb{N}$
functions, and $\Xi$ an auxiliary sentence. For each $1\leq j\leq n$, let
$\theta_{j}$ be an auxiliary sentence. Suppose that for all
$M\in\textnormal{Mod}\text{-}R$, there exist modules $M_{i}\models\theta_{j}$
such that $M\equiv\bigoplus_{j=1}^{n}M_{j}$. Then
${\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi\in V$ if and only if

$\bigsqcup_{(\overline{f},\overline{g})\in\Omega_{(f,g,n)}}\bigsqcap_{j=1}^{n}{\raisebox{1.5pt}{$\chi$}}_{f_{j},g_{j}}\wedge\theta_{j}\wedge\Xi\in\mathbb{V}.$

Moreover, for all $(\overline{f},\overline{g})\in\Omega_{f,g,n}$ and $1\leq
j\leq n$,

$\ \ \ \ \ \
\mathrm{clx}_{1}({\raisebox{1.5pt}{$\chi$}}_{f_{j},g_{j}}\wedge\theta_{j}\wedge\Xi)\leq\mathrm{clx}_{1}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi)\text{
and }$
$\mathrm{clx}_{2}({\raisebox{1.5pt}{$\chi$}}_{f_{j},g_{j}}\wedge\theta_{j}\wedge\Xi)\leq\mathrm{clx}_{2}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi).$

The next lemma is more precise than we will need in this section. However, we
will need its full strength in section 9. The total order $\prec$ on the set
$\\{\emptyset,=,\leq\\}$ is defined as $\emptyset\,\prec\,=\,\prec\,\leq$.

######  Lemma 5.6.

Let $\varphi/\psi,\varphi^{\prime}/\psi^{\prime},\sigma/\tau$ be pp-pairs,
$\square,\square^{\prime}\in\\{=,\geq\\}$, $E,E^{\prime}\in\mathbb{N}_{2}$ and
let $\Sigma$ be an $\mathcal{L}_{R}$-sentence. Suppose that $M\models\Sigma$
implies

$|\varphi/\psi(M)|=|\sigma/\tau(M)|\cdot|\varphi^{\prime}/\psi^{\prime}(M)|$

for all $M\in\textnormal{Mod}\text{-}R$.

There is an algorithm which, given
$\varphi/\psi,\varphi^{\prime}/\psi^{\prime},\sigma/\tau$,
$\square,\square^{\prime}\in\\{=,\geq\\}$, $E,E^{\prime}\in\mathbb{N}_{2}$ and
$\Sigma$ as above, either returns $\Omega:=\\{\bot\\}$, in which case

$T_{R}\models\lnot(\Sigma\wedge|\varphi/\psi|\square
E\wedge|\varphi^{\prime}/\psi^{\prime}|\square^{\prime}E^{\prime}),$

or, returns $\Omega$, a finite set of tuples
$(D_{1},D_{2},\square_{1},\square_{2})\in\mathbb{N}^{2}\times\\{=,\geq\\}^{2}$
such that

$T_{R}\models\Sigma\wedge|\varphi/\psi|\square
E\wedge|\varphi^{\prime}/\psi^{\prime}|\square^{\prime}E^{\prime}\leftrightarrow\bigvee_{(D_{1},D_{2},\square_{1},\square_{2})\in\Omega}\Sigma\wedge|\tau/\sigma|\square_{1}D_{1}\wedge|\varphi^{\prime}/\psi^{\prime}|\square_{2}D_{2}$

and $D_{1}\cdot D_{2}<E\cdot E^{\prime}$, $\square_{1}\preceq\square$ and
$\square_{2}\preceq\square^{\prime}$ for all
$(D_{1},D_{2},\square_{1},\square_{2})\in\Omega$.

###### Proof.

Case 1: $\square$ and $\square^{\prime}$ are both $=$.

Let $\Omega:=\\{\bot\\}$ if $E^{\prime}$ does not divide $E$, otherwise
$\Omega:=\\{(E/E^{\prime},E^{\prime},=,=)\\}$. Note $(E/E^{\prime})\cdot
E^{\prime}=E<E\cdot E^{\prime}$ because $E^{\prime}\geq 2$.

Case 2: $\square$ is $\geq$ and $\square^{\prime}$ is $=$.

Let $\Omega:=\\{(\lceil E/E^{\prime}\rceil,E^{\prime},\geq,=)\\}$. Note

$\lceil E/E^{\prime}\rceil\cdot E^{\prime}<(E/E^{\prime}+1)\cdot
E=E+E^{\prime}\leq E\cdot E^{\prime}.$

Case 3: $\square$ is $=$ and $\square^{\prime}$ is $\geq$.

Let $X:=\\{D\in\mathbb{N}\ |\ D|E\text{ and }D\geq E^{\prime}\\}$. Define
$\Omega:=\\{\bot\\}$ if $X=\emptyset$ and $\Omega:=\\{(E/D,D,=,=)\ |\ D\in
X\\}$. Note $(E/D)\cdot D=E<E\cdot E^{\prime}$.

Case 4: $\square$ and $\square^{\prime}$ are both $\geq$.

If $E^{\prime}\geq E$ then let $\Omega:=\\{(1,E^{\prime},\geq,\geq)\\}$. If
$E>E^{\prime}$ then set

$\Omega:=\\{(\lceil E/D\rceil,D,\geq,=)\ |\ E>D\geq
E^{\prime}\\}\cup\\{(1,E,\geq,\geq)\\}.$

Note that $E^{\prime}<E\cdot E^{\prime}$, $E<E\cdot E^{\prime}$ and

$\lceil E/D\rceil\cdot D<(E/D+1)\cdot D=E+D\leq E\cdot E^{\prime}.\qed$

The following remark is easy to prove. We record it here because we will use
it frequently.

######  Remark 5.7.

Let $R$ be a commutative ring. For all $a,b\in R$ and
$M\in\textnormal{Mod}\text{-}R$,

$\left|\nicefrac{{a|x}}{{ab|x}}(M)\right|=\left|\nicefrac{{x=x}}{{xa=0+b|x}}(M)\right|$

and

$\left|\nicefrac{{xab=0}}{{xa=0}}(M)\right|=\left|\nicefrac{{a|x\wedge
xb=0}}{{x=0}}(M)\right|.$

######  Proposition 5.8.

Let $R$ be a recursive arithmetical ring. There is an algorithm which given
$w\in W$ with $\mathrm{clx}_{1}(w)>1$ outputs $\underline{w}\in\mathbb{W}$
such that $\mathrm{clx}_{1}(\underline{w})<\mathrm{clx}_{1}(w)$,
$\mathrm{clx}_{2}(\underline{w})\leq\mathrm{clx}_{2}(w)$, and, $w\in V$ if and
only if $\underline{w}\in\mathbb{V}$.

###### Proof.

Let $X,Y$ be disjoint finite sets of pp-pairs of the form $d|x/x=0$ and
$xb=0/c|x$. Let $f:X\rightarrow\mathbb{N}_{2}$ and
$g:Y\rightarrow\mathbb{N}_{2}$ be functions, and let $\Xi$ be an auxiliary
sentence. Let $w$ be

$\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
X}\left|\nicefrac{{\varphi}}{{\psi}}\right|=f(\nicefrac{{\varphi}}{{\psi}})\wedge\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
Y}\left|\nicefrac{{\varphi}}{{\psi}}\right|\geq
g(\nicefrac{{\varphi}}{{\psi}})\wedge\Xi.$

Suppose that there exist non-equal $a,b\in R$ such that
$\nicefrac{{a|x}}{{x=0}},\nicefrac{{b|x}}{{x=0}}\in X\cup Y$ i.e.
$\mathrm{clx}_{1}(w)>1$. Let $\alpha,r,s\in R$ be such that $a\alpha=br$ and
$b(\alpha-1)=as$. Define

  1. (1)

$\Sigma_{1}:=\left|\nicefrac{{x=x}}{{\alpha|x}}\right|=1\wedge\left|\nicefrac{{rb|x}}{{x=0}}\right|=1$,

  2. (2)

$\Sigma_{2}:=\left|\nicefrac{{x=x}}{{\alpha|x}}\right|=1\wedge\left|\nicefrac{{xb=0}}{{r|x}}\right|=1$,

  3. (3)

$\Sigma_{3}:=\left|\nicefrac{{x=x}}{{(\alpha-1)|x}}\right|=1\wedge\left|\nicefrac{{as|x}}{{x=0}}\right|=1$,
and

  4. (4)

$\Sigma_{4}:=\left|\nicefrac{{x=x}}{{(\alpha-1)|x}}\right|=1\wedge\left|\nicefrac{{xa=0}}{{s|x}}\right|=1$.

It follows directly from 2.9 that, for any $M\in\textnormal{Mod}\text{-}R$,
there are $M_{i}\models\Sigma_{i}$ for $1\leq i\leq 4$ such that $M\equiv
M_{1}\oplus M_{2}\oplus M_{3}\oplus M_{4}$. Therefore, by 5.5, $w\in V$ if and
only if

$\bigsqcup_{(\overline{f},\overline{g})\in\Omega_{f,g,4}}\bigsqcap_{i=1}^{4}{\raisebox{1.5pt}{$\chi$}}_{f_{i},g_{i}}\wedge\Xi\wedge\Sigma_{i}\in\mathbb{V}.$

For each $(\overline{f},\overline{g})\in\Omega_{f,g,4}$ and $1\leq i\leq 4$,
it is enough to compute $\underline{w}_{i}\in\mathbb{W}$ such that
$\mathrm{clx}_{1}(\underline{w}_{i})<\mathrm{clx}_{1}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi)$,
$\mathrm{clx}_{2}(\underline{w}_{i})\leq\mathrm{clx}_{2}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi)$
and ${\raisebox{1.5pt}{$\chi$}}_{f_{i},g_{i}}\wedge\Xi\wedge\Sigma_{i}\in V$
if and only if $\underline{w}_{i}\in V$.

Fix $(\overline{f},\overline{g})\in\Omega_{f,g,4}$. For each $1\leq i\leq 4$,
let $X_{i}$ be the domain of $f_{i}$ and $Y_{i}$ be the domain of $g_{i}$.

Case i=1: Suppose $M\models\Sigma_{1}$. Then $M\alpha=M$ and hence $Ma=Mbr=0$.
Therefore, if $M\models\Sigma_{1}$ then
$\left|\nicefrac{{a|x}}{{x=0}}(M)\right|=1$.

If $\nicefrac{{a|x}}{{x=0}}\in X_{1}$ and $f_{1}(\nicefrac{{a|x}}{{x=0}})=1$
then
$\mathrm{clx}_{1}({\raisebox{1.5pt}{$\chi$}}_{f_{1},g_{1}}\wedge\Xi\wedge\Sigma_{1})<\mathrm{clx}_{1}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi)$
and, by 5.5,
$\mathrm{clx}_{2}({\raisebox{1.5pt}{$\chi$}}_{f_{1},g_{1}}\wedge\Xi\wedge\Sigma_{1})\leq\mathrm{clx}_{2}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi)$.
So,
$\underline{w}_{i}:={\raisebox{1.5pt}{$\chi$}}_{f_{1},g_{1}}\wedge\Xi\wedge\Sigma_{1}$
has the required properties.

If $\nicefrac{{a|x}}{{x=0}}\in X_{1}$ and $f_{1}(\nicefrac{{a|x}}{{x=0}})\neq
1$ then, by the first paragraph,
${\raisebox{1.5pt}{$\chi$}}_{f_{1},g_{1}}\wedge\Xi\wedge\Sigma_{1}$ is not
satisfied by any $R$-module. If $\nicefrac{{a|x}}{{x=0}}\notin X_{1}$ then
$\nicefrac{{a|x}}{{x=0}}\in Y_{1}$ since $X\cup Y=X_{1}\cup Y_{1}$. Moreover
$g_{1}(\nicefrac{{a|x}}{{x=0}})=g(\nicefrac{{a|x}}{{x=0}})$. So
$g_{1}(\nicefrac{{a|x}}{{x=0}})>1$ and hence
${\raisebox{1.5pt}{$\chi$}}_{f_{1},g_{1}}\wedge\Xi\wedge\Sigma_{1}$ is not
satisfied by any $R$-module. In either case, set $\underline{w}_{i}:=\bot$.
Then $\underline{w}_{i}\in\mathbb{V}$ if and only if
${\raisebox{1.5pt}{$\chi$}}_{f_{1},g_{1}}\wedge\Xi\wedge\Sigma_{1}\in V$. By
definition
$\mathrm{clx}_{1}(\bot)<\mathrm{clx}_{1}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi)$
and
$\mathrm{clx}_{2}(\bot)\leq\mathrm{clx}_{2}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi)$.

Case i=2: Suppose $M\models\Sigma_{2}$. Then $Ma=M\alpha a=Mbr$. So, since
$xb=0\leq_{M}r|x$, by 5.7,

$\left|\nicefrac{{b|x}}{{x=0}}(M)\right|=\left|\nicefrac{{b|x}}{{br|x}}(M)\right|\cdot\left|\nicefrac{{br|x}}{{x=0}}(M)\right|=\left|\nicefrac{{x=x}}{{r|x}}(M)\right|\cdot\left|\nicefrac{{a|x}}{{x=0}}(M)\right|.$

Let
$X^{\prime}=X_{2}\backslash\\{\nicefrac{{a|x}}{{x=0}},\nicefrac{{b|x}}{{x=0}}\\}$
and
$Y^{\prime}=Y_{2}\backslash\\{\nicefrac{{a|x}}{{x=0}},\nicefrac{{b|x}}{{x=0}}\\}$.
Let $\square,\square^{\prime}\in\\{=,\geq\\}$ and $A,B$ be such that
${\raisebox{1.5pt}{$\chi$}}_{f_{2},g_{2}}\wedge\Xi\wedge\Sigma_{2}$ is

$\left|\nicefrac{{a|x}}{{x=0}}\right|\square
A\wedge\left|\nicefrac{{b|x}}{{x=0}}\right|\square^{\prime}B\wedge\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
X^{\prime}}\left|\nicefrac{{\varphi}}{{\psi}}\right|=f_{2}(\nicefrac{{\varphi}}{{\psi}})\wedge\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
Y^{\prime}}\left|\nicefrac{{\varphi}}{{\psi}}\right|\geq
g_{2}(\nicefrac{{\varphi}}{{\psi}})\wedge\Xi\wedge\Sigma_{2}.$

By 5.6, there is an algorithm which either returns $\Omega:=\\{\bot\\}$, in
which case

$T_{R}\models\lnot\Sigma_{2}\wedge\left|\nicefrac{{a|x}}{{x=0}}\right|\square
A\wedge\left|\nicefrac{{b|x}}{{x=0}}\right|\square^{\prime}B,$

or, a set $\Omega\subseteq\mathbb{N}^{2}\times\\{=,\geq\\}^{2}$ such that

$\Sigma_{2}\wedge\left|\nicefrac{{a|x}}{{x=0}}\right|\square
A\wedge\left|\nicefrac{{b|x}}{{x=0}}\right|\square^{\prime}B$

is equivalent, with respect to $T_{R}$, to

$\bigvee_{(D_{1},D_{2},\square_{1},\square_{2})\in\Omega}\Sigma_{2}\wedge\left|\nicefrac{{x=x}}{{r|x}}\right|\square_{1}D_{1}\wedge\left|\nicefrac{{a|x}}{{x=0}}\right|\square_{2}D_{2}.$

If $\Omega:=\\{\bot\\}$ then
${\raisebox{1.5pt}{$\chi$}}_{f_{2},g_{2}}\wedge\Xi\wedge\Sigma_{2}\in V$ if
and only if $\bot\in\mathbb{V}$. By definition
$\mathrm{clx}_{1}(\bot)<\mathrm{clx}_{1}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi)$
and
$\mathrm{clx}_{2}(\bot)\leq\mathrm{clx}_{2}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi)$.
Otherwise, for each $(D_{1},D_{2},\square_{1},\square_{2})\in\Omega$, let
$u_{(D_{1},D_{2},\square_{1},\square_{2})}$ be

$\left|\nicefrac{{x=x}}{{r|x}}\right|\square_{1}D_{1}\wedge\left|\nicefrac{{a|x}}{{x=0}}\right|\square_{2}D_{2}\wedge\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
X^{\prime}}\\!\left|\nicefrac{{\varphi}}{{\psi}}\right|=f_{2}(\nicefrac{{\varphi}}{{\psi}})\wedge\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
Y^{\prime}}\\!\left|\nicefrac{{\varphi}}{{\psi}}\right|\geq
g_{2}(\nicefrac{{\varphi}}{{\psi}})\wedge\Xi\wedge\Sigma_{2}.$

Then ${\raisebox{1.5pt}{$\chi$}}_{f_{2},g_{2}}\wedge\Xi\wedge\Sigma_{2}$ is
equivalent to

$\bigvee_{(D_{1},D_{2},\square_{1},\square_{2})\in\Omega}u_{(D_{1},D_{2},\square_{1},\square_{2})}$

with respect to $T_{R}$. Therefore
${\raisebox{1.5pt}{$\chi$}}_{f_{2},g_{2}}\wedge\Xi\wedge\Sigma_{2}\in V$ if
and only if

$\bigsqcup_{(D_{1},D_{2},\square_{1},\square_{2})\in\Omega}u_{(D_{1},D_{2},\square_{1},\square_{2})}\in\mathbb{V}.$

Moreover,

$\mathrm{clx}_{1}(u_{(D_{1},D_{2},\square_{1},\square_{2})})\leq
1+(\mathrm{clx}_{1}({\raisebox{1.5pt}{$\chi$}}_{f_{2},g_{2}}\wedge\Xi\wedge\Sigma_{2})-2)<\mathrm{clx}_{1}({\raisebox{1.5pt}{$\chi$}}_{f_{2},g_{2}}\wedge\Xi\wedge\Sigma_{2})$

and
$\mathrm{clx}_{2}(u_{(D_{1},D_{2},\square_{1},\square_{2})})=\mathrm{clx}_{2}({\raisebox{1.5pt}{$\chi$}}_{f_{2},g_{2}}\wedge\Xi\wedge\Sigma_{2})$.
So we are done, since, by 5.5,
$\mathrm{clx}_{1}({\raisebox{1.5pt}{$\chi$}}_{f_{2},g_{2}}\wedge\Xi\wedge\Sigma_{2})\leq\mathrm{clx}_{1}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi)$
and
$\mathrm{clx}_{2}({\raisebox{1.5pt}{$\chi$}}_{f_{2},g_{2}}\wedge\Xi\wedge\Sigma_{2})\leq\mathrm{clx}_{2}({\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Xi)$.

The case $i=3$ is similar to $i=1$ and the case $i=4$ is similar to $i=2$. ∎

We now start work on showing that there exists an algorithm which given $w\in
W$ with $\mathrm{clx}_{2}w>1$ outputs $\underline{w}\in\mathbb{W}$ such that
$w\in V$ if and only if $\underline{w}\in\mathbb{V}$ and
$\mathrm{clx}_{2}(\underline{w})<\mathrm{clx}_{2}(w)$. This uses the same
ideas as for $\mathrm{clx}_{1}$ but is significantly more complicated.

$\Lambda^{\prime}_{1}$$\Lambda_{1}$$\Lambda_{2}$$\Lambda^{\prime}_{2}$$\Lambda_{3}$$\Lambda^{\prime}_{3}$$\Lambda^{\prime}_{4}$$\Lambda_{4}$$P^{\prime}_{4}$$P_{4}$$\Lambda_{6}^{\prime}$$\Lambda_{6}$$\Lambda_{5}^{\prime}$$\Lambda_{5}$$P^{\prime}_{5}$$P_{5}$$P_{6}^{\prime}$$P_{6}$$\left|\frac{x=x}{\alpha|x}\right|=1$$\left|\frac{x=x}{\alpha-1|x}\right|=1$$\left|\frac{c^{\prime}u|x}{x=0}\right|=1$$\left|\frac{cu^{\prime}|x}{x=0}\right|=1$$\left|\frac{xu=0}{c^{\prime}|x}\right|=1$$\left|\frac{xu^{\prime}=0}{c|x}\right|=1$$\left|\frac{x(\beta-1)=0}{x=0}\right|=1$$\left|\frac{x(\beta^{\prime}-1)=0}{x=0}\right|=1$$\left|\frac{x\beta=0}{x=0}\right|=1$$\left|\frac{x\beta^{\prime}=0}{x=0}\right|=1$$\left|\frac{us|x}{x=0}\right|=1$$\left|\frac{u^{\prime}s^{\prime}|x}{x=0}\right|=1$$\left|\frac{xs=0}{u|x}\right|=1$$\left|\frac{xs^{\prime}=0}{u^{\prime}|x}\right|=1$$\left|\frac{x\delta=0}{x=0}\right|=1$$\left|\frac{x\delta^{\prime}=0}{x=0}\right|=1$$\left|\frac{x(\delta-1)=0}{x=0}\right|=1$$\left|\frac{x(\delta^{\prime}-1)=0}{x=0}\right|=1$$\left|\frac{xs=0}{c^{\prime}u|x}\right|=1$$\left|\frac{xs^{\prime}=0}{cu^{\prime}|x}\right|=1$$\left|\frac{xb=0}{c^{\prime}u|x}\right|=1$$\left|\frac{xb^{\prime}=0}{cu^{\prime}|x}\right|=1$$\left|\frac{c^{\prime}bu|x}{x=0}\right|=1$$\left|\frac{cb^{\prime}u^{\prime}|x}{x=0}\right|=1$$\left|\frac{cu^{\prime}s^{\prime}|x}{x=0}\right|=1$$\left|\frac{c^{\prime}us|x}{x=0}\right|=1$$\left|\frac{\lambda
s|x}{x=0}\right|=1$$\left|\frac{\lambda^{\prime}s^{\prime}|x}{x=0}\right|=1$$\left|\frac{x\lambda=0}{s|x}\right|=1$$\left|\frac{x\lambda^{\prime}=0}{s^{\prime}|x}\right|=1$$\left|\frac{b\mu|x}{x=0}\right|=1$$\left|\frac{b^{\prime}\mu^{\prime}|x}{x=0}\right|=1$$\left|\frac{x\mu=0}{b|x}\right|=1$$\left|\frac{x\mu^{\prime}=0}{b^{\prime}|x}\right|=1$Figure
1

######  Lemma 5.9.

Let $R$ be an arithmetical ring and let $b,c,b^{\prime},c^{\prime}\in R$. Let
$\alpha,u,u^{\prime},\allowbreak\beta,\beta^{\prime},s,\allowbreak
s^{\prime},\allowbreak
r\allowbreak,r^{\prime},\allowbreak\delta,\delta^{\prime},\lambda,\lambda^{\prime},\mu,\mu^{\prime}\in
R$ be such that

$\begin{array}[]{ccccccccccccccc}&&&&c\alpha&\\!\\!\\!\\!=\\!\\!\\!\\!&c^{\prime}u,&&c^{\prime}(\alpha-1)&\\!\\!\\!\\!=\\!\\!\\!\\!&cu^{\prime}&&&&\\\
u\beta&\\!\\!\\!\\!=\\!\\!\\!\\!&b^{\prime}r,&&b^{\prime}(\beta-1)&\\!\\!\\!\\!=\\!\\!\\!\\!&us,&&u^{\prime}\beta^{\prime}&\\!\\!\\!\\!=\\!\\!\\!\\!&br^{\prime},&&b(\beta^{\prime}-1)&\\!\\!\\!\\!=\\!\\!\\!\\!&u^{\prime}s^{\prime}\\\
b\delta&\\!\\!\\!\\!=\\!\\!\\!\\!&s\lambda,&&s(\delta-1)&\\!\\!\\!\\!=\\!\\!\\!\\!&b\mu,&&b\delta^{\prime}&\\!\\!\\!\\!=\\!\\!\\!\\!&s^{\prime}\lambda^{\prime},&&s^{\prime}(\delta^{\prime}-1)&\\!\\!\\!\\!=\\!\\!\\!\\!&b^{\prime}\mu^{\prime}.\end{array}$

Define the sentences $\Lambda_{i}$ and $\Lambda_{i}^{\prime}$ for $1\leq i\leq
6$ and $P_{i}$ and $P_{i}^{\prime}$ for $4\leq i\leq 6$ to be the conjunction
of sentences labeling the edges in the path from the root of the tree in
Figure 1 to the leaf of the tree with that sentence as label.

Every $R$-module is elementary equivalent to an $R$-module of the form

$(\bigoplus_{i=1}^{6}M_{i}\oplus\bigoplus_{i=4}^{6}N_{i})\oplus(\bigoplus_{i=1}^{6}M_{i}^{\prime}\oplus\bigoplus_{i=4}^{6}N_{i}^{\prime})$

where $M_{i}\models\Lambda_{i}$ and
$M_{i}^{\prime}\models\Lambda_{i}^{\prime}$ for $1\leq i\leq 6$ and
$N_{i}\models P_{i}$ and $N_{i}^{\prime}\models P_{i}^{\prime}$ for $4\leq
i\leq 6$.

Moreover, for all $M\in\textnormal{Mod}\text{-}R$,

  1. (i)

$M\models\Lambda_{1}$ implies $c\in\textnormal{ann}_{R}M$ and hence
$\left|\nicefrac{{xb=0}}{{c|x}}(M)\right|=\left|\nicefrac{{xb=0}}{{x=0}}(M)\right|$,

  2. (ii)

$M\models\Lambda_{2}$ implies
$\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}(M)\right|=1$,

  3. (iii)

$M\models\Lambda_{3}$ implies $b^{\prime}\in\textnormal{ann}_{R}M$ and hence
$\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}(M)\right|=\left|\nicefrac{{x=x}}{{c^{\prime}|x}}(M)\right|$,

  4. (iv)

$M\models\Lambda_{4}$ implies
$\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}(M)\right|=1$,

  5. (v)

$M\models\Lambda_{5}$ implies $b\in\textnormal{ann}_{R}M$ and hence
$\left|\nicefrac{{xb=0}}{{c|x}}(M)\right|=\left|\nicefrac{{x=x}}{{c|x}}(M)\right|$,

  6. (vi)

$M\models\Lambda_{6}$ implies

$\left|\nicefrac{{xb=0}}{{c|x}}(M)\right|=\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}(M)\right|\cdot\left|\nicefrac{{x\lambda=0}}{{x=0}}(M)\right|,$

  7. (vii)

$M\models P_{4}$ implies $\left|\nicefrac{{xb=0}}{{c|x}}(M)\right|=1,$

  8. (viii)

$M\models P_{5}$ implies $b^{\prime}\in\textnormal{ann}_{R}M$ and hence
$\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}(M)\right|=\left|\nicefrac{{x=x}}{{c^{\prime}|x}}(M)\right|,$
and

  9. (ix)

$M\models P_{6}$ implies

$\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}(M)\right|=\left|\nicefrac{{xb=0}}{{c|x}}(M)\right|\cdot\left|\nicefrac{{x\mu=0}}{{x=0}}(M)\right|.$

Similarly, the symmetry of figure 1, gives 9 conditions for
$\Lambda_{i}^{\prime}$ and $P_{i}^{\prime}$, where $c,b$ and
$c^{\prime},b^{\prime}$ are interchanged and $\lambda,\mu$ are replaced by
$\lambda^{\prime},\mu^{\prime}$, respectively.

###### Proof.

There are two edges coming out of each node of the tree in Figure $1$. In each
instance the two edges are either

  1. (1)

$\left|\nicefrac{{x=x}}{{\gamma|x}}\right|=1$ and
$\left|\nicefrac{{x=x}}{{(\gamma-1)|x}}\right|=1$ for some $\gamma\in R$,

  2. (2)

$\left|\nicefrac{{x\gamma=0}}{{x=0}}\right|=1$ and
$\left|\nicefrac{{x(\gamma-1)=0}}{{x=0}}\right|=1$ for some $\gamma\in R$, or

  3. (3)

$\left|\nicefrac{{ab|x}}{{x=0}}\right|=1$ and
$\left|\nicefrac{{xa=0}}{{b|x}}\right|=1$.

By 2.9, in each $(1),(2)$ and $(3)$, for all modules
$M\in\textnormal{Mod}\text{-}R$, there exist $M_{1}$ satisfying the first
sentence and $M_{2}$ satisfying the second sentence such that $M\cong
M_{1}\oplus M_{2}$. The first claim follows from this fact.

For any $M\in\textnormal{Mod}\text{-}R$, $\alpha\notin\textnormal{Div}M$
implies $c|x$ is equivalent to $c^{\prime}u|x$ in $M$ because
$c\alpha=c^{\prime}u$.

$(i)$ Suppose $M\models\Lambda_{1}$. Since
$\left|\nicefrac{{c^{\prime}u|x}}{{x=0}}(M)\right|=1$, $Mc=Mc^{\prime}u=0$. So
$c\in\textnormal{ann}_{R}M$.

$(ii)$ Suppose $M\models\Lambda_{2}$. Then $\beta\notin\textnormal{Ass}M$ and
so, since $u\beta=b^{\prime}r$, $xb^{\prime}r=0$ is equivalent to $xu=0$ in
$M$. Since $xu=0\leq_{M}c^{\prime}|x$, we conclude

$xb^{\prime}=0\leq_{M}xb^{\prime}r=0\leq_{M}xu=0\leq_{M}c^{\prime}|x.$

$(iii)$ Suppose $M\models\Lambda_{3}$. Then $\beta-1\notin\textnormal{Ass}M$
and so, since $b^{\prime}(\beta-1)=us$, $xb^{\prime}=0$ is equivalent to
$xus=0$ in $M$. Since $\left|\nicefrac{{us|x}}{{x=0}}(M)\right|=1$,
$us\in\textnormal{ann}_{R}M$ and hence $b^{\prime}\in\textnormal{ann}_{R}M$.

Claim: If
$M\models\left|\nicefrac{{x=x}}{{\alpha|x}}\right|=1\wedge\left|\nicefrac{{xu=0}}{{c^{\prime}|x}}\right|=1\wedge\left|\nicefrac{{x(\beta-1)=0}}{{x=0}}\right|=1\wedge\left|\nicefrac{{xs=0}}{{u|x}}\right|=1$
then
$\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}(M)\right|=\left|\nicefrac{{xs=0}}{{c^{\prime}u|x}}(M)\right|$.

First note that since $\beta-1\notin\textnormal{Ass}M$ and
$b^{\prime}(\beta-1)=us$, $xb^{\prime}=0$ is equivalent to $xus=0$ in $M$. We
show that
$\left|\nicefrac{{xus=0}}{{c^{\prime}|x}}(M)\right|=\left|\nicefrac{{xs=0}}{{c^{\prime}u|x}}(M)\right|$.

Consider the map $f:xus=0/x=0(M)\rightarrow xs=0/c^{\prime}u|x(M)$ defined by
$f(m):=mu+c^{\prime}u|x(M)$. Now $f$ is surjective since
$\left|\nicefrac{{xs=0}}{{u|x}}\right|=1$. Suppose
$f(m)=m^{\prime}c^{\prime}u$ for some $m^{\prime}\in M$. Then
$(m-m^{\prime}c)u=0$. Since
$\left|\nicefrac{{xu=0}}{{c^{\prime}|x}}\right|=1$, $m-m^{\prime}c\in
c^{\prime}|x(M)$ and hence $m\in c^{\prime}|x(M)$. Therefore $\ker
f=c^{\prime}|x(M)$. So we have proved the claim.

We now prove the statements about modules satisfying
$\Lambda_{4},\Lambda_{5},\Lambda_{6}$. The statements for modules satisfying
$P_{4},P_{5}$ and $P_{6}$ follow similarly.

$(iv)$ Suppose $M\models\Lambda_{4}$. Then
$\left|\nicefrac{{xs=0}}{{c^{\prime}u|x}}(M)\right|=1$ and by the claim
$\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}(M)\right|=\left|\nicefrac{{xs=0}}{{c^{\prime}u|x}}(M)\right|$.

$(v)$ Suppose $M\models\Lambda_{5}$. Since $\delta\notin\textnormal{Ass}M$,
$xb=0$ is equivalent to $xs\lambda=0$ in $M$. Since
$\left|\nicefrac{{s\lambda|x}}{{x=0}}(M)\right|=1$,
$s\lambda\in\textnormal{ann}_{R}M$ and hence $b\in\textnormal{ann}_{R}M$.

$(vi)$ Suppose $M\models\Lambda_{6}$. Since $\delta\notin\textnormal{Ass}M$,
$xb=0$ is equivalent to $xs\lambda=0$ in $M$. Since
$xs=0\geq_{M}c^{\prime}u|x$,

$\left|\nicefrac{{xb=0}}{{c|x}}(M)\right|=\left|\nicefrac{{xs\lambda=0}}{{c^{\prime}u|x}}(M)\right|=\left|\nicefrac{{xs\lambda=0}}{{xs=0}}(M)\right|\cdot\left|\nicefrac{{xs=0}}{{c^{\prime}u|x}}(M)\right|.$

By 5.7,
$\left|\nicefrac{{xs\lambda=0}}{{xs=0}}(M)\right|=\left|\nicefrac{{s|x\wedge
x\lambda=0}}{{x=0}}(M)\right|$. So, since
$\left|\nicefrac{{x\lambda=0}}{{s|x}}\right|=1$,

$\left|\nicefrac{{xb=0}}{{c|x}}\left(M\right)\right|=\left|\nicefrac{{xs\lambda=0}}{{xs=0}}\left(M\right)\right|\cdot\left|\nicefrac{{xs=0}}{{c^{\prime}u|x}}\left(M\right)\right|=\left|\nicefrac{{x\lambda=0}}{{x=0}}\left(M\right)\right|\cdot\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}\left(M\right)\right|.$

∎

######  Proposition 5.10.

There is an algorithm which, given $w\in W$ with $\mathrm{clx}_{2}(w)>1$,
outputs $\underline{w}\in\mathbb{W}$ such that
$\mathrm{clx}_{2}(\underline{w})<\mathrm{clx}_{2}(w)$,
$\mathrm{clx}_{1}(\underline{w})\leq\mathrm{clx}_{1}(w)$, and, $w\in V$ if and
only if $\underline{w}\in\mathbb{V}$.

###### Proof.

We start with a special case. Let $b,c,b^{\prime},c^{\prime}\in
R\backslash\\{0\\}$. Let
$P_{6},P^{\prime}_{6},\Lambda_{6},\Lambda^{\prime}_{6}$ be as in 5.9. Let
$\Sigma_{1}:=\left|c|x/x=0\right|=1$, $\Sigma_{2}:=\left|b|x/x=0\right|=1$,
$\Sigma_{3}:=\left|c^{\prime}|x/x=0\right|=1$,
$\Sigma_{4}:=\left|b^{\prime}|x/x=0\right|=1$,
$\Sigma_{5}:=\left|\nicefrac{{xb=0}}{{c|x}}\right|=1$,
$\Sigma_{6}:=\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}\right|=1$,
$\Sigma_{7}:=\Lambda_{6}$, $\Sigma_{8}:=P_{6}$,
$\Sigma_{9}:=\Lambda^{\prime}_{6}$ and $\Sigma_{10}:=P^{\prime}_{6}$.

Fix $1\leq i\leq 4$ or $7\leq i\leq 10$. Suppose $w$ is

$\left|\nicefrac{{xb=0}}{{c|x}}\right|\square
E\wedge\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}\right|\square^{\prime}E^{\prime}\wedge{\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Sigma_{i}\wedge\Xi.$

Case i=1: Let $w^{\prime}$ be

$\left|\nicefrac{{xb=0}}{{x=0}}\right|\square
E\wedge\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}\right|\square^{\prime}E^{\prime}\wedge{\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Sigma_{i}\wedge\Xi.$

Then $\mathrm{clx}_{1}w^{\prime}=\mathrm{clx}_{1}w$ and
$\mathrm{clx}_{2}w^{\prime}<\mathrm{clx}_{2}w$. Since $T_{R}\models
w\leftrightarrow w^{\prime}$, we get $w\in V$ if and only if $w^{\prime}\in
V$.

Case i=2,3,4: The same argument as for $i=1$ works.

Case i=7: By 5.9, if $M\models\Sigma_{7}=\Lambda_{6}$ then

$\left|\nicefrac{{xb=0}}{{c|x}}(M)\right|=\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}(M)\right|\cdot\left|\nicefrac{{x\lambda=0}}{{x=0}}(M)\right|.$

By 5.6, there is an algorithm which either returns $\Omega:=\bot$, in which
case

$T_{R}\models\lnot(\left|\nicefrac{{xb=0}}{{c|x}}\right|\square
E\wedge\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}\right|\square^{\prime}E^{\prime}),$

or, a set $\Omega\subseteq\mathbb{N}^{2}\times\\{=,\geq\\}^{2}$ such that

$\Sigma_{7}\wedge\left|\nicefrac{{xb=0}}{{c|x}}\right|\square
E\wedge|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}|\square^{\prime}E^{\prime}$

is equivalent, with respect to $T_{R}$, to

$\bigvee_{(D_{1},D_{2},\square_{1},\square_{2})\in\Omega}\Sigma_{7}\wedge\left|\nicefrac{{x\lambda=0}}{{x=0}}\right|\square_{1}D_{1}\wedge\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}\right|\square_{2}D_{2}.$

If $\Omega:=\\{\bot\\}$ then $w\in V$ if and only if $\bot\in\mathbb{V}$ and
by definition $\mathrm{clx}_{1}\bot\leq\mathrm{clx}_{1}w$ and
$\mathrm{clx}_{2}\bot<\mathrm{clx}_{2}w$. Otherwise,

$\left|\nicefrac{{xb=0}}{{c|x}}\right|\square
E\wedge\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}\right|\square^{\prime}E^{\prime}\wedge{\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Sigma_{7}\wedge\Xi$

is equivalent to

$\bigvee_{(D_{1},D_{2},\square_{1},\square_{2})\in\Omega}\left|\nicefrac{{x\lambda=0}}{{x=0}}\right|\square_{1}D_{1}\wedge\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}\right|\square_{2}D_{2}\wedge{\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Sigma_{7}\wedge\Xi.$

For each $(D_{1},D_{2},\square_{1},\square_{2})\in\Omega$, let

$w_{(D_{1},D_{2},\square_{1},\square_{2})}:=\left|\nicefrac{{x\lambda=0}}{{x=0}}\right|\square_{1}D_{1}\wedge\left|\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}\right|\square_{2}D_{2}\wedge{\raisebox{1.5pt}{$\chi$}}_{f,g}\wedge\Sigma_{7}\wedge\Xi.$

So $w\in V$ if and only if

$\bigsqcup_{(D_{1},D_{2},\square_{1},\square_{2})\in\Omega}w_{(D_{1},D_{2},\square_{1},\square_{2})}\in\mathbb{V}.$

For all $(D_{1},D_{2},\square_{1},\square_{2})\in\Omega$,
$\mathrm{clx}_{1}w_{(D_{1},D_{2},\square_{1},\square_{2})}=\mathrm{clx}_{1}w$
and
$\mathrm{clx}_{2}w_{(D_{1},D_{2},\square_{1},\square_{2})}<\mathrm{clx}_{2}w$.

Case i=8,9,10: The same argument as for $i=7$ works.

We now deal with the general case. Let

$w:=\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
X}\left|\nicefrac{{\varphi}}{{\psi}}\right|=f(\nicefrac{{\varphi}}{{\psi}})\wedge\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
Y}\left|\nicefrac{{\varphi}}{{\psi}}\right|\geq
g(\nicefrac{{\varphi}}{{\psi}})\wedge\Xi\in W$

where $X,Y$ are disjoint finite sets of pp-pairs of the form $d|x/x=0$ and
$xb=0/c|x$, $f:X\rightarrow\mathbb{N}_{2}$, $g:Y\rightarrow\mathbb{N}_{2}$ and
$\Xi$ is an auxiliary sentence.

Suppose that
$\nicefrac{{xb=0}}{{c|x}},\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}\in X\cup
Y$ are distinct pp-pairs. Let $\Omega\subseteq\Omega_{f,g,10}$ such that
$(\overline{f},\overline{g})\in\Omega$ if and only if
$\nicefrac{{xb=0}}{{c|x}}\in X_{5}$,
$\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}\in X_{6}$,
$f_{5}(\nicefrac{{xb=0}}{{c|x}})=1$, and
$f_{6}(\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}})=1$.

Then $w\in V$ if and only if

$\bigsqcup_{(\overline{f},\overline{g})\in\Omega}\bigsqcap_{i=1}^{10}\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
X}\left|\nicefrac{{\varphi}}{{\psi}}\right|=f_{i}(\nicefrac{{\varphi}}{{\psi}})\wedge\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
Y}\left|\nicefrac{{\varphi}}{{\psi}}\right|\geq
g_{i}(\nicefrac{{\varphi}}{{\psi}})\wedge\Sigma_{i}\wedge\Xi\in\mathbb{V}.$

For each $(\overline{f},\overline{g})\in\Omega$ and $1\leq i\leq 10$, let

$w_{i,\overline{f},\overline{g}}:=\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
X}\left|\nicefrac{{\varphi}}{{\psi}}\right|=f_{i}(\nicefrac{{\varphi}}{{\psi}})\wedge\bigwedge_{\nicefrac{{\varphi}}{{\psi}}\in
Y}\left|\nicefrac{{\varphi}}{{\psi}}\right|\geq
g_{i}(\nicefrac{{\varphi}}{{\psi}})\wedge\Sigma_{i}\wedge\Xi.$

By definition of $\Omega_{f,g,10}$, for each $1\leq i\leq 10$,
$\mathrm{clx}_{1}w_{i,\overline{f},\overline{g}}\leq\mathrm{clx}_{1}w$,
$\mathrm{clx}_{2}w_{i,\overline{f},\overline{g}}\leq clx_{2}w$.

By assumption $\nicefrac{{xb=0}}{{c|x}}\in X$ and
$f(\nicefrac{{xb=0}}{{c|x}})>1$ or $\nicefrac{{xb=0}}{{c|x}}\in Y$ and
$g(\nicefrac{{xb=0}}{{c|x}})>1$. So, since $\nicefrac{{xb=0}}{{c|x}}\in X_{5}$
and $f_{5}(\nicefrac{{xb=0}}{{c|x}})=1$, for each
$(\overline{f},\overline{g})\in\Omega_{f,g,10}$,
$\mathrm{clx}_{2}w_{5,\overline{f},\overline{g}}<\mathrm{clx}_{2}w$. Replacing
$\nicefrac{{xb=0}}{{c|x}}$ by $\nicefrac{{xb^{\prime}=0}}{{c^{\prime}|x}}$,
the same argument gives
$\mathrm{clx}_{2}w_{6,\overline{f},\overline{g}}<\mathrm{clx}_{2}w$.

If $1\leq i\leq 4$ or $7\leq i\leq 10$ then $w_{i,\overline{f},\overline{g}}$
is of the form of the special case considered at the beginning of the proof.
Thus we may replace each $w_{i,\overline{f},\overline{g}}$ by a lattice
combination of $w^{\prime}\in W$ such that
$\mathrm{clx}_{1}w^{\prime}\leq\mathrm{clx}_{1}w_{i,\overline{f},\overline{g}}$,
and, either
$\mathrm{clx}_{2}w^{\prime}<\mathrm{clx}_{2}w_{i,\overline{f},\overline{g}}$
or
$\mathrm{clx}_{2}w^{\prime}\leq\mathrm{clx}_{2}w_{i,\overline{f},\overline{g}}$.
∎

###### Proof of 5.2.

By 5.1, in order to show that $T_{R}$ is decidable, it is enough to show that
there exists an algorithm which given $w\in W$ answers whether $w\in V$ or
not. By assumption, the set of $w^{\prime}\in V$ with
$\mathrm{clx}_{1}w^{\prime}\leq 1$ and $\mathrm{clx}_{2}w^{\prime}\leq 1$ is
recursive. Thus the set of $\underline{w}\in\mathbb{V}$ with
$\mathrm{clx}_{1}\underline{w}\leq 1$ and $\mathrm{clx}_{2}\underline{w}\leq
1$ is recursive.

Since $\mathbb{N}_{0}$ is artinian as an order, iteratively applying 5.8 and
5.10, gives an algorithm which given $w\in W$ with either
$\mathrm{clx}_{1}w>1$ or $\mathrm{clx}_{2}w>1$ outputs
$\underline{w}\in\mathbb{W}$ such that
$\mathrm{clx}_{1}\underline{w},\mathrm{clx}_{2}\underline{w}\leq 1$, and,
$w\in V$ if and only if $\underline{w}\in\mathbb{V}$. ∎

##  6\. Uniserial modules with finite invariants sentences

Descriptions of the uniserial (and hence indecomposable pure-injective)
modules, $U$, over a valuation domain which have
$\nicefrac{{\varphi}}{{\psi}}(U)$ finite but non-zero for a given pp-pair
$\nicefrac{{\varphi}}{{\psi}}$ are given for valuation domains with dense
value groups in [PPT07] and for valuation domains with non-dense value groups
in [Gre15]. However, we need a uniform description that works for both
valuation domains with dense and non-dense value groups. This is done in
Lemmas 6.1, 6.2 and 6.3 and used in section 9 and 10. The rest of the section
is about these modules in preparation for sections 7, 8 and 10.

######  Lemma 6.1.

Let $V$ be a valuation domain. If $d\in V$ and $U$ is a uniserial $V$-module
such that $\nicefrac{{d|x}}{{x=0}}(U)=Ud$ is finite and non-zero then $U\cong
V/dI$ for some $I\lhd V$ and $Ud\cong V/I$.

###### Proof.

For any module $M$,
$\nicefrac{{x=x}}{{xd=0}}(M)\cong\nicefrac{{d|x}}{{x=0}}(M)$. Thus if
$\nicefrac{{d|x}}{{x=0}}(U)\cong\nicefrac{{x=x}}{{xd=0}}(U)$ is finite but not
equal to the zero module then, by 2.12, $U\cong V/J$ for some ideal $J\lhd V$.
Since $Ud\neq 0$, $d\notin J$ and therefore $dV\supseteq J$. So there exists
$I\lhd V$ such that $dI=J$. ∎

Note that in the assumptions of the second clause of the next lemma we are not
excluding that $I=V$ or consequently that $xb=0/c|x(I/bcV)=0$.

######  Lemma 6.2.

Let $V$ be a valuation domain and $b,c\in V\backslash\\{0\\}$. If $U$ is a
uniserial $V$-module such that $b,c\notin\text{ann}_{V}U$ and
$\nicefrac{{xb=0}}{{c|x}}(U)$ is finite but non-zero then there exists $I\lhd
V$ with $b,c\in I$ such that $U\equiv I/bcV$ and
$\nicefrac{{xb=0}}{{c|x}}(U)\cong V/I$.

Conversely, if $0\neq I\lhd V$ is an ideal and $b,c\in I\backslash\\{0\\}$
then $\nicefrac{{xb=0}}{{c|x}}(I/bcV)\cong V/I$.

###### Proof.

Let $Q$ be the field of fractions of $V$. By [Zie84, pg 168], for any non-zero
uniserial module $U$, there exist submodules $K\subsetneq J\subseteq Q$ such
that $U\equiv J/K$. Now $b,c\notin\text{ann}_{V}J/K$ imply $(K:b)\subsetneq J$
and $cJ\supsetneq K$ respectively. Therefore, since
$\nicefrac{{xb=0}}{{c|x}}(J/K)\neq 0$, $xb=0/c|x(J/K)=(K:b)/cJ\cong K/cbJ$.
Since $K/cbJ$ is a non-zero finite uniserial module, it has the form $V/I$ for
some proper ideal $I\lhd V$. Therefore $K=\lambda V$ for some $\lambda\in
Q\backslash\\{0\\}$ and $\lambda^{-1}cbJ=I$. Thus $J/K\cong I/bcV$ as
required.

Let $0\neq I\lhd V$ be an ideal and $b,c\in I\backslash\\{0\\}$. Then
$\nicefrac{{xb=0}}{{c|x}}(I/bcV)=cV/cI\cong V/I$. ∎

######  Lemma 6.3.

Let $V$ be a valuation domain and $c\in V$. If $U$ is a uniserial $V$-module
such that $\nicefrac{{x=x}}{{c|x}}(U)$ is finite but non-zero then $U\cong
V/K$ for some ideal $K\lhd R$. Moreover, if $\nicefrac{{x=x}}{{c|x}}(U)$ is
finite but non-zero then either $U\cong V/cI$ for some $I\lhd V$ and
$V/cV\cong\nicefrac{{x=x}}{{c|x}}(U)$, or, $c\in\textnormal{ann}_{R}U$ and
$U\cong\nicefrac{{x=x}}{{c|x}}(U)$.

###### Proof.

The first claim is a consequence of 2.12. If $c\in K$ then
$c\in\textnormal{ann}_{R}V/K$. If $c\notin K$ then $cV\supseteq K$ and hence
there exists $I\lhd V$ such that $K=cI$. ∎

We avoid dealing directly with uniserial $V$-modules $U$ such that
$\nicefrac{{xb=0}}{{x=0}}(U)$ is finite but non-zero by using duality.

###  6.1. $(\mathfrak{p},I)\models(r,a,\gamma,\delta)$

######  Definition 6.4.

Let $r,a,\gamma,\delta\in R$, $\mathfrak{p}\lhd R$ a prime ideal and $I\lhd
R_{\mathfrak{p}}$ an ideal. We write
$(\mathfrak{p},I)\models(r,a,\gamma,\delta)$ if $rR_{\mathfrak{p}}\supseteq
I$, $a\in I$, $\gamma\notin\mathfrak{p}$ and $\delta\notin I^{\\#}$.

The task of this subsection is to show that given an auxiliary sentence $\Xi$
and $\lambda\in R\backslash\\{0\\}$, we can compute
$(r_{i},r_{i}a_{i},\gamma_{i},\delta_{i})$ for $1\leq i\leq n$ such that for
any prime ideal $\mathfrak{p}\lhd R$ and ideal $I\lhd R_{\mathfrak{p}}$,
$R_{\mathfrak{p}}/\lambda I\models\Xi$ if and only if
$(\mathfrak{p},I)\models(r_{i},r_{i}a_{i},\gamma_{i},\delta_{i})$ for some
$1\leq i\leq n$. However, in 10.5, we will need the
$(r_{i},r_{i}a_{i},\gamma_{i},\delta_{i})$ that we compute to interact well
with the duality defined in 2.3.

######  Remark 6.5.

Let $r,a,\gamma,\delta,\alpha\in R$. For all prime ideals $\mathfrak{p}\lhd R$
and ideals $I\lhd R_{\mathfrak{p}}$,
$(\mathfrak{p},I)\models(r,a,\gamma,\delta)$ if and only if
$(\mathfrak{p},I)\models(r,a,\gamma\alpha,\delta\alpha)$ or
$(\mathfrak{p},I)\models(r,a,\gamma(\alpha-1),\delta(\alpha-1))$.

###### Proof.

This is true because for all prime ideals $\mathfrak{p}\lhd R$, either
$\alpha\notin\mathfrak{p}$ or $\alpha-1\notin\mathfrak{p}$. ∎

######  Lemma 6.6.

Let $R$ be a Prüfer domain and $b,c,d\in R$ with $b\neq 0$. Let
$\mathfrak{p}\lhd R$ be a prime ideal and $I\lhd R_{\mathfrak{p}}$ be an
ideal.

  1. (1)

Then $\left|xb=0/c|x(R_{\mathfrak{p}}/I)\right|=1$ if and only if $b\notin
I^{\\#}$, $c\notin\mathfrak{p}$, $bcR_{\mathfrak{p}}\supseteq I$ or $1\in I$.

  2. (2)

Then $\left|d|x/x=0(R_{\mathfrak{p}}/I)\right|=1$ if and only if $d\in I$.

###### Proof.

(1) For any ideal $I\lhd R_{\mathfrak{p}}$,
$\left|xb=0/c|x(R_{\mathfrak{p}}/I)\right|=1$ if and only if
$cR_{\mathfrak{p}}+I\supseteq(I:b)$. Since $R_{\mathfrak{p}}$ is a valuation
ring, $cR_{\mathfrak{p}}+I\supseteq(I:b)$ if and only if $I\supseteq(I:b)$ or
$cR_{\mathfrak{p}}\supseteq(I:b)$. So it is enough to note that
$I\supseteq(I:b)$ if and only if $b\notin I^{\\#}$ or $1\in I$, and,
$cR_{\mathfrak{p}}\supseteq(I:b)$ if and only if $bcR_{\mathfrak{p}}\supseteq
I$ or $c\notin\mathfrak{p}$.

(2) is obvious. ∎

######  Lemma 6.7.

Given
$(r,a,\gamma,\delta),(r^{\prime},a^{\prime},\gamma^{\prime},\delta^{\prime})\in
R^{4}$ we can compute $n\in\mathbb{N}$ and
$(r_{i},a_{i},\gamma_{i},\delta_{i})\in R^{4}$ for $1\leq i\leq n$ such that

$(\mathfrak{p},I)\models(r,a,\gamma,\delta)\text{ and
}(\mathfrak{p},I)\models(r^{\prime},a^{\prime},\gamma^{\prime},\delta^{\prime})$

if and only if

$(\mathfrak{p},I)\models(r_{i},a_{i},\gamma_{i},\delta_{i})$

for some $1\leq i\leq n$, and,

$(\mathfrak{p},I)\models(r,a,\delta,\gamma)\text{ and
}(\mathfrak{p},I)\models(r^{\prime},a^{\prime},\delta^{\prime},\gamma^{\prime})$

if and only if

$(\mathfrak{p},I)\models(r_{i},a_{i},\delta_{i},\gamma_{i})$

for some $1\leq i\leq n$.

###### Proof.

Let $\alpha,u_{1},u_{2},\beta,v_{1},v_{2}\in R$ be such that
$r\alpha=r^{\prime}u_{1}$, $r^{\prime}(\alpha-1)=ru_{2}$,
$a\beta=a^{\prime}v_{1}$ and $a^{\prime}(\beta-1)=av_{2}$. Then one verifies
easily that

$(\mathfrak{p},I)\models(r,a,\gamma,\delta)\text{ and
}(\mathfrak{p},I)\models(r^{\prime},a^{\prime},\gamma^{\prime},\delta^{\prime})$

if and only if
$(\mathfrak{p},I)\models(r,a^{\prime},\alpha\beta\gamma\gamma^{\prime},\alpha\beta\delta\delta^{\prime})$,
$(\mathfrak{p},I)\models(r,a,\alpha(\beta-1)\gamma\gamma^{\prime},\alpha(\beta-1)\delta\delta^{\prime})$,
$(\mathfrak{p},I)\models(r^{\prime},a^{\prime},(\alpha-1)\beta\gamma\gamma^{\prime},(\alpha-1)\beta\delta\delta^{\prime})$
or
$(\mathfrak{p},I)\models(r^{\prime},a,(\alpha-1)(\beta-1)\gamma\gamma^{\prime},(\alpha-1)(\beta-1)\delta\delta^{\prime})$.
∎

######  Lemma 6.8.

Given $(r,a,\gamma,\delta)\in R^{4}$ and $\lambda\in R\backslash\\{0\\}$, we
can compute $n\in\mathbb{N}$ and $(r_{j},a_{j},\gamma_{j},\delta_{j})$ for
$1\leq j\leq n$ such that, for all prime ideals $\mathfrak{p}\lhd R$ and
ideals $I\lhd R_{\mathfrak{p}}$,

  * •

$(\mathfrak{p},\lambda I)\models(r,a,\gamma,\delta)$ if and only if
$(\mathfrak{p},I)\models(r_{j},a_{j},\gamma_{j},\delta_{j})$ for some $1\leq
j\leq n$ and

  * •

$(\mathfrak{p},\lambda I)\models(r,a,\delta,\gamma)$ if and only if
$(\mathfrak{p},I)\models(r_{j},a_{j},\delta_{j},\gamma_{j})$ for some $1\leq
j\leq n$.

###### Proof.

Let $\alpha,u,v,\beta,u^{\prime},v^{\prime}\in R$ be such that
$r\alpha=\lambda u$, $\lambda(\alpha-1)=rv$, $a\beta=\lambda u^{\prime}$ and
$\lambda(\beta-1)=av^{\prime}$. By 6.5, $(\mathfrak{p},\lambda
I)\models(r,a,\gamma,\delta)$ if and only if $(\mathfrak{p},\lambda
I)\models(r,a,\alpha\beta\gamma,\alpha\beta\delta)$, $(\mathfrak{p},\lambda
I)\models(r,a,\alpha(\beta-1)\gamma,\alpha(\beta-1)\delta)$,
$(\mathfrak{p},\lambda
I)\models(r,a,(\alpha-1)\beta\gamma,(\alpha-1)\beta\delta)$ or
$(\mathfrak{p},\lambda
I)\models(r,a,(\alpha-1)(\beta-1)\gamma,(\alpha-1)(\beta-1)\delta)$.

It is straightforward to see that:

  * •

If $\alpha\notin\mathfrak{p}$ then $rR_{\mathfrak{p}}\supseteq\lambda I$ if
and only if $uR_{\mathfrak{p}}\supseteq I$.

  * •

If $\alpha-1\notin\mathfrak{p}$ then $rR_{\mathfrak{p}}\supseteq\lambda I$.

  * •

If $\beta\notin\mathfrak{p}$ then $a\in\lambda I$ if and only if
$u^{\prime}\in I$.

  * •

If $\beta-1\notin\mathfrak{p}$ then $a\in\lambda I$ if and only if $1\in I$
and $v^{\prime}\notin\mathfrak{p}$ (and hence $v^{\prime}\notin I^{\\#}$).

Recall that, since $\lambda\neq 0$, $(\lambda I)^{\\#}=I^{\\#}$. Therefore,
$(\mathfrak{p},\lambda I)\models(r,a,\gamma,\delta)$ if and only if
$(\mathfrak{p},I)\models(u,u^{\prime},\alpha\beta\gamma,\alpha\beta\delta)$,
$(\mathfrak{p},I)\models(u,1,\alpha(\beta-1)v^{\prime}\gamma,\alpha(\beta-1)v^{\prime}\delta)$,
$(\mathfrak{p},I)\models(1,u^{\prime},(\alpha-1)\beta\gamma,(\alpha-1)\beta\delta)$
or
$(\mathfrak{p},I)\models(1,1,(\alpha-1)(\beta-1)v^{\prime}\gamma,(\alpha-1)(\beta-1)v^{\prime}\delta)$.
∎

######  Lemma 6.9.

Given $(r,a,\gamma,\delta)\in R^{4}$, we can compute $n\in\mathbb{N}$ and
$(r_{j},r_{j}a_{j},\gamma_{j},\delta_{j})$ for $1\leq j\leq n$ such that for
all prime ideals $\mathfrak{p}\lhd R$ and ideals $I\lhd R_{\mathfrak{p}}$,

  * •

$(\mathfrak{p},I)\models(r,a,\gamma,\delta)$ if and only if
$(\mathfrak{p},I)\models(r_{j},r_{j}a_{j},\gamma_{j},\delta_{j})$ for some
$1\leq j\leq n$ and

  * •

$(\mathfrak{p},I)\models(r,a,\delta,\gamma)$ if and only if
$(\mathfrak{p},I)\models(r_{j},r_{j}a_{j},\delta_{j},\gamma_{j})$ for some
$1\leq j\leq n$.

###### Proof.

If $a=0$ then $(r,a,\gamma,\delta)=(r,r\cdot 0,\gamma,\delta)$ is already of
the required form. So suppose $a\neq 0$.

Let $\alpha,u,v\in R$ be such that $a\alpha=ru$ and $r(\alpha-1)=av$. By 6.5,
$(\mathfrak{p},I)\models(r,a,\gamma,\delta)$ if and only if
$(\mathfrak{p},I)\models(r,a,\gamma\alpha,\delta\alpha)$ or
$(\mathfrak{p},I)\models(r,a,\gamma(\alpha-1),\delta(\alpha-1))$. Since
$a\alpha=ru$, $(\mathfrak{p},I)\models(r,a,\gamma\alpha,\delta\alpha)$ if and
only if $(\mathfrak{p},I)\models(r,ru,\gamma\alpha,\delta\alpha)$. Since
$r(\alpha-1)=av$,
$(\mathfrak{p},I)\models(r,a,\gamma(\alpha-1),\delta(\alpha-1))$ if and only
if $(\mathfrak{p},I)\models(av,a,\gamma(\alpha-1),\delta(\alpha-1))$. Now,
since $a\neq 0$, $avR_{\mathfrak{p}}\supseteq I$ and $a\in I$ if and only if
$v\notin\mathfrak{p}$, $aR_{\mathfrak{p}}\supseteq I$ and $a\in I$. So
$(\mathfrak{p},I)\models(av,a,\gamma(\alpha-1),\delta(\alpha-1))$ if and only
if $(\mathfrak{p},I)\models(a,a,\gamma\alpha v,\delta\alpha v)$.