Prove the Robinson arithmetic has infinite non-isomorphic models

Question

I found this question: Can finite theory have only infinite models?, where is proved that Robinson's Arithmetic can have infinite models, but I've been unable to prove or find a proof of the existence of infinite non-isomorphic models for this arithmetic (if the statement it's true) or to prove it's false.

Answer 1

The basic idea to prove the problem is put an infinitely large element in the standard structure of natural numbers, say $\Bbb{N}$. Also, you may know that the standard structure of natural numbers satisfies Robinson arithmetic.

To add an infinite element, we will use compactness theorem. At first, add a constant symbol $c$ into the language of the arithmetic. Let $Q$ be the set of axioms of Robinson arithmetic. Also, let define $\Sigma$ be the set of all sentences of the form $$c>S^n(0)$$ (where $n$ is a standard natural numbers, and $S^n$ means iterating $S$ $n$-times. e.g. $S^2(0)=S(S(0))$, where $S$ is the successor function.)

You can check that every finite subset of $Q\cup\Sigma$ is consistent (Hint. Consider $Q\cup\Sigma_0$, where $\Sigma_0$ is a finite subset of $\Sigma$.), so $Q\cup\Sigma$ has a model, by compactness. Let $\mathfrak{A}$ be a such model, then you can check that $\mathfrak{A}$ is not isomorphic to the structure of standard natural numbers.

---

In fact, you can change $Q$ in above to the set of all sentences true over $\Bbb{N}$, and it shows the existence of countable non-standard model of true arithmetic.

Answer 2

Here is a proof which uses Gödel's completeness and incompleteness theorems. Let $Q$ be the axioms of Robinson Arithmetic. We assume that $Q$ has at least one model and is therefore consistent. By incompleteness, there must be a sentence $\varphi$ such that not $Q \vdash \varphi$ and not $Q \vdash \neg\varphi$. From completeness, it follows that not $Q \vDash \varphi$ and not $Q \vDash \neg\varphi$. This means that there are two models $M$ and $N$ of $Q$ with $M \vDash \neg \varphi$ and $N \vDash \varphi$. These models cannot be isomorphic since isomorphic models always satisfy exactly the same formulas.