The additive structure of models of arithmetic

It is shown that for a model of Presburger arithmetic to have an expansion to a model of Peano arithmetic it is necessary that the model be recursively saturated. For countable models this condition is also sufficient; for uncountable models it is not. This note arises from consideration of the question of when a model of Presburger arithmetic (Pr) (see the definition below) can be expanded to a model of Peano arithmetic (P). In the countable case an answer is given by the following: THEOREM 1. A countable, nonstandard model of Presburger arithmetic can be expanded to a model of Peano arithmetic if and only if it is recursively saturated. In [3] it is shown that the recursively saturated models of P are just the nonstandard models of P which can be expanded to models of a certain fragment of analysis. Theorem 1 again involves the application of the abstract characterization of recursive saturation to an even more familiar algebraic setting. Theorem 1 is proved in ? 1. The analogy, however, between this result and that of [3] does not go any further. While the main result of [3] holds without modification for all infinite cardinalities, Theorem 1 does not extend as shown by the example of ?2 below. The complete generality of the main result of [3] is easy to understand in view of the simple expansion which is given in a uniform way. The expansion provided for by Theorem 1 is obtained in a completely nonconstructive fashion from the general fact that countable recursively saturated models are resplendent [2]. This nonconstructivity can be explained, at least in part, by Theorem 2 of ?3. DEFINITIONS. (1) Presburger arithmetic (Pr) is the theory of the additive semigroup . We shall think of Pr in the language n=1,2,3,..., since in this language Pr admits an elimination of quantifiers [6]. < and=n are definable from 0, 1, and +. A complete set of axioms for Pr is: (i) The axioms for discretely ordered abelian semigroups with 0, and smallest nopzero element 1. (ii)x

Keywords:

• Peano axioms
• Uncountable set
• Arithmetic
• Countable set
• Semigroup
• Discrete mathematics
• Additive function
• Axiom
• Analogy
• Presburger arithmetic
• Mathematics
• Abelian group

• Correction
• Source
• Cite
• Save
• Machine Reading By IdeaReader