Equivalence of statements over $RCA_0$

197 Views Asked by At

I am trying to show that, for each $k\in\omega$, $\Sigma^0_k$ induction is equivalent to bounded $\Sigma^0_k$ comprehension over $RCA_0$, where bounded $\Sigma^0_k$ comprehension is the following statement

$$ \forall n\, \exists X\, \forall i<n ~ (i\in X \leftrightarrow (i<n \land \varphi(i))\, ) $$

with $\varphi$ being a $\Sigma^0_k$ formula. I'm struggling to prove the $\rightarrow$ implication.

Here's my reasoning: we already know that $RCA_0 \vdash \Sigma^0_1 \text{ induction} \leftrightarrow \text{bounded }\Sigma^0_1 $comprehension. Let's assume we already proved the statement for $k-1$. Write $\varphi(i)= \exists j\, \theta(i,j)$. We want to show that there exists the set $\{i\,:\,i<n \land \varphi(i)\}$. By bounded $\Sigma^0_{k-1}$ comprehension we can define the set $$X_n := \{(i,j)\,:\, i<n \land j<n \land \theta(i,j) \}$$

Using the fact that $\Sigma^0_k$ induction is equivalent to the strong $\Sigma^0_k$ bounding principle, i.e. for each $\Sigma^0_k$ formula $\psi$, $$\forall m\,\exists h\,\forall i<m(\,(\exists j\,\psi(i,j))\rightarrow (\exists j<h)\, \psi(i,j)\,)$$ we can fix $n$ and apply the strong $\Sigma^0_k$ bounding principle to $\varphi$, so to conclude that there exists a $h$ s.t. $\forall i<n\, ( \varphi(i) \leftrightarrow (\exists j<h)\, (i,j) \in X_h)$. The set $X:= \{i\,: (i,j)\in X_h \land i<n\}$ is the set we are looking for.

I would like to know whether my reasoning is correct and how we can prove the same without using the strong $\Sigma^0_k$ bounding principle (I'm following Simpson's "Subsystems of second order arithmetic" and this is exercise II.3.13, while the equivalence between $\Sigma^0_k$ induction and the strong $\Sigma^0_k$ bounding principle is exercise II.3.15, so I'm probably cheating using it).