Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it possible to prove Goodstein's theorem without transfinite induction? Is there such a proof?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

I'm pretty sure the short answer is "no" (if you mean, can you prove Goodstein's theorem without invoking apparatus as strong as a transfinite induction which can't be reduced to an ordinary induction). For if I recall correctly, Goodstein's theorem is actually equivalent (over a weak base theory) to transfinite induction up to $\varepsilon_0$. My first port of call to check this would be Kirby and Paris's paper on 'Accessible independence results for Peano Arithmetic'.

share|improve this answer
1  
I can't tell if you are just being modest, but the phrasing of your reply suggests some uncertainty. If so, please let me assure you that I believe that your answer is exactly correct. –  MJD Dec 17 '12 at 14:41
    
I studied this a bit further. I guess that we need transfinite induction if we stick with first-order logic(?). If we allow quantification over sets, could we do with ordinal induction? I ask because I came across this link math.niu.edu/~rusin/known-math/00_incoming/goodstein Notice the the comment by Torkel Franzen. –  rank Dec 17 '12 at 19:23

I found the following paper which seems fairly relevant:

Miller J.T. On the independence of Goodstein’s theorem. 2001, Citeseer.

share|improve this answer
    
Very interesting link, thank you! But I'm afraid it does not (directly) address the question? (I didn't read it through yet, though..) –  rank Dec 17 '12 at 19:25
    
@rank: Look at the section about the independence itself. This means that you cannot prove the theorem from first-order PA without some extra assumptions, which are ultimately equivalent to the transfinite induction. –  Asaf Karagila Dec 17 '12 at 19:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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