2
$\begingroup$

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!

$\endgroup$
6
  • 2
    $\begingroup$ The converse is very far from true. The surprise in question arises from the widely popularised Gödel's incompleteness theorems and I am amazed you haven't heard about this. Also it doesn't make sense to say that a theory PA is an elementary extension of a model $\Bbb{N}$: elementary extension is a relationship between models. Am I misreading your question? $\endgroup$
    – Rob Arthan
    Commented Sep 16, 2018 at 21:20
  • 1
    $\begingroup$ Oh, that's embarassing. I'm taking a logic course and we didn't get there yet (Peano arithmetic comes first). Therefore I only have a vague idea about what it means, and I'm definitely not well-acquinted with it's applications yet. This is just a thought that I've had while learning about PA, but I guess I'm ahead of my time... $\endgroup$
    – 35T41
    Commented Sep 16, 2018 at 21:28
  • 1
    $\begingroup$ Every model of PA is an extension of $\mathbb N$, but not necessarily an elementary extension. $\endgroup$
    – hmakholm left over Monica
    Commented Sep 16, 2018 at 21:31
  • 3
    $\begingroup$ @35T41: don't be embarrassed! You made a very natural and very interesting conjecture, that turns out to be false for deep and important reasons. Making good conjectures is an important part of the art of mathematics regardless of whether the conjectures turn out to be true. $\endgroup$
    – Rob Arthan
    Commented Sep 16, 2018 at 21:57
  • 2
    $\begingroup$ As an addendum to the comments/answer, let me observe that this fact is much harder to show than simply "there are nonstandard models of PA" - the latter follows immediately from the compactness theorem, but the incompleteness of PA takes serious work. OK, I guess that's rude, since the compactness theorem itself takes serious work, but my point is that - unlike the existence of nonstandard models of PA - Godel's incompleteness theorem isn't an immediate corollary of any "general fact" of first-order logic. $\endgroup$
    – Noah Schweber
    Commented Sep 16, 2018 at 22:33

1 Answer 1

Reset to default
6
$\begingroup$

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.)

$\endgroup$
1
  • $\begingroup$ For example $PA$ cannot prove his consistency. Really poor speaking $PA$ cannot say "I'm consistent". In other words there exist a true arithmetical sentence that express the consistency of $PA$ but it is not demonstrable in $PA$. $\endgroup$
    – Marco Lecci
    Commented Sep 16, 2018 at 21:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .