DECIDABILITY OF THE THEORY OF MODULES OVER COMMUTATIVE VALUATION DOMAINS

G. PUNINSKI, V. PUNINSKAYA, C. TOFFALORI

Abstract. We prove that, if V is an effectively given commutative valuation domain such that its value group is dense and archimedean, then the theory of all V -modules is decidable.

1. Introduction

A classical strategy to prove the decidability of the theory T_{R} of all modules over a given ring R is to ‘eliminate quantifiers’, that is, to translate uniformly any sentence σ in the language of R-modules into a simpler equivalent sentence σ′ without quantifiers or where quantifiers are as less as possible, such that checking the truth of σ′ in R-modules becomes almost trivial.

This is exactly the way Wanda Szmielew used to prove her capital result opening this line of research [8]: the theory of abelian groups (that is, ℤmodules) is decidable. A famous Baur–Monk theorem (see [4, Cor. 2.13]) gives a good push in a general case, over an arbitrary ring R: every sentence is equivalent in T_{R} to a boolean combination of ‘invariant’ sentences (which are ∀∃ sentences, so that we have an elimination of quantifiers down to ∀∃ level). Unfortunately the structure of invariant sentences can be extremely complicated, which often makes a further syntactical analysis incredibly hard.

A more modern and powerful way to prove decidability of the theory of all modules over a ring is to use the Ziegler spectrum of R, Zg_{R}, a topological space whose points are indecomposable pure-injective R-modules. A good account of this approach and an overview of existing results can be found in [4, Ch. 17] or unpublished M. Prest’s notes [5]. Although these ideas have been circulated for quite a while, there are a few examples where this approach was put to the full force. The problem is that to make it work we should collect a substantial amount of information about the Ziegler spectrum of R, both about points and topology. Even for relatively moderate rings this is a problem of scaring complexity.

2000 Mathematics Subject Classification. 03B25, 13L05, 13A18, 13C11.

Key words and phrases. Theory of modules, commutative valuation domain, decidability, Ziegler spectrum.

The first author is partially supported by the NSF grant no. 0501224. He also thanks University of Camerino for kind hospitality.

If V is a commutative valuation domain, a complete classification of points of Zg_{V} is known from [9], and a satisfactory description of the topology is also available (see for example [6]). Thus it seems reasonable to expect that a characterization of (countable) commutative valuation domains with a decidable theory of modules should not be a very hard problem. For instance, if V is finite, then it has a finite representation type, hence T_{V} is a decidable theory. It follows from Szmielew’s result [8] that, for every prime p, the theory of all modules over the localization ℤ_{(p)} (which is a commutative valuation domain) is decidable.

An easy generalization of this result (that can be also derived from [1]) is that the theory of all modules over an effectively given noetherian commutative valuation domain is decidable. Thus the answer is known for (effectively given) commutative valuation domains whose value group is isomorphic to the ordered group (ℤ, +, ≤) (that is, for discrete rank one commutative valuation domains).

In this paper we consider an opposite case: when the value group of a rank one commutative valuation domain is densely ordered (say, orderly isomorphic to the rationals). Additional difficulties we encounter in this case are that the Ziegler spectrum of V is uncountable, and even (see [7, Thm. 12.12]) there exists a super-decomposable pure-injective V -module.

We show that none of these appearing obstacles affects decidability. Namely, we prove that, if V is a commutative valuation domain with a densely ordered archimedean value group, and V is effectively given in a sense we are going to explain later, then the theory of all modules over V is decidable.

As it should be, the proof of this result relies on the Ziegler spectrum approach as it was outlined in [9] or [4]. We also have in mind (though suppress in proofs) a geometrical interpretation of positive-primitive types over commutative valuation domains as in [7, Ch. 12]. Thus to decide whether a given sentence holds true in the theory of all V -modules, we should answer a question about a configuration of rectangles and lines on the plane. If the value group of V is densely ordered and archimedean this approach provides us with a clear picture convertible (though with some technicalities) into a formal proof. Drawing diagrams backs most proofs of this paper, and we doubt that they could have been worked out or understood otherwise.

We separate our proof of decidability in two cases: when the residue field of V is infinite or finite. The proof in the infinite case is more conceptual and relies mostly on the usage of Ziegler topology. As it is quite common, the finite case is essentially more difficult, because a combinatorics of finite invariants comes in play. Luckily we show that, if the value group of V is dense, then finite invariants are rather rare, hence the proofs are still bearable.

An ideal answer we would expect in general case (that is, for arbitrary countable commutative valuation domains) is the following: the theory T_{V} of all V -modules is decidable if and only if some questions in the first order theory of V (as a ring) can be answered effectively. Indeed this is what happens in the dense archimedean case, as the condition ‘V effectively given’ just has this content. Anyhow we show that, if a value group of V is nonarchimedean, then some non first-order parts of the theory of V can be encoded in the (first order) theory of V -modules.

Thus the case, when the value group of V is not archimedean (or not dense), appears to be essentially more difficult and may require tremendous combinatorial efforts.

2. Valuation domains

All rings in this paper will be commutative rings with unity and all modules will be unitary (usually right) modules.

A ring V is said to be a valuation ring, if the lattice of ideals of V is a chain. This is the same as for every a, b ∈ V there exists c ∈ V such that either ac = b or bc = a. A valuation ring without zero divisors is called a valuation domain.

For instance, ℤ_{(p)}, the localization of ℤ at a prime ideal p ℤ, is a valuation domain. Note that ℤ_{(p)} ⊃ p ℤ_{(p)} ⊃ p^{2} ℤ_{(p)} ⊃ … ⊃ 0 is a complete list of ideals of ℤ_{(p)}, in particular this ring is noetherian.

Every valuation domain V is a local ring: the set of non-invertible elements of V forms a unique maximal ideal Jac(V), the Jacobson radical of V. We will consider only infinite valuation domains which are not fields, hence Jac(V) is always nonzero. The factor F = V/ Jac(V) is a field called a residue field of V. For instance, if V = ℤ_{(p)}, then Jac(V) = p ℤ_{(p)}, hence V/ Jac(V) ≅ ℤ/p ℤ is a finite field of p elements.

If V is a valuation domain, then Q = Q(V) will denote the field of quotients of V, and U = U(V) = V \ Jac(V) is the group of units of V. Clearly every element of Q \ V is of the form j^{−1} for some 0 ≠ j ∈ Jac(V). Let Γ = Γ(V) be a collection of all cosets qU, 0 ≠ q ∈ Q. Then (see [3, Ch. 1]) Γ is a linearly ordered abelian group called the value group of V. Namely, given 0 ≠ q, q′ ∈ Q, we define qU + q′U = qq′U and set qU ≤ q′U if and only if q^{−1}q′ ∈ V.

The map v : Q\{0} → Γ(V) given by v(q) = qU is called a valuation of Q (corresponding to V). This map is usually extended to a map Q → Γ(V)∪∞ by sending 0 to ∞. In particular, v(qq′) = v(q) + v(q′) and v(q + q′) ≥ min{v(q), v(q′)} for all q, q′ ∈ Q. Also, if a, b ∈ V, then v(a) ≤ v(b) if and only if b ∈ aV, that is, bV ⊆ aV. For more on valuations of fields and valuation domains see [3].

Recall that, by Krull’s theorem (see [3, Thm. 3.4]), for every linearly ordered abelian group Γ and every field F there exists a valuation domain V whose value group is isomorphic to Γ, and whose residue field is isomorphic to F.

The following is a particular case of Krull’s construction.

Example 2.1. (see [3, p. 12]) Let R = F [x_{q}, q ∈ ℚ] be the ring of polynomials over a field F. If 0 ≠ α ∈ F and q_{i} ∈ ℚ, we define v(αx_{q_{1}}^{k_{1}} · . . . · x_{q_{n}}^{k_{n}}) = k_{1}q_{1} + ⋯ + k_{n}q_{n} and v(∑ αx_{q_{1}}^{k_{1}} · . . . · x_{q_{n}}^{k_{n}}) = min v(αx_{q_{1}}^{k_{1}} · . . . · x_{q_{n}}^{k_{n}}). Then the set of fractions {f/g | f, g ∈ R and v(f) ≥ v(g)} is a valuation domain whose value group is ℚ and whose residue field is F.

We say that a linearly ordered abelian group (Γ, +, ≤) is archimedean if, for all positive a, b ∈ Γ, there exists a positive integer n such that na ≥ b. By Hölder’s theorem (see [3, Prop. 2.2]) Γ is archimedean if and only if it is isomorphic to an additive subgroup of the reals (ℝ, +, ≤). In this case either Γ is isomorphic to (ℤ, +, ≤), or Γ is dense, that is, for every a < b ∈ Γ there is c ∈ Γ such that a < c < b. For example, the rationals (ℚ, +, ≤) are a dense archimedean linearly ordered abelian group.

An ideal P of a valuation domain V is said to be prime, if ab ∈ P for a, b ∈ V implies a ∈ P or b ∈ P. For instance, {0} is a prime ideal of V so as Jac(V). For every prime ideal P ≠ Jac(V), the quotient V/P is an infinite valuation domain.

The following fact is a part of Hölder’s theorem.

Fact 2.2. Jac(V) is the only nonzero prime ideal of V if and only if Γ(V) is archimedean.

Thus we can ‘surround’ any ideal of V by two elements of V whose distance can be made arbitrarily small.

Corollary 2.3. Let V be a valuation domain with a dense archimedean value group. If I is a nonzero ideal of V and c ∈ Jac(V), then there are a, b ∈ V such that a ∉ I, b ∈ I and v(a^{−1}b) < v(c), that is, c ∈ a^{−1}b Jac(V).

Proof. Let P consist of elements r ∈ V such that dr ∈ I for some d ∈ V \ I. It is easily checked that P is an ideal of V and I ⊆ P. Moreover, P is a prime ideal. Indeed, if ab ∈ P, then d · ab ∈ I for some d ∉ I. Then either da ∈ I, hence a ∈ P, or da ∉ I, therefore b ∈ P.

