9
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Perhaps it is worth pointing out that "There are infinitely many primes" is formulated as "There is always a bigger prime", so when you say there are infinitely many primes can be false what you mean is that the set of primes is bounded. $\endgroup$ – Asaf Karagila May 28 '16 at 5:48
  • $\begingroup$ @AsafKaragila That's a good point - fixed. $\endgroup$ – Noah Schweber May 28 '16 at 5:48
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Note, however, that this doesn't provide an example for the specific model the OP mentions. $\endgroup$ – Noah Schweber May 28 '16 at 5:33
  • $\begingroup$ Sure, but also note that the question is "What is an example of how the first order induction schema fails in a computable, nonstandard model of $Q$?", and there are many computable nonstandard models of Q. $\endgroup$ – Asaf Karagila May 28 '16 at 5:46
  • $\begingroup$ Yes - I didn't want to give the impression that I thought this was a bad answer, I just wanted to clarify for the OP. $\endgroup$ – Noah Schweber May 28 '16 at 5:47
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.