Nonstandard models of Presburger ArithmeticI 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?

Question

tektonikafrs · Accepted Answer

Step 1As you describe it,the set of polynomials with rational coefficients with positive leading coefficient and a (positive) integer constant coefficientis not a model of Presburger arithmetic. Presburger arithmetic proves  ∀  a  :  a  =  0  ∨  a  =  1  ∨  ∃  b  :  a  =  b  +  1  +  1but this is not true in your model for   a  =  X  +  1 (where X is the formal variable in the polynomial).Step 2I 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 &quot;infinity&quot;, 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&#039;t ask me for proof that there&#039;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.

Jadon Camacho · Accepted Answer

Step 1A simple model of Presburger&#039;s arithmetic is a subset of complex numbers  M  =  {  a  +  b  i  :  a  ∈  Z  ∧  b  ∈  Q  ∧  b  ≥  0  ∧  (  b  =  0    ⟹    a  ≥  0  )  }Step 2with addition and two constants   (  0  +  0  i  ) and   (  1  +  0  i  )

Answered question

Answer & Explanation

New Questions in Algebra II