[FOM] Provability in PA

[Charles Parsons]

At 11:11 AM -0400 8/17/06, Studtmann, Paul wrote:
>Let I-Sigma-n be Peano Arithmetic (PA) with the induction schema restricted
>to Sigma-n formulas.  Can anyone tell me whether the following is true or
>false:
>
>(*) There is some n such that for all Sigma-2 sentences, s, if PA |- s, then
>I-sigma-n |- s.
>
>I am in fact interested in the general case but (*) is easier to state and
>read.
>
>If it is known that (*) is true or that it is false, I would like to know
>whether it can be proven to be true, if true, or false, if false, within PA.
>And of course I would be interested to know where I can find the proofs.
>
>Paul Studtmann

(*) is certainly false. Unless I've misunderstood, among the sigma-2 
sentences envisaged is the sentence asserting the consistency of 
I-sigma-n.

That adding quantifiers in inductions yielded new theorems at low 
levels is probably already proved in an old paper of Kreisel and 
Wang, "Some applications of formalized consistency proofs," in 
Fundamenta Mathematicae, about 1955.

For each n we can thus exhibit a sigma-2 (in fact pi-1) sentence that 
is provable in PA and prove in PA that it is not provable in 
I-sigma-n. But the generalization can't be provable in PA, because it 
would imply that for every n there is a sentence not provable in 
I-sigma-n, thus that the latter is consistent for every n. But that 
implies the consistency of PA.

You may be interested also in an old paper of mine, "On n-quantifier 
induction," JSL 37, 1972.

Charles Parsons