Since Γ(V) is archimedean, Fact 2.2 implies that P = Jac(V). Since Γ(V) is dense, there is r ∈ Jac(V) such that v(r) < v(c). Now choose a ∈ V \ I, such that ar ∈ I and put b = ar. Clearly a and b work. □

3. Decidability. Preliminaries

Recall that a (countable) theory T is said to decidable, if there is an algorithm that decides, for any sentence φ, whether φ ∈ T or not. We will stick with this informal definition throughout the paper. A more rigorous definition is that the set of all theorems of T is recursive.

The following is a standard setup for decidability of the theory of all modules over a ring (see [4, Ch. 17]). We introduce it in the particular framework of a countable valuation domain V. In the sequel T_{V} will denote the first order theory of all V -modules (that is, the set of all first order sentences that are true in every V -module).

We say that a countable valuation domain is effectively given, if the elements of V can be listed (with repetitions)) as r_{0} = 0, r_{1} = 1, r_{2}, … such that the following holds.

1) There is an algorithm which, given a, b ∈ V, produces a + b, −a, and ab.

2) There is an algorithm that, given a, b ∈ V, decides whether a = b or not.

3) There is an algorithm that, given a ∈ V, decides whether a is a unit or not.

Note that (see [4, Sect. 17.1]) 1) shows that a standard system of axioms of T_{V} can be arranged into an effective list, that is, T_{V} is recursively enumerable. Then 2) and 3) are necessary to ensure the decidability of T_{V}. Indeed, if a, b ∈ V, then it is easily checked that T_{V} ⊧ ∀ x (xa = xb) if and only if a = b. Thus, a decision algorithm of T_{V}, when restricted to the sentences ∀ x (xa = xb) with a, b ∈ V, provides 2). Similarly 3) can be encoded in T_{V} by the sentence ∀ x (xa = 0 → x = 0).

For instance, V can be given as a factor ring of the ring of polynomials R = F [x_{1}, x_{2}, …] over a finite field F, that is, V ≅ R/I for some ideal I of R. In this case a standard enumeration of polynomials f_{0} = 0, f_{1} = 1, … gives an effective presentation of V, if the question f_{i} = f_{j} in V (that is, f_{i} − f_{j} ∈ I) can be decided effectively.

From now on V will be an effectively given valuation domain.

Remark 3.1. There is algorithm that, given a ∈ V, decides whether a is a unit, and if it is, produces the inverse a^{−1}.

Proof. The first part is just 3). If a is a unit, then due to 1) we make a list ar_{0}, ar_{1}, … and at each step we compare ar_{i} with the unity of V using 2). Since a is a unit, this process terminates on r_{i} such that ar_{i} = 1, and then r_{i} = a^{−1}. □

Remark 3.2. There is an algorithm which, given a, b ∈ V finds c ∈ V such that ac = b, or decides that such an element c does not exist.

Proof. We make two parallel lists: ar_{0}, ar_{1}, …; br_{0}, br_{1}, …, and at each step compare elements of the first list with b, and of the second list with a. Since V is a valuation domain, we will find r_{i} ∈ V such that either ar_{i} = b or br_{i} = a.

If ar_{i} = b we are done. Otherwise br_{i} = a. Using 3) we decide whether r_{i} is a unit. If it is, we will find r_{i}^{−1} using Remark 3.1, and then ar_{i}^{−1} = b. Otherwise r_{i} ∈ Jac(V), hence b ∉ aV. □

As a consequence, there is an algorithm which, given a, b in V, decides whether v(a) = v(b), or v(a) > v(b), or v(a) < v(b).

A positive-primitive formula (pp-formula) φ(x) is a formula ∃ ȳ(ȳA = xb̄), where ȳ = (y_{1}, …, y_{k}) is a set of (quantified) variables, A is a k × l matrix over V, and b̄ = (b_{1}, …, b_{l}) is a row of elements of V. We will abbreviate this formula as A | xb̄ (A divides xb̄).

Let M be a V -module and let m ∈ M. We say that m satisfies φ in M, and write M ⊧ φ(m), if there exists a tuple \overline{m} = (m_{1}, …, m_{k}) ∈ M such that \overline{m}A = mb̄. Then φ(M) = \{m ∈ M | M ⊧ φ(m)\} is a positive-primitive subgroup (pp-subgroup) of M. Moreover, since V is commutative, φ(M) is a submodule of M.

For instance, if a ∈ V, then a | x ≐ ∃ y (ya = x) is a divisibility formula, and (a | x)(M) = Ma. Also, if b ∈ V, then xb = 0 is an annihilator formula, and (xb = 0)(M) = ann(M)(b) = {m ∈ M | mb = 0}.

Given pp-formulae φ(x) and ψ(x), we say that φ implies ψ, φ → ψ if, for every module M, φ(M) ⊆ ψ(M). For instance, given a, a′ ∈ V, it is easily checked that a | x → a′ | x if and only if a ∈ a′V, that is, v(a′) ≤ v(a). Similarly xb = 0 → xb′ = 0 for b, b′ ∈ V if and only if b′ ∈ bV, that is, v(b) ≤ v(b′).

We say that pp-formulae φ(x) and ψ(x) are equivalent, written φ ↔ ψ, if φ(M) = ψ(M) for every module M. For instance, a | x ↔ a′ | x if and only if aV = a′V, that is, v(a) = v(a′). Similarly, xb = 0 ↔ xb′ = 0 if and only if bV = b′V, and hence, again, if and only if v(b) = v(b′). Also recall that the sum of two pp-formulae φ(x) and ψ(x) is defined as the formula (φ + ψ)(x) ≐ ∃ y (φ(y) ∧ ψ(x − y)). It is easily seen that φ + ψ can be expressed as a pp-formula.

Lemma 3.3. There exists an algorithm that, given a pp-formula φ(x) over V, produces a formula ∧_{i=1}^{n}c_{i} | x + xd_{i} = 0, c_{i}, d_{i} ∈ V, equivalent to φ.

Proof. Every matrix over a valuation domain can be diagonalized using elementary row and column operations. By Remark 3.2 we can execute these operations effectively.

Thus, if φ is A | xb̄, we will find invertible matrices U and W such that UAW is a diagonal matrix. Clearly φ is equivalent to UAW | xb̄W, that is, we may assume that A = diag(a_{1}, …, a_{n}) is a diagonal matrix. Then φ is equivalent to a conjunction of pp-formulae a_{i} | xd_{i}, a_{i}, d_{i} ∈ V. If d_{i} ∈ a_{i}V (and we can decide this effectively), then a_{i} | xd_{i} is a trivial formula, hence equivalent to the formula 1 | x. Otherwise (using Remark 3.2) we will find c_{i} ∈ V such that a_{i} = d_{i}c_{i}. Then a_{i} | xd_{i} is c_{i}d_{i} | xd_{i} which is equivalent to c_{i} | x + xd_{i} = 0. □

Corollary 3.4. Every pp-formula over V is effectively equivalent to a formula ∑_{i=1}^{n} a_{i} | x ∧ xb_{i} = 0, a_{i}, b_{i} ∈ V.

∑ refers here to sum of pp-formulae.

Proof. By Lemma 3.3 and elementary duality (see [4, Ch. 8]) which is clearly effective. □

4. The Ziegler spectrum

A module M is said to be pure-injective, if it is injective with respect to pure embeddings. Our main interest will be indecomposable pure-injective modules over a valuation domains V. It is known (see [9, p. 161]) that every indecomposable pure-injective V -module is isomorphic to the pure-injective envelope of a module A/B, where B ⊆ A are fractional ideals of V (that is, V -submodules of Q). We will use a somewhat different description of indecomposable pure-injective V -modules using pp-types.

A positive-primitive pp-type (pp-type) p over V is a maximal consistent set of pp-formulae and their negations. For instance, if m is an element of a module M, then the set {φ(x) | M ⊧ φ(m)} is a pp-type (of m in M), pp_{M}(m). For every pp-type p there exists a pure-injective module M and an element m ∈ M such that pp_{M}(m) = p and M is ‘minimal’ among all pure-injective modules realizing m (see [4, Ch. 4] for precise definitions). M is unique up to an isomorphism fixing m and called a pure-injective envelope of p, PE(p). A pp-type p is said to be indecomposable, if PE(p) is an indecomposable module.

Although the pure-injective envelope of a pp-type is uniquely determined, different pp-types may have isomorphic pure-injective envelopes (that is, different elements of an indecomposable pure-injective module may have different pp-types). Thus to classify indecomposable pure-injective V -modules we describe indecomposable pp-types, and an equivalence relation corresponding to the isomorphism of their pure-injective envelopes.

By Lemma 3.3, every pp-type is uniquely determined by the set of ppformulae a | x + xb = 0 ∈ p, a, b ∈ V. Moreover (see [7, Cor. 11.7]), p is indecomposable if and only if a | x + xb = 0 ∈ p implies a | x ∈ p or xb = 0 ∈ p. Thus indecomposable pp-types are uniquely determined by their divisibility and annihilator formulae. Namely, set I(p) = {b ∈ V | xb = 0 ∈ p} and J(p) = {a ∈ V such that a | x ∉ p}. If p is nonzero, then I = I(p) and J = J(p) are (proper) ideals of V, and p is uniquely determined by the pair (I, J). Moreover, for every pair (I, J) of ideals of V there exists a unique indecomposable pp-type p = p(I, J) such that I = I(p) and J = J(p). Let PE(I, J) denote the pure-injective envelope of p (hence PE(I, J) is an indecomposable pure-injective module).

The following fact states that two pairs of ideals of V lead to isomorphic indecomposable pure-injective modules if and only if they can be identified by a shift by an element of V.

Fact 4.1. (see [7, L. 11.1]) PE(I, J) ≅ PE(I′, J′) if and only if there exist r ∉ I′, s ∉ J′ such that either a) Ir = I′ and J = J′r, or b) I = I′s and Js = J′.

The following corollary is almost immediate.

Corollary 4.2. 1) If I = bV and J = cV, then PE(I, J) ≅ PE(I′, J′) if and only if I′ = b′V, J′ = c′V for some b′, c′ ∈ V such that v(bc) = v(b′c′).

