Restricted induction principle
Paul Blain Levy
p.b.levy at cs.bham.ac.uk
Sat Jun 13 16:10:51 EDT 2020
Hi,
I'm puzzled about the strength of a restricted induction principle in
subsystems of second order arithmetic.
Recall that, for a formula of the form Forall x,X. P(n,x,X), the
ordinary induction principle is as follows:
Forall x,X. P(0,x,X) and
Forall n. ( (Forall X. P(n,x,X)) => (Forall X. P(n+1,x,X)) ) implies
Forall n,x,X. P(n,x,X).
The restricted induction principle I want to consider is as follows:
Forall x,X. P(0,x,X) and
Forall n, X. ( (Forall x,y. P(n,x,{z | Q(n,x,X,y,z) })) => P(n+1,x,X) )
implies
Forall n. Forall x,X. P(n,x,X)
with no extra parameters allowed, i.e. P(n,x,X) has only those three
parameters, and Q(n,x,X,y,z) has only those five parameters. (So this
principle is restricted in two ways: by disallowing extra parameters and
by weakening the inductive hypothesis.)
My questions are as follows.
Q1. Take ACA_0 extended with restriction induction for arithmetical P
and Q. Is this stronger than ACA_0? In particular, can it prove Con(PA)?
Q2. Take RCA_0 extended with restricted induction for P and Q that are
Delta_0(PRA), i.e. that contain only restricted quantifiers but may use
all primitive recursive functions. Is this stronger than RCA_0? In
particular, can it prove Con(PRA)?
I suspect the answer to Q1 is yes but I have no idea about Q2.
Paul
More information about the FOM
mailing list