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.

In proof-theory one can prove that in, say, Peano Arithmetic one can't prove a function $f$ total. Often this seems to mean $f$ is growing too fast to be provably total.

I have some background in logic and know the very basics about formal proofs in FO, but overall I'm more familiar with finite model theory than proof-theory. Now I want to learn how to prove a function total in PA and how to prove that a function can't be proved total in PA.

Are there any books that would cover the topic with my background? Also, if there are any lecture notes near the area, I would be very happy receive pointers to them (books do cost a lot and I think I can only afford one).

share|improve this question

1 Answer 1

up vote 4 down vote accepted

The proof theoretic terminology for this concept is "Provable Total Functions"/"Provably Recursive Functions" of a theory.

You will find quite a number of articles on the topic if you search for these terms.

The third chapter of Samuel Buss, "Handbook of Proof Theory", 1998, is devoted to the topic:

  • Matt Fairtlough and Stanley S. Wainer, "Hierarchies of Provably Recursive Functions".

Part 5 of the chapter is "Independence results for PA".

The totalness of (a $\Sigma^0_1$ representation of) a function corresponds to a $\Sigma^0_1$ formula, or equivalently $\Pi^0_2$ sentence. Therefore proving that a function is not total in a theory corresponds to an independence result for a $\Pi^0_2$ sentence, and there are not that many core techniques to do this. One technique as you mentioned is to show that the function is growing too fast, so fast that its totality would imply the consistency of the theory at hand. (There are some tricky issues here about the representation chosen for the function.)

share|improve this answer
Thank you for the answer. It actually happened that I made a search before posting the question and came across the very same article you refer to. Unfortunately I can't access that book and it would be a bit risky to invest book of that price without checking it beforehand. Have you read the book? What do you think of it? –  rank Aug 2 '12 at 5:33
@rank, it is generally a very good book. For a professional review, see this or this. (Arai says it is an excellent exposition of the topic and recommends it for beginners.) But I would suggest using a library copy in place of buying it. It is a handbook after all. –  Kaveh Aug 2 '12 at 6:01

Your Answer


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.