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
  • 3
    $\begingroup$ For what it's worth, I disagree with the vote to close. $\endgroup$
    – Noah Schweber
    Commented 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
    Commented 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
    Commented Apr 1, 2015 at 20:50
  • $\begingroup$ Isn't that the usual statement of Tennenbaum's theorem? $\endgroup$
    – Noah Schweber
    Commented Apr 2, 2015 at 1:47

You must log in to answer this question.

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