A model of Presburger Arithmetic, (Γ, +, <, 0, 1), is an ordered abelian group with least positive element 1 satisfying the axiom schema

∀ x ∈ Γ ∃ y ∈ Γ ∃ i ∈ {0, 1, …, n − 1}(x = ny + i)

Definition 1. ℤ̂ is the group of sequences (r_{n})_{n∈ℕ} such that

0 ≤ r_{n} < n  for all n ≥ 1,
r_{nm} ≡ r_{n} (mod n) for all n, m ≥ 1,

where

(r_{n})_{n∈ℕ} + (s_{n})_{n∈ℕ} = (r_{n} + s_{n} (mod n))_{n∈ℕ}.

Definition 2. For Γ a Presburger group, the natural residue map

ϱ: Γ → ℤ̂

is the homomorphism

ϱ(γ) = (γ (mod 1), γ (mod 2), γ (mod 3), …)

for all γ ∈ Γ.

Definition 3. Γ is divisible if for all x ∈ Γ and all n > 0 from ℕ there is y ∈ Γ with ny = x.

Proposition 4. If Γ is a Presburger group then ℤ ↪ Γ as a convex subgroup, so Γ/ℤ is divisible.

Theorem 5. Suppose \overline{Γ} is a divisible ordered abelian group and \overline{ϱ}: \overline{Γ} → ℤ̂/ℤ a homomorphism. Then for some Presburger group Γ we have

Γ ⟶ Γ/ℤ ⟶^{θ} \overline{Γ}
↓ ϱ  ↓ \overline{ϱ}
ℤ̂ ⟶ ℤ̂/ℤ

where θ: Γ/ℤ → \overline{Γ} is an isomorphism and the unmarked arrows represent natural quotient maps.

Notation 6. We write \overline{ϱ}: \overline{Γ} → ℤ̂/ℤ to mean the induced map

ϱ/ℤ: Γ/ℤ → ℤ̂/ℤ.

Definition 7. Let α: \overline{Γ} → \overline{Γ} be an automorphism of \overline{Γ} as an ordered divisible abelian group so that

\overline{ϱ}(α(a)) = \overline{ϱ}(a) for all a ∈ \overline{Γ} .

Then we say the map α: \overline{Γ} → \overline{Γ} preserves residues and call α a residue-automorphism.

Proposition 8. If α: \overline{Γ} → \overline{Γ} is a residue-automorphism, then α lifts to an automorphism:

α̂: Γ → Γ.

Definition 9. Γ is homogeneous if for ā,b̄ ∈ Γ^{n} with tp(ā) = tp(b̄) there is some α ∈ Aut(Γ) with āα = b̄.

Definition 10. For a, b ∈ \overline{Γ} with a, b > ℤ, we define

st (\frac{a}{b}) = \{ q ∈ ℚ : qb < a\} .

This is an extended cut, identified with an extended real r ∈ [0, ∞] ⊆ ℝ ∪ \{∞\}, where r = sup st (\frac{a}{b}).

Lemma 11. For a, b, c ∈ \overline{Γ} , q ∈ ℚ the following hold:

1. st (\frac{a}{b}) · st (\frac{b}{c}) = st (\frac{a}{c}) provided the LHS is defined;

2. st (\frac{qa}{b}) = q · st (\frac{a}{b});

3. st (\frac{a}{qb}) = \frac{1}{q} · st (\frac{a}{b}) for q ≠ 0;

4. st (\frac{a+b}{c} ) = st (\frac{a}{c}) + st (\frac{b}{c}) provided the RHS is defined;

5. if a ≤ b then st (\frac{a}{c}) ≤ st (\frac{b}{c});

6. if st (\frac{a}{b}) ∉ \{0, ±∞\} then st (\frac{a}{b}) = st (\frac{b}{a})^{−1}.

Definition 12. If a, b ∈ \overline{Γ} then a ≡ b if either a = b = 0 or a, b ≠ 0 and

st (\frac{a}{b}) ∉ \{0, ±∞\}.

This is an equivalence relation so we may define:

Definition 13. V = \overline{Γ} /≡ is the set of values of \overline{Γ} and is linearly ordered by

a/≡ < b/≡ ⟺ a/≡ ≠ b/≡ and |a| < |b|.

The valuation map v : \overline{Γ} → V is defined by

a ↦ a/≡.

v : \overline{Γ} → V has the following properties:

1. v(qa) = v(a) for all q ∈ ℚ \ {0};

2. if |a| ≤ |b| then v(a) ≤ v(b);

3. if n|a| < |b| for all n ∈ ℕ then v(a) < v(b);

