Countable Pseudo-Recursively Saturated Models of Presburger Arithmetic
The following is a brief overview of Presburger arithmetic and pseudo-recursive saturation, which form the basis of my Ph.D. thesis. You can also read my thesis abstract
, or get a copy of my entire thesis from the links at the end of this page. If you are interested in this area of mathematics then please feel free to e-mail
me. Any suggestions or information will be gratefully received.
is a model of Presburger arithmetic if
is an Abelian group with binary operation +, < a linear order and such that
- (i.e. order respects );
- (i.e. order is discrete);
- for each .
we use the following notation:
It's also worth pointing out that A3
constitutes an axiom schema rather than a single axiom, which defines the congruence classes of elements mod
. The least positive element described in axiom A2
will also be referred to as 1.
we can define the residue map,
Presburger arithmetic constitutes the theory of addition, for example, as we might expect it to hold in the integers Z
It is straightforward to show (using our element
) that any model of Presburger arithmetic will have a copy of Z
embedded in it. It's therefore possible to consider the quotient group
of a model of Presburger arithmetic, which by A3
will be divisible. An automorphism of
can always be lifted to an automorphism of
. Combine this with the divisibility of
and we discover that the construction of automorphisms becomes considerably easier.
A representation of a model of Presburger arithmetic
The notion of a pseudo-recursively saturated model of Presburger arithmetic was developed by Richard Kaye
using ideas from a paper by Victor Harnik
. No explicit definition of the notion has yet been published. In order to provide a definition here, we first need some other concepts.
and consider this as a Dedikind cut identified with some extended real
so we can extend this definition to cover the quotient group. i.e.
is well defined and equal to
Although these 'standard parts' are not actually fractions, they share many of the properties of fractions and with care can often be manipulated in similar ways. For a model
we refer to the set of all such standard parts for the model as
is strongly independent
is linearly independent over
as a subset of
with the set of 'values'
We use these definitions of standard parts
to provide a definition for what we mean by pseudo-recursive saturation.
is a countable model of Presburger arithmetic with
then we say that
is pseudo-recursively saturated
- for , each has dense pre-image;
- for with , there is some such that
- the set of values is a dense linear order with respect to < having least point 0 and no greatest point.
Pseudo-recursive saturation is designed to capture the properties of a models of Presburger arithmetic which allow automorphisms to be created relatively easily. Normally we might consider models which were recursively saturated
, however in the Presburger case this condition is too strong, and for this reason we prefer the weaker condition of pseudo-recursive saturation. It is straightforward to show that
, whilst the reverse direction is not the case. PRS is not, however, any form of saturation in the model theoretic sense.
The following result gives an indication of why PRS is useful.
is countable PRS and that
are strongly independent subsets of
which satisfy the following:
- for all ;
- for all .
Then there exists an automorphism
is taken to be countable, a proof of this can be found by a back-and-forth construction. The PRS models of Presburger arithmetic are also closely connected to homogeneous models and the above result can be used to show one aspect of this connection.
The main project of my Ph.D. was to discover all of the closed normal subgroups of the automorphism group of the models described above. It turns out that this can be done using the notion of stQ-closure.
- each is non-empty and closed under pointwise multiplication;
- each is closed under inversion (where );
- when and then ;
- when and then there exists at least one so that .
We find that for a countable PRS model of Presburger arithmetic with trivial centre, the proper non-trivial closed normal subgroups of the automorphism group of
are precisely the sets
is stQ-closed and
In the above expression we have written maps on the right and
refers to the set of automorphisms which preserve values
, that is, the set of all automorphisms
. The only two closed normal subgroups which cannot be written in the above form are therefore the whole automorphism group and also the trivial group containing only the identity map. All other closed normal subgroups, however, can be written as some
and all such
constitute closed normal subgoups.
Having found all such closed normal subgroups we may be able to discover more properties of the automorphism group, and since automorphisms preserve properties of the Presburger model this may then shed new light on essential properties of Presburger arithmetic. One obvious result which follows from the description of the closed normal subgroups given above is that there are precisely
closed normal subgroups of the automorphism group for a model of Presburger arithmetic as described above.
If you would like to dowload a complete copy of my Ph.D. thesis, please click on one of the links:
Or just the abstract
You can also download a poster 'A Galois Correspondence for Z-Groups' which gives a survey of my research into Presburger arithmetic. I first exhibited this at the LMS regional meeting
, held in Birmingham University in February 2001:
Finally, if those haven't yet put you off, download the slides for a talk I gave in Oxford, also in February 2002, entitled 'Automorphisms of Models of Presburger Arithmetic':
-like Recursively Saturated Models of Presburger Arithmetic; Journal of Symbolic Logic, Volume 51, Number 2, June 1996.