4
$\begingroup$

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$
5
  • 2
    $\begingroup$ Is your Question about whether the given model's definition can be extended to multiplication, or whether it can be done in the way you tried to do it? $\endgroup$
    – hardmath
    Oct 30, 2014 at 15:15
  • 1
    $\begingroup$ It seems to me that the definition $∀n \in N a \times n = b$ does not fit with Axiom (Q6) : $\forall z (z \times 0 = 0)$. $\endgroup$ Oct 30, 2014 at 16:07
  • $\begingroup$ @hardmath the first one. I just tried to extend it. $\endgroup$
    – mau
    Oct 30, 2014 at 17:10
  • $\begingroup$ maybe the "proof" in the Wikipedia article was less than half-baked. Unfortunately it was written in 2006 and the original poster does not seem to work anymore on the encyclopedia. I think I will eventually delete that proof, or maybe I will try to correct it: unluckily the first idea I have ($a$ being a "even infinity" and $b$ a "odd infinity") works with the finite sums but preserves commutativity too. $\endgroup$
    – mau
    Oct 30, 2014 at 18:25
  • $\begingroup$ In Robinson arithmetic $x+S(y)=S(x+y)$. Suppose in your example $x=a$, $y=0$. Then 1) $x+S(y) = a+S(0)=a+1=a$, 2) $S(x+y) = S(a+0) = S(a)=b$. So, your example is not a model $\endgroup$
    – sas
    Nov 3, 2020 at 1:14

3 Answers 3

4
$\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 :

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$.

$\endgroup$
6
  • $\begingroup$ But at that point the question becomes "is it possible to have a model of Q which is not the standard one and in which $S(k) \ne k$ for all elements $k$"? With this model I may just use the statement above as an undecidable sentence. $\endgroup$
    – mau
    Oct 30, 2014 at 21:24
  • $\begingroup$ @mau - If we agree that the above definition (PSmith's one) is consistent with $\mathsf Q$'s axioms, then clearly we must have that $\forall n(S(n) \ne n)$ must not be provable, because we have $S(a)=a$... $\endgroup$ Oct 31, 2014 at 7:25
  • 1
    $\begingroup$ that's not my question :-) (but re-reading it, I agree that it was not clear what I was asking. Of course $\forall n (S(n) \ne n)$ is not provable. This means that there exist models where the statement is true (natural numbers) and models where it is false (the one above). For my purposes, this is enough. But I was wondering if a model may be produced where $\forall n (S(n) \ne n)$ and commutativity is false. $\endgroup$
    – mau
    Oct 31, 2014 at 10:48
  • 1
    $\begingroup$ @mau - Ok, I've understood now. But you have to take into account that with $S(a)=b, S(b)=a$ you have the inconsistency : $a+S(n)=a$ by def and $a+S(n)=S(a+n)=S(a)=b$ by def and recursive axiom for sum ... $\endgroup$ Oct 31, 2014 at 11:08
  • 1
    $\begingroup$ Also, in the last paragraph, I presume you meant "with $Sx$ defined as $x+1$" rather than "with $x$ defined as $x+1$". $\endgroup$ Jul 12, 2020 at 21:01
2
$\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:

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

$\endgroup$
1
$\begingroup$

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
  • $\begingroup$ I was worried because of the lack of symmetry, just this. $\endgroup$
    – mau
    Oct 30, 2014 at 17:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .