4
$\begingroup$

Does $\textsf{PA}$+Con($\textsf{PA}$) entail the existence of non-standard models of $\textsf{PA}$?

Is there a reasonable way in which to code, inside $\textsf{PA}$, the statement that $\textsf{PA}$ has non-standard models?

If so, suppose we start from $\textsf{PA}$ and iteratively add consistency statements, obtaining a transfinite hierarchy of theories $\{\Gamma_{\alpha}\}_{\alpha\in\textsf{On}}$, each asserting the consistency of its predecessor. Is there some ordinal $\alpha$ at which $\Gamma_{\alpha}$ proves that $\textsf{PA}$ has non-standard models?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ For what it's worth, I disagree with the vote to close. $\endgroup$
    – Noah Schweber
    Mar 23, 2015 at 4:01

1 Answer 1

Reset to default
12
$\begingroup$

$PA$ is a weird theory to work with, here: if you want to talk about models, then a two-sorted theory like $RCA_0$ or $ACA_0$ is probably better. $PA$ cannot directly talk about models, since it can't directly talk about sets.

However, $PA$ (in fact, much less than $PA$) proves that if $PA$ is consistent, then so is the theory $PA^*$ in the language of arithmetic + one new constant, $c$, and containing the axioms $c\not=n$ for each (standard) natural number $n$; so in that sense, $PA+Con(PA)$ would prove that $PA$ has nonstandard models.

If one wants to talk about models directly, using a two-sorted theory, then things get more interesting: there is a reasonable theory, $RCA_0$ - its first-order part is $I\Sigma_1$, $PA$ but with induction substantially restricted - which can prove that $Con(PA)$ implies $Con(PA+\neg Con(PA))$, and which proves that complete consistent theories have models, but can't quite prove that arbitrary consistent theories have models. So, for example, $RCA_0+Con(RCA_0)$ cannot prove that $RCA_0$ has nonstandard models (the easiest way to see this is via Tennenbaum's theorem).

Note that this added complexity means that the distinction between models and consistencies [sic] is actually very significant, and not something to be lightly swept under the rug.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Once PA knows that the theory $\text{PA}^*$ is consistent, then it can define the Henkin model, since that is arithmetically definable in PA. That is, we may define in PA a (class) domain of objects and functions $+$ and $\cdot$ on them and an interpretation for $0$ and $1$ and $c$, so that the resulting class is a nonstandard model of PA. So this is a sense in which PA may talk about the models directly. $\endgroup$
    – Joel David Hamkins
    Mar 23, 2015 at 12:25
  • $\begingroup$ To show that $RCA_{0}+Con(RCA_{0})$ cannot prove that $RCA_{0}$ has nonstandard models, do we need Tennenbaum's theorem as usually stated, or just the fact that nonstandard models code non-recursive sets? $\endgroup$
    – stan
    Apr 1, 2015 at 20:50
  • $\begingroup$ Isn't that the usual statement of Tennenbaum's theorem? $\endgroup$
    – Noah Schweber
    Apr 2, 2015 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.