4. st (\frac{a}{b}) = 1 ⇒ v(a − b) < v(a), v(b);

5. st (\frac{a}{b}) ≠ 1 ⇒ v(a − b) = max (v(a), v(b)).

Definition 14. The set B ⊆ \overline{Γ} is strongly independent if 0 ∉ B and every nontrivial ℚ-linear combination

a = q_{1}b_{1} + ⋯ + q_{n}b_{n}

has value

v(a) = max { v(b_{j}) : 1 ≤ j ≤ n, q_{j} ≠ 0}

where q̄ ∈ ℚ and b̄ ∈ B.

Lemma 15 (Exchange Lemma). If a_{1}, …, a_{n} are strongly independent in \overline{Γ} , and a ∈ \overline{Γ} then

either a ∈ ⟨a_{1}, …, a_{n}⟩
or ∃ a_{n+1} ∈ ⟨a_{1}, …, a_{n}, a⟩ such that a_{1}, …, a_{n}, a_{n+1}

are strongly independent and a ∈ ⟨a_{1}, …, a_{n}, a_{n+1} ⟩ .

Lemma 16. If \{x_{1}, …, x_{n}\} ⊆ \overline{Γ} and \{y_{1}, …, y_{n}\} ⊆ \overline{Γ} are both strongly independent sets, then the following are equivalent:

1. tp(x̄) = tp(ȳ);

2. ϱ(x_{i}) = ϱ(y_{i}) and st (\frac{x_{i}}{x_{j}} ) = st (\frac{y_{i}}{y_{j}} ) for all 1 ≤ i ≤ j ≤ n.

Proof. Follows from quantifier elimination.

Theorem 17. Suppose Γ is 2-homogeneous, then the following are equivalent:

1. Γ has no smallest non-standard value, and there is some nontrivial g ∈ G;

2. there is some x ∈ Γ with ϱ(x) = 0 and there are non-standard elements with value less than v(x);

3. there is a value-defying automorphism h ∈ G;

4. Γ contains a unique maximal convex submodel with values forming a dense linear order, with ϱ^{−1}(r) dense in Γ for all r and so that for all non-standard x, y, z ∈ Γ there is w ∈ Γ such that st (\frac{w}{z}) = st (\frac{x}{y}).

Definition 18. A Presburger group Γ is pseudo-recursively saturated if Γ ≅ℤ̸ and

1. for \overline{ϱ}: \overline{Γ} → ℤ̂/ℤ and each ℤ+r ∈ Im(\overline{ϱ}), the inverse image \overline{ϱ}^{−1}(ℤ+ r) is dense in \overline{Γ} ;

2. for x, y, z ∈ Γ with z ∉ ℤ, there is some w ∉ ℤ for which

st (\frac{w}{z}) = st (\frac{x}{y});

3. the set of values V is a dense linear order with respect to < having least point 0 and no greatest point.

Theorem 19. Let \overline{Γ} be prs and suppose that (a_{1}, …, a_{n}) = ā ∈ \overline{Γ} and (b_{1}, …, b_{n}) = b̄ ∈ \overline{Γ} are such that tp(ā) = tp(b̄). Then there are strongly independent sets {a′_{1}, …, a′_{n}} and {b′_{1}, …, b′_{n}} for which:

1. ⟨a_{1}, …, a_{n}⟩ = ⟨a′_{1}, …, a′_{n}⟩ and ⟨b_{1}, …, b_{n}⟩ = ⟨b′_{1}, …, b′_{n}⟩;

2. a_{i} = q_{1}a′_{1} + ⋯ + q_{n}a′_{n} if and only if b_{i} = q_{1}b′_{1} + ⋯ + q_{n}b′_{n} where q_{1}, …, q_{n} ∈ ℚ;

3. \overline{ϱ}(a′_{i}) = \overline{ϱ}(b′_{i}) for 1 ≤ i ≤ n;

4. st (\frac{a′_{i}}{a′_{j}} ) = st (\frac{b′_{i}}{b′_{j}} ) for 1 ≤ i ≤ j ≤ n.

Theorem 20. Suppose Γ is countable prs, and that

A = {a_{1}, a_{2}, …, a_{n}}, B = {b_{1}, b_{2}, …, b_{n}},

are strongly independent subsets of Γ with:

1. ϱ(a_{i}) = ϱ(b_{i}) for all 1 ≤ i ≤ n;

2. st (\frac{a_{i}}{a_{j}} ) = st (\frac{b_{i}}{b_{j}} ) for all 1 ≤ i, j ≤ n. Then there exists an automorphism θ: Γ → Γ mapping a_{i} to b_{i} for all i. Corollary 21. If Γ is countable prs then Γ is homogeneous.

Example 22.

G_{v} = {g ∈ G : v(γg) = v(γ) for all γ ∈ Γ}

is a non-trivial, proper, closed normal subgroup of G.

Theorem 23. Let Γ be countable prs with h ∈ G and suppose a_{1}, …, a_{n} ∈ Γ\ℤ and b_{1}, …, b_{n} ∈ Γ\ℤ are such that tp(ā) = tp(b̄). Suppose further that ∞ ∈ stQ (⟨h⟩). Then there are g_{1}, g_{2} ∈ G such that

āh^{g_{1}}h^{−g_{2}} = b̄.

Lemma 24. Suppose h ∈ G preserves values, and let g ∈ G be arbitrary. Then v(γg^{−1}hg) = v(γ) for all γ ∈ Γ.

Definition 25. If S_{n} ⊆ (stQ (\overline{Γ} ))^{n} ⊆ (ℝ_{>0}^{∗})^{n} and S = ⋃_{n∈ω} S_{n} then the stQ -closure properties are as follows:

1. Each S_{n} is nonempty and closed under pointwise multiplication;

2. each S_{n} is closed under pointwise inversion;

3. if (r_{1}, …, r_{n}) ∈ S and m ≤ n then (r_{1}, …, r_{m−1}, r_{m+1} , …, r_{n}) ∈ S;

4. if (r_{1}, …, r_{n}) ∈ S and m ≤ n + 1 then there exists at least one r′_{m} so that (r_{1}, …, r_{m−1}, r′_{m}, r_{m}, …, r_{n}) ∈ S.

Definition 26. If S ⊆ ⋃_{n∈ω}(stQ (\overline{Γ} ))^{n} is stQ -closed, then G_{S}^{<ω} is the set of residue automorphisms

G_{S}^{<ω} = { g ∈ G_{v} : ∀ n ∈ ω ∀ v(x_{1}) < ⋯ < v(x_{n})

(st (\frac{x_{1}g}{x_{1}}) , …, st (\frac{x_{n}g}{x_{n}})) ∈ S\} .

Theorem 27. If S ⊆ ⋃_{n∈ω}(stQ (\overline{Γ} ))^{n} is stQ -closed then G_{S}^{<ω} is a closed normal subgroup of G.

Theorem 28. Suppose N ⊴ G is a normal subgroup of residue automorphisms. If

S = \{(st (\frac{x_{1}g}{x_{1}}) , …, st (\frac{x_{n}g}{x_{n}})) : n ∈ ω, g ∈ N, v(x_{1}) < ⋯ < v(x_{n})\}

then S satisfies the stQ -closure properties and N ⊆ G_{S}^{<ω}.

Theorem 29. Suppose that G has trivial centre and that N is a closed normal subgroup of G. If

S = \{(st (\frac{x_{1}g}{x_{1}}) , …, st (\frac{x_{n}g}{x_{n}})) : n ∈ ω, g ∈ N, v(x_{1}) < ⋯ < v(x_{n})\}

then N = G_{S}^{<ω}.

Definition 30. Let γ_{1}, γ_{2} ∈ Γ. We say γ_{1} is close to γ_{2} if

st (\frac{γ_{1}}{γ_{2}} ) = 1 or γ_{1} = γ_{2} = 0.

We denote this property by writing γ_{1} ⌢ γ_{2}.

Proposition 31. Suppose h ∈ G preserves values. Suppose further that a_{1}, …, a_{n} ∈ \overline{Γ} are such that 0 < v(a_{n}) < ⋯ < v(a_{1}) and that b_{1}, …, b_{n} ∈ \overline{Γ} are such that tp(a_{i}) = tp(b_{i}) with st (\frac{b_{i}}{a_{i}}) ∈ stQ (h) for 1 ≤ i ≤ n. Then there is some w ∈ ⟨h^{G}⟩ such that a_{i}w ⌢ b_{i} for all 1 ≤ i ≤ n.

Proposition 32. Suppose h ∈ G is non-trivial, fixes some initial segment and that γh ⌢ γ for all γ ∈ \overline{Γ} . Suppose further that a_{1} < ⋯ < a_{n} ∈ \overline{Γ} are strongly independent, that 1 ≤ k ≤ n and that b_{k} ⌢ a_{k} so that \overline{ϱ}(b_{k}) = \overline{ϱ}(a_{k}). Then there exists some g_{k} ∈ ⟨h^{G}⟩ which fixes each a_{i} with v(a_{i}) ≥ v(a_{k}) except a_{k}, which maps a_{k} to b_{k} and so that γg_{k} ⌢ γ for all γ ∈ \overline{Γ} .

Corollary 33. Suppose h ∈ G is non-trivial, fixes some initial segment and that γh ⌢ γ for all γ ∈ \overline{Γ} . Suppose also that

{a_{1}, …, a_{n}} and {b_{1}, …, b_{n}}

are both strongly independent, that a_{i} ⌢ b_{i} with \overline{ϱ}(a_{i}) = \overline{ϱ}(b_{i}) and st (\frac{a_{i}}{a_{j}} ) = st (\frac{b_{i}}{b_{j}} ) for all 1 ≤ i, j ≤ n. Then there exists some

w ∈ ⟨h^{G}⟩ which maps w: a_{i} ↦ b_{i} for all 1 ≤ i ≤ n.

Proposition 34. If T_{1}, T_{2} ⊆ ⋃_{n∈ω}(stQ (\overline{Γ} ))^{n} are stQ -closed and there exists some (r_{1}, …, r_{n}) with

(r_{1}, …, r_{n}) ∈ T_{1} but (r_{1}, …, r_{n}) ∉ T_{2},

then there is a residue automorphism g ∈ G with g ∈ G_{T_{1}}^{<ω} but g ∉ G_{T_{2}}^{<ω}.

Proposition 35. Suppose T_{1} ⊆ T_{2}. Then G_{T_{1}}^{<ω} ⊆ G_{T_{2}}^{<ω}.

Proposition 36. Suppose T_{1} and T_{2} are both stQ -closed. Then ⟨T_{1} ∪ T_{2}⟩ = { t_{1}.t_{2} : t_{1} ∈ T_{1}, t_{2} ∈ T_{2}} is stQ -closed.

Definition 37. If S ⊆ ⋃_{n∈ω}(stQ (\overline{Γ} ))^{n} then the stQ -reduction of S is defined to be:

\overline{S}^{stQ} = ⋃ ; T ⊆⟨S⟩ T stQ -closed T.

Proposition 38. If S ⊆ ⋃_{n∈ω}(stQ (\overline{Γ} ))^{n} then \overline{S}^{stQ} is stQ -closed and \overline{S}^{stQ} ⊆ ⟨S⟩.

Proposition 39. Let T_{1} and T_{2} be stQ -closed. Then

G_{⟨T_{1}∪T_{2}⟩}^{<ω} = \overline{⟨G_{T_{1}}^{<ω} ∪ G_{T_{2}}^{<ω}⟩}.

Proposition 40. Let T_{1} and T_{2} be stQ -closed. Then

G_{\overline{T_{1}∩T_{2}}^{stQ}}^{<ω} = G_{T_{1}}^{<ω} ∩ G_{T_{2}}^{<ω} .

Definition 41. Let Γ_{v} ⊆ ⋃_{n∈ω} Γ^{n} be the set of tuples x̄ with v(x_{1}) < ⋯ < v(x_{n}).

Definition 42. If T is stQ -closed and x̄, ȳ ∈ \overline{Γ_{v}} we say that x̄ ∼_{T} ȳ if tp(x̄) = tp(ȳ) and

(st (\frac{x_{1}}{y_{1}} ) , …, st (\frac{x_{n}}{y_{n}})) ∈ T.

Lemma 43. Suppose x̄, ȳ ∈ Γ_{v} . Then x̄ ∼_{T} ȳ if and only if x̄g = ȳ for some g ∈ G_{T}^{<ω}.

Theorem 44. In the diagram:

1. G_{T_{1}}^{<ω} ⊆ G_{T_{2}}^{<ω} if and only if for all x̄, ȳ ∈ Γ_{v} we have x̄ ∼_{T_{1}} ȳ ⇒ x̄ ∼_{T_{2}} ȳ.

2. The arrows are bijections.

Proposition 45. Suppose ∼ is a G-invariant equivalence relation on Γ_{v} and that

1. if x_{1}, …, x_{n} ∼ y_{1}, …, y_{n} and m ≤ n then

x_{1}, …, x_{m−1}, x_{m+1} , …, x_{n} ∼ y_{1}, …, y_{m−1}, y_{m+1} , …, y_{n};

2. if x_{1}, …, x_{n} ∼ y_{1}, …, y_{n} and m ≤ n + 1 then there is at least one pair x′_{m}, y′_{m} with

x_{1}, …, x_{m−1}, x′_{m}, x_{m}, …, x_{n} ∼ y_{1}, …, y_{m−1}, y′_{m}, y_{m}, …, y_{n};

3. suppose x̄, ȳ are such that x̄ ⌢ ȳ, then x̄ ∼ ȳ.

Then there is an stQ -closed T with x̄ ∼ ȳ if and only if x̄ ∼_{T} ȳ.