# 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

```