FREE ABELIAN LATTICE-ORDERED GROUPS

A.M.W. GLASS, ANGUS MACINTYRE, AND FRANÇOISE POINT^{1}

Abstract. Let n be a positive integer and F Aℓ(n) be the free abelian latticeordered group on n generators. We prove that F Aℓ(m) and F Aℓ(n) do not satisfy the same first-order sentences in the language L={+, −, 0, ∧, ∨} if m ≠ n. We also show that T h(F Aℓ(n)) is decidable iff n ∈ {1, 2}. Finally, we apply a similar analysis and get analogous results for the free finitely generated vector lattices.

A. M. S. Classification: 03B25; 06F20; 20F60

Keywords: free abelian lattice-ordered groups, elementary equivalence, decidability, simplices.

1. Introduction.

The class of lattice-ordered abelian groups forms a variety. We will consider the theories of the free lattice-ordered abelian groups F Aℓ(n) on n generators, for n ∈ ℤ_{+}, in the language L:={+, −, 0, ∧, ∨}. We are concerned with decidability and elementary equivalence as n varies.

Free abelian groups on finitely many generators of different cardinalities cannot be elementarily equivalent: an abelian group G is freely generated by exactly n elements iff the index of the subgroup of the 2-divisible elements in the whole group is equal to 2^{n}; i.e., [G, 2.G] = 2^{n}. The decidability of the theory of the free abelian group on n generators follows from Szmielew’s classification of the theories of abelian groups (see [9]). In contrast, the free modular lattice on 5 generators has undecidable theory [5].

We show that, as in the case of free abelian groups, one can distinguish between the theories of free lattice-ordered abelian groups by the number of generators, but one gets undecidable theories for n > 2. Note that F Aℓ(1) is just the direct product ℤ × ℤ with the usual addition and lattice order: (m, n) ≥ 0 iff m ≥ 0 and n ≥ 0; it is generated by (1, −1) since (1, −1) ∨ (0, 0) = (1, 0). This structure is decidable by the Feferman-Vaught Theorem [3] (Proposition 6.3.2) and Presburger’s decidability result for (ℤ, +, 0, 1, <) (see for instance [4]).

2 A.M.W. GLASS, ANGUS MACINTYRE, AND FRANÇOISE POINT^{1}

Using the decidability of Presburger arithmetic, we will first establish that F Aℓ(2) is decidable. Next, we will note that F Aℓ(2) ≢ F Aℓ(n) for any n > 2. We will then prove that F Aℓ(m) ≢ F Aℓ(n) if n ≠ m. As a consequence of our proof and an undecidability result (due to Grzegorczyk) of some topological theories [7], we will derive that the theory of F Aℓ(n) is undecidable if n > 2.

Date: October 20, 2004.

1Senior Research Associate at the ”Fonds National de la Recherche Scientifique”.

Finally, as one might expect, we will show that one can prove parallel results for the free finitely generated vector lattices.

2. Preliminaries.

Let n be a positive natural number. Consider the additive group of continuous functions from ℝ^{n} to ℝ with the pointwise ordering, and let π_{i} : ℝ^{n} → ℝ, 1 ≤ i ≤ n, be the projection functions: π_{i}(x_{1}, ⋯, x_{n}) = x_{i}. Then, the lattice-ordered sublattice subgroup generated by these n projections is (isomorphic to) the free lattice-ordered abelian group F Aℓ(n) on n generators ([1] or [6] Theorem 5.A). It has the following representation: F Aℓ(n) := {f = ⋀_{i} ⋁_{j} f_{ij} : f_{ij} ∈ Hom(ℤ^{n}, ℤ)}. Note that any g ∈ Hom(ℤ^{n}, ℤ) is equal to ∑_{i∈S} z_{i}.π_{i}, where z_{i} ∈ ℤ, S = {j ∈ {1, …, n} : g(e_{j}) ≠ 0} and g(e_{i}) = z_{i}. To take full advantage of the geometry of Euclidean n-space, we will often regard the elements of F Aℓ(n) as functions from ℝ^{n} to ℝ. Let F Aℓ(n)^{+} be the set of elements of F Aℓ(n) such that g(x) ≥ 0 for all x ∈ ℝ^{n}. Let F Aℓ(n)_{+} = F Aℓ(n)^{+} \ {0}.

Definition 2.1. A subspace ∑_{i=1}^{n} m_{i}x_{i} = 0 (with all m_{i} ∈ ℤ) will be called an integral hyperspace, and the corresponding n-dimensional subsets ∑_{i=1}^{n} m_{i}x_{i} > 0, ∑_{i=1}^{n} m_{i}x_{i} < 0, ∑_{i=1}^{n} m_{i}x_{i} ≥ 0, ∑_{i=1}^{n} m_{i}x_{i} ≤ 0 (with all m_{i} ∈ ℤ) will be called integral half spaces. A cone in ℝ^{n} is a subset which is invariant under multiplication by elements of ℝ_{+}. A closed cone is a cone which is closed in the topology of ℝ^{n} and which contains the origin. We will always confine ourselves to such cones defined by integral half spaces. A closed (or open) integral polyhedral cone is a cone obtainable by finite unions and intersections from closed (or open) integral half spaces. It is convex if it is obtained using only intersections.

Zero sets of the elements of F Aℓ(n) will play a crucial role in our solution.

Definition 2.2. For f ∈ F Aℓ(n), let Z(f) be the zero set of f; i.e.,

Z(f) = {x ∈ ℝ^{n} : f(x) = 0}.

Let S(f) be the support of f; i.e.,

S(f) = {x ∈ ℝ^{n} : f(x) ≠ 0}.

Let K be a subset of ℝ^{n}; then S_{K}(f) is the support of f on K (={x ∈ K : f(x) ≠ 0}).

Let I, J be finite sets and {f_{i,j} : i ∈ I, j ∈ J} ⊆ Hom(ℤ^{n}, ℤ). For each i ∈ I, let f_{i} = ⋁_{j∈J}(f_{i,j} ∨ 0). Then each Z(f_{i}) is a closed convex polyhedral cone and we can consider its dimension as a subset of ℝ^{n}. If f = ⋀_{i∈I} ⋁_{j∈J}(f_{i,j} ∨ 0) = ⋀_{i∈I} f_{i}, then Z(f) = ⋃{Z(f_{i}) : i ∈ I} and we define dim(Z(f)) = max{dim(Z(f_{i})) : i ∈ I}.

Caution: Under this consideration, the number of closed convex polyhedral cones comprising Z(f) is dependent on the way we write f as a meet of a join of elements. For example, if f_{1} = π_{n} ∨0 and f_{2} = −π_{n} ∨0, then Z(f_{1}) = {(x_{1}, …, x_{n}) ∈ ℝ^{n} : x_{n} ≤ 0} and Z(f_{2}) = {(x_{1}, …, x_{n}) ∈ ℝ^{n} : x_{n} ≥ 0}, both of which have dimension n. However, f := f_{1} ∧ f_{2} is the zero function whose zero set is the entire space ℝ^{n}. So, viewing f as 0 one obtains a single closed convex polyhedral cone; but viewing f as f_{1} ∧ f_{2} yields two closed convex polyhedral cones (whose union is ℝ^{n}).

Definition 2.3. If f ∈ F Aℓ(n) and Z(f) has dimension n, then Z(f) is said to have only one piece of dimension n if the interior of Z(f) is a single connected open polyhedral cone of ℝ^{n} of dimension n.

This definition is independent of the way that f is expressed as a meet of joins of elements of the subgroup generated by π_{1}, …, π_{n}.

We recall some results and notions that appear in [1].

Proposition 2.1. ([1], Lemma 3.2) The zero sets Z(f), f ∈ F Aℓ(n), are precisely the closed integral polyhedral cones in ℝ^{n}.

Given an element f of a lattice-ordered abelian group, we define |f| = f_{+} + f_{−} where f_{+} = f ∨ 0 and f_{−} = (−f) ∨ 0. Then f_{+} ⊥ f_{−} where we write a ⊥ b for a ∧ b = 0.

Proposition 2.2. ([1], Lemma 3.3) Let f, g ∈ F Aℓ(n) and let K be a closed integral polyhedral cone in ℝ^{n}. Suppose that S_{K}(f) ⊂ S_{K}(g). Then there is an natural number m such that |f| ≤ m.|g| on K.

A subset C of F Aℓ(n) is called convex if c_{1}, c_{2} ∈ C and g ∈ F Aℓ(n) with c_{1} ≤ g ≤ c_{2} always implies that g ∈ C. The convex sublattice subgroups of F Aℓ(n) are called ℓ-ideals. They are the kernels of homomorphisms of L-structures.

Corollary 2.3. Let J be an ℓ-ideal of F Aℓ(n). Suppose that g ∈ J and S(f) ⊂ S(g). Then f ∈ J.

Given an element f ∈ F Aℓ(n), let < f >_{cl} be the ℓ-ideal generated by f; i.e., the subgroup generated by all elements g with |g| ≤ m.|f|, for some natural number m.

