Interaction of completeness and second incompleteness theorems

Question

So I was reading the Wikipedia article on Godel's completeness theorem, the section on its relation to completeness. It says that completeness gives the existence of a model of arithmetic $\mathcal M \models PA$ where $\mathcal M \vdash \neg \text{Cons}(PA)$, but that the Godel number of the any contradiction is non-standard. Unfortunately, Wikipedia gives no citations for this claim.

Why does completeness imply the existence of this model? How does the Godel number of the contradiction being non-standard avoid actually proving that PA is inconsistent? What does "consistent when viewed from outside" mean? How does that work out?

Answer 1

Well, there is a hedge here. If $\mathsf{PA}$ is consistent (meaning in some sufficiently nice meta-theory, or the "real world", one cannot prove contradictory statements), then by Gödel's Second Incompleteness Theorem $\mathsf{PA} \not\vdash \mathrm{Cons}(\mathsf{PA})$, and so by a standard argument it follows that $\mathsf{PA} + \neg \mathrm{Cons}(\mathsf{PA})$ is also consistent. By Gödel's Completeness Theorem there is a model $\mathcal{M}$ of this theory. As $\neg \mathrm{Cons}(\mathsf{PA})$ is an existential statement ($(\exists x) ( \varphi(x) )$), there is some object $x \in \mathcal{M}$ which exhibits (from the point-of-view of $\mathcal{M}$) the inconsistency of $\mathsf{PA}$: it codes a proof of some fixed contradiction, using some fixed Gödel numbering.

Now if $x$ corresponded to some standard number $m \in \mathbb{N}$, then that "real" natural number would code a real proof of a contradiction in $\mathsf{PA}$: the standard model $\mathbb{N}$ "knows" that either $m$ is a code of a proof of a fixed contradiction, or it is not, and in the latter case there is no extension $\mathcal{M}$ of $\mathbb{N}$ in which $m$ can code a proof of an extension. But this then contradicts our assumption that $\mathsf{PA}$ is consistent.

---

Addendum

(due to a comment below)

Let's first sort of get a handle on "nonstandard" numbers (and nonstandard models). Well, first of all, a model of $\mathsf{PA}$ is nonstandard if it is not isomorphic to the standard model; pretty obvious, I guess. The thing about models of $\mathsf{PA}$ is that they always start the same: if $\mathcal{M}$ is a model of $\mathsf{PA}$, then the first elements of $\mathcal{M}$ are $$0^{\mathcal{M}},\; 1^{\mathcal{M}}{=}S^{\mathcal{M}} ( 0^{\mathcal{M}} ),\; 2^{\mathcal{M}}{=}S^{\mathcal{M}} ( 1^{\mathcal{M}} ),\; 3^{\mathcal{M}}{=}S^{\mathcal{M}} ( 2^{\mathcal{M}} ),\;\ldots$$ and these object satisfy all the usual arithmetic properties of the "real" natural numbers. In fact, we will usually just say that $\mathbb{N}$ is an initial segment of any model of $\mathsf{PA}$.

But can this be all of them? Unfortunately, no.

Append to the language of $\mathsf{PA}$ a new constant symbol $c$, and let $T$ be the theory extending $\mathsf{PA}$ obtained by adding $\ulcorner n \urcorner < c$ as a new axiom for each natural number $n$ (where $\ulcorner n \urcorner$ denotes the term $\overbrace{S \cdots S}^{n\text{ times}}0$). By the Compactness Theorem, if $\mathsf{PA}$ is consistent, then so is $T$. If $\mathcal{M}$ is a model of $T$, then consider $c^\mathcal{M}$. For each natural number $n$, as $\mathcal{M} \models \ulcorner n \urcorner < c$ it follows that $n <^{\mathcal{M}} c^{\mathcal{M}}$. That is, $c^{\mathcal{M}}$ does not correspond to any natural number.

An object in a nonstandard model of $\mathsf{PA}$ which does not correspond to a natural number is called a nonstandard number. One thing should be clear: any nonstandard number comes after all the standard numbers. Of course, if $x \in \mathcal{M}$ is a nonstandard number, then so is $S^{\mathcal{M}}(c)$ and $S^{\mathcal{M}} ( S^{\mathcal{M}} ( c ) )$. Also, $c$ will have a immediate predecessor which is also nonstandard. In practice, the collection of nonstandard numbers is fairly messy.

