$RCA\_0$ has $\Delta\_0$-comprehension and $\Sigma\_1$ induction. Let $X\Sigma\_{n}$ be $RCA\_0$ plus $\Sigma\_n$-induction and let $X\Sigma\_{\omega}$-induction be $RCA\_0$ plus the full induction schema. 


Does any of the systems $X\Sigma\_{\delta}$ for $\delta\in\omega + 1$ prove the existence of sets that are not proved by $\Delta\_0$-comprehension, and if so to what level of comprehension do such sets belong?



What can be achieved by liberalizing induction for $RCA_0$?
One answer is trivially "Yes" - fix some first-order sentence $\varphi$ which is provable from $X\Sigma\_n$ but not $RCA\_0$ alone and consider the formula $$\psi(x)\equiv (\varphi \vee \neg(x\in 0'))$$ (where "$x\in 0'$" is shorthand for the standard $\Sigma^0\_1$ formula defining the Halting Problem). Then $RCA\_0$ does not prove comprehension for $\psi$, but $X\Sigma\_n$ does. Moreover, by choosing $\varphi$ to be a true $\Pi^0\_1$ sentence, we can have $\psi$ be $\Pi^0\_1$, so this gives examples as low in the arithmetic hierarchy as possible.


I suspect this is not what you mean. The problem is, it's not clear how to interpret your question. The $\omega$-models of $RCA\_0$ and of $X\Sigma\_n$ are of course the same, so there are no "true" sets of natural numbers whose existence requires induction.


Maybe you can clarify what you are asking?




---


EDIT: Another response which you might find more satisfactory:


Actually, induction axioms should be thought of as **anti**comprehension axioms - they show that definable cuts can't exist!


One instance of this is:



> 
> Let $M=(\omega\_M, \mathbb{R}\_M)$ be a model of $RCA\_0$ such that, for some $\mathbb{R}'\supseteq\mathbb{R}\_M$, we have $(\omega\_M, \mathbb{R}')\models X\Sigma\_n$. Then $M\models X\Sigma\_n$.
> 
> 
> 


Basically, the only way a model $M$ of $RCA\_0$ could fail to be a model of $X\Sigma\_n$ is if the first-order part of $M$ has a $\Sigma\_n$-definable-from-parameters-in-$\mathbb{R}\_M$ cut; but if $(\omega\_M, \mathbb{R}')\models X\Sigma\_n$ for some larger $\mathbb{R}'$, then this can't happen.


In particular, for any model $\omega\_M$ of the first-order part $I\Sigma\_n$ of $X\Sigma\_n$, the structure $(\omega\_M, D)$ - where $D$ is the class of $\Delta^0\_1$ subsets of $\omega\_M$ - is a model of $X\Sigma\_n$. But $(\omega\_M, D)$ is also the smallest model of $RCA\_0$ with first-order part $\omega\_M$! 


So adding induction doesn't add sets.


