I'm trying to understand the Kripke-Putnam proof of Gödel's incompleteness theorem, somewhat recently cited in this MO question, and can't figure out how to close a gap in the argument. I apologize in advance for this post's length; if you've read the paper, scroll down to my analysis of claim (2).
Putnam's article has two key pieces.
First, let "PA" denote the axioms of Peano Arithmetic. Putnam discusses an enumeration of PA, but is terribly imprecise. I interpret his discussion as follows.
Let $\{\mathrm{PA}_j\}_{j\in\mathbb{N}}$ be a primitive recursive (p.r.) enumeration of (Gödel codes of) PA, indexed by the standard (minimal) model of PA. We can clearly do this, because $\mathrm{PA}\vdash(\text{PA is r.e.})$, so $\mathbb{N}\models(\text{PA is r.e.})$. Fix any model $\mathcal{N}\models\mathrm{PA}$. Since an r.e. set is interpretable in the language of PA, we can extend our recursive "program" $\{\mathrm{PA}_j\}_{j\in\mathbb{N}}$ to $\{\mathrm{PA}_j\}_{j\in\mathcal{N}}$ (just plug in nonstandard inputs). I call nonstandard-indexed axioms "nonstandard axioms"; it may not be (and likely is not) the case that a nonstandard axiom follows from PA. Moreover, the exact value of a nonstandard axiom depends on the model $\mathcal{N}$; I will write $\{\mathrm{PA}_j^{\mathcal{N}}\}_j$ to emphasize this dependence.
Because this interpretation is not spelled out in the text, it may be wrong; I discuss why I think this interpretation is correct below.
Second, pick $\mathcal{N}\models\mathrm{PA}$. Putnam defines a relation, fullfillment, between arbitrary-length tuples and (Gödel codes of) formulas, which I will write as $\vec{s}\Vdash\phi$. I hope that the precise details of $\Vdash$ are not necessary to work around my difficulty; if they are, then I direct readers to the third page (p. 55) of the linked document above. The intuition for fullfillability is that we weaken our notion of truth by adversarily bounding the range of each quantifier; the end result ends up being manipulable without the much machinery.
Fullfillment satisfies the following properties:
- If $\vec{s}$ is cofinal in $\mathcal{N}$ and $\vec{s}\Vdash\phi$, then $\mathcal{N}\models\phi$;
- Conversely, if $\mathcal{N}\models\phi$, then for any $n\in\mathcal{N}$, there exists $\vec{s}\in\mathcal{N}^n$ such that $\vec{s}\Vdash\phi$.
- For technical reasons, if $\vec{s}\Vdash\phi$, then $\vec{s}$ grows rapidly.
Putnam is interested in the "fullfillable" predicate $$F_n(\phi)=(\exists\vec{s}\in\mathcal{N}^n)(\vec{s}\Vdash\phi)$$ Importantly, $\Vdash$ is p.r. for $\mathcal{N}$-finite tuples, and so can be interpreted in the language of Peano Arithmetic. If we define (III) to be the statement $$(\forall N)F_N\left(\bigwedge_{n\leq N}{\mathrm{PA}_n}\right)$$ then (III) is also interpretable.
Putnam claims the following:
- If $\mathcal{N}=\mathbb{N}$ (the standard model), then $\mathcal{N}\models\mathrm{(III)}^\mathcal{N}$.
- There exists a nonstandard model $\mathcal{N}$ such that $\mathcal{N}\models\neg\mathrm{(III)}^\mathcal{N}$.
These immediately imply $PA\not\vdash\mathrm{(III)},\neg\mathrm{(III)}$ and thus Gödel's famous claim that there is an undecidable sentence.
Putnam seems to think (1) is obvious. I disagree: any such proof must use a property of the standard model in an essential way, lest we be in case (2) — but all such properties are noncomputable. However, (1) falls out quickly from my analysis of enumerating PA above;Fn. 1 for that reason, I think it is safe to impute that analysis into Putnam's text.
To see claim (2), Putnam proceeds as follows: given any nonstandard model $\mathcal{M}$, by overspill, there must be an nonstandard $N\in\mathcal{M}$ for which $$\mathcal{M}\models F_N\left(\bigwedge_{n\leq N}{\mathrm{PA}_n^{\mathcal{M}}}\right)$$ Thus there exists $\vec{s}\in\mathcal{M}^N$ of minimal Gödel code such that $\vec{s}\Vdash\bigwedge_{n\leq N}{\mathrm{PA}_n^{\mathcal{M}}}$.
Let $\mathcal{N}$ be the subset of $\mathcal{M}$ in which $\vec{s}$ is cofinal; since $\vec{s}$ grows rapidly, $\mathcal{N}$ is a structure in the language of PA. Moreover, since $\vec{s}$ is cofinal, $$(\forall n\leq N)(\mathcal{N}\models\mathrm{PA}_n^{\mathcal{M}})$$ Since we cover all the axioms of PA when $n$ is standard, this implies $\mathcal{N}\models\mathrm{PA}$ (as the notation would suggest).
But it's easy to see that the Gödel code of $\vec{s}$ is too large to lie in $\mathcal{N}$, and so $\mathcal{N}\not\models F_N\left(\bigwedge_{n\leq N}{\mathrm{PA}_n^{\mathcal{M}}}\right)$. Putnam wants to conclude that (III) is violated, namely $$\mathcal{N}\not\models F_N\left(\bigwedge_{n\leq N}{\mathrm{PA}_n^{\mathcal{N}}}\right)$$ But I don't see why we can replace the non-standard axiom $\mathrm{PA}_n^{\mathcal{N}}$ for $\mathrm{PA}_n^{\mathcal{M}}$. (Since Putnam is imprecise about his enumerations, the issue doesn't even come up in the text.) Why is that?
Fn. 1: Fix $N\in\mathbb{N}$; since $N$ is standard, $$\mathrm{PA}\vdash\bigwedge_{n\leq N}{\mathrm{PA}_n^{\mathbb{N}}}$$ Thus $\mathbb{N}\models\bigwedge_{n\leq N}{\mathrm{PA}_n^{\mathbb{N}}}$ and we can find some $\vec{s}\in\mathbb{N}^N$ such that $\vec{s}\Vdash\bigwedge_{n\leq N}{\mathrm{PA}_n^{\mathbb{N}}}$.