Wikipedia in Italian has a sketch-of-proof that Robinson arithmetic is not complete, since commutativity of addition is undecidable. The sketch of proof creates a model that adds two elements, $a$ and $b$, to the usual natural numbers: then it goes on by defining
$\mathsf{S(a)=b}$
$\mathsf{S(b)=a}$
$\mathsf{\forall n\in N \; (a+n = a)}$
$\mathsf{\forall n\in N \; (b+n = b)}$
$\mathsf{\forall n\in N \; (n+a = b)}$
$\mathsf{\forall n\in N \; (n+b = a)}$
$\mathsf{a+a=b}$
$\mathsf{b+b=a}$
$\mathsf{a+b=a}$
$\mathsf{b+a=b}$
and saying "we could also define multiplication, but it is useless, since we already have that $\mathsf{b+a} \ne \mathsf{a+b}$". But I am not sure that the model may actually be extended to multiplication. I tried with
$\mathsf{a\times b=b}$
$\mathsf{b\times b=a}$
$\mathsf{b\times a=a}$
$\mathsf{a\times a=b}$
$\mathsf{\forall n\in N \; a\times n=b}$
$\mathsf{\forall n\in N \; b\times n=a}$
[EDIT]: of course $\mathsf{ a\times 0 = b\times 0 =0}$
but I am stuck with $\mathsf{n\times a}$ and $\mathsf{n\times b}$; it seems to me that setting all of them to $\mathsf{a}$ should work, but I am not sure about it. Could someone help me?
P.S.: I read this question, and I understand that just a single element $\mathsf{a}$ may be added. But I'd prefer to have the implicit axiom that $\mathsf{\forall x \; (S(x) \ne x)}$.
$\endgroup$ 53 Answers
$\begingroup$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:
$\endgroup$ $\begingroup$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 :
$\endgroup$ 6 $\begingroup$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$.
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.
$\endgroup$ 1