So, in particular, we have that if S(f) = S(g), then < f >_{cl} is equal to < g >_{cl}. Finally, we have the Baker-Beynon Duality Theorem (see Theorem 5.B in [6]).

Proposition 2.4. (Beynon [2]) Let f ∈ F Aℓ(n) and g ∈ F Aℓ(m). Then F Aℓ(n)/ < f >_{cl} is isomorphic to F Aℓ(m)/ < g >_{cl} (as L-structures) iff there is a piecewise integral linear homeomorphism θ from ℝ^{m} to ℝ^{n} such that θ(Z(g)) is equal to Z(f).

3. Decidability results for F Aℓ(2).

Let f ∈ F Aℓ(2). Then, if r ∈ ℝ_{+}, for any (x_{1}, x_{2}) ∈ ℝ^{2}, we have r.f(x_{1}, x_{2}) = f(r.x_{1}, r.x_{2}).

Let C be the circle in ℝ^{2} of radius 1 and centre (0, 0), and C_{0} := C∩{(cos θ, sin θ) : tan θ ∈ ℚ ∪ {±∞}}. Let [0, 2π)_{0} = {θ ∈ [0, 2π) : (cos θ, sin θ) ∈ C_{0}}. Each element f of F Aℓ(2) has the form ⋁_{j∈J} ⋀_{i∈I} m_{ij}.π_{1} + n_{ij}.π_{2}, with m_{ij}, n_{ij} ∈ ℤ. There are (0 = r_{ℓ+1} = r_{0} < r_{1} < ⋯ < r_{ℓ}), with r_{k} ∈ [0, 2π)_{0} such that f is linear on each arc [e^{i.r_{k}}, e^{i.r_{k+1}}] — we abuse notation and also write the points of C in the simpler form e^{ir} (0 ≤ r < 2π). That is, on each arc f has the form m_{k}.π_{1}+n_{k}.π_{2}, and moreover satisfies the obvious compatibility (continuity) conditions at the {e^{i.r_{k}} : k = 0, …, n}. Conversely, any finite sequence of linear functions satisfying these compatibility conditions gives rise to an element of F Aℓ(2).

Definition 3.1. Let z_{1}, z_{2} ∈ C_{0} and (g_{1}, ⋯, g_{m}) be a tuple of elements of F Aℓ(2). We say that the order type of (g_{1}, ⋯, g_{m}) is the same at z_{1} and z_{2} iff

g_{σ(1)}(z_{1}) ≤ ⋯ ≤ g_{σ(m)}(z_{1}) ⟷ g_{σ(1)}(z_{2}) ≤ ⋯ ≤ g_{σ(m)}(z_{2}),

for any permutation σ of {1, ⋯, m}.

Now given a tuple ḡ = (g_{1}, ⋯, g_{m}) of elements of F Aℓ(2), there is a cell-like decomposition for it in the following sense. There exists a finite subset of C_{0} such that each g_{i} is linear on each interval of the corresponding subdivision and the order type of ḡ is the same at any two points of the same interval.

Notation. Let L := {+, −, 0, ∧, ∨} and L_{≤} := {+, −, 0, 1, ≤, ./n : n ∈ ℤ_{+}}, where the unary functions /n are defined by: z/n := z′ iff OR_{i=0}^{n−1} z = z′.n + i.

Remarks:

(1) If |w| = w ∨ −w, then (in any abelian lattice-ordered group) |w| ≥ 0 with equality iff w = 0 (see, [6], Corollary 2.3.9). Indeed, op. cit., w_{1} = 0 & … & w_{n} = 0 iff (|w_{1}| ∨ ⋯ ∨ |w_{n}|) = 0. Thus every open L-formula can be written as a conjunction of formulae each of which is a disjunction of atomic formulae and at most one negation of an atomic formula.

(2) The composition of the unary functions /n is well behaved: (u/n)/m = u/(n.m), and (a + b)/n = a/n + b/n + 1 if (a − n.(a/n)) + (b − n.(b/n)) ≥ n, and (a + b)/n = a/n + b/n otherwise. If we consider the discretely ordered abelian group ℤ, we can view it as an L_{≤}-structure: we will denote this by ℤ_{L_{≤}}.

(3) In ℤ_{L_{≤}} we have x ≥ j is equivalent to x/j > 0 and x ∈ jℤ is equivalent to x − j.(x/j) = 0 (j ∈ ℤ_{+}).

Recall