2) If I = d Jac(V) and J = a Jac(V), then PE(I, J) ≅ PE(I′, J′) if and only if I′ = d′ Jac(V), J′ = a′ Jac(V) for some a′, d′ ∈ V such that v(a′d′) = v(ad).

Proof. 1) Suppose that I = bV and J = cV. If Ir = I′ and J = J′r for some r ∉ I′, then I′ = Ir = brV, hence take b′ = br. From J = cV we obtain J′r = cV. If r ∈ cV, then r = cr′ for some r′ ∈ V, hence J′cr′ = cV yields J′r′ = V, a contradiction. Thus c = rc′ for some c′ ∈ Jac(V), hence J′r = cV yields J′ = c′V. Also b′c′ = brc′ = bc, hence v(b′c′) = v(bc).

The proof in case b) and the converse is similar.

2) Suppose that I = d Jac(V), J = a Jac(V) and Ir = I′, J = J′r for some r ∉ I′. Then I′ = Ir = dr Jac(V), hence take d′ = dr. If r ∈ a Jac(V), then r = ar′ for some r′ ∈ Jac(V), hence J′ar′ = a Jac(V) implies J′r′ = Jac(V). From r′ ∈ Jac(V) it follows that j′r′ = r′ for some j′ ∈ J′, therefore j′ = 1 ∈ J′, a contradiction.

Thus we may assume that a = ra′ for some a′ ∈ V. Then J′r = a Jac(V) is J′r = ra′ Jac(V), hence a′ Jac(V) = J′. Now a′d′ = a′ · dr = a′r · d = ad yields v(a′d′) = v(ad).

The proof in case b) and the converse is similar. □

If K is an ideal of V and c ∈ V \K, one defines (K : c) = {d ∈ V | cd ∈ K}. Using this notation, a) in Fact 4.1 can be written as I = (I′ : r) and J = J′r; and b) as I = I′s and J = (J′ : s).

We will give the following ‘geometrical’ interpretation of indecomposable pp-types. Let Γ^{+} = Γ^{+}(V) be the nonnegative part of the value group Γ(V) of a valuation domain V. The elements of Γ^{+}(V) are cosets uQ, u ∈ V thus correspond to principal ideals uV of V. The smallest element of Γ^{+} corresponds to 1 · V = V and the largest element of Γ^{+} (∞) corresponds to 0 · V = 0. Thus we use elements of V to denote elements of Γ^{+}. We represent pp-formulae by points on the plane Γ^{+} × Γ^{+}. Namely, if a, b ∈ V, then we assign to the pp-formula a | x+xb = 0 the point (b, a) of this plane:

[figure: •; 0; x=0; •; xb=0; •; x=x; ∘; Γ^{+}; a; •; a|x+xb=0; •; x=x; 1; 1; ∘; Γ^{+}; b; ∘; 0]

For instance, the point (b, 0) corresponds to the formula 0 | x + xb = 0 which is equivalent to xb = 0. Thus, all annihilator formulae live at the upper side of the above square, and the divisibility formulas occupy its left side. There is a singularity in this representation: all points at the lower side and at the right side of the square represent the (trivial) formula x = x.

Every ideal I of V defines a cut in Γ^{+} in the obvious way: we take all elements from I in the upper part of the cut, and all elements not in I in the lower part of the cut. An indecomposable pp-type p = p(I, J) consists of pp-formulae a | x + xb = 0 such that b ∈ I or a ∉ J, that is, p consists of points (b, a) that are below or on the following one step ladder:

[figure: ⌣; J; ∘; (; I]

Each dashed line on this diagram is an ‘imaginary line’, that is, a cut on Γ^{+}. One can convert this lines into real ones, completing Γ by cuts, but we avoid these unnecessary complications. Still, if I = bR is a principal ideal of V, then the vertical line on the diagram is real (has an equation x = b). Thus p can be thought of as an imaginary point (at the junction of two dashed lines in the above diagram) of the plane. If both ideals I = bV and J = aV are principal, then (I, J) represents a real point (b, a). Therefore, due to Fact 4.1, the set of all pp-types realized in a given indecomposable pureinjective module can be considered as an (imaginary) line v(x)+v(y) = const on the plane (see [7, Ch. 12] for more on that):

[figure: J; ⌣; ∘; I; (]

The Ziegler spectrum of V, Zg_{V} is a topological space whose points are the (isomorphism classes of) indecomposable pure-injective V -modules, and a basis of open sets is given by (φ/ψ) = {M ∈ Zg_{V} | φ(M)/(φ∧ψ)(M) ≠ 0}, where φ(x) and ψ(x) are pp-formulae over V. If φ are ψ are (typographically) complicated, we will write (φ / ψ) instead of (φ/ψ). It is known (see [4, Thm. 4.66]) that with respect to this topology Zg_{V} is a compact space.

Corollary 4.3. Every (nonempty) basic open set (φ/ψ) in the Ziegler spectrum of a valuation domain V is a finite union of basic open sets (a | x∧xb = 0 / c | x + xd = 0), where a, b, c, d ∈ V, v(a) < v(c) and v(d) < v(b).

Proof. By Corollary 3.4, φ is equivalent to ∑_{i} φ_{i}, where φ_{i} ≐ a_{i} | x∧xb_{i} = 0, a_{i}, b_{i} ∈ V. Also, by Lemma 3.3, ψ is equivalent to ∧_{j}ψ_{j}, where ψ_{j} ≐ c_{j} | x + xd_{j} = 0, c_{j}, d_{j} ∈ V. It is easily checked that (φ/ψ) = ∪_{i,j}(φ_{i}/ψ_{j}).

It remains to notice that, if v(a) ≥ v(c), then a | x → c | x, hence (a | x ∧ xb = 0 / c | x + xd = 0) is a trivial pair. The same is true, if v(d) ≥ v(b), because xb = 0 → xd = 0 in this case. □

We will assign to the pair (a | x ∧ xb = 0 / c | x + xd = 0) the following rectangle on the plane Γ^{+} × Γ^{+}:

[figure: ∘; c; ∘; a; ∘; d; ∘; b]

The explanation for this picture is the following. Suppose that I, J are ideals of V such that d ∉ I, b ∈ I and a ∉ J, c ∈ J. Then clearly PE(I, J) ∈ (a | x ∧ xb = 0 / c | x + xd = 0). Indeed, by the definition of p = p(I, J), b ∈ I implies xb = 0 ∈ p and a ∉ J yields a | x ∈ p. Thus, a | x ∧ xb = 0 ∈ p.

On the other hand, d ∉ I implies xd = 0 ∉ p and c ∈ J yields c | x ∉ p, hence (since p is indecomposable — see a remark above) c | x + xd = 0 ∉ p. Thus, if m is an element of PE(I, J) that satisfies p, then m witnesses PE(I, J) ∈ (a | x ∧ xb = 0 / c | x + xd = 0). Geometrically, this is true, because the (imaginary) point (I, J) is within the rectangle:

[figure: ∘; c; ⌣; J; ∘; ∘; a; ∘; d; (; I; ∘; b]

Now we explain why two sides of the rectangle are dashed. Indeed, suppose that a point representing an indecomposable pp-type p = p(I, J) belongs to the left side of the rectangle, hence I = dV and a ∉ J, c ∈ J. Since xd = 0 ∈ p, the natural realization of p fails to open (a | x ∧ xb = 0 / c | x + xd = 0).

More generally, for any ideals I′, J′ of V, we have that PE(I′, J′) ∈ (a | x∧xb = 0 / c | x+xd = 0) if and only if the (imaginary) line corresponding to p(I′, J′) intersects the rectangle:

[figure: ∘; c; ⌣; J′; ∘; ∘; a; ∘; d; ∘; b; (; I′]

Now we convert this geometrical observation into a formal result.

Lemma 4.4. Let φ ≐ a | x∧xb = 0, ψ ≐ c | x+xd = 0, and let p′ = p(I′, J′). Then the following is equivalent:

1) PE(p′) ∈ (φ/ψ);

2) there are d′ ∉ I′, b′ ∈ I′ and a′ ∉ J′, c′ ∈ J′ such that v(a) + v(d) ≤ v(a′) + v(d′) and v(b′) + v(c′) ≤ v(b) + v(c).

Geometrically this means that we should approximate an imaginary line corresponding to p′ by two real lines from the above and from the below such that the first line separates p′ from the right upper corner of the rectangle, and the second line separates p′ from the left lower corner of the rectangle:

[figure: ∘; c; ∘; ∘; a; ∘; d; ∘; b; p′]

Proof. 1) ⇒ 2). There is an element m ∈ M = PE(I′, J′) such that M ⊧ φ(m) ∧ ¬ψ(m). Hence, if p = pp_{M}(m), then p = p(I, J), where d ∉ I, b ∈ I and a ∉ J, c ∈ J. By Fact 4.1, (I, J) is obtained from (I′, J′) by a shift by a certain element of V. Precisely, there are r ∉ I′, s ∉ J′ such that either a) I = (I′ : r) and J = J′r, or b) I = I′s and J = (J′ : s).

In case a) we have d ∉ (I′ : r), b ∈ (I′ : r) and a ∉ J′r, c ∈ J′r. Take d′ = dr ∉ I′, b′ = br ∈ I′, and c′ = cr^{−1} ∈ J′ (recall that r^{−1} is the inverse of r in Q). Put a′ = ar^{−1} ∉ J′ if ar^{−1} ∈ V, and a′ = 1 ∉ J′ otherwise. In any case v(a′) ≥ v(ar^{−1}). Then v(a′) + v(d′) ≥ v(ar^{−1}) + v(dr) = v(ar^{−1}dr) = v(ad) = v(a) + v(d) and v(b′) + v(c′) = v(brcr^{−1}) = v(b) + v(c).

In case b) we have d ∉ I′s, b ∈ I′s and a ∉ (J′ : s), c ∈ (J′ : s). Take b′ = bs^{−1} ∈ I′ and a′ = as ∉ J′, c′ = cs ∈ J′. Put d′ = ds^{−1} ∉ I′ if ds^{−1} ∈ V and d′ = 1 ∉ I′ otherwise. In any case v(d′) ≥ v(ds^{−1}). Then v(a′)+v(d′) ≥ v(as)+v(ds^{−1}) = v(asds^{−1}) = v(a)+v(d) and v(b′)+v(c′) = v(bs^{−1}cs) = v(b) + v(c).

