5
$\begingroup$

By Löwenheim-Skolem we know there are models of (first order) PA that are not isomorphic to the standard model, but are elementary equivalent to it, i.e. they satisfy the same set of first-order sentences.

By Gödel's incompleteness result, we know there is a model of PA in which the canonical unprovable Gödel sentence G is true (the standard model), and (non-standard) models where G is false.

Since G is a first-order sentence, this seems to answer the question I posed in the title to the negative. Correct so far?

I am wondering then, is it a meaningful, i.e. well defined question to ask if for any "other" first-order sentences, those that intuitively express more naturally "arithmetic truths", all models of PA are elementary equivalent? are there other more arithmetically meaningful$^1$ (first order) sentences that are independent from the PA axioms?

$^1$ where 'more ... meaningful' is probably too vague to hope for an answer, but I am essentially asking, can we be sure that any first-order property we hold as evident of $\mathbb{N}$ is provable from the axioms of PA?

$\endgroup$
3
  • $\begingroup$ It is unclear what you mean by "... for any other first-order sentences, ..., all models of $PA$ are elementarily equivalent": elementary equivalence is a property of models. What does "elementary equivalent for a first-order sentence" mean? $\endgroup$
    – Rob Arthan
    Jun 21, 2015 at 21:09
  • $\begingroup$ @RobArthan Yes, apologies, my mistake, should have said instead: "Not all models are elementarily equivalent, as per Gödel sentence G. But are there also 'more arithmetically meaningful*' sentences that are independent from the PA axioms?". * Where "... meaningful" is, I am aware, quite possibly too vague to receive an answer. $\endgroup$
    – Bert Zangle
    Jun 22, 2015 at 13:50
  • 1
    $\begingroup$ It sounds like you are interested in results like the Paris-Harringtion theorem, a combinatorial property with no logical baggage attached that is not provable in PA. $\endgroup$
    – Rob Arthan
    Jun 22, 2015 at 21:45

1 Answer 1

Reset to default
6
$\begingroup$

As you say, no, not all models of $\sf PA$ are elementarily equivalent. Here's a nice point:

If $T$ is a theory without finite models, then $T$ is complete if and only if all of its models are elementarily equivalent.

So the incompleteness is a quick way to deduce that $\sf PA$ is incomplete (note that there are no finite models of $\sf PA$ because of the axioms about the successor function being injective but not surjective).

As for "normal statements", that depends on what you mean exactly. We can say that as far as $\Delta_1$ statements, the answer is positive.

The reason is that a $\Sigma_1$ statement is true in $\Bbb N$ if and only it $\sf PA$ proves it. And therefore given a $\Delta_1$ statement, both it and its negation are $\Sigma_1$, one of them is true in $\Bbb N$ and therefore provable from $\sf PA$.

Whether or not $\Delta_1$ statements are "reasonable" is up to you. And pushing it further down the arithmetical hierarchy is impossible, since $\operatorname{Con}(\sf PA)$ is a $\Pi_1$ statement and its negation is $\Sigma_1$ statement; neither of which is provable from $\sf PA$.

$\endgroup$
8
  • $\begingroup$ I seem to have some major gap in understanding here. Perhaps you can help me filling it in. Your statement: "The reason is that a $\Sigma_1$ statement is true in $\mathbb{N}$ if and only it 𝖯𝖠 proves it" is true simply by our definition of the arithmetical hierarchy, correct? But how do we know that any first-order property we assume to hold for $\mathbb{N}$ is decided, either way - we don't care, by the axioms of PA? $\endgroup$
    – Bert Zangle
    Jun 22, 2015 at 14:17
  • $\begingroup$ I'm not entirely sure what you mean. $\Bbb N$ is a structure, by the truth definition, every sentence is either true there or false there. The question is whether or not we can prove that sentence from $\sf PA$. If a statement is $\Sigma_1$, then we can show that it is true in $\Bbb N$ if and only if it is provable from $\sf PA$. This is not "by definition", this is an actual factual theorem which is not at all trivial. $\endgroup$
    – Asaf Karagila ♦
    Jun 22, 2015 at 15:06
  • $\begingroup$ I see. Probably this is the connection between truth in $\mathbb{N}$ and provability from the axioms that I am missing. Is there a version of this proof you think I could look at and perhaps even understand parts of it? $\endgroup$
    – Bert Zangle
    Jun 22, 2015 at 16:12
  • 1
    $\begingroup$ Something provable is of course true in $\Bbb N$. The other direction is the difficult part (where we must restrict to $\Sigma_1$ sentences). The point behind the proof is to first show that for $\Sigma_0$ sentences this is true, which requires somewhat uncomfortable, and then conclude from that for $\Sigma_1$ sentences by a silly trick. But generally this is somewhat technical. As for something that you can understand, I don't know what you know or don't know and how well, so the answer is a resounding no. I think that the proof appears on Peter Smith's books about incompleteness. $\endgroup$
    – Asaf Karagila ♦
    Jun 22, 2015 at 16:19
  • $\begingroup$ @AsafKaragila by the completeness theorem, given a theory $T$, isn't "$T$ is complete" and "all model of $T$ are elementarily equivalent" equivalent statements? $\endgroup$
    – Anguepa
    Dec 13, 2015 at 12:28

You must log in to answer this question.

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