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!

  • $\begingroup$ I wasn't sure whether this would fit better here or MO. I'm open to hearing others' opinions on this matter. $\endgroup$ Aug 29 '10 at 18:25
  • 1
    $\begingroup$ Would seem to be just about appropriate on either site, though I suspect you're more likely to get an answer on MO. $\endgroup$
    – Noldorin
    Aug 29 '10 at 21:05
  • $\begingroup$ I'll give it a day or 2 on this site to see if I get any answers. If not, what is the proper course of action? Should I delete this page? Should I answer it with whatever answer I get on MO (made CW so I don't gain rep for it)? $\endgroup$ Aug 29 '10 at 23:53
  • $\begingroup$ I don't know of any easy compactness proof to generate a model where Goodstein's theorem fails, but I did write an answer below explaining the issue with the argument you sketched. $\endgroup$ Aug 30 '10 at 11:30
  • 1
    $\begingroup$ I've just asked the question on MO: mathoverflow.net/questions/37329/… $\endgroup$ Aug 31 '10 at 22:57

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.

  • $\begingroup$ Thanks for pointing out the flaw in my argument! I knew it couldn't be that easy. $\endgroup$ Aug 30 '10 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.