Skip to main content
3 of 7
TeX
Gerald Edgar
  • 41.1k
  • 5
  • 125
  • 219

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 link text there is a diophantine equation $D_{\phi}$ that has no solutions in $\mathbb {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 allowed to have negative coeffients, 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 coeffiecients 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.

Ali Enayat
  • 17.7k
  • 2
  • 63
  • 105