Robinson arithmetic and its incompleteness

Solution 1:

Long comment ...

See Peter Smith, An Introduction to Gödel's Theorems (1st ed 2007), page 56 :

Ch.8.4 $\mathsf Q$ [Robinson Arithmetic] is not complete

The counterexample assume two "rogue" elements $a,b$ such that :

$Sa = a$ and $Sb = b$.

In this way, Axioms 1 to 3 are satisfied.

Then :

re-interpret $\mathsf Q$’s function ‘+’. Suppose we take this to pick out addition*, where

$m+^∗ n = m+ n$ for any natural numbers $m, n$ in the domain, while

$a +^∗ n = a$ and $b +^∗ n = b$.

Further, for any $x$ (whether number or rogue element),

$x +^∗ a = b$ and $x +^∗ b = a$.

It is easily checked that interpreting ‘+’ as addition* still makes Axioms 4 and 5 true. But by construction,

$0 +^∗ a \ne a$,

so this interpretation makes $∀x(0 + x = x)$ false.

Added

See John Burgess, Fixing Frege (2005), page 56 :

None of the usual associative, commutative, or distributive laws for addition and multiplication can be proved in $\mathsf Q$ nor can even the law $Sx \ne x$. As to this last point, a natural model of $\mathsf Q$ is provided (as Saul Kripke pointed out to the author) by the cardinal numbers, with $S(x)$ defined as $x+1$. For infinite cardinals we then have $Sx=x$.

Solution 2:

It looks like that ought to work -- all you need to check is whether the recursion equations for $\times$ are satisfied by your definitions when one or both free variables are instantiated to $\mathsf a$ or $\mathsf b$.

You could also choose to set $n\times \mathsf a = n\times \mathsf b = \mathsf b$; either choice will work.

Solution 3:

As a footnote to Mauro's answer, the question is set in one of the exercise sheets for the Gödel book, and you'll find the answer spelt out in the solution sheet (for Qn2) here:

http://www.logicmatters.net/resources/pdfs/godelexercises/ArithWoInd_solutions.pdf