Nonstandard models of Presburger Arithmetic

Question

I have a question about nonstandard models of Presburger Arithmetic. I read that an example of a nonstandard model is the set of polynomials with rational coefficients with positive leading coefficient and a (positive) integer constant coefficient. It is obvious that all axioms other than the induction axiom schema are satified; but how can one prove that the induction axiom holds?

Answer 1

As you describe it,

the set of polynomials with rational coefficients with positive leading coefficient and a (positive) integer constant coefficient

is not a model of Presburger arithmetic. Presburger arithmetic proves $$ \forall a : a=0 \lor a=1 \lor \exists b: a=b+1+1 $$ but this is not true in your model for $a=X+1$ (where $X$ is the formal variable in the polynomial).

I think that you might get a model if you allow the constant term to be negative when it is not the leading coefficient. In that case $X$ would intuitively model "infinity", and $X^2$ an even larger infinity and so forth. Then a more-or-less standard compactness argument shows that Presburger arithmetic must have a model containing at least all of these elements, but don't ask me for proof that there's enough of them to constitute a model.

A proof will probably not attempt to verify each axiom directly, but will instead prove that the model is elementarily equivalent to the ordinary naturals, relative to the restricted language of Presburger Arithmetic. Some form of quantifier elimination may work.

Answer 2

A simple model of Presburger's arithmetic is a subset of complex numbers

$$ M=\{a+bi: a \in Z \land b \in Q \land b \geq 0 \land (b=0 \implies a\geq 0) \} $$

with addition and two constants (0+0i) and (1+0i).

See editor's remarks to the paper of Th. Skolem published in 1934 in Fundamenta Mathematice. pp.150-161 (available here) The editor (presumably A. Tarski) attributes this remark to S. Jaśkowski.