Model of Robinson Arithmetic but not Peano Arithmetic
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.
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.