Consider the first-order Peano Arithmetic axioms (which consist of the standard succesor, addition and multiplication axioms, along with first-order induction axioms, as detailed in Wikipedia). This is a first-order theory (let us denote it $PA$) over the signature $\sigma=\left \langle 0,1,+,\cdot \right \rangle$ (equality included in the language).
Let $X_{PA}$ be the set of all sentences that are provable from $PA$ (or equivalently, by Godel's completeness theorem, all the sentences that are logically valid w.r.t this theory). Also, let $X_{\mathbb{N}}$ be the set of all sentences (over $\sigma$) that are true in the standard model $\mathbb{N}$ for $PA$.
My question is: can we show that $X_{PA}=X_{\mathbb{N}}$?
One direction is clear: since $\mathbb{N}$ is a model for $PA$, every sentence that can be derived from $PA$ must be true in $\mathbb{N}$. But is the converse also true? I want to believe that it is, but logic can have its surprises.
I think I've heard that there's a theorem which states that every model of $PA$ is an elementary extension of $\mathbb{N}$ (it's easy to see that it is an extension…) but I couldn't find it. I can see why such a theorem would answer the question.
Thanks in advance!
Best Answer
No. $X_{\mathbb N}$ complete (in the sense that for any sentence, either the sentence or its negation is in $X_{\mathbb N}$), and $X_{PA}$ quite famously is not, by Godel's incompleteness theorem. So $X_{PA}$ is a proper subset of $X_{\mathbb N.}$
By the same token, it is not the case that every model of PA is an elementary extension of $\mathbb N.$ This is due to the completeness theorem. For any sentence $\phi$ that is not decided by $PA,$ there is a model of PA where that sentence is true and another model of PA where it is false. And only one of these models can agree with $\mathbb N.$
(And as Henning just commented, it is the case that $\mathbb N$ can be embedded in all models of PA, since we can map $0$ to $0$ and $1$ to $S0,$ etc., but this embedding is not generally elementary.)