2) ⇒ 1). By Corollary 2.3, there are d′ ∉ I′, b′ ∈ I′ and a′ ∉ J′, c′ ∈ J′ such that v(b′)−v(d′) ≤ v(b)−v(d) and v(c′)−v(a′) ≤ v(c)−v(a). Moreover, by the assumption (changing a′, b′, c′ and d′ if necessarily) we may assume that v(b′) + v(c′) ≤ v(b) + v(c) and v(a) + v(d) ≤ v(a′) + v(d′). This implies that

v(a) − v(a′), v(b′) − v(b) ≤ v(c) − v(c′), v(d′) − v(d)

and so the following system of inequalities

\{ \begin{matrix}v(b′) − v(b) ≤ z ≤ v(d′) − v(d) \\ v(a) − v(a′) ≤ z ≤ v(c) − v(c′) \end{matrix}

has a solution z in Γ. Choose r ∈ Q such that v(r) = z. Suppose first that z is nonnegative, hence r ∈ V. If r ∈ I′, then z > v(d′) (since d′ ∉ I′), and also z ≤ v(d′) − v(d), hence z − v(d′) ≤ −v(d). The left part of this inequality is positive, but the right part is not, a contradiction.

Thus r ∉ I′, and we prove that PE(I, J) ∈ (φ/ψ), where I = (I′ : r) and J = J′r. Since (by Fact 4.1), PE(I′, J′) ≅ PE(I, J), it would follow that PE(p′) ∈ (φ/ψ).

It suffices to check that d ∉ I, b ∈ I and a ∉ J, c ∈ J. Indeed, v(r) = z ≤ v(d′)−v(d) implies v(dr) ≤ v(d′). From d′ ∉ I′ it follows that dr ∉ I′, hence d ∉ I = (I′ : r). Similarly v(b′) − v(b) ≤ z = v(r) yields that v(b′) ≤ v(br). Since b′ ∈ I′, we conclude that br ∈ I′, hence b ∈ I = (I′ : r).

By similar arguments, v(a) − v(a′) ≤ z implies a ∉ J, and z ≤ v(c) − v(c′) yields c ∈ J.

If z is negative, then −z = −v(r) = v(r^{−1}) is positive, hence s = r^{−1} ∈ V. If s ∈ J′, then −v(r) = v(s) > v(a′), and also (from the above inequalities) v(a) − v(a′) ≤ v(r^{−1}), that is, v(a) ≤ v(a′) − v(s). Looking at the signs of both parts of this inequality we obtain a contradiction. Thus s ∉ J′.

Now as above it is not difficult to check that, if I = I′s and J = (J′ : s), then PE(I, J) ∈ (φ/ψ), hence PE(I′, J′) ≅ PE(I, J) is also in (φ/ψ). □

Now we are in a position to analyze an inclusion of two basic open sets (φ/ψ) ⊆ (φ_{1}/ψ_{1}), where φ ≐ a | x ∧ xb = 0, ψ ≐ c | x + xd = 0 and φ_{1} ≐ a_{1} | x ∧ xb_{1} = 0, ψ_{1} ≐ c_{1} | x + xd_{1} = 0. Geometrically that means that every line v(x) + v(y) = const crossing the rectangle (φ/ψ) also intersects the rectangle (φ_{1}/ψ_{1}):

[figure: ∘; c_{1}; ∘; a_{1}; ∘; c; ∘; a; ∘; d_{1}; ∘; b_{1}; ∘; d; ∘; b]

An instant look at this diagram suggests an answer: the main diagonal (from the left lower corner to the right upper one) of the rectangle (φ/ψ) should be covered by the main diagonal of the rectangle (φ_{1}/ψ_{1}), that is, v(a_{1}d_{1}) ≤ v(ad) and v(bc) ≤ v(b_{1}c_{1}).

Now we give a formal proof.

Proposition 4.5. Let φ ≐ a | x ∧ xb = 0, ψ ≐ c | x + xd = 0, and φ_{1} ≐ a_{1} | x ∧ xb_{1} = 0, ψ_{1} ≐ c_{1} | x + xd_{1} = 0. Then the following are equivalent:

1) (φ/ψ) ⊆ (φ_{1}/ψ_{1});

2) v(a_{1}) + v(d_{1}) ≤ v(a) + v(d) and v(b) + v(c) ≤ v(b_{1}) + v(c_{1}).

Proof. 1) ⇒ 2). First we prove that v(a_{1}) + v(d_{1}) ≤ v(a) + v(d).

Let I′ = d Jac(V) and J′ = a Jac(V) (thus p(I′, J′) represents a line that goes above the left lower corner of the rectangle (φ/ψ) as close as possible). Clearly PE(I′, J′) ∈ (φ/ψ), hence, by the assumption, PE(I′, J′) ∈ (φ_{1}/ψ_{1}). By Lemma 4.4, there are d′ ∉ I′ and a′ ∉ J′ such that v(a_{1})+v(d_{1}) ≤ v(a′)+ v(d′). But a′ ∉ J′ = a Jac(V) implies v(a′) ≤ v(a), and d′ ∉ I′ = d Jac(V) yields v(d′) ≤ v(d), hence v(a′) + v(d′) ≤ v(a) + v(d). Combining this with v(a_{1})+v(d_{1}) ≤ v(a′)+v(d′) we obtain v(a_{1})+v(d_{1}) ≤ v(a)+v(d), as desired.

Now we check that v(b) + v(c) ≤ v(b_{1}) + v(c_{1}). Indeed, take I′ = bV and J′ = cV (thus p(I′, J′) represents a line that goes through the upper right corner of the rectangle (φ/ψ)). Clearly PE(I′, J′) ∈ (φ/ψ), hence, by the assumption, PE(I′, J′) ∈ (φ_{1}/ψ_{1}). By Lemma 4.4, there are b′ ∈ I′ and c′ ∈ J′ such that v(b′) + v(c′) ≤ v(b_{1}) + v(c_{1}). From b′ ∈ I′ = bV it follows that v(b′) ≥ v(b), and c′ ∈ J′ = cV implies v(c′) ≥ v(c), hence v(b′) + v(c′) ≥ v(b) + v(c). Combining this with v(b′) + v(c′) ≤ v(b_{1}) + v(c_{1}) we obtain v(b) + v(c) ≤ v(b_{1}) + v(c_{1}).

2) ⇒ 1). Let PE(I′, J′) ∈ (φ/ψ). By Lemma 4.4, there are d′ ∉ I′, b′ ∈ I′ and a′ ∉ J′, c′ ∈ J′ such that v(a) + v(d) ≤ v(a′) + v(d′) and v(b′) + v(c′) ≤ v(b) + v(c). By the assumption, v(a_{1}) + v(d_{1}) ≤ v(a) + v(d) and v(b)+v(c) ≤ v(b_{1})+v(c_{1}). It follows that v(a_{1})+v(d_{1}) ≤ v(a′)+v(d′) and v(b′)+v(c′) ≤ v(b_{1})+v(c_{1}). By Lemma 4.4 again, PE(I′, J′) ∈ (φ_{1}/ψ_{1}). □

5. Inclusion

In this section we consider a question which is crucial for a proof of decidability: when (φ/ψ) ⊆ ∪_{i=1}^{n}(φ_{i}/ψ_{i}) for basic open sets in the Ziegler spectrum of V? We assume here that φ ≐ a | x ∧ xb = 0, ψ ≐ c | x + xd = 0 and φ_{i} ≐ a_{i} | x ∧ xb_{i} = 0, ψ_{i} ≐ c_{i} | x + xd_{i} = 0 for i = 1, …, n. Looking at the diagram below we can guess the answer: the main diagonal of the rectangle (φ/ψ) should be covered by the union of main diagonals of rectangles (φ_{i}/ψ_{i}), that is, [v(ad), v(bc)] ⊆ ∪_{i=1}^{n}[v(a_{i}d_{i}), v(b_{i}c_{i})], where [v(ad), v(bc)] refers to the interval {z ∈ Γ(V) | v(ad) ≤ z ≤ v(bc)}, and similarly for [v(a_{i}d_{i}, v(b_{i}c_{i}))].

[figure: φ_{1}/ψ_{1}; φ_{2}/ψ_{2}; φ/ψ]

In fact the answer is more subtle (mainly because some sides of the rectangles are dashed). But first we consider some examples. If V is an (uncountable!) valuation domain whose value group is (ℝ, +, ≤), then every ideal I of V is either principal or of the form r Jac(V), r ∈ V. Indeed, every ideal I of V corresponds to a filter (that is, upward closed subset) F of the linearly ordered set of nonnegative reals ℝ^{+}. If I is not principal, then F is not principal, that is, has no smallest element. Then the set ℝ^{+} \ F is bounded from above, hence has a largest element z (since ℝ^{+} is Dedekind complete). If r ∈ V is such that v(r) = z, then r ∉ I and I = r Jac(V).

On the other hand, if V is a valuation domain whose value group is (ℚ, +, ≤), then V has a non-principal ideal that is not of the form r Jac(V) for any r ∈ V. Indeed, take a filter F = \{q ∈ ℚ | q ≥ \sqrt{2}\}. Then F is nonprincipal, and the set ℚ^{+} \ F has no largest element.

Moreover, let I be an ideal of V corresponding to the filter {q ∈ ℚ | q ≥ \sqrt{2}\} and let J correspond to the filter \{q ∈ ℚ | q ≥ 2 − \sqrt{2}\}. Then for every d′ ∉ I, b′ ∈ I and a′ ∉ J, c′ ∈ J we have v(a′d′) < 2 < v(b′c′).

We need the following generalization of this example. The authors are indebted to a (anonymous) referee for pointing out the following lemma that simplifies the proof of the next corollary.

Lemma 5.1. Let Γ ⊆ ℝ be a countable ordered abelian group. Suppose that α, β, γ, δ, z ∈ Γ are such that α < γ, δ < β and α + δ < z < β + γ. Then there exists an element y ∈ ℝ \ Γ such that α < y < γ and δ < z − y < β.

Proof. Since the sum of open intervals (α, γ) and (δ, β) in ℝ is an open interval (α + δ, β + γ), there must be α_{1} ∈ (α, γ) and β_{1} ∈ (δ, β) such that α_{1} + β_{1} = z. If α_{1} ∉ Γ, we set y = α_{1} and we are done. Otherwise, we choose some ε ∉ Γ such that 0 < ε < μ = min{γ − α_{1}, β_{1} − δ}; this exists, since Γ is countable but the interval (0, μ) in ℝ is not. Then α_{1} + ε ∈ (α, γ), z − (α_{1} + ε) = β_{1} − ε ∈ (δ, β) and α = α_{1} + ε ∉ Γ. □

Corollary 5.2. Assume that Γ(V) is dense and archimedean. Let a, b, c, d ∈ V be such that v(d) < v(b) and v(a) < v(c), and let z ∈ Γ(V) be such that z ∈ (v(ad), v(bc)), that is, v(ad) < z < v(bc). Then there are ideals I, J of V such that d ∉ I, b ∈ I, a ∉ J, c ∈ J; and v(a′d′) < z < v(b′c′) for all d′ ∉ I, b′ ∈ I, a′ ∉ J, c′ ∈ J.

Proof. Take α = v(a), β = v(b), γ = v(c), δ = v(d) and z, and apply Lemma 5.1 to obtain y ∉ Γ. We observe that z − y ∉ Γ, and we set I = {r ∈ V | v(r) ≥ z − y} = {r ∈ V | v(r) > z − y} and J = {s ∈ V | v(s) ≥ y} = {s ∈ V | v(s) > y}. It follows that d ∉ I, b ∈ I and a ∉ J, c ∈ J. Further, if d′ ∉ I, b′ ∈ I and a′ ∉ J, c′ ∈ J, then v(d′) < z − y < v(b′) and v(a′) < y < v(c′) which yields v(a′d′) < z < v(b′c′). □

Now we are in a position to prove main result of this section.

Proposition 5.3. Let φ ≐ a | x ∧ xb = 0, ψ ≐ c | x + xd = 0 and let φ_{i} ≐ a_{i} | x ∧ xb_{i} = 0, ψ_{i} ≐ c_{i} | x + xd_{i} = 0, i = 1, …, n. Then the following are equivalent:

1) (φ/ψ) ⊆ ∪_{i=1}^{n}(φ_{1}/ψ_{i});

2) (v(ad), v(bc)) ⊆ ∪_{i=1}^{n}(v(a_{i}d_{i}), v(b_{i}c_{i}));

3) [v(ad), v(bc)] ⊆ ∪_{i=1}^{n}[v(a_{i}d_{i}), v(b_{i}c_{i})] and, if v(ad) < z < v(bc) for some z = v(a_{i}d_{i}) = v(b_{j}c_{j}), then there is k = 1, …, n such that v(a_{k}d_{k}) < z < v(b_{k}c_{k}).

Proof. 1) ⇒ 2). Suppose that v(ad) < z < v(bc) for some z ∈ Γ(V). By Corollary 5.2, there are ideals I, J such that d ∉ I, b ∈ I, a ∉ J, c ∈ J, and v(a′d′) < z < v(b′c′) for all d′ ∉ I, b′ ∈ I, a′ ∉ J, c′ ∈ J.

Clearly PE(I, J) ∈ (φ/ψ). By the assumption, PE(I, J) ∈ (φ_{i}/ψ_{i}) for some i. Then, by Lemma 4.4, there are d′ ∉ I, b′ ∈ I, a′ ∉ J, c′ ∈ J such that v(a_{i}d_{i}) ≤ v(a′d′) and v(b′c′) ≤ v(b_{i}c_{i}). From v(a′d′) < z < v(b′c′) we conclude that v(a_{i}d_{i}) < z < v(b_{i}c_{i}), hence z ∈ (v(a_{i}d_{i}), v(b_{i}c_{i})).

2) ⇒ 3) is obvious.

3) ⇒ 1). Let p be a pp-type such that PE(p) ∈ (φ/ψ) and we have to prove that PE(p) ∈ (φ_{k}/ψ_{k}) for some k. Clearly we may assume that p = p(I′, J′), where d ∉ I′, b ∈ I′ and a ∉ J′, c ∈ J′.

First suppose that there are d′ ∉ I′, b′ ∈ I′, a′ ∉ J′, c′ ∈ J′ such that v(a_{i}d_{i}) ≤ v(a′d′) and v(b′c′) ≤ v(b_{i}c_{i}) for some i. Then, by Lemma 4.4, PE(p) ∈ (φ_{i}/ψ_{i}). Otherwise we may assume that for every i one of the following holds.

a) v(a_{i}d_{i}) > v(a′d′) for all d′ ∉ I′, a′ ∉ J′, or

b) v(b′c′) > v(b_{i}c_{i}) for all b′ ∈ I′, c′ ∈ J′.

Let S ⊆ {1, …, n} consist of indices i such that a) holds, and let T consist of indices j satisfying b). By the assumption, S ∪ T = {1, …, n}. If S = ∅, then T = {1, …, n}. Since b ∈ I and c ∈ J, it follows that v(bc) > v(b_{i}c_{i}) > v(a_{i}d_{i}) for every i, hence v(bc) is not covered by the intervals [v(a_{i}d_{i}), v(b_{i}c_{i})], a contradiction. Thus, S is not empty, and by similar arguments T is not empty.

•  • v(b_{j}c_{j}) • v(a_{i}d_{i})  • • v(a′d′)  • v(b′c′)

If i ∈ S and j ∈ T, then v(a_{i}d_{i}) ≥ v(b_{j}c_{j}). Indeed, otherwise v(a_{i}d_{i}) < v(b_{j}c_{j}), and choose r ∈ Jac(V) such that v(r) = v(b_{j}c_{j}) − v(a_{i}d_{i}). Since Γ(V) is dense, there are s, t ∈ Jac(V) such that v(s) + v(t) = v(r). Now (using Corollary 2.3) choose d′ ∉ I′, b′ ∈ I′, a′ ∉ J′, c′ ∈ J′ such that v(b′) − v(d′) < v(s) and v(c′) − v(a′) < v(t). Then v(b_{j}c_{j}) < v(b′c′) (since j ∈ T) and v(a′d′) < v(a_{i}d_{i}) (since i ∈ S), which implies v(b_{j}c_{j}) − v(a_{i}d_{i}) < v(b′c′) − v(a′d′) < v(s) + v(t) = v(r), a contradiction.

Let z_{1} = max_{j} v(b_{j}c_{j}), j ∈ T and let z_{2} = min_{i} v(a_{i}d_{i}), i ∈ S. By what we have just proved, z_{1} ≤ z_{2}. If z_{1} < z_{2}, then there is a z ∈ [v(ad, v(bc))] such that z_{1} < z < z_{2}, hence z ∉ ∪_{k}[v(a_{k}d_{k}, v(b_{k}c_{k}))], a contradiction.

Indeed, otherwise v(a_{k}d_{k}) < z < v(b_{k}c_{k}). Then v(a_{k}d_{k}) < z_{2}, hence k ∉ S. Similarly v(b_{k}c_{k}) > z_{1} shows that k ∉ T, a contradiction.

Thus z_{1} = z_{2}, hence z_{1} = v(b_{j}c_{j}) = v(a_{i}d_{i}) for some j ∈ T and i ∈ S. By the assumption, there is k such that v(a_{k}d_{k}) < z_{1} < v(b_{k}c_{k}). By the definition of S and T, v(a′d′) < z_{1} < v(b′c′) for all d′ ∉ I′, b′ ∈ I′ and a′ ∉ J′, c′ ∈ J′. Since the value of v(b′c′) − v(a′d′) can be made arbitrary small, we may assume that v(a_{k}d_{k}) ≤ v(a′d′) and v(b′c′) ≤ v(b_{k}c_{k}). Then PE(p) ∈ (φ_{k}/ψ_{k}) by Lemma 4.4. □

6. Decidability. Infinite residue field.

In this section we show that Proposition 5.3 implies decidability of the theory T_{V} of all modules over a valuation domain V with a dense archimedean value group and an infinite residue field. The arguments we use are quite standard and can be found in [4, Sect. 17.3].

Let φ(x) and ψ(x) be pp-formulae and let n be a positive integer. Then there exists a first order sentence Inv(φ, ψ) ≥ n (called an invariant sentence) such that, for every module M, one has M ⊧ Inv(φ, ψ) ≥ n if and only if the factor φ(M)/(φ ∧ ψ)(M) has at least n elements. Then the sentence Inv(φ, ψ) = n, that is, Inv(φ, ψ) ≥ n ∧ ¬ (Inv(φ, ψ) ≥ n + 1), says that there are exactly n elements in the corresponding factor. Similarly Inv(φ, ψ) ≤ n ≐ ¬ (Inv(φ, ψ) ≥ n + 1) claims that the corresponding factor has at most n elements. To simplify notations, we will write Inv(M, φ, ψ) ≥ n instead of M ⊧ Inv(φ, ψ), and similarly for other boolean combinations of invariant sentences. For instance Inv(M, φ, ψ) = 1 if and only if φ(M)/(φ ∧ ψ)(M) is a zero module, that is, φ(M) ⊆ ψ(M). We also define Inv(M, φ, ψ) = ∞, if Inv(M, φ, ψ) ≥ n for every n, that is, if φ(M)/(φ ∧ ψ)(M) is an infinite group. Thus Inv(φ, ψ) = ∞ is an (infinite) conjunction of the sentences Inv(φ, ψ) ≥ n, n ≥ 1.

The importance of invariant sentences is backed by the following result.

Fact 6.1. (Baur-Monk theorem — see [4, Cor. 2.13]) Every first order sentence in the language of modules over a given ring is equivalent to a boolean combination of invariant sentences.

Now we prove the main result of this section.

