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

nyle2k8431

nyle2k8431

Answered question

2022-11-14

Nonstandard models of Presburger Arithmetic
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 & Explanation

tektonikafrs

tektonikafrs

Beginner2022-11-15Added 15 answers

Step 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
a : a = 0 a = 1 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).
Step 2
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.
Jadon Camacho

Jadon Camacho

Beginner2022-11-16Added 2 answers

Step 1
A simple model of Presburger's arithmetic is a subset of complex numbers
M = { a + b i : a Z b Q b 0 ( b = 0 a 0 ) }
Step 2
with addition and two constants ( 0 + 0 i ) and ( 1 + 0 i )

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?