How to prove a formula is not valid in robinson arithmetic

Question

I have known that $\forall x \, (s(0)∗ x = x)$ is a theorem of Peano Arithmetic. But how to prove that this formula is not a theorem of Robinson Arithmetic?

Answer 1

Let $Q = \{Q_1, Q_2, Q_3, Q_4, Q_5, Q_6, Q_7\}$ the set of axioms of Robinson Arithmetic as written here.

We build a model $\mathcal{M}$ of $Q$ that does not satisfies the formula $\forall x \, s(0)*x = x$.

The elements of $\mathcal{M}$ are the natural numbers plus two new distinct elements $a$, $b$. We have to define the behavior of $s$, +, $*$ with respect to $a$ and $b$.

We set $s(a) = a$ and $s(b) = b$. Therefore, $\mathcal{M} \models Q_1 \land Q_2 \land Q_3$.

We set $a + n = a$ and $b + n = b$ for any natural number $n$, moreover we set $x + a = b$ and $x + b = a$ for any element $x$ of $\mathcal{M}$ (natural number or $a$ or $b$). Thus, $\mathcal{M} \models Q_4 \land Q_5$.

We set $a*0 = 0$, $b*0 = 0$, $a * n = b$ and $b * n = a$ for any positive natural number $n$. Moreover we set $b * a = a$ and $x * a = b$ for any $x \in \mathbb{N} \cup\{a\}$, $a * b = b$ and $x * b = a$ for any $x \in \mathbb{N} \cup \{b\}$. You can easily prove that $\mathcal{M} \models Q_6 \land Q_7$.

Finally, observe that $s(0) * a = b \neq a$ by definition, hence $\mathcal{M} \not\models \forall x \, s(0)*x = x$.

You can find more details here.