Theorem 6.2. Let V be an effectively given valuation domain with an infinite residue field and such that the value group of V is dense and archimedean. Then the theory T_{V} of all modules over V is decidable.

Proof. As we have already mentioned, T is recursively axiomatized, that is, there is an effective list of first order sentences true in every V -module. Thus what we need is an effective list of first order sentences false in every V -module, equivalently (passing to negations) of the first order sentences true in some V -module. This is the same as the existence of an algorithm that, given a sentence σ in the language of V -modules, decides whether there is a module M satisfying σ. We describe this algorithm.

It is not difficult to see that Baur-Monk theorem is effective. Apply this theorem and replace σ by a Boolean combination of invariant sentences. Pulling disjunctions ahead, we represent σ as a disjunction of σ_{h}, where each σ_{h} is a conjunction of invariant sentences or their negations. Then ‘there exists M such that M ⊧ σ ≐ ∨_{h}σ_{h}’ is the same as ‘for some h there exists M_{h} such that M_{h} ⊧ σ_{h}’. Thus we may assume that σ is a conjunction of invariant sentences and their negations.

Here is the place to put in use that F is infinite (to simplify the proof). Indeed, since F is infinite, it is easily checked (see Lemma 7.5 ) that for all pp-formulas φ(x), ψ(x) and every V -module M, the factor φ(M)/(φ∧ψ)(M) is either zero or infinite. Thus all sentences Inv(φ, ψ) ≥ n for n ≥ 2 are equivalent (to Inv(φ, ψ) > 1). Therefore we may further assume that every conjunct of σ is either Inv(φ, ψ) > 1 or Inv(φ, ψ) = 1 for some pp-formulas φ and ψ.

By Corollary 3.4, we can (effectively) replace φ by an equivalent formula ∑_{i} φ_{i}, where φ_{i} ≐ a_{i} | x ∧ xb_{i} = 0, and (by Lemma 3.3) we can replace ψ by ∧_{j}ψ_{j}, where ψ_{j} ≐ ∧_{j}c_{j} | x + xd_{j} = 0. Clearly Inv(φ, ψ) > 1 is equivalent to ∨_{i,j} Inv(φ_{i}/ψ_{j}) > 1, therefore Inv(φ/ψ) = 1 is equivalent to ∧_{i,j} Inv(φ_{i}/ψ_{j}) = 1.

Thus, getting rid of disjunctions and separating conjunctions, we may assume that every conjunct of σ is of the form Inv(φ, ψ) > 1 or Inv(φ, ψ) = 1, where (φ/ψ) are basic open sets in the Ziegler spectrum of V (see Corollary 4.3).

Moreover we can suppose that there exists at most one pp-formula Inv(φ, ψ) > 1 among conjuncts of σ; otherwise, for every invariant sentence Inv(φ, ψ) > 1, look for a V -module satisfying it and all the sentences involving equality, then form the direct sum of the modules obtained in this way and get a module M as required. Thus we end up with the following question: given basic open sets (φ_{i}/ψ_{i}), i = 1, …, n and (φ/ψ) in the Ziegler spectrum of V, does there exists a V -module M such that Inv(M, φ_{i}, ψ_{i}) = 1 and Inv(M, φ, ψ) > 1?

But (see [4, Cor. 4.36]) every module is elementarily equivalent to a direct sum of indecomposable pure-injective modules. Thus (by obvious arguments) we may look for an indecomposable pure-injective M. In this framework our question boils down to the following: is it true that (φ/ψ) ⊆ ∪_{i=1}^{n}(φ_{i}/ψ_{i}) for basic open sets in the Ziegler spectrum of V? But Proposition 5.3 suggests the answer, and clearly the item 3) of this proposition can be verified effectively. □

A countable field F is said to be effectively given if F is listed as f_{0} = 0, f_{1} = 1, f_{2}, … such that all operations of F can be executed effectively, and we can effectively solve the word problem f_{i} = f_{j} for F. For instance, every finite field and the field of rationals can be effectively given, as well as their algebraic closures.

Corollary 6.3. Let V be a valuation domain as in Example 2.1 such that F is effectively given and infinite. Then the theory of V -modules is decidable.

Proof. Using an effective presentation of F, it is not difficult to obtain an effective presentation for V (since every element of V is a rational function, and we can deal with polynomials effectively). It remains to apply Theorem 6.2. □

7. Finite invariants

In this section we analyze finite invariants of (indecomposable pure-injective) modules. But first we need some preliminaries.

For every module M there exists a ‘minimal’ pure-injective module PE(M) containing M as a pure submodule. PE(M) is called a pure-injective envelope of M. By [4, Thm. 4.21] M is an elementary substructure of PE(M), in particular M is elementary equivalent to PE(M).

A module M is said to be uniserial, if the lattice of submodules of M is a chain. For instance, the field of quotients of a commutative valuation domain V, and V itself, are uniserial V -modules. Also, a vector space over a field is uniserial if and only if it is one-dimensional. Every submodule and every factor module of a uniserial module is uniserial. Fact 7.1. Every indecomposable pure-injective module over a commutative valuation domain is the pure-injective envelope of a uniserial module. Proof. By Ziegler’s analysis of modules over a commutative valuation domain [9, p. 161], every indecomposable pure-injective V -module is isomorphic to the pure-injective envelope of a module A/B, where B ⊆ A are V -submodules of Q, the field of quotients of V. But Q is a uniserial module, hence the same is true for A and A/B. □

However, it is not true that every indecomposable pure-injective module over a valuation domain is uniserial. What we can say is the following. Fact 7.2. [7, Cor. 11.5] If M is an indecomposable pure-injective module over a commutative valuation domain, then pp-subgroups of M form a chain, that is, if φ(x) and ψ(x) are pp-formulae, then either φ(M) ⊆ ψ(M) or ψ(M) ⊆ φ(M).

For instance, if φ(M) ⫅̸ ψ(M), then ψ(M) ⊂ φ(M), hence (φ ∧ ψ)(M) = ψ(M). We will freely use this fact to simplify notations in what follows. Another obvious consequence of this fact is the following corollary. Corollary 7.3. Let M be an indecomposable pure-injective module over a commutative valuation domain V. If φ ≐ ∑_{i} φ and ψ ≐ ∧_{j}ψ_{j} are ppformulae, then Inv(M, φ, ψ) = max_{i,j} Inv(M, φ_{i}, ψ_{j}).

We need one more fact about uniserial modules.

Fact 7.4. [2, Prop. 5.1] If M is a uniserial module over a commutative ring, then PE(M) is an indecomposable module.

Let M be a V -module and let φ(x), ψ(x) be pp-formulae. In the following definition for the sake of simplicity we assume that ψ → φ. If ψ does not imply φ, one should replace ψ by φ ∧ ψ first.

We say that (φ/ψ) is a minimal pair (in the theory of M), if ψ(M) ⊂ φ(M) and for every pp-formula θ(x), ψ(M) ⊆ θ(M) ⊆ φ(M) implies ψ(M) = θ(M) or θ(M) = φ(M).

For instance, if M = ℤ_{p^{2}} = ℤ/p^{2}ℤ considered as a module over ℤ_{(p)}, then (xp = 0/x = 0) defines the socle of M, hence this pair is minimal.

The next lemma shows that finite minimal pairs cannot occur, if the residue field of V is infinite.

Lemma 7.5. Let V be a valuation domain with the residue field F. Suppose that M is an indecomposable pure-injective V -module and (φ/ψ) is a minimal pair in the theory of M such that φ(M)/ψ(M) is finite. Then φ(M)/ψ(M) is a one-dimensional vector space over F, in particular F is finite.

Proof. Since V is commutative, a multiplication by any r ∈ V is an endomorphism of M. Let P consists of r ∈ V which act as non-automorphisms of M. By [9, Thm. 5.4], P is a prime ideal of V, and multiplying by r ∈ P one properly increases the pp-type of any nonzero element of M. Thus, if m ∈ φ(M) \ ψ(M) and r ∈ P, then mr ∈ ψ(M). Therefore P annihilates φ(M)/ψ(M), hence φ(M)/ψ(M) is a V/P -module (and V/P is a valuation domain).

Every element of V \P acts on M as an automorphism, hence φ(M)/ψ(M) is a vector space over Q(V/P), the quotient field of V/P. If P ≠ Jac(V), then V/P is infinite, hence φ(M)/ψ(M) is infinite, a contradiction. Thus P = Jac(V), F = V/ Jac(V) is a finite field, and φ(M)/ψ(M) is a vector space over F.

By Fact 7.1, M is isomorphic to the pure injective envelope PE(N) of a uniserial V -module N. Since N is an elementary submodule of M, φ(N)/ψ(N) is a vector space over F. But φ(N)/ψ(N) is a uniserial V - module, hence the dimension of this vector space is one. Since M is elementarily equivalent to N, and elementary equivalent modules have the same finite invariants, φ(M)/ψ(M) is also one-dimensional over F. □

The following corollary shows that over valuation domains with a dense valuation group finite invariants are rather rarity.

Corollary 7.6. Let V is a valuation domain with a dense value group and let φ(x), ψ(x) be pp-formulae over V. Let M be an indecomposable pureinjective V -module such that φ(M)/ψ(M) is finite. Then φ(M)/ψ(M) is a one-dimensional vector space over F, the residue field of V, hence (φ/ψ) is a minimal pair in the theory of M.

Proof. Since the value group of V is dense, Jac(V) = Jac(V)^{2}.

By Lemma 7.5, the result is true if φ/ψ is a minimal pair in the theory of M. Otherwise we may assume that ψ(M) ⊂ θ(M) ⊂ φ(M) for some ppformula θ. Arguing by induction on the length of φ(M)/ψ(M) we prove that φ(M) · Jac(V) ⊆ ψ(M). By the induction hypothesis, we may assume that φ(M)·Jac(V) ⊆ θ(M) and θ(M)·Jac(V) ⊆ ψ(M). But then φ(M)·Jac(V) = φ(M) · Jac^{2}(V) ⊆ ψ(M), as desired.

Thus φ(M)/ψ(M) is a vector space over F, and the proof can be completed as in Lemma 7.5. □