Proposition 3.1. [Presburger (see [4] chapter 3, (paragraph 2)] ℤ_{L_{≤}} admits quantifier elimination.

Proposition 3.2. Let g_{1}, ⋯, g_{m} ∈ F Aℓ(2), and let θ, θ_{j}, (j ∈ J) be open L_{≤}- formulae. Then one can effectively construct open L_{≤}-formulae θ′, θ′_{j} (j ∈ J) such that

∃y ∈ F Aℓ(2)[(∀u ∈ ℤ^{2}) ℤ ⊧ θ(y(u), ḡ(u)) and &_{j∈J}(∃u_{j} ∈ ℤ^{2}) ℤ ⊧ θ_{j}(y(u_{j}), ḡ(u_{j}))]

iff [(∀u ∈ ℤ^{2}) ℤ ⊧ θ′(ḡ(u)) and &_{j∈J}(∃u_{j} ∈ ℤ^{2}) ℤ ⊧ θ′_{j}(ḡ(u_{j}))]

Proof: We first show that, for n ∈ ℤ_{+}, the existential formula

(∃f)[(max_{i}{t_{1i}}) ≤ n.f ≤ (min_{j}{t_{2j}})]

is equivalent in ℤ to the open L_{≤}-formula

max{t_{1i}} ≤ min{t_{2j}} and [(min{t_{2j}}−max{t_{1i}})/n > 0 or ((min{t_{2j}}−max{t_{1i}})/n

= 0 and max{t_{1i}} + (n − (max{t_{1i}} − n · (max{t_{1i}}/n))) ≤ min{t_{2j}})].

Let t = max{t_{1i}} and u = min{t_{2j}}. Clearly, there is z ∈ ℤ with t ≤ n.z ≤ t + n ≤ u if (u − t)/n > 0 (and hence a solution to (∃f)(t ≤ n.(f/m) ≤ u)). If (u − t)/n = 0, then there is a solution iff nℤ ∩ {t, t + 1, …, u} ≠ ∅. These are the above conditions since if t = nk + r, then t − (n · (t/n)) = r.

Now consider the existential formula in parameters ḡ = (g_{1}, …, g_{m}) ∈ F Aℓ(2)^{m}:

(∃f̂ ∈ F Aℓ(2))(∀u ∈ ℤ^{2})[ĥ_{1}(u, ḡ) ≤ d · f̂(u) ≤ ĥ_{2}(u, ḡ)],

where ĥ_{j}(u, ḡ) ∈ F Aℓ(2) involve suprema and infima of group terms (j = 1, 2). Its satisfaction in F Aℓ(2) is equivalent to:

(∃f)∀x ∈ [0, 2π)_{0} [h_{1}(x) ≤ d · f(x) ≤ h_{2}(x)],

where h_{j}(x) := ĥ_{j}((cosx, sinx), ḡ) (j = 1, 2) and f(x) = f̂((cosx, sinx), ḡ).

Let (r_{0}, r_{1}, ⋯, r_{ℓ}) be a subdivision of [0, 2π)_{0} such that g_{1}, …, g_{m} are linear on each arc of C corresponding to each interval [r_{k} r_{k+1}] (k = 0, …, ℓ − 1) and of the same order type (whence h_{1} and h_{2} are linear on each interval, too). Thus the original inequality is equivalent to

(∃f) ⋀_{k=0}^{ℓ−1} ∀x ∈ [r_{k} r_{k+1}) [h_{1}(x) ≤ d.f(x) ≤ h_{2}(x)].

Provided that lim_{x→r_{k}−} f_{k}(x) = lim_{x→r_{k}+} f_{k}(x) for all k, this is equivalent to

⋀_{k=0}^{ℓ−1}(∃f_{k})∀x ∈ [r_{k} r_{k+1}) [h_{1}(x) ≤ d.f_{k}(x) ≤ h_{2}(x)]. (1)

Claim: (1) is equivalent to

⋀_{k=0}^{ℓ−1} ∀x ∈ [r_{k} r_{k+1}) (∃z)[h_{1}(x) ≤ d.z ≤ h_{2}(x)], (2)

(which in turn is equivalent to: ∀x ∈ [0, 2π)_{0} (∃z)[h_{1}(x) ≤ d.z ≤ h_{2}(x)])

where z is to be an integer linear combination of cos x and sin x.

Proof of Claim: Clearly (1) implies (2), so we assume (2) and deduce (1). Fix k ∈ {0, …, ℓ − 1} and let ĥ_{j}(x_{1}, x_{2}) = m_{j}x_{1} + n_{j}x_{2} where (x_{1}, x_{2}) = (cos x, sin x) and x ∈ [r_{k}, r_{k+1}] (j = 1, 2). We assume, without loss of generality, that π is one of the r_{j}.

We will consider two cases separately: firstly, the interval [r_{k}, r_{k+1}] does not contain π/2 or 3π/2; secondly, the interval [r_{k}, r_{k+1}] contains either π/2 or 3π/2.

Case 1: We suppose that the closed interval [r_{k}, r_{k+1}] is included in [0, π/2), the other three possibilities being similar. Now (cos r_{k}, sin r_{k}) = (cos r_{k})(1, q_{1}) and (cos r_{k+1}, sin r_{k+1}) = (cos r_{k+1})(1, q_{2}), where q_{1}, q_{2} ∈ ℚ_{+} and q_{2} > q_{1}. For j = 1, 2, let q_{j} = a_{j}/b_{j} where a_{1}, a_{2}, b_{1}, b_{2} ∈ ℤ_{+} and g.c.d{a_{j}, b_{j}} = 1. By using a trivial case of Minkowski’s counting (of lattice points in a convex body), we reduce to the case that Δ := b_{1}.b_{2}.(q_{2} − q_{1}) = a_{2}.b_{1} − a_{1}.b_{2} ∈ ℤ_{+} is equal to 1.

Let P_{j} := (b_{j}, a_{j}) (j = 1, 2) and O be the origin. The vectors OP_{1} and OP_{2} form a basis for a lattice in ℝ^{2} with determinant Δ. By counting lattice points (see, e.g., Lemma 2B, page 3 in [8]), if Δ > 1 there is Q ∈ ℤ^{2} \ {O, P_{1}, P_{2}, P_{1} + P_{2}} in the parallelogram with adjacent sides OP_{1} and OP_{2}, and hence in the closed triangle O, P_{1}, P_{2} (subtract the vector OQ−OP_{1} from OP_{2} if necessary). Since g.c.d{a_{j}, b_{j}} = 1, we get in addition that the point Q cannot belong to the segments [O, P_{1}] and [O, P_{2}]. By the choice of Q, the lattice generated by OP_{j} and OQ has determinant an integer strictly smaller than Δ (j = 1, 2). Hence this process terminates in a finite number of steps. By subdividing the interval [r_{k}, r_{k+1}] accordingly, we can reduce to the case that Δ = 1, which we now assume.

Let

M = ( \begin{matrix}b_{1} & b_{2} \\ a_{1} & a_{2} \end{matrix} ) ∈ SL(2, ℤ).

So M is the linear transformation mapping (1, 0) to P_{1} and (0, 1) to P_{2} (it has determinant 1). Then

M^{−1} = ( \begin{matrix}a_{2} & −b_{2} \\ −a_{1} & b_{1} \end{matrix} ) ∈ SL(2, ℤ).

The interval [r_{k}, r_{k+1}] determines an integral cone D_{k} of ℤ^{2}; any element ū of D_{k}

has the form M ( \begin{matrix}v_{1} \\ v_{2} \end{matrix} ) , where (v_{1}, v_{2}) ∈ D := \{(x_{1}, x_{2}) ∈ ℤ^{2} : x_{1}, x_{2} ≥ 0\}.

Our formula (restricted to [r_{k}, r_{k+1}]) is equivalent to

∀x̄ ∈ D_{k} ∃y ĥ_{1}(x_{1}, x_{2}) = m_{1}.x_{1} + n_{1}.x_{2} ≤ d.y ≤ ĥ_{2}(x_{1}, x_{2}) = m_{2}.x_{1} + n_{2}.x_{2}.

Replacing x̄ by Mv̄ with (v_{1}, v_{2}) ∈ D, we get that

ĥ_{1}(Mv̄) = (m_{1}.b_{1} + n_{1}.a_{1}).v_{1} + (m_{1}.b_{2} + n_{1}.a_{2}).v_{2} and
ĥ_{2}(Mv̄) = (m_{2}.b_{1} + n_{2}.a_{1}).v_{1} + (m_{2}.b_{2} + n_{2}.a_{2}).v_{2}.

By (2), for all (v_{1}, v_{2}) ∈ D there are m′, n′ ∈ ℤ (dependent on the point (v_{1}, v_{2})) such that

ĥ_{1}(Mv̄) ≤ d.m′.(b_{1}.v_{1} + b_{2}.v_{2}) + d.n′.(a_{1}.v_{1} + a_{2}.v_{2}) ≤ ĥ_{2}(Mv̄).

Evaluating the functions at (1, 0), we get that, for some (m′, n′) ∈ ℤ^{2},

(m_{1}.b_{1} + n_{1}.a_{1}) ≤ d.(m′.b_{1} + n′.a_{1}) ≤ (m_{2}.b_{1} + n_{2}.a_{1}) (∗)

and at (0, 1) we get that, for some (m′′, n′′) ∈ ℤ^{2},

(m_{1}.b_{2} + n_{1}.a_{2}) ≤ d.(m′′.b_{2} + n′′.a_{2}) ≤ (m_{2}.b_{2} + n_{2}.a_{2}) (∗)

To establish the claim, we need to show how to choose m, n ∈ ℤ independent of the point in D so that both inequalities (∗) hold.

Let X_{j} = [m_{1}.b_{j} + n_{1}.a_{j}, m_{2}.b_{j} + n_{2}.a_{j}] ∩ dℤ (j = 1, 2). Now X_{j} ≠ ∅ (j = 1, 2) by (∗). That is:

[ĥ_{1}(b_{j}, a_{j}), ĥ_{2}(b_{j}, a_{j})] ∩ d.ℤ ≠ ∅ (j = 1, 2) (†) .

Let y_{j} ∈ X_{j} (j = 1, 2). Since (v_{1}, v_{2}) ∈ D we have v_{1}, v_{2} ≥ 0. Therefore

(m_{1}.b_{j} + n_{1}.a_{j}).v_{j} ≤ d.y_{j}.v_{j} ≤ (m_{2}.b_{j} + n_{2}.a_{j}).v_{j} (j = 1, 2).

Summing these inequalities, we get:

∑_{j=1}^{2}(m_{1}.b_{j} + n_{1}.a_{j}).v_{j} ≤ d.y_{1}.v_{1} + d.y_{2}.v_{2} ≤ ∑_{j=1}^{2}(m_{2}.b_{j} + n_{2}.a_{j}).v_{j}.

Equivalently, for all (v_{1}, v_{2}) ∈ D, we have

ĥ_{1}(Mv̄) ≤ d.(y_{1}.v_{1} + y_{2}.v_{2}) ≤ ĥ_{2}(Mv̄).

Using now the inverse matrix M^{−1}, we get for all points of D_{k}:

ĥ_{1}(x̄) ≤ d.(y_{1}, y_{2}).(M^{−1}.x̄) ≤ ĥ_{2}(x̄).

Thus, for all x̄ ∈ D_{k}:

ĥ_{1}(x̄) ≤ d.(y_{1}.a_{2} − y_{2}.a_{1}).x_{1} + d.(y_{2}.b_{1} − y_{1}.b_{2}).x_{2} ≤ ĥ_{2}(x̄).

This completes Case 1.

Case 2: Suppose that the interval [r_{k}, r_{k+1}] contains π/2 or 3π/2.

We consider only the case that π/2 ∈ [r_{k}, r_{k+1}], the other case being similar.

Evaluating ĥ_{1}, ĥ_{2} at the point (0, 1), by (2) we may suppose that

n_{1} ≤ d.y ≤ n_{2}

for some y ∈ ℤ; and evaluating them at the point (z′_{1}, z′_{2}) ∈ C_{0} (with the additional hypotheses that 0 < z′_{1} ≤ 1, z′_{2} > 0), that

m_{1}.z′_{1} + n_{1}.z′_{2} ≤ d.y′ ≤ m_{2}.z′_{1} + n_{2}.z′_{2}.

We seek m′, n′ ∈ ℤ such that

m_{1}.x_{1} + n_{1}.x_{2} ≤ d.(m′.x_{1} + n′.x_{2}) ≤ m_{2}.x_{1} + n_{2}.x_{2}

holds whenever 0 ≤ x_{1} ≤ z′_{1} and 1 ≥ x_{2} ≥ z′_{2}.

Subcase (i): n_{1} < n_{2}.

Let y ∈ ℤ be such that n_{1} ≤ d.y ≤ n_{2} and put n′ = y. Then (for x_{1} ≠ 0) we need

m_{1} + (n_{1} − d.y).x_{2}/x_{1} ≤ d.m′ ≤ m_{2} + (n_{2} − d.y).x_{2}/x_{1}.

Now the left hand side tends to −∞ (if d.y ≠ n_{1}) and the right hand side to +∞ (if d.y ≠ n_{2}) as x_{2}/x_{1} goes to +∞. So, if n_{1} ≠ n_{2}, we can always find m′ ∈ ℤ and (z′′_{1}, z′′_{2}) for which the inequalities hold for all 0 ≤ x_{1} ≤ z′′_{1} ≤ z′_{1} and 1 ≥ x_{2} ≥ z′′_{2} ≥ z′_{2}.

Subcase (ii): n_{1} = d.y = n_{2} with y ∈ ℤ.

Let q = tan r_{k} ∈ ℚ_{+} and choose a ∈ ℤ_{+} with a ≥ q. Let r′_{k} ∈ [r_{k}, π/2) with tan r′_{k} = a. By (2), for some m′, n′ ∈ ℤ

ĥ_{1}(1, a) = m_{1} + n_{1}.a ≤ d.(m′ + n′.a) ≤ m_{2} + n_{2}.a = ĥ_{2}(1, a).

Hence m_{1} ≤ d.(m′ + (n′ − y).a) ≤ m_{2}. Therefore [m_{1}, m_{2}] ∩ d.ℤ ≠ ∅.

Let m = m′ + (n′ − y).a ∈ ℤ; so d.m ∈ [m_{1}, m_{2}]. Then

m_{1}.z_{1} + n_{1}.z_{2} ≤ d.(m.z_{1} + y.z_{2}) ≤ m_{2}.z_{1} + n_{2}.z_{2},

for all z_{1}, z_{2} ∈ ℤ_{+}. Hence (1) holds for the interval [r′_{k}, π/2].

Therefore, letting r be such that e^{i.r} = (z′′_{1}, z′′_{2}) or r := r′_{k}, we refine our interval [r_{k}, r_{k+1}] into [r_{k}, r], [r, π/2], [π/2, r_{k+1}]. We have just described what to do for the second of these intervals; the argument for the third is similar, and the first of these intervals is covered by Case 1. This completes the proof of the claim.

We deal with strict < similarly, and also with a single ≤ or < in place of the pair ĥ_{1}(ḡ) ≤ d.f̂ ≤ ĥ_{2}(ḡ); and replace x ≠ y (in ℤ) by the disjunction x < y or y < x.

For the general case, write θ and θ_{j} in disjunctive normal form, each conjunct being an inequality (possibly strict and possibly with d = 1) of the above form or the negation of such, and possibly congruence relations (by the Remarks). Then, with the same subintervals of C_{0} as above, one can check the finite sets arising (if π/2, 3π/2 do not belong to the subinterval and there is a pair of (two-sided) inequalities — strict or otherwise), and check each of the possible solutions at the endpoints of adjacent subintervals to ensure the final solution is continuous, etc. Thus the satisfaction of

∃y ∈ F Aℓ(2)[(∀u ∈ ℤ^{2}) ℤ ⊧ θ(y(u), ḡ(u)) and &_{j∈J}(∃u_{j} ∈ ℤ^{2}) ℤ ⊧ θ_{j}(y(u_{j}), ḡ(u_{j}))]

is equivalent to the solution of a finite system of “basic” L_{≤}-inequalities and strict inequalities at the endpoints of these intervals each of which is handled as above, as well as continuity conditions at this finite set of endpoints. The proposition follows. □

Proposition 3.3. For any L-formula ϕ, one can effectively construct open L_{≤}- formulae θ_{i} (i ∈ I), and θ′_{j} (j ∈ J_{i}) such that for any tuple of elements ḡ of F Aℓ(2),

F Aℓ(2) ⊧ ϕ(ḡ) ⟷ OR_{i∈I} \{ \begin{matrix}& (∀u ∈ ℤ^{2}) & ℤ ⊧ θ_{i}(ḡ(u)) \\ &_{j∈J_{i}} & (∃u_{j} ∈ ℤ^{2}) & ℤ ⊧ θ′_{j}(ḡ(u_{j})). \end{matrix}

Proof: By induction on the complexity of ϕ.

The proposition is clear for atomic L-formulae.

If the proposition holds for ϕ, then it clearly holds for ¬ϕ, and similarly for the disjunction of ϕ_{1} or ϕ_{2} if it holds for ϕ_{1} and ϕ_{2}.

Suppose now that the induction hypothesis holds for ψ(f, x̄) and that ϕ(x̄) is of the form ∃fψ(f, x̄). Let θ_{i}, θ′_{j} be open L_{≤}-formulae (i ∈ I, j ∈ J_{i}) such that F Aℓ(2) ⊧ ∃fψ(f, ḡ) ⟷ OR_{i} (∃f ∈ F Aℓ(2)) [(∀u ∈ ℤ^{2}) ℤ ⊧ θ_{i}(f(u), ḡ(u)) & &_{j∈J_{i}}(∃u_{j} ∈ ℤ^{2}) ℤ ⊧ θ′_{j}(f(u_{j}), ḡ(u_{j}))].

By Proposition 3.2, we can effectively construct open L_{≤}-formulae θ′′_{i}, θ′′′_{j} (i ∈ I′, j ∈ J′_{i}) such that this last equivalent is equivalent to

OR_{i} [(∀u ∈ ℤ^{2}) ℤ ⊧ θ′′_{i}(ḡ(u)) & &_{j∈J′_{i}}(∃u_{j} ∈ ℤ^{2}) ℤ ⊧ θ′′′_{j}(ḡ(u_{j}))]. □

Corollary 3.4. Let σ be an L-sentence. Then, one can effectively obtain an open L_{≤}-sentence θ such that F Aℓ(2) ⊧ σ ⟷ ℤ ⊧ θ.

Corollary 3.5. F Aℓ(2) is decidable.

Proof: This follows from the results of this section since ℤ is decidable as a latticeordered group (by Presburger) and the procedure to associate θ with σ is effective by the preceding corollary. □

4. Undecidability results.

We will prove that the lattice-ordered abelian groups F Aℓ(n) are not elementarily equivalent if n ≠ m, and (as a consequence of the method) that for n > 2 their theories are undecidable.

The proof relies on the fact that one can obtain formulae in our language which express the dimension of the zero set of an element of F Aℓ(n). We will get these formulae by induction on n.

If one factors out ⟨π_{n+1}⟩_{cl} from F Aℓ(n + 1), then the quotient is isomorphic (as an L-structure) to F Aℓ(n). And one can hope to use this correspondence to inductively define the dimension of a zero set in F Aℓ(n + 1). This we will achieve in a series of lemmata. One cannot capture π_{n+1} by automorphisms of L-structures, and so certainly not by first order sentences in the language. However, one can capture (using the first order language L) elements in F Aℓ(n + 1) which are “π_{n+1}-like”. We will then use the dimension of zero sets in the resulting quotient F Aℓ(n) to define the dimension of a zero set in F Aℓ(n + 1) correctly.

The key idea to do this is to cover the n-sphere with two n-dimensional pieces (the zero sets of f_{1}, f_{2} > 0 intersected with the n-sphere), so that f_{1} ∧ f_{2} = 0 and the overlap of these restricted zero sets (the zero set of f = f_{1} ∨ f_{2} intersected with the n-sphere) is of dimension n − 1. This will be characterised by the formula χ(f, f_{1}, f_{2}) in Lemma 4.5. If f, f_{1}, f_{2} are such that the restricted zero set of f is minimal with this property, then we next obtain relativised formulae ξ^{r}(x̄, y) so that F Aℓ(n) ≅ F Aℓ(n + 1)/⟨f⟩_{cl} ⊧ ξ(h̄ + ⟨f⟩_{cl}) iff F Aℓ(n + 1) ⊧ ξ^{r}(h̄, f) (Lemma 4.6). Finally, we will use these relativised formulae to transfer (the expressibility of) the dimension of zero sets in F Aℓ(n) to (the expressibility of) the corresponding dimension theory for all zero sets of elements in F Aℓ(n + 1), and thereby complete the proofs of the theorems.

Let S^{n} be the n-sphere; i.e., {ȳ ∈ ℝ^{n+1} : d(ȳ, 0) = 1}. To any nonzero x̄ ∈ ℝ^{n+1}, we associate the point p̄ ∈ S^{n} with ∃r ∈ ℝ^{+}(r · x̄ = p̄). Let ϕ be this map, the projection of x̄ from the origin onto S^{n}. Now for each f ∈ F Aℓ(n + 1) and x̄ ∈ ℝ^{n+1}, we have f(x̄) = r · f(ϕ(x̄)),where r is the norm of x̄. So for inductive purposes it is enough to consider the images of Z(f) and S(f) under ϕ; we denote these by Z(f) and S(f), respectively. We will regard Z(f) as a finite union of integral polyhedra Z(f_{j}), analogously to Z(f).

Since Z(g) = Z(|g|), we need only consider the zero sets of positive elements.

By our conventions, we have

Z(f) ∪ Z(g) = Z(f ∧ g) and Z(f) ∩ Z(g) = Z(f ∨ g), and so
Z(f) ∪ Z(g) = Z(f ∧ g) and Z(f) ∩ Z(g) = Z(f ∨ g).

Our first result (Theorem 4.2) is that we can easily distinguish T h(F Aℓ(2)) from all T h(F Aℓ(n)) with n > 2 (in the language L). (We can distinguish F Aℓ(1) from all the others by noting that the index of the subgroup 2.F Aℓ(1) in F Aℓ(1) is equal to 4.)

For convenience, we begin with a lemma in which we express, in F Aℓ(n), that a zero-set has dimension n.

We will check that our formulae are invariant under the equivalence relation on F Aℓ(n)_{+} given by f ∼ f′ iff Z(f) = Z(f′).

Lemma 4.1. For every n, there are formulae ψ_{n,n−1}(x), ϕ_{n,n−1}(x) such that for all f ∈ F Aℓ(n)_{+},

(1) F Aℓ(n) ⊧ ψ_{n,n−1}(f) iff dim(Z(f)) = n.

(2) F Aℓ(n) ⊧ ϕ_{n,n−1}(f) iff Z(f) has only one piece of dimension n.

Proof:

We first express (in the language L) that the zero set of one element contains the support of another. Then we go on to express (in the language L) that the zero set of an element has dimension n. Let

ψ_{n,n−1}(f, g) := (g ⊥ f and g ≠ 0), and ψ_{n,n−1}(f) := (∃g)ψ_{n,n−1}(f, g).

Note that dim(S(g)) = n−1 for all g ≠ 0; and (g ≠ 0 and f ⊥ g) implies S(g) ⊆ Z(f) (or, equivalently, S(g) ⊆ Z(f)). Since dim(Z(f)) = n − 1 implies that Z(f) includes a closed convex polyhedral cone of dimension n (which, necessarily, contains the support of an element of F Aℓ(n)_{+}), we get (for f, g > 0)

F Aℓ(n) ⊧ ψ_{n,n−1}(f, g) iff S(g) ⊆ Z(f),

and

F Aℓ(n) ⊧ ψ_{n,n−1}(f) iff dim(Z(f)) = n − 1.

Observe that ψ_{n,n−1} is an existential formula and that it is invariant under the equivalence relation ∼ .

We next express that the support, S(h), of an element h > 0, is connected. Let θ(h) be the formula:

(h > 0) and ¬((∃h_{1}, h_{2} > 0)(h_{1} ⊥ h_{2}, and h_{1} ∨ h_{2} = h)).

Clearly, for f > 0, the algebraic set Z(f) has only one n-dimensional piece iff

F Aℓ(n) ⊧ ψ_{n,n−1}(f) and (∀g > 0)(g ⊥ f → (∃h ≥ g)(h ⊥ f and θ(h))).

Denote this formula by ϕ_{n,n−1}(f).

Again, it is invariant under the equivalence relation ∼. The complexity of this formula is ∀∃∀. □

We can now distinguish F Aℓ(2) from the other F Aℓ(n).

Theorem 4.2. F Aℓ(2) ≢ F Aℓ(n) for any n > 2.

Proof:

Consider the sentence:

(∀f_{1}, f_{2} > 0)⋀_{i=1}^{2}(∀h_{i,1}, h_{i,2})[(f_{1} ⊥ f_{2} and ⋀_{i=1}^{2}f_{i} = h_{i,1} ∨ h_{i,2} and h_{i,1} ⊥ h_{i,2} and

θ(h_{i,1}) and θ(h_{i,2})] → [ ⋀_{i=1,2 k=1,2}(∃h′_{i,k} > 0)( h′_{i,k} ≤ h_{i,k} and θ(h′_{i,k}) and

( ⋀_{i=1,2} ∃g_{i} ≥ (h′_{i,1} ∨ h′_{i,2}) and (g_{1} ⊥ g_{2}) and θ(g_{1}) and θ(g_{2})))].

It holds in F Aℓ(n) if n > 2, but not in F Aℓ(2). □

We next wish to prove

Theorem 4.3. The structures (F Aℓ(n), +, −, ∧, ∨, 0) and (F Aℓ(m), +, −, ∧, ∨, 0) with 2 < m < n, m, n ∈ ℤ_{+}, are not elementarily equivalent.

Proof:

Our goal is to find formulae in the language L which encode in F Aℓ(n) the usual notion of the dimension of a variety in Euclidean space 𝔼_{n}. This we achieve by induction.

Induction hypothesis: for every m ∈ {2, …, n} and m − 1 ≥ k ≥ −1, we have

F Aℓ(m) ⊧ ψ_{m,k}(f)

iff dim(Z(f)) = k

(iff Z(f) contains the positive span of (k + 1) ℝ-linearly independent vectors in ℝ^{m} (but not (k + 2) such)).

The case n = 2 of the induction is summed up in the following lemma:

Lemma 4.4. Let f ∈ F Aℓ(2)_{+}. Then (1) F Aℓ(2) ⊧ ψ_{2,1}(f) iff Z(f) contains an interval;

(2) F Aℓ(2) ⊧ ψ_{2,0}(f) iff Z(f) is a non-empty finite set of points;

(3) F Aℓ(2) ⊧ ψ_{2,−1}(f) iff Z(f) = ∅.

Proof: We have already defined the formula ψ_{2,1}(f) in Lemma 4.1.

Define ψ_{2,0}(f) by:

¬ψ_{2,1}(f) and (∃f_{1}, f_{2} > 0)(f = f_{1} ∨ f_{2} and ⋀_{i=1,2} ψ_{2,1}(f_{i}) and ϕ_{2,1}(f_{1} ∧ f_{2})).

Note that there is nothing specific to the case n = 2 in this formula.

(In fact, one can show that the formula ψ_{n,n−2}(f) obtained by replacing ψ_{2,1} by ψ_{n,n−1} and ϕ_{2,1} by ϕ_{n,n−1} encodes in F Aℓ(n) the zero sets of dimension n − 2.)

It remains to express that a zero set is empty. This can simply be done with the formula

¬ψ_{2,1}(f) and ¬ψ_{2,0}(f).

Alternatively, we can use the equivalent (in F Aℓ(2)) formula ψ_{2,−1}(f):

¬ψ_{2,1}(f) and ¬ψ_{2,0}(f) and (∀f_{1}, f_{2} > 0)[(f = f_{1} ∨ f_{2} and ϕ_{2,1}(f_{1}) and ϕ_{2,1}(f_{2}))

→ (∀h_{1}, h_{2})[(⋀_{j=1}^{2} h_{j} ⊥ f_{j}) → (∀h ≥ h_{1} ∨ h_{2})(¬(θ(h)) or h ⊥̸ (f_{1} ∧ f_{2})]].

Note that in this case we use the geometry of the circle to ensure that this formula has the desired meaning. □

Assume our induction hypothesis up to n ≥ 2. We wish to deduce it for F Aℓ(n+1). This will be undertaken in the following three lemmata. Our main technical tool will be the Baker-Beynon Duality Theorem (see [2] Theorem 4.1 or Section 2 above). We will apply it as follows:

Suppose that an element f ∈ F Aℓ(n + 1)_{+} behaves like π_{n+1} in the sense that

F Aℓ(n + 1)/ < f >_{cl}≅ F Aℓ(n).

This property holds iff Z(f) and ℝ^{n} are piecewise homogeneous integral linear homeomorphic, which entails that the above isomorphism can be described quite explicitly. Namely, let θ be a piecewise linear integral homeomorphism from ℝ^{n} to ℝ^{n+1} sending ℤ^{n} onto Z(f). It is of the form: θ(x̄) = (u_{1}(x̄), ⋯, u_{n+1}(x̄)) with u_{1}, ⋯, u_{n+1} ∈ F Aℓ(n). Let T (θ) be the induced map from F Aℓ(n + 1) to F Aℓ(n) sending h to h ∘ θ. One may identify h ∘ θ with h|_{Z(f)}. The kernel of T (θ) is the ℓ-ideal < f >_{cl} . For convenience we will denote the image T (θ)(f) by f^{θ} and write T^{∗}(θ) for the induced ℓ-isomorphism between F Aℓ(n + 1)/ < f >_{cl} and F Aℓ(n) (see Corollary 5.2.2 in [6]).

Lemma 4.5. There is a formula χ(y) such that if f ∈ F Aℓ(n+1)_{+} and F Aℓ(n+1) ⊧ χ(f), then there exists f′ ≥ f such that F Aℓ(n + 1) ⊧ χ(f′) and, say, ϑ : F Aℓ(n + 1)/ < f′ >_{cl}≃ F Aℓ(n). Moreover, this element f′ satisfies the following minimality condition: for any g ∈ F Aℓ(n + 1)_{+} with Z(g) ⊊ Z(f′), then F Aℓ(n + 1)_{+} ⊧ ¬χ(g). In addition, we have that, for k ∈ {−1, 0, …, n − 1}

dimZ(ϑ(h+ < f′ >_{cl})) = k iff dim(Z(h) ∩ Z(f′)) = k.

Proof: Let

χ(f, f_{1}, f_{2}) := f > 0 and f = f_{1} ∨ f_{2} and ¬ψ_{n+1,n}(f) and ⋀_{i=1}^{2} ϕ_{n+1,n}(f_{i}) and f_{1} ⊥ f_{2}.

Let

χ(f) := (∃f_{1} > 0, ∃f_{2} > 0)χ(f, f_{1}, f_{2}).

Again note that this formula is invariant under the equivalence relation ∼.

We first check that χ(|π_{n+1}|) holds. Let p_{1} := (−π_{n+1} ∨ 0) and p_{2} := (π_{n+1} ∨ 0). Then we have that |π_{n+1}| = p_{1} ∨ p_{2}, p_{1} ⊥ p_{2} and ⋀_{i=1}^{2} ϕ_{n+1,n}(p_{i}).

Next we show the minimality property for |π_{n+1}|. Take any element h > 0 such that Z(h) ⊊ Z(π_{n+1}). We claim that ¬χ(h) holds.

Suppose that χ(h) holds. Then there are positive elements h_{1} and h_{2} (each Z(h_{j}) having exactly one n-dimensional piece) such that Z(h_{1}) ∪ Z(h_{2}) = S^{n} and Z(h_{1}) ∩ Z(h_{2}) = Z(h). Denote the n-dimensional piece of Z(h_{j}) by Z_{n}(h_{j}) (j = 1, 2). Since Z(h_{1}) ∪ Z(h_{2}) = S^{n} and Z(h_{1}) ∩ Z(h_{2}) ⊆ Z(π_{n+1}), we cannot have both Z_{n}(h_{1}) ∩ Z(p_{1}) ⊈ Z(π_{n+1}) and Z_{n}(h_{2}) ∩ Z(p_{1}) ⊈ Z(π_{n+1}). Mutatis mutandis with p_{2} in place of p_{1}. Thus one may assume that Z_{n}(h_{j}) ⊆ Z(p_{j}) (j = 1, 2). On the other hand, Z(h) is strictly included in Z(π_{n+1}) (by assumption), so either Z_{n}(h_{1}) ⊊ Z(p_{1}) or Z_{n}(h_{2}) ⊊ Z(p_{2}). This contradicts the fact that Z(h_{1}) ∪ Z(h_{2}) = S^{n}. Hence ¬χ(h) holds.

Let θ be the embedding of ℝ^{n} into ℝ^{n+1} sending (x_{1}, ⋯, x_{n}) to (x_{1}, ⋯, x_{n}, 0) and T^{∗}(θ) be the induced ℓ-isomorphism between F Aℓ(n + 1)/ < |π_{n+1}| >_{cl} and F Aℓ(n).

Let f, f_{1}, f_{2} ∈ F Aℓ(n + 1)_{+} be such that F Aℓ(n + 1) ⊧ χ(f, f_{1}, f_{2}). Then, since ϕ_{n+1,n}(f_{i}) hold for i = 1, 2, we get that (to within lower dimensional varieties) Z(f_{1}) has one piece of dimension n+1 (that is equal to a finite union of (n+1)-dimensional polyhedral cones) and that Z(f_{2}), also up to varieties of lower dimension, is equal to the the closure of the complement of Z(f_{1}). In particular, Z(f_{1}) contains an (n + 1)- dimensional closed polyhedral cone C_{1} whose boundary is included in Z(f_{1} ∨ f_{2}). Define f′_{1} ≥ f_{1} to be a function whose zero set is equal to C_{1} and f′_{2} ≥ f_{2} a function whose zero set is the closure of the complement of C_{1}. Let f′ = f′_{1} ∨f′_{2}. We have that Z(f′) = Z(f′_{1} ∨ f′_{2}) ⊆ Z(f_{1} ∨ f_{2}). The boundary of the cone C_{1} is piecewise linearly homeomorphic to Z(|π_{n+1}|); so denoting this homeomorphism (extended to ℝ^{n+1}) by τ and the induced ℓ-automorphism of F Aℓ(n + 1) by τ̂, we have that < f′ >_{cl} is equal to < |π_{n+1}|τ̂ >_{cl}. Thus χ(|π_{n+1}|) ↔ χ(|π_{n+1}|τ̂). Moreover, χ is invariant under ∼, and so we get that χ(f′) holds. Indeed, this function f′ is minimal such. For let g be such that Z(g) ⊊ Z(f′). Then Z(g^{τ̂^{−1}}) ⊊ Z(|π_{n+1}|), so F Aℓ(n + 1) ⊧ ¬χ(g^{τ̂^{−1}}). But τ̂ is an ℓ-isomorphism and so we also get that F Aℓ(n + 1) ⊧ ¬χ(g).

Let ϑ := T^{∗}(τ^{−1} ∘ θ). Then, ϑ is an ℓ isomorphism between: F Aℓ(n + 1)/ < f′ >_{cl} and F Aℓ(n). Moreover,

h+ < f′ >_{cl} ↦ h|_{Z(f′)}

is well-defined since h ∈< f′ >_{cl} iff Z(h) ⊇ Z(f′).

The last assertion of the lemma follows from the fact that we may identify h^{ϑ} with h|_{Z(f′)}. □

Lemma 4.6. There is a definable relation R(h, f), such that whenever f ∈ F Aℓ(n+ 1)_{+} is such that χ(f) holds and if Z(f′) ⊊ Z(f) then ¬χ(f′), then R(h, f) iff Z(h) contains the n-dimensional-part of Z(f). Further, for any formula ξ(x̄) one can explicitly construct a formula ξ^{r}(x̄, y) such that for any h̄ ⊆ F Aℓ(n + 1),

F Aℓ(n + 1)/ < f >_{cl}⊧ ξ(h̄+ < f >_{cl}) iff F Aℓ(n + 1) ⊧ ξ^{r}(h̄, f).

Proof: Define R(h, f) by

(∃f_{1} > 0)(∃f_{2} > 0)(χ(f, f_{1}, f_{2}) and

(∃h_{1} ≥ 0)(∃h_{2} ≥ 0)[h = h_{1} ∨ h_{2} and ⋀_{i=1}^{2} ∀k((k ⊥ f_{i}) ↔ (k ⊥ h_{i})]).

This relation R expresses that the (n + 1)-dimensional part of Z(h_{i}) is equal to that of Z(f_{i}) for i = 1, 2. Now the minimality hypothesis of Z(f) implies that its n-dimensional part is equal to the intersection of the (n + 1)-dimensional part of Z(f_{1}) and Z(f_{2}).

We define ξ^{r} by induction on the complexity of the formula ξ. For an atomic formula ξ(x̄) := (t(x̄) = 0), we define ξ^{r}(x̄, y) as R(t(x), y). For a quantifier-free formula ξ(x̄) (i.e., a Boolean combination of atomic formulae ξ_{i}(x̄) := t_{i}(x̄) = 0), we define ξ^{r}(x̄, y) to be the same Boolean combination of ξ_{i}^{r}(x̄, y). Finally, if ξ(x̄) is in prenex form Q(z̄)ξ(z̄, x̄), where Q(z̄) is a block of quantifiers, define ξ^{r}(x̄, y) as Q(z̄)ξ^{r}(z̄, x̄, y).

We now prove the equivalence: for any h̄ ∈ F Aℓ(n + 1),

F Aℓ(n + 1)/ < f >_{cl}⊧ ξ(h̄+ < f >_{cl}) iff F Aℓ(n + 1) ⊧ ξ^{r}(h̄, f),

by induction on the complexity of the formula. It suffices to prove it for atomic formulae. This is immediate as t(h̄+ < f >_{cl}) = 0 iff t(h̄) ∈< f >_{cl} iff t(h̄)|_{Z(f)} = 0 iff Z(t(h̄)) ⊇ Z(f). By the minimality of Z(f) (subject to χ(f)), the zero set of f comprises a single piece of dimension n; hence the last equivalent condition holds iff R(t(h̄), f). □

Let f > 0 be such that F Aℓ(n + 1)/ < f >_{cl}≅ F Aℓ(n) and let ϑ be this isomorphism. By the induction hypothesis on F Aℓ(n), we get that

F Aℓ(n) ⊧ ψ_{n,k}(ϑ(h+ < f >_{cl}) iff dim(Z(h) ∩ Z(f)) = k,

for k = −1, ⋯, n − 1. Since ϑ is an isomorphism, we also get that

F Aℓ(n + 1)/ < f >_{cl}⊧ ψ_{n,k}(h+ < f >_{cl}) iff dim(Z(h) ∩ Z(f)) = k.

We are now ready to define the formulae ψ_{n+1,i}(x), for i = −1, ⋯, n.

Definition 4.1. Recall that ψ_{n+1,n}(x) has been defined by:

∃g (g ⊥ x and g ≠ 0).

Then for −1 ≤ i ≤ n − 1, define ψ_{n+1,i}(x) to be the formula

¬ψ_{n+1,n}(x) and ∃f [χ(f) and ∀f′ ≥ f (χ(f′) → ψ_{n,i}^{r}(x, f′))] and

¬[∃f(χ(f) and ⋁_{0<j<n−i} ψ_{n,i+j}^{r}(x, f))].

Remarks: (1) If we denote the block of quantifiers of maximal complexity in the formulae ψ_{m,k} in prenex forms by Q (where 0 ≤ k ≤ m − 1 and 2 ≤ m ≤ n), then we get that the complexity of the formulae ψ_{n+1,k} is at most max{∃∀∃∀∃, ∃∀Q, ∀¬Q}.

(2) By construction, these formulae ψ_{n+1,i}, −1 ≤ i ≤ n, are pairwise inconsistent.

It remains to prove that they really capture the notion of dimension (in 𝔼_{n+1}).

Lemma 4.7. Let h ∈ F Aℓ(n + 1)_{+}. Suppose that dim(Z(h))=i, for some −1 ≤ i ≤ n − 1. Then there is f ∈ F Aℓ(n + 1)_{+} such that χ(f) and dim(Z(h) ∩ Z(f))=i and F Aℓ(n + 1) ⊧ ψ_{n+1,i}(h).

Conversely, if F Aℓ(n + 1) ⊧ ψ_{n+1,i}(h), then dim(Z(h))=i.

Proof: Let h > 0 and assume that dim(Z(h))=i. So its zero set contains the positive span of (i + 1) ℝ-linearly independent elements: u_{1}, ⋯, u_{i+1}. Without loss of generality, we may assume that this span is maximal with these properties. Complete this set to a basis of ℤ^{n+1} and obtain u_{1}, ⋯, u_{n+1}. Let σ be the transformation sending (u_{1}, ⋯, u_{n+1}) to (e_{1}, ⋯ e_{n+1}) the canonical basis of ℤ^{n+1}. It is a piecewise linear integral homeomorphism. Let f ∈ F Aℓ(n + 1)_{+} with zero set the ℝ-span of u_{1}, ⋯, u_{n}. Then, F Aℓ(n + 1)/ < f >_{cl}≅ F Aℓ(n + 1)/ < π_{n+1} >_{cl}≅ F Aℓ(n). Denote by ς the isomorphism between F Aℓ(n + 1)/ < f >_{cl} and F Aℓ(n). As in the proof of Lemma 4.5, we have that F Aℓ(n + 1) ⊧ χ(f) and F Aℓ(n + 1) ⊧ ¬χ(f′) whenever Z(f′) ⊊ Z(f).

By the induction hypothesis applied to F Aℓ(n), we have dim Z(ς(h+ < f >_{cl})) = i iff F Aℓ(n) ⊧ ψ_{n,i}(ς(h+ < f >_{cl}) iff F Aℓ(n + 1)/ < f >_{cl}⊧ ψ_{n,i}(h+ < f >_{cl}) iff, by the preceding Lemma, F Aℓ(n + 1) ⊧ ψ_{n,i}^{r}(h, f). Finally, we have that dim Z(h) ∩ Z(f) = i iff dim Z(ς(h+ < f >_{cl})) = i.

Now assume that F Aℓ(n+1) ⊧ ψ_{n+1,i}(h); so there is f > 0 such that for all f′ ≥ f with χ(f′) we have ψ_{n,i}^{r}(h, f′). Choose f′ as in Lemma 4.5; i.e., such that

F Aℓ(n + 1)/ < f′ >_{cl}≅ F Aℓ(n + 1)/ < π_{n+1} >_{cl}≅ F Aℓ(n)

and f′ also satisfies the minimality assumption. Let ς be the above isomorphism. We may apply Lemma 4.6. By hypothesis, we have that F Aℓ(n + 1) ⊧ ψ_{n,i}^{r}(h, f′); it follows that F Aℓ(n + 1)/ < f′ >_{cl}⊧ ψ_{n,i}(h+ < f′ >_{cl}). Hence we get that F Aℓ(n) ⊧ ψ_{n,i}(ς(h+ < f′ >_{cl})). By induction hypothesis, we have that dim(Z(ς(h+ < f′ >_{cl} )))=i. So, by Lemma 4.5 again, we have that dim(Z(f′) ∩ Z(h)) = i. Therefore, dim(Z(h)) ≥ i. Suppose that dim(Z(h)) = j > i. Then by the first part of the lemma, there would be g > 0 such that χ(g) and F Aℓ(n + 1) ⊧ ψ_{n,j}^{r}(h, g). This contradicts F Aℓ(n + 1) ⊧ ψ_{n+1,i}(h). □

Proof of Theorem 4.3 (continued): We apply Lemmata 4.5, 4.6 and 4.7.

Observe first that the formulae ψ_{n,n−1}(x, y) and θ(x) are independent of n. So if m ≤ n and h ∈ F Aℓ(m)_{+}, then

F Aℓ(m) ⊧ ψ_{n,n−1}(h) iff F Aℓ(m) ⊧ ψ_{m,m−1}(h)

and

F Aℓ(m) ⊧ ϕ_{n,n−1}(h) iff F Aℓ(m) ⊧ ϕ_{m,m−1}(h).

It follows that χ(x, y, z) and χ(x) are likewise independent of n, whence so is the passage from a formula ξ(x̄) to ξ^{r}(x̄, y).

Let n > j and let σ_{n,j} be the sentence (∃h > 0)ψ_{n,j}(h). By Lemmata 4.5, 4.6 and 4.7, F Aℓ(n) ⊧ σ_{n,j}.

So to prove the theorem, it is enough to establish (by induction on m ≥ 2)

(∀n > m) F Aℓ(m) ⊧ ¬σ_{n,0} (Hyp(m)).

We first establish Hyp(2).

Let h ∈ ℤ_{+}^{k}. We write Z(h) for {i ∈ {1, …, k} : h(i) = 0}. By the definitions of ψ_{2,1}, ϕ_{2,1} and χ,

(I) ℤ^{k} ⊧ ψ_{2,1}(h) iff Z(h) ≠ ∅, and (II) Z(h) = ∅ if ℤ^{k} ⊧ χ(h). Hence (III) ℤ^{2} ⊧ χ(h) iff Z(h) = ∅, and (IV) ℤ^{k} |̸= χ(h) if k ≥ 3.

Further, by taking g = (1, 1) in the formula ϕ_{2,1} and noting that any (x, y) with x, y > 0 can be written as (x, 0) ∨ (0, y), it follows that

(V) ℤ^{2} |̸= ϕ_{2,1}(0)

Note that if f ∈ F Aℓ(2)_{+} and F Aℓ(2) ⊧ χ(f), then Z(f) is a finite set of points, say k, with k ≥ 2. Thus by (I) — (V), we have F Aℓ(2)/⟨f⟩_{cl} ≅ ℤ^{k}. Therefore

(VI) F Aℓ(2) ⊧ ψ_{2,1}^{r}(h, f) and χ(f) iff dim(Z(h)) ≥ 0.

Moreover if f, f′ ∈ F Aℓ(2)_{+} are such that F Aℓ(2) ⊧ χ(f) and χ(f′), then

(VII) F Aℓ(2) ⊧ χ^{r}(f, f′) iff Z(f) ∩ Z(f′) = ∅.

Now assume m = 2 and n = 3. By the way of contradiction, suppose that F Aℓ(2) ⊧ ψ_{3,0}(h) for some h ∈ F Aℓ(2)_{+}. By the last clause of the definition of ψ_{3,0} and (VI), we know that dim(Z(h)) = −1. Further, by the previous clause in that definition, there is f ∈ F Aℓ(2)_{+} with |Z(f)| = 2 such that F Aℓ(2) ⊧ χ(f) and ψ_{2,0}^{r}(h, f). Hence ℤ^{2} ≅ F Aℓ(2)/⟨f⟩_{cl} ⊧ ψ_{2,0}(h + ⟨f⟩_{cl}). By the definition of ψ_{2,0} and (I) we have h + ⟨f⟩_{cl} = (a, b) with a, b > 0 (since ℤ^{2} ⊧ ¬ψ_{2,1}(h + ⟨f⟩_{cl}) ), whence f_{1} = (a, 0) and f_{2} = (0, b) in the definition. Since f_{1} ∧ f_{2} = 0, it follows that ℤ^{2} ⊧ ϕ_{2,1}(0). This contradicts (V) and establishes the m = 2, n = 3 case.

To complete the proof of Hyp(2), let n > 3. We prove that F Aℓ(2) ⊧ ¬σ_{n,j} for all j with −1 ≤ j ≤ n − 4. Indeed, we will show that for any h ∈ F Aℓ(2)_{+},

F Aℓ(2) ⊧ ψ_{n,n−1}(h) or (∃f > 0) [χ(f) and (ψ_{n−1,n−2}^{r}(h, f) or ψ_{n−1,n−3}^{r}(h, f))].

Suppose that h ∈ F Aℓ(2)_{+}.

Case 1. dim(Z(h)) = 1. By Lemma 4.4, F Aℓ(2) ⊧ ψ_{2,1}(h) iff Z(h) is 1-dimensional. Since ψ_{n−1,n−2}(x)

is exactly the same formula as ψ_{2,1}(x), when we take the relativized formula with respect to Z(f), we get that F Aℓ(2) ⊧ ψ_{n−1,n−2}^{r}(h, f).

Case 2. dim(Z(h)) = 0. Choose f ∈ F Aℓ(2)_{+} such that |Z(f)| = 2 (whence F Aℓ(2) ⊧ χ(f)). Then

F Aℓ(2) ⊧ ψ_{n−1,n−2}^{r}(h, f) by (VI).

Case 3. dim(Z(h)) = −1. Thus F Aℓ(2) ⊧ ¬ψ_{n,n−1}(h) and ¬[∃f(χ(f) and ψ_{n−1,n−2}^{r}(h, f))].

Choose f, f′ ∈ F Aℓ(2)_{+} with |Z(f)| = 2 = |Z(f′)| and Z(f′) ∩ Z(f) = ∅. Therefore, by (VII),

F Aℓ(2) ⊧ χ^{r}(f′, f) and ∀g ≥ f′ (χ^{r}(g, f) → ψ_{n−2,n−3}^{r^{(2)}}(h, g, f)).

Hence Hyp(2) as

F Aℓ(2) ⊧ (∃f > 0) [χ(f) and (ψ_{n−1,n−3}^{r}(h, f))].

Now assume Hyp(k) holds but Hyp(k + 1) fails. Then for some h ∈ F Aℓ(k + 1)_{+} and n + 1 > k + 1, we have F Aℓ(k + 1) ⊧ ψ_{n+1,0}(h). By definition, we have that

F Aℓ(k + 1) ⊧ ¬ψ_{n+1,n}(h) and ∃f [χ(f) and ∀f′ ≥ f (χ(f′) → ψ_{n,0}^{r}(h, f′))] and

¬[∃f(χ(f) and ⋁_{0<i<n} ψ_{n,i}^{r}(h, f))].

Since the formula ψ_{n+1,n} does not depend on n, it is equivalent to ψ_{k+1,k}; so Z(h) has dimension k_{0}, say, with k_{0} ≤ k − 1. By Lemma 4.5, there is f′ ≥ f such that F Aℓ(k + 1) ⊧ χ(f′) and F Aℓ(k + 1)/ < f′ >_{cl}≅ F Aℓ(k). By Lemma 4.6, F Aℓ(k) ⊧ ψ_{n,0}(h̄), where h̄ is the image of h+ < f′ >_{cl} in F Aℓ(k)_{+}. This contradiction to Hyp(k) completes the induction step, and hence the proof of the theorem. □

By the above, one can express by formulae (though of different complexities in each F Aℓ(n)) the fact that a zero set is empty. We now show that we can interpret in each F Aℓ(n) the lattice of zero sets of elements of F Aℓ(n) for n ≥ 2. For n > 2, this will imply the desired undecidability results. The idea of the proof is to use a result of A. Grzegorczyk on the undecidability of some topological theories (see Theorems 5 and 6 in [7]). By interpreting Peano arithmetic, he showed that (assuming certain separation axioms) the theory of a class of closed subsets is undecidable.

Define a topology on ϕ(ℤ^{n+1})∩S^{n} as follows. The closed sets are the images under ϕ of the closed polyhedral cones in ℤ^{n+1}, the zero sets of the elements of F Aℓ(n+1) (by Proposition 2.1). Let Zer(S^{n}) denote this set of closed subsets of S^{n}. We next observe that for n ≥ 2, the topological space Zer(S^{n}) satisfies Grzegorczyk’s conditions and furthermore, in any F Aℓ(n + 1), we can interpret the lattice of these closed subsets of S^{n}. To prove this we recall the separation and connectedness conditions required on the space:

The topological space must be Hausdorff, connected, and satisfy the axiom of normality (namely, two disjoint closed sets have disjoint neighbourhoods), the second axiom of countability (namely it has a countable basis), any non-empty closed subset has to contain an atom (i.e. a closed subset which is minimal). Further, if A and B are two finite closed subsets, then

(i) if A ∩ B = ∅ and A ∪ B is included in a connected open subset E, then there exist two connected open sets C ⊃ A and D ⊃ B such that the intersection of their closures is empty and their union included in E; and (ii) if there exists a bijection between A and B, then there exists a closed set C such that A ∪ B ⊂ C and every component D of C contains exactly one point of A and one point of B (see paragraphs 2 and 3 in [7]). (Recall that a component is the union of all connected subsets of C containing a given element of C.)

Note that properties (i) and (ii) fail in S^{1}.

Theorem 4.8. (Zer(S^{n}), ∩, ∪, −, =, 0, 1) is interpretable in (F Aℓ(n+1), +, −, ∧, ∨, 0).

Proof: In the proof of Theorem 4.3 we obtained a formula expressing that the zero set of a positive element f is empty; for simplicity, we will write Z(v) = ∅ for the formula expressing this. We also have the definability of the lattice operations in Zer(S^{n}). The constant 1 is given by 1 = Z(0), the constant 0 = Z(f) for any function f for which ψ_{n+1,−1}(f) holds; i.e., for which Z(f) = ∅.

We have already defined the union and intersection of zero sets of positive elements; they correspond to the lattice operations in F Aℓ(n + 1).

We next define the complement; this is done using the fact that we can express the fact that a zero set is empty.

Assume that f, g > 0. The relative complement Z(g) in Z(f) will be defined as Z(h), where h > 0 and satisfies the formula θ′′(h, f, g); this latter will be a formula θ′(h, f, g) with an additional minimality assumption. Let θ′(h, f, g) be:

h ≥ f and (∀k ≥ f)Z(k ∨ [h ∧ (f ∨ g)]) ≠ ∅,

and θ′′(h, f, g) be θ′(h, f, g) and

¬[(∃h_{1} ≥ h)[θ′(h_{1}, f, g) and (∃h_{2} > 0)(h ≥ h_{1} ∧ h_{2} and Z(h_{1} ∨ h_{2}) = ∅ ≠ Z(h_{2})).

Finally, observe that the equivalence relation ∼ is now definable in F Aℓ(n + 1) since Z(f) = Z(g) iff their symmetric difference is empty. □

Corollary 4.9. (F Aℓ(n), +, −, ∧, ∨, 0) is undecidable, for n ≥ 3. □

5. Free vector lattices.

Let F V ℓ(n), n ∈ ℤ_{+}, be the free vector lattice (over ℝ) on n generators. We will consider it as an L_{ℝ}-structure where L_{ℝ}:={+, −, 0, ∧, ∨, r· : r ∈ ℝ}, and r· is an unary function symbol that will be interpreted by scalar multiplication by r ∈ ℝ. F V ℓ(n) can be represented as the real vector lattice of all continuous piecewiselinear functions from ℝ^{n} to ℝ with pointwise operations and scalar multiplication by elements of ℝ. All the technical results we developed for F Aℓ(n) also hold in F V ℓ(n). [Usually, they are first proved for free vector lattices and then adapted to F Aℓ(n).]

So, applying the same techniques as previously, we get:

Theorem 5.1. For n = 1, 2, the structures F V ℓ(n) have decidable theories, and for n > 2, the theories are undecidable. Moreover, they are pairwise non-elementarily equivalent.

Proof: The decidability result for n = 1, 2 relies this time on the quantifier elimination and decidability results for the theory of divisible totally ordered abelian groups. □

References

[1] K.A. Baker, Free vector lattices, Canad. J. Math. 20 (1968) 58-66.

[2] W.M. Beynon, Duality theorems for finitely generated vector lattices, Proc. London Math.Soc. (3) 31 (1975) 114-128.

[3] C.C. Chang, H.J. Keisler, Model Theory, North Holland Pub. Co., (Amsterdam), 1973.

[4] H.B. Enderton, A mathematical introduction to logic, Academic Press, Inc.(London), 1972.

[5] R. Freese, Free modular lattices, Trans. American Math. Soc. 261 (1980) 81-91.

[6] A.M.W. Glass, Partially ordered groups, Series in Algebra, volume 7, World Scientific Pub. Co. (Singapore), 1999.

[7] A. Grzegorczyk, Undecidability of some topological theories, Fund. Math. 38 (1951) 137-152.

[8] W.M. Schmidt, Diophantine Approximation, Lecture Notes in Mathematics 785, Springer-Verlag, 1980.

[9] W. Szmielew, Elementary properties of abelian groups, Fund. Math. 41 (1954) 203-271.

A. M.W. Glass, DPMMS, Wilberforce Road, Cambridge CB3 OWB, England

 E-mail address: amwg@dpmms.cam.ac.uk

Angus Macintyre, Department of Maths. and Stats., James Clerk Maxwell bldg., Edinburgh University, Mayfield Road, Edinburgh EH9 3JZ, Scotland

 E-mail address: angus@maths.ed.ac.uk

Françoise Point, Institut de Mathématique et Informatique, Université de Mons-Hainaut, Le Pentagone, 6, avenue du Champ de Mars, B-7000 Mons, Belgium

 E-mail address: point@logique.jussieu.fr