

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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|cite|improve this question
up vote 5 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|cite|improve this answer
@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

