How does induction fail in computable nonstandard models?

Tennenbaum's theorem does not apply to Robinson Arithmetic ($Q$). There is a computable, nonstandard model of $Q$ "consisting of integer-coefficient polynomials with positive leading coefficient, plus the zero polynomial, with their usual arithmetic."

What is an example of how the first order induction schema fails in a computable, nonstandard model of $Q$? Can such a model have a predicate, in the language of Q, that is only true for standard natural numbers and false for "infinite" natural numbers? Can a computable nonstandard model have overspill?

Given the model above, what is an example of a statement, in the language of $Q$, that is true for the zero polynomial and all successors of the zero polynomial and false for some other polynomial in the model?

Solution 1:

Here's an even simpler one: "Every number is either even or odd." That is, $$\forall x\exists y(x=y+y \mbox{ or } x=y+y+1).$$ The polynomial $x$ is a counterexample.

Ignoring the specific model and focusing on the theory, it's also worth noting that Robinson arithmetic doesn't even prove that addition is commutative or that the successor of a number is different from that number! (If I recall correctly, this is covered in Burgess' book Fixing Frege - see a review at http://www.utexas.edu/cola/_files/iaa4774/On_Burgess_Fixing_Frege.pdf.)

EDIT: Now that I look more closely, this is basically all covered in the wikipedia page on Robinson arithmetic, in the section "Metamathematics"; I suggest you read it and the linked references.

FURTHER EDIT: Here's even more statements, with easy induction proofs, that Robinson doesn't believe! :P (Note that these do in fact hold in the specific model in the OP.)

• $\sqrt{2}$ is irrational.

• There are infinitely many primes. More precisely, "for every $x$ there is a prime $>x$."

• Unique factorization into primes.

See Francois Dorais' answer to https://mathoverflow.net/questions/19857/has-decidability-got-something-to-do-with-primes.

Solution 2:

Here is another example, $$\forall x(S(x)\neq x)$$

It holds for $0$, and if it holds for $x$, then it holds for $S(x)$ as well. But it is possible to have a model with an element which is its own successor.

Solution 3:

For a sentence true for the ordinary natural numbers, but false in the polynomials described above, we can use $$\forall w\exists y_1\exists y_2\exists y_3\exists y_4(w=y_1^2+y_2^2+y_3^2+y_4^2),$$ since by a result of Lagrange every non-negative integer is the sum of $4$ squares, but the polynomial $x$ is not a sum of $4$ squares of polynomials.