0
$\begingroup$

By the Kirby–Paris theorem, Goodstein's theorem is independent of Peano arithmetic (PA). Therefore there are non-standard models in which every Goodstein sequence terminates. However, Tennenbaum's theorem states that there is no countable recursive non-standard model of PA. So in what sense do Goodstein sequences in non-standard models terminate? Do they terminate after a non-standard number of steps?

$\endgroup$
2
  • 2
    $\begingroup$ Since Goodstein's theorem is true in the standard model, all Goodstein sequences terminate in the standard model. The independence result provides nonstandard models in which there are Goodstein sequences that don't terminate. (But meanwhile, there are also nonstandard models of true arithmetic, so it is also true that there are nonstandard models where all Goodstein sequences terminate.) $\endgroup$ Jun 17, 2015 at 3:18
  • $\begingroup$ I'm voting to close this question because it has been essentially answered in a comment, and is no longer relevant. $\endgroup$ Jun 18, 2015 at 5:12

1 Answer 1

4
$\begingroup$

"In what sense do Goodstein sequences in non-standard models terminate?" In the sense that the sentence, in the language of PA, expressing "All Goodstein sequences terminate" is true in some non-standard models of PA. (Of course, it's false in some other non-standard models of PA, because it's not provable in PA.) If a Goodstein sequence starts with non-standard number, termination will take a non-standard number of steps.

(I don't see the relevance of Tennenbaum's theorem to any of this.)

$\endgroup$

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