One very useful idea is the following. If $\mathcal{M}$ is a model of $\mathsf{PA}$, we will call a subset $I \subseteq \mathcal{M}$ a cut (in $\mathcal{M}$), if it is a nonempty, initial segment of $\mathcal{M}$ which is closed under the successor operator. (So $\mathbb{N}$ is a cut in any model of $\mathsf{PA}$. The following fact is interesting:

Overspill Lemma. Suppose that $\mathcal{M}$ is a nonstandard model of $\mathsf{PA}$, and $I \subsetneq \mathcal{M}$ is a cut. Suppose that $\varphi ( x , y_1 , \ldots , y_n )$ is a formula and $a_1 , \ldots , a_n \in \mathcal{M}$ are such that for each $z \in I$ there is an $x \in I$ such that $$\mathcal{M} \models x \geq z \wedge \varphi ( x , a_1 , \ldots , a_n ).$$ Then there is an $x \in \mathcal{M} \setminus I$ such that $\mathcal{M} \models \varphi ( x , a_1 , \ldots , a_n )$.

Let's apply this in two ways:

• First, there is no formula $\sigma (m)$ such that $$\mathcal{M} \models \sigma ( x ) \quad \Leftrightarrow \quad x\text{ is standard}$$ for any model $\mathcal{M}$ of $\mathsf{PA}$ and any $x \in \mathcal{L}$. (Simply because $\mathbb{N}$ is a cut in any model, and if $\mathcal{M}$ is a nonstandard model, then $\mathbb{N}$ is a proper cut, and so if $\sigma (x)$ is a formula true about all standard numbers, by the Overspill Lemma it must also be true about a nonstandard number.

• It is not difficult to show that if $\mathrm{Formula}_{\mathsf{PA}} (x)$ denotes the formula distinguishing the natural numbers coding formulas from those that do not, then the set of all natural numbers $n$ such that $\mathbb{N} \models \mathrm{Formula}_{\mathsf{PA}} (n)$ is unbounded, and so if $\mathcal{M}$ is a non-standard model of $\mathsf{PA}$, by the Overspill Lemma there is a nonstandard number $x \in \mathcal{M}$ such that $\mathcal{M} \models \mathrm{Formula}_{\mathsf{PA}} (x)$. But you could not decode this $x$ into an actual formula of $\mathsf{PA}$: it may be of nonstandard ("infinite") length, or it may employ "variables" with nonstandard indices. But as $\mathcal{M}$ can't tell standard numbers from nonstandard numbers, so $\mathcal{M}$ just "thinks" that $x$ codes a formula.

Now, recall that $\mathrm{Cons}(\mathsf{PA})$ is just a formula (sentence). We built it up to have some significance under a suitable interpretation, but this significance critically used the idea that "real" natural numbers were being used.

So what happens if a nonstandard model $\mathcal{M}$ satisfies $\neg \mathrm{Cons}(\mathsf{PA})$, even if the standard model does not? Being a bit more exact than above, $\neg \mathrm{Cons} ( \mathsf{PA} ) \equiv (\exists x ) ( \mathrm{Proof}_{\mathsf{PA}} ( x , \ulcorner \psi \urcorner ) )$, where $\psi$ is some fixed contradictory sentence. If $\mathcal{M} \models \neg \mathrm{Cons} ( \mathsf{PA} )$, then there must be some $x \in \mathcal{M}$ such that $\mathcal{M} \models \mathrm{Proof}_{\mathsf{PA}} ( x , \ulcorner \psi \urcorner ) )$. But if $x$ were a standard number, it would follow that $\mathbb{N} \models \mathrm{Proof}_{\mathsf{PA}} ( x , \ulcorner \psi \urcorner ) )$, which we have assumed cannot be the case. So such an $x$ must be nonstandard.

Well, what does this mean? According to the definition of $\mathrm{Proof}_{\mathsf{PA}}$ it means that $\mathcal{M}$ "thinks" that $x$ codes a sequence of numbers, and each number in this sequence codes a formula, and these formulas constitute a proof of $\psi$. But, like the above, something about this encoded "proof" is going to be nonstandard: it may have nonstandard ("infinite") length, or it may involve nonstandard formulas. This says that $x$ does not really encode a proof of a contradiction in $\mathsf{PA}$, but only that $\mathcal{M}$ "thinks" that it does.

Answer 2

Simplifying a little bit, Gödel's Completeness Theorem for first-order logic (with one of the "usual" proof systems, i.e. logical axioms+rules of inferences) says that :

$\Gamma \vDash \varphi$ iff $\Gamma \vdash \varphi$,

i.e. all the logical consequences of a set of sentences are provable with the (logical) rules and axioms.

If we apply it to $\mathsf {PA}$, we have that $\Gamma$ is the set of f-o Peano's axioms.

The above theorem says that all f-o formulae of $\mathsf {PA}$ that are provable from Peano's axioms are logical consequences of the axioms, i.e. they must be true in all models of the axioms.

Godel's Incompletenss Theorem says that $\mathsf {PA} \nvdash Cons(\mathsf {PA})$.

But, if we assume $\mathsf {PA}$ consistent, and this assumption is necessary for the proof of G's Incompletenss Th, we have that the formula $Cons(\mathsf {PA})$ is true.

$Cons(\mathsf {PA})$ being unprovable from f-o Peano's axioms, we have that it is not a logical consequence of the axioms.

And if it is not a logical consequence of the axioms, it is not true in all models of the axioms, i.e.it must be false in some of their models.

But we know that it is true in the "standard" model $\mathbb N$; thus, it must be false in some "non-standard" model.

Then, Arthur's argument follows.