Independence of Goodstein’s Theorem from PA

I was asked in email about a good source about Goodstein sequences and the independence of Goodstein’s Theorem from Peano Arithmetic. The independence result is due to Kirby and Paris in a 1983 paper in the Proceedings of the London Mathematical Society (vol. 14), using the method of indicators. Georg Moser suggested the following paper by Cichon, which appeals to the characterization of provably recursive functions in PA only:

E. A. Cichon, A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods. Proceedings of the American Mathematical Society 87/4 (1983), 704-706. JSTOR

Cichon’s proof can also be found in Fairtlough and Wainer’s chapter on “Hierarchies of Provably Recursive Functions” in the Handbook of Proof Theory, S. Buss, ed. (Elsevier, 1998).

Posted

September 25, 2006

Uncategorized

Richard Zach

Tags:

Comments

One response to “Independence of Goodstein’s Theorem from PA”

Anonymous

October 20, 2006

Dear Richard,I accidently bumped into this blog of yours.Little correction for this post: the Goodstein independence was proved by Paris and Kirby essentially by the Ketonen-Solovay method (ordinals), not by the method of indicators (models of arithmetic). However, there is another paper by Paris (“Hierarchies of cuts…”) which does indicator proofs for alpha-large sets, which an expert can modify to be indicator proofs for hyrda or Goodstein. Overall, ordinals are much better for hydra and Goodstein than model theory. In Ramsey theory it is opposite: indicators are better than ordinals. Posted by Andrey

Reply

Independence of Goodstein’s Theorem from PA

Comments

One response to “Independence of Goodstein’s Theorem from PA”

Leave a Reply to Anonymous Cancel reply