Model of Robinson Arithmetic but not Peano Arithmetic

Question

I am curious how can structure of with linear successor function that do not admin induction looks like. In other words I would like to see structure of Peano Arithmetic without induction. I believe such axiomatization is called Robinson Arithmetic but I could not find any model of RA that is not model of PA.

Answer 1

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$ [i.e. Robinson arithmetic] 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 $x$ defined as $x+1$. For infinite cardinals we then have $Sx=x$.

See Peter Smith, An Introduction to Gödel's Theorems (1st ed 2007), page 56, for a model of $\mathsf Q$ made of the "usual" natural numbers plus 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.

In one of the exercise sheets for P.Smith's book, we'll find the complete verification of $\mathsf Q$’s axioms for this model :

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

---

The proof in $\mathsf {PA}$ of $∀x(0 + x = x)$ uses induction :

Basis : $0+0=0$, by first axiom for sum : $∀x(x + 0 = x)$

Induction step : assume $0 + x = x$; by axioms for identity : $(0 + x)' = x'$. By second axioms for sum : $(0 + x)' = 0 + x'$ and thus, again by identity : $0 + x' = x'$.

Thus, by induction, we conclude with : $∀x(0 + x = x)$.

---

In conclusion, the above model of $\mathsf Q$ does not satisfy induction.