Presburger Arithmetic and Pseudo-Recursive Saturation

David Llewellyn-Jones

School of Mathematics and Statistics The University of Birmingham Edgbaston, Birmingham, B15 2TT, U.K. llewelld@for.mat.bham.ac.uk www.mat.bham.ac.uk/llewelld/

August 2nd, 2001

The first half of this thesis looks at well known general properties of Presburger arithmetic, including quantifier elimination, types, compactness and homogeneity. It is accessible to the algebraist as well as the model theorist.

Let Γ be a model of Presburger arithmetic. Define the residue map ϱ: Γ → ℤ̂ sending an element to the sequence of its remainders and the standard part st (\frac{γ_{1}}{γ_{2}} ) ∈

ℝ ∪ \{±∞\} for γ_{1}, γ_{2} ∈ Γ to be the supremum of the set \{ \frac{r}{s} ∈ ℚ : rb < sa\}. Define a

partitioning of our model by the equivalence relation γ_{1} ≡ γ_{2} if and only if st (\frac{γ_{1}}{γ_{2}} ) ∉ {0, ±∞} and let v: Γ → Γ/ ≡ be the natural valuation.

We say that Γ is pseudo-recursively saturated if: the inverse image of the residue map is dense in Γ/ℤ; for x, y, z ∈ Γ there exists w ∈ Γ such that st (\frac{w}{z}) = st (\frac{x}{y}); and Γ/ ≡ forms a dense linear order with least point 0 and no greatest point.

We prove that pseudo-recursive saturation implies homogeneity and give results in the opposite direction indicating an affinity between the two.

Our main result concerns the automorphism group, G, of the countable pseudorecursively saturated models of Presburger arithmetic, giving a correlation between the closed normal subgroups of G and sets of tuples of the standard parts of the model. We define S ⊆ ⋃_{n∈ω} \{ st (\frac{γ_{1}}{γ_{2}} ) : γ_{1}, γ_{2} ∈ Γ\}^{n} to be stQ-closed if: all subsets of S defined to be those tuples of a certain length form a group; if (r_{1}, …, r_{n}) ∈ S and m ≤ n then (r_{1}, …, r_{m−1}, r_{m+1}, …, r_{n}) ∈ S; and similarly if m ≤ n + 1 then there exists some r′_{m} such that (r_{1}, …, r_{m−1}, r′_{m}, r_{m}, …, r_{n}) ∈ S. We then have that N is a closed normal subgroup of G if and only if N preserves some stQ-closed set S or N = G.

From this we are able to provide some results about the closed normal subgroups of G and to present a pair of Galois connections between closed normal subgroups of G, stQ-closed subsets of the set of standard parts and equivalence relations on Γ.