Is there a natural model of Peano Arithmetic where Goodstein's theorem fails?

Goodstein's Theorem is the statement that every Goodstein sequence eventually hits 0. It is known to be independent of Peano Arithemtic (PA), and in fact, was the first such purely number theoretic result. It is provable in ZFC.

One way of phrasing this is that the theory "PA + Goodstein's theorem is false" is consistent (assuming PA is).

By Godel's completeness theorem, there must exist a model of PA in which Goodstein's theorem fails. In fact, applying the downward Lowenheim-Skolem theorem, we may assume this model is countable.

However, in the interest of speaking about this result to a group of grad students (of various interests), I'd like to run this backwards. So,

is there some known, obvious, or easy to construct countable nonstandard model of $PA$ in which Goodstein's theorem fails?

In answering this, I'm willing to accept the "foundational" first order logic theorems: Godel's completeness and compactness results, the Lowenheim-Skolem theorem.

Here is the kind of answer I'd really like: There is an explicit countable collection $\Sigma = \{\phi_n\}$ of first order sentences (possibly in a slightly larger language) such that $\mathbb{N}$ is a model of $PA + \Sigma_0$ for any finite $\Sigma_0\subseteq \Sigma$, and such that $PA + \Sigma$ implies Goodstein's theorem is false.


One approach I've thought of is to first enlarge the language by adding a constant symbol c. Next, let $\phi_n$ be the statement "The Goodstein sequence for $c$ takes longer than "n" steps to terminate". (While I do not personally know how to encode "the Goodstein sequence for $c$" in first order language, I am confident it can be done, for otherwise, one could not even formulate "PA proves the Goodstein sequence converges".)

In this case, $\mathbb{N}$ is a model of any $PA + \Sigma_0$ by simply setting c = n+1, where n is the largest subscript of a $\phi_k$ in $\Sigma_0$ (which exists because $\Sigma_0$ is finite).

By Godel's and Lowenheim-Skolem theorems, $PA + \Sigma$ has a countable model $M$. Then the interpretation of $c$ in this model satisfies $\phi_n$ for all $n$, and hence the Goodstein sequence doesn't terminate for $c$ in this model.

However, since the independence of Goodstein's theorem was so difficult to prove, I'm quite certain there's a mistake in this line of reasoning (though I don't know where). I'd love for someone to patch this up into something correct.

As always, please feel free to retag as neccesary, and thank you for the reponses!


Here's the flaw in the compactness argument you sketched. In the model you construct, the interpretation of $c$ will indeed be a nonstandard number whose Goodstein sequence does not halt in a standard number of steps. But Goodstein's theorem has a universal quantifier for the number of steps, so nonstandard "Goodstein sequences" are also permitted. That is, when the theorem says "there is a finite sequence", in a particular model that "finite" sequence might have the length of a nonstandard number, which cannot be excluded by the sequence of sentences in your argument.

One way to find an extension of PA where Goodstein's theorem is provable is to add enough transfinite induction to PA to formalize the usual proof of Goodstein's theorem. The details of how to do that are not so bad, although they may take too much time for an elementary class.