Since the Godel sentence for PA (G henceforth) is independent of PA, if PA is consistent, so is PA plus not-G. Thus, since PA is a first-order theory, if PA is consistent, PA plus not-G has some models. My question concerns what are these models like. I've read a couple of times that these are 'non-standard models' but I've got the following query. Presumably PA is part of the theory of arithmetic -- call it 'Teo(N)' -- (the whole set of sentences of the language of PA that are true in the standard model) and so is G. Using compactness and downward LS, we show that Teo(N) has models that are non-standard (models containing elements that cannot be reached from 0 by a finte number of applications of the successor function; in fact, these models contain denumerably many galaxies of such elements). Call these models 'NSM1'. If G is part of Theo(N), G is true in NSM1. Thus, if PA plus not-G has models, these must be distinct (non-isomorphic) to NSM1. So, it seems, there must be something specific about these models, not just that they're non-standard. What is it (or is my reasoning flawed somewhere)? Thanks!
2 Answers
Here is the most "tangible" distinctive feature of models of $PA$ that satisfy the negation of Gödel's true but unprovable sentence.
Let $\phi$ be a true $\Pi^0_1$ arithmetical sentence that is not provable from $PA$, e.g., $\phi$ can be chosen as the sentence expressing "I am unprovable from $PA$" [as in the first incompleteness theorem], or the sentence "$PA$ is consistent" [as in the second incompleteness theorem].
Thanks to a remarkable theorem of Matiyasevich-Robinson-Davis-Putnam, known as the MRDP theorem [see here], there is a diophantine equation $D_{\phi}$ that has no solutions in $\Bbb{N}$, but has the property that for any model $M$ of $PA$, $D_{\phi}$ has a solution in $M$ iff $M$ satisfies the negation of $\phi$.
[note: $D_{\phi}$ is of the form $E=0$, where $E$ is a polynomial in several variables that is allowed to have negative coefficients, but $D_{\phi}$ can be re-expressed as an equation of the form $P=Q$, where $P$ and $Q$ are polynomials [of several variables] with coefficients in $\Bbb{N}$; hence it makes perfectly good sense to talk about $D_{\phi}$ having a solution in $M$].
Let me close by recommending two good sources for the study of nonstandard models of $PA$.
Richard Kaye, Models of Peano arithmetic. Oxford Logic Guides, 15. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1991.
Roman Kossak and James H. Schmerl, The structure of models of Peano arithmetic, Oxford Logic Guides, 50. Oxford Science Publications. The Clarendon Press, Oxford University Press, Oxford, 2006.
While there is only one standard model, there are indeed many distinct (and elementarily nonequivalent) nonstandard models. As for distinguishing those that satisfy G and those that do not, I’m afraid there is no better answer than Tarski’s definition of satisfaction. All countable nonstandard models look superficially alike in that they have isomorphic order relation: the standard natural numbers followed by countably many copies of $\mathbb Z$ arranged in a densely ordered way (i.e., $\mathbb N+\mathbb Q\times_{\mathrm{Lex}}\mathbb Z$). However, the structure of $+$ and especially $\cdot$ in the models are much more complicated (for instance, no countable nonstandard model of PA has computable $+$ or $\cdot$) and next to impossible to classify.
The Gödel sentence is $\Pi^0_1$: its negation is equivalent to a formula $\exists x\,\theta(x)$ where $\theta$ is bounded, and therefore absolute in end-extensions. Thus, the most important feature of a model of PA + ¬G is a witness to the existential quantifier in the above formula, which is necessarily nonstandard (in the usual construction of the Gödel formula, the witness will be a Gödel number of a proof of G). That’s more or less everything you can say in general about the model.${}{}{}$