Now we decide what pairs of pp-formulae cut out finite invariants on indecomposable pure-injective modules.

Lemma 7.7. Let V be a valuation domain with a dense value group such that the residue field F of V is finite. Let (φ/ψ), where φ ≐ a | x ∧ xb = 0 and ψ ≐ c | x + xd = 0, be a basic open set in the Ziegler spectrum of V. Suppose that M = PE(I, J) is an indecomposable pure-injective V -module and m ∈ M realizes p = p(I, J). Then the following are equivalent:

1) m ∈ φ(M) \ ψ(M) and φ(M)/ψ(M) is finite;

2) m ∈ φ(M) \ ψ(M) and φ(M)/ψ(M) is a one-dimensional vector space over F;

3) either I = bV and J = cV, or I = d Jac(V) and J = a Jac(V).

Proof. 1) is equivalent to 2) by Corollary 7.6.

2) ⇒ 3). Suppose first that J ≠ Jac(V).

Choose j ∈ Jac(V) \ J . From j ∉ J we obtain j | x ∈ p, hence there exists m′ ∈ M such that m′j = m. If q = pp_{M}(m′) then (as it easily checked) q = p(I′, J′), where I′ = Ij and J′ = (J : j). Since Jac(V) kills all minimal pairs, we must have m′ ∉ φ(M) (otherwise m = m′j ∈ ψ(M), a contradiction). It follows that a | x ∧ xb = 0 ∉ q, hence either b ∉ I′ = Ij or a ∈ J′ = (J : j), that is, aj ∈ J. Since this is true for every j ∈ Jac(V) \ J (and b ∈ I, a ∉ J), we obtain that I = bV or J = a Jac(V).

Now suppose that I ≠ Jac(V).

Take any i ∈ Jac(V) \ I. Let m′ = mi and q = pp_{M}(m′). Then q = p(I′, J′), where I′ = (I : i) and J′ = Ji. Again, because Jac(V) kills (φ/ψ), one gets m′ = mi ∈ ψ(M), that is, c | x + xd = 0 ∈ q. Since q is indecomposable, it follows that c | x ∈ q or xd = 0 ∈ q, that is, c ∉ J′ = Ji or d ∈ I′ = (I : i), that is, di ∈ I. Because this is true for all i ∈ Jac(V) \ I (and d ∉ I, c ∈ J), we conclude that I = d Jac(V) or J = cV.

Thus, if I ≠ Jac(V) and J ≠ Jac(V) we got that I = bV or J = a Jac(V), and I = d Jac(V) or J = cV. Since Jac(V) = Jac(V)^{2}, all the ideals r Jac(V), 0 ≠ r ∈ V are not principal. Thus, if I = bV, then I ≠ d Jac(V), hence J = cV. Otherwise I ≠ bV, hence J = a Jac(V). Then J ≠ cV, therefore I = d Jac(V).

Suppose that J = Jac(V), hence a ∉ J is invertible. If I = Jac(V) we can take a = d = 1. Thus we may assume that I ≠ Jac(V), hence (see above) either I = d Jac(V) or J = cV. But J = Jac(V) = cV is not possible, hence I = d Jac(V) (and we take a = 1). Similarly, if I = Jac(V) (hence d is invertible), then we obtain J = a Jac(V).

3) ⇒ 2). Suppose that I = bV and J = cV. Observe that c ∈ Jac(V). Let N = Jac(V)/cbV, and let m denote the coset of c in N. Put p = pp_{N}(m). Since N is uniserial, by Fact 7.4 its pure-injective envelope is indecomposable. In particular, p is an indecomposable pp-type. Looking at the divisibility and the annihilator formulae valid on m in N, we see that p = p(I, J), in particular PE(N) ≅ M and m ∈ φ(M). If i ∈ Jac(V), then c divides mi in N, hence mi ∈ ψ(M). Also, if j ∈ Jac(V) \ J and m′ ∈ N is such that m′j = m, then m′b ≠ 0 in N, hence m′ ∉ φ(M). It follows that φ(N)/ψ(N) is a one-dimensional vector space over F (generated by m), hence the same is true for M ≅ PE(N).

Similarly, if I = d Jac(V) and J = a Jac(V), then the projection m of a in the quotient module N = V/ad Jac(V) realizes p = p(I, J). Then M ≅ PE(N) and φ(M)/ψ(M) is a one-dimensional vector space over F generated by m. □

Proposition 7.8. Let V be a valuation domain with a dense value group such that the residue field F of V is finite. Let (φ/ψ), where φ ≐ a | x∧xb = 0 and ψ ≐ c | x + xd = 0, be a basic open set in the Ziegler spectrum of V. Suppose that I′, J′ are ideals of V, p′ = p(I′, J′) and M = PE(p′). Then the following are equivalent:

1) φ(M)/ψ(M) is a finite module; 2) φ(M)/ψ(M) is a one-dimensional vector space over F;

3) either a) I′ = b′V, J′ = c′V and v(b′c′) = v(bc), or b) I′ = d′ Jac(V), J′ = a′ Jac(V) and v(a′d′) = v(ad).

Geometrical explanation for this proposition is the following. A pair (φ/ψ) cuts out a finite nonzero chunk of M if and only if the line corresponding to p(I′, J′) either crosses the rectangle (φ/ψ) at precisely one point, its upper right corner (and so it is a real line), or separates the left lower corner from the rest of the rectangle (and so it is an imaginary line):

[figure: ∘; c; •; ∘; a; ∘; ∘; d; ∘; b]

Proof. 1) is equivalent to 2) by Corollary 7.6.

2) ⇒ 3). Choose m ∈ φ(M)\ψ(M) and let p = pp_{M}(m), hence p = p(I, J) for some ideals I, J of V. By Lemma 7.7, we obtain that either a) I = bV and J = cV, or b) I = d Jac(V) and J = a Jac(V). Since M = PE(p′) ≅ PE(p), the result follows by Corollary 4.2.

3) ⇒ 2). By Corollary 4.2 again, PE(I′, J′) ≅ PE(I, J) = M. It remains to apply Lemma 7.7. □

In the following lemma we calculate invariants of an indecomposable pureinjective module given by principal ideals. As we will see there are only 3 possibilities for those: 1, |F | and ∞.

Lemma 7.9. Let V be a valuation domain with a dense value group such that the residue field F of V consists of p elements. Let (φ/ψ), where φ ≐ a | x ∧ xb = 0 and ψ ≐ c | x + xd = 0, be a basic open set in the Ziegler spectrum of V. Let I′ = b′V, J′ = c′V be principal ideals of V, p′ = p(I′, J′) and M = PE(p′). Then the following holds.

1) Inv(M, φ, ψ) > 1 if and only if v(ad) < v(b′c′) ≤ v(bc).

2) Inv(M, φ, ψ) = n for some n ≥ 2 if and only if n = p and v(ad) < v(b′c′) = v(bc).

3) Inv(M, φ, ψ) = ∞ if and only if v(ad) < v(b′c′) < v(bc).

4) Otherwise Inv(M, φ, ψ) = 1.

Proof. 1) Suppose Inv(M, φ, ψ) > 1, equivalently M ∈ (φ/ψ). Then, by Lemma 4.4, there are d′′ ∉ I′, b′′ ∈ I′ and a′′ ∉ J′, c′′ ∈ J′ such that v(ad) ≤ v(a′′d′′) and v(b′′c′′) ≤ v(bc). Since b′′ ∈ I′ = b′V, then v(b′′) ≥ v(b′) and similarly v(c′′) ≥ v(c′). Thus v(b′c′) ≤ v(b′′c′′) ≤ v(bc).

From a′′ ∉ J′ = c′V it follows that v(a′′) < v(c′), and similarly v(d′′) < v(b′). Thus v(b′c′) > v(a′′d′′) ≥ v(ad), as desired.

The converse is an immediate consequence of Lemma 4.4.

2) Suppose that Inv(M, φ, ψ) = n for some n ≥ 2. In particular, Inv(M, φ, ψ) > 1, hence, by 1), v(ad) < v(b′c′) ≤ v(bc). Also, by Corollary 7.6, (φ/ψ) is a minimal pair in the theory of M and n = p. Apply Proposition 7.8 and conclude v(bc) = v(b′c′).

The converse is similar.

3) and 4) is a consequence of 1), 2) and Corollary 7.6. □

The following lemma is similar (so we omit the proof).

Lemma 7.10. Let V be a valuation domain with a dense value group such that the residue field F of V consists of p elements. Let (φ/ψ), where φ ≐ a | x∧xb = 0 and ψ ≐ c | x+xd = 0, be a basic open set in the Ziegler spectrum of V. Let I′ = d′ Jac(V), J′ = a′ Jac(V), p′ = p(I′, J′) and M = PE(p′). Then the following holds.

1) Inv(M, φ, ψ) > 1 if and only if v(ad) ≤ v(a′d′) < v(bc).

2) Inv(M, φ, ψ) = n for some n ≥ 2 if and only if n = p and v(ad) = v(a′d′) < v(bc).

3) Inv(M, φ, ψ) = ∞ if and only if v(ad) < v(a′d′) < v(bc).

4) Otherwise Inv(M, φ, ψ) = 1.

8. Decidability. Finite residue field

In this section we prove decidability of the theory of all modules over an effectively given valuation domain V with a dense archimedean value group and a finite residue field F. But first we clarify the notion of effectiveness in this particular case.

Suppose that the theory of all V -modules is decidable, and F is finite. Could we find the number of elements of F effectively? The answer is ‘yes’. Indeed, by Corollary 7.6, this number is exactly the integer n > 1 such that there exists a V -module M satisfying Inv(φ, ψ) = n for some pp-formulae φ and ψ. In fact (by Proposition 7.7), we can choose (any!) a, b, c, d ∈ V such that v(d) < v(b), v(a) < v(c) and set φ ≐ a | x ∧ xb = 0, ψ ≐ c | x + xd = 0. Now we proceed, starting from n = 2, answering the question: ‘Does there exists a module M such that Inv(φ, ψ, M) = n?’ (this is equivalent to check that a suitable first order sentence of the language of V -modules is in T_{V} – see a discussion in Section 6). The first ‘yes’ we get will determine n.

Thus, aiming to prove decidability of the theory T_{V} we are required to know the size of F in advance. So let F have exactly p elements. First we prove an auxiliary lemma.

Lemma 8.1. Let V be an effectively given valuation domain with a dense value group and such that the residue field F of V has p elements. Let I = bV, J = cV or I = d Jac(V), J = a Jac(V); p = p(I, J) and M = PE(p). Suppose that φ(x) and ψ(x) are pp-formulae. Then we can effectively calculate Inv(M, φ, ψ), and it is equal to 1, p or ∞.

Proof. Represent φ as ∑_{i} φ_{i}, where φ_{i} ≐ a_{i} | x ∧ xb_{i} = 0 and ψ as ∧_{j}ψ_{j}, where ψ_{j} ≐ c_{j} | x + xd_{j} = 0. Lemmas 7.9 and 7.10 give an effective way to calculate each Inv(M, φ_{i}, ψ_{j}), which is 1, p or ∞. Now, by Corollary 7.3, Inv(M, φ, ψ) = max_{i,j} Inv(M, φ_{i}, ψ_{j}), and the result follows. □

Now we are in a position to prove decidability.

Theorem 8.2. Let V be an effectively given valuation domain with a dense archimedean value group and such that the residue field F of V consists of p elements. Then the theory T_{V} of all V -modules is decidable.

Proof. As in the proof of Theorem 6.2 we may assume that we are given a first order sentence σ which is a conjunction of invariant sentences and their negations, and we should (uniformly) decide if there exists a V -module M satisfying σ.

Without loss of generality we can assume that each conjunct of σ is of one of the following forms:

1) Inv(φ_{1}, ψ_{1}) ≥ n_{1} for some n_{1} ≥ 2;

2) Inv(φ_{2}, ψ_{2}) = 1;

3) Inv(φ_{3}, ψ_{3}) = n_{3}, for some n_{3} ≥ 2.

It is also known, that, if such a module M exists, it can be found between finite direct sums of indecomposable pure-injective modules. So we are going to check on potential candidates for modules M of this form.

First assume that 3) is empty. Then proceed as in the proof of Theorem 6.2 with minor changes. Namely, by that proof we can effectively check the existence of a module M satisfying all sentences Inv(φ_{1}, ψ_{1}) > 1 as in 1), and all sentences in 2). If no such M exists, then σ has no models. Otherwise M^{k} for some (large enough) k will satisfy 1) and 2).

Thus we may assume that 3) is nonempty. Take a pair (φ_{3}/ψ_{3}) from this list. If there exists a module N such that Inv(N, φ_{3}, ψ_{3}) = n_{3}, then there exists an indecomposable pure-injective V -module M such that Inv(M, φ_{3}, ψ_{3}) > 1 is finite, hence equal to p. Moreover we can assume that N itself is a finite direct sum of indecomposable pure-injective modules with this property. In particular, if n_{3} is not a power of p, then σ cannot admit any model. Thus we may assume that n_{3} is a power of p. (In the same way, we may replace each n_{1} in 1) by the smallest power of p which is ≥ n_{1}, and assume that n_{1} itself is a power of p).

Now we decide whether an indecomposable pure-injective module M_{3} such that Inv(M_{3}, φ_{3}, ψ_{3}) = p exists and make a (finite) list of such modules.

Represent φ_{3} ≐ ∑_{l} φ_{3l}, where φ_{3l} ≐ a_{l} | x ∧ xb_{l} = 0 and ψ_{3} ≐ ∧_{k}ψ_{3k}, where ψ_{3k} ≐ c_{k} | x + xd_{k} = 0. Recall that (φ_{3}/ψ_{3}) = ∪_{kl}(φ_{3l}/ψ_{3k}). By Proposition 7.8, if M_{3} exists, then we must have M_{3} ≅ PE(I, J), where either (I, J) = (b_{l}V, c_{k}V) or (I, J) = (d_{k} Jac(V), a_{l} Jac(V) for some l and k (only finitely many possibilities). Now, using Lemmas 7.9 and 7.10, we calculate (for each pair (I, J) as above) Inv(PE(I, J), φ_{3}, ψ_{3}), which is 1, p or ∞. If no indecomposable pure-injective modules PE(I, J) with Inv(PE(I, J), φ_{3}, ψ_{3}) = p exists, then σ has no model. Repeat this procedure for every conjunct in 3).

Otherwise let M(0), …, M(s) be a complete list of indecomposable pureinjective modules whose (φ_{3}/ψ_{3})-invariant is p for every pair (φ_{3}, ψ_{3}) in 3). For each module M(t) with t ≤ s we calculate all the invariants from the first and the second list. If M(t) does not satisfy some sentence Inv(φ_{2}, ψ_{2}) = 1 in 2), then we drop M(t) from consideration (it cannot be a direct summand of any model of σ). Thus we may assume that Inv(M(t), φ_{2}, ψ_{2}) = 1 for every pair conjunct in 2).

Now we ‘subtract’ M(t) from a potential candidate on a model of σ and see what happens. Namely, we change our original question to a similar one, but replace Inv(φ_{3}, ψ_{3}) = n_{3} by Inv(φ_{3}, ψ_{3}) = n_{3}/p for each sentence in 3). Further, we drop a sentence Inv(φ_{1}, ψ_{1}) ≥ n_{1} from 1) whenever Inv(M(t), φ_{1}, ψ_{1}) = ∞ (as it has been already satisfied); replace it by Inv(φ_{1}, ψ_{1}) ≥ n_{1}/p, if Inv(φ_{1}, ψ_{1}) = p; and leave it unchanged otherwise (i.e., if Inv(φ_{1}, ψ_{1}) = 1). Further, we leave all the sentences in 2) unchanged.

Applying this procedure, eventually we end up with a list as above, but excluding any sentence as in 3). At this point we go back to the beginning of the proof. □

Corollary 8.3. Let V be a valuation domain from Example 2.1 , where F is a finite field. Then the theory of all V -modules is decidable.

9. Conclusions

As we have seen, if the value group of an effectively given valuation domain V is ‘nice’, then only very simple fragments of the first order theory of V (as a ring) can be interpreted in the theory of V -modules. Now we give an example showing that in general T_{V} does encode some conditions on V which cannot be expressed by first order sentences.

Recall that, if I is an ideal of V, then the radical of I, rad(I) is the intersection of all prime ideals containing I. Since the ideals of V are linearly ordered, rad(I) is a prime ideal. It is well known that b ∈ rad(I) if and only if b^{n} ∈ I for some positive integer n.

Lemma 9.1. Let V be a valuation domain and let a, b ∈ V. Then the following are equivalent:

1) ∃ x (x ≠ 0 ∧ xa = 0) → ∃ y (y ≠ 0 ∧ yb = 0) holds true in the theory of all V -modules;

2) b^{n} ∈ aV for some n;

3) b ∈ rad(aV).

Proof. 2) is equivalent to 3) by the above remark.

1) ⇒ 2). Otherwise b ∉ P = rad(aV), and P is a prime ideal. Let M = V/P and m = 1 + P. Then m ≠ 0 and ma = 0 in M, because a ∈ P and so a acts as 0 on M. On the other hand, since P is prime and b ∉ P, m′b = 0 implies m′ = 0 for every m′ ∈ M, a contradiction.

2) ⇒ 1). Suppose that m is a nonzero element of a module M such that ma = 0. If b^{n} = as for s ∈ V, then mb^{n} = mas = 0. Then there is a non-negative integer k < n such that mb^{k} ≠ 0 but mb^{k+1} = 0. If m′ = mb^{k}, then m′ ≠ 0 but m′b = 0. □

If V is a valuation domain with an archimedean value group and 0 ≠ a, b ∈ V, it is always true that b^{n} ∈ aV for some n. But, if the value group of V is not archimedean, checking the decidability of T_{V} requires to answer a non-trivial non first-order question on V, that is, membership to the radical of aV for a ∈ V.

So we guess that there may exist an effectively given valuation domain V such that the first order theory of V is decidable, but the theory of all V -modules is undecidable.

In particular we suggest the following conjecture.

Conjecture 9.2. Let V be an effectively given valuation domain such that the value group of V is dense. The the following are equivalent.

1) The theory of all V -modules is decidable.

2) There is an algorithm that, given a, b ∈ V, answers whether b^{n} ∈ aV for some integer n ≥ 1.

References

[1] P.C. Eklof, E. Fischer, Elementary theory of abelian groups, Ann. Math. Logic, 4 (1972), 115–171.

[2] A. Facchini, Relative injectivity and pure-injective modules over Prüfer rings, J. Algebra, 110 (1987), 380–406.

[3] L. Fuchs, L. Salce, Modules over Valuation Domains. Marcel Dekker, Lecture Notes Pure Appl. Math., 97 (1985).

[4] M. Prest, Model Theory and Modules. Cambridge University Press, London Math. Soc. Lecture Note Series, 130 (1987).

[5] M. Prest, Decidability for modules – summary, unpublished notes, 1991.

[6] G. Puninski, Cantor–Bendixson rank of the Ziegler spectrum over a commutative valuation domain, J. Symbolic Logic, 64 (1999), 1512–1518.

[7] G. Puninski, Serial Rings. Kluwer, 2001.

[8] W. Szmielew, Elementary properties of abelian groups, Fund. Math., 41 (1955), 203– 271.

[9] M. Ziegler, Model theory of modules, Ann. Pure Appl. Logic, 26 (1984), 149–213.

(V. Puninskaya, C. Toffalori) Dipartimento di Matematica e Informatica, Universitá di Camerino, Via Madonna delle Carceri 9, 62302, Camerino, Italy

E-mail address, Vera Puninskaya: vera.puniskaya@unicam.it

  E-mail address, C. Toffalori: carlo.toffalori@unicam.it

(G. Puninski) School of Mathematics, Manchester University, Lamb Building, Booth Street East, Manchester, M13 9PL, UK

  E-mail address: gpuninski@maths.man.ac.uk