MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 added 4 characters in body

You can prove that the two theories are, in fact, equivalent. By induction (NB: 'meta-induction') on the number of parameters, we can reduce the claim to the case where you have a theory $T$ with the usual induction schema and a theory $T'$ that is an extension of $T$ by a one-parameter induction schema.

So assume $T$ and $T'$ are not equivalent. This implies that there is a model $\mathcal{M} \vDash T'$ and a two-place open sentence $\phi(x,y)$ such that

$$\mathcal{M} \vDash \phi(0,\beta) \wedge (\forall x (\phi(x,b) \phi(x,\beta) \rightarrow \phi(x+1,\beta))) $$

but also,

$$\mathcal{M} \nvDash \forall x \phi(x,\beta)$$

for some $\beta \in \mathcal{M}$. But note now that the above is equivalent to

$$ \mathcal{M} \vDash \exists y (\phi(0,y) \wedge (\forall z (\phi(z,y) \rightarrow \phi(z+1,y))) \wedge \neg \forall z \phi(z,y) $$

and if you call this last sentence $S$ then you get that $S \wedge \phi ' (x)$ violates the usual induction-schema, where $\phi ' (x)$ is the one-place open sentence we get by by closing $y$ under the existential quantifier in $S$. That is to say we have $S \wedge \phi ' (0)$ and $ \forall x (S \wedge \phi ' (x) \rightarrow S \wedge \phi ' (x+1))$ but not $\forall x S \wedge \phi ' (x)$. But that is a contradiction since $\mathcal{M}$ is a model of $T$. Hence the two theories are equivalent.
show/hide this revision's text 2 edited body

You can prove that the two theories are, in fact, equivalent. By induction (NB: 'meta-induction') on the number of parameters, we can reduce the claim to the case where you have a theory $T$ with the usual induction schema and a theory $T'$ that is an extension of $T$ by a one-parameter induction schema.

So assume $T$ and $T'$ are not equivalent. This implies that there is a model $\mathcal{M} \vDash T'$ and a two-place open sentence $\phi(x,y)$ such that

$$\mathcal{M} \vDash \phi(0,\beta) \wedge (\forall x (\phi(x,b) \rightarrow \phi(x+1,\beta))) $$

but also,

$$\mathcal{M} \nvDash \forall x \phi(x,\beta)$$

for some $\beta \in \mathcal{M}$. But note now that the above is equivalent to

$$ \mathcal{M} \vDash \exists y (\phi(0,y) \wedge (\forall x z (\phi(x,y) \phi(z,y) \rightarrow \phi(x+1,y))) phi(z+1,y))) \wedge \neg \forall x z \phi(x,y) phi(z,y) $$

and if you call this last sentence $S$ then you get that $S \wedge \phi ' (x)$ violates the usual induction-schema, where $\phi ' (x)$ is the one-place open sentence we get by by closing $y$ under the existential quantifier in $S$. That is to say we have $S \wedge \phi ' (0)$ and $ \forall x (S \wedge \phi ' (x) \rightarrow S \wedge \phi ' (x+1))$ but not $\forall x S \wedge \phi ' (x)$. But that is a contradiction since $\mathcal{M}$ is a model of $T$. Hence the two theories are equivalent.
show/hide this revision's text 1

You can prove that the two theories are, in fact, equivalent. By induction (NB: 'meta-induction') on the number of parameters, we can reduce the claim to the case where you have a theory $T$ with the usual induction schema and a theory $T'$ that is an extension of $T$ by a one-parameter induction schema.

So assume $T$ and $T'$ are not equivalent. This implies that there is a model $\mathcal{M} \vDash T'$ and a two-place open sentence $\phi(x,y)$ such that

$$\mathcal{M} \vDash \phi(0,\beta) \wedge (\forall x (\phi(x,b) \rightarrow \phi(x+1,\beta))) $$

but also,

$$\mathcal{M} \nvDash \forall x \phi(x,\beta)$$

for some $\beta \in \mathcal{M}$. But note now that the above is equivalent to

$$ \mathcal{M} \vDash \exists y (\phi(0,y) \wedge (\forall x (\phi(x,y) \rightarrow \phi(x+1,y))) \wedge \neg \forall x \phi(x,y) $$

and if you call this last sentence $S$ then you get that $S \wedge \phi ' (x)$ violates the usual induction-schema, where $\phi ' (x)$ is the one-place open sentence we get by by closing $y$ under the existential quantifier in $S$. That is to say we have $S \wedge \phi ' (0)$ and $ \forall x (S \wedge \phi ' (x) \rightarrow S \wedge \phi ' (x+1))$ but not $\forall x S \wedge \phi ' (x)$. But that is a contradiction since $\mathcal{M}$ is a model of $T$. Hence the two theories are equivalent.