Induction, collection and least numbers

Item 2 follows from item 1 by negation, since the negation of a $\Sigma^0_n$ formula is logically equivalent to a $\Pi^0_n$ formula. It suffices to treat one operation at a time. By renaming bound variables, $\exists y\, \alpha \wedge \exists z\, \beta$ is equivalent to $\exists y\, \exists z\, (\alpha \wedge \beta)$, and similarly for $\vee$; $\exists x < t\ \exists y\, \alpha$ is equivalent to $\exists y\ \exists x < t\ \alpha$; and an existential quantifier merges with the first block. We may also assume that the first block of a $\Sigma^0_n$ formula consists of a single quantifier: $\exists y_1\, \exists y_2\, \alpha$ is equivalent to $\exists w\ \exists y_1 < w\ \exists y_2 < w\ \alpha$, and $\exists y_1 < w\ \exists y_2 < w\ \alpha$, with $\alpha \in \Pi^0_{n-1}$, is bounded if $n = 1$ and equivalent to a $\Pi^0_{n-1}$ formula by item 2 for $n - 1$ if $n \geq 2$, in the induction below. The only non-trivial case is the bounded universal quantifier. We proceed by induction on $n$.

For $n = 1$, let $\varphi = \exists y\, \delta(x, y)$ with $\delta$ bounded. Then $\forall x < t\ \exists y\ \delta$ implies $\exists b\ \forall x < t\ \exists y < b\ \delta$ by $\mathsf B\Sigma^0_1$, and the converse is logical. The second formula is $\Sigma^0_1$.

Let $n \geq 1$, assume the lemma for $n$, and assume $\mathsf B\Sigma^0_{n+1}$, which contains $\mathsf B\Sigma^0_n$. A $\Sigma^0_{n+1}$ formula has the form $\exists y\, \psi$ with $\psi \in \Pi^0_n$. Conjunctions and disjunctions of $\Pi^0_n$ formulas, and bounded quantifications of them, are equivalent to $\Pi^0_n$ formulas by item 2 for $n$; so the easy cases above stay within $\Sigma^0_{n+1}$. For the bounded universal quantifier, $\forall x < t\ \exists y\ \psi(x, y)$ is equivalent to $\exists b\ \forall x < t\ \exists y < b\ \psi(x, y)$ by $\mathsf B\Sigma^0_{n+1}$ applied to $\psi$, which is $\Sigma^0_{n+1}$. By item 2 for $n$, $\forall x < t\ \exists y < b\ \psi$ is equivalent to a $\Pi^0_n$ formula, so the whole formula is equivalent to a $\Sigma^0_{n+1}$ formula.

($\mathsf I\Sigma^0_n \Rightarrow \mathsf I\Pi^0_n$) Let $\varphi$ be $\Pi^0_n$ with $\varphi(0)$ and $\forall x\, (\varphi(x) \rightarrow \varphi(x+1))$, and suppose that $\neg \varphi(a)$. Let

The formula $\neg \varphi$ is equivalent to a $\Sigma^0_n$ formula, and the conjunction with the bounded formula $x + y = a$ can be moved inside its innermost block; so $\theta$ is equivalent to a $\Sigma^0_n$ formula. We have $\theta(0)$, with $x = a$. Suppose $\theta(y)$, and let $y + 1 \leq a$. Then $y < a$, and there is $x$ with $x + y = a$ and $\neg \varphi(x)$; $x \neq 0$, since $y < a$, so $x = x' + 1$. Since $\varphi(x')$ would imply $\varphi(x)$, we have $\neg \varphi(x')$, and $x' + (y + 1) = a$: this is $\theta(y + 1)$. By $\mathsf I\Sigma^0_n$, $\theta(a)$ holds, which gives $x$ with $x + a = a$, so $x = 0$, and $\neg \varphi(0)$: a contradiction.

($\mathsf I\Pi^0_n \Rightarrow \mathsf I\Sigma^0_n$) Let $\varphi$ be $\Sigma^0_n$ with $\varphi(0)$ and $\forall x\, (\varphi(x) \rightarrow \varphi(x+1))$, and suppose $\neg \varphi(a)$. Let

equivalent to a $\Pi^0_n$ formula. Then $\eta(0)$ holds since $\neg \varphi(a)$. Suppose $\eta(y)$ and $y + 1 \leq a$, and let $x + (y + 1) = a$. Then $(x + 1) + y = a$, so $\neg \varphi(x + 1)$, hence $\neg \varphi(x)$. So $\eta(y+1)$. By $\mathsf I\Pi^0_n$, $\eta(a)$ holds, and with $x = 0$ it gives $\neg \varphi(0)$: a contradiction.

By induction on $n$. Assume $\mathsf I\Sigma^0_n$, and, if $n \geq 2$, the theorem for $n - 1$, so that $\mathsf B\Sigma^0_{n-1}$ holds and Lemma 1.3 applies to $\Pi^0_{n-1}$ formulas.

Let $\varphi(x, y) \equiv \exists z\, \psi(x, y, z)$ with $\psi \in \Pi^0_{n-1}$ (bounded if $n = 1$), and suppose that $\forall x < a\ \exists y\ \varphi(x, y)$. Let

It is equivalent to a $\Pi^0_{n-1}$ formula: for $n = 1$ it is bounded, and for $n \geq 2$ by Lemma 1.3. Moreover $\forall x < a\ \exists w\ \chi(x, w)$: take $w$ larger than a witness $y$ and a witness $z$. Let

The formula $\forall x < c\ \exists w < b\ \chi$ is equivalent to a $\Pi^0_{n-1}$ formula, by the same argument, so $\theta$ is equivalent to a $\Sigma^0_n$ formula. Then $\theta(0)$ holds with $b = 0$. Suppose $\theta(c)$ and $c + 1 \leq a$; let $b$ be given by $\theta(c)$, and $w_0$ with $\chi(c, w_0)$, which exists since $c < a$. Then $b' = \max(b, w_0 + 1)$ witnesses $\theta(c+1)$. By $\mathsf I\Sigma^0_n$, $\theta(a)$ holds: there is $b$ such that for every $x < a$ some $w < b$ satisfies $\chi(x, w)$, hence some $y < w < b$ satisfies $\varphi(x, y)$.

($\mathsf L\Pi^0_n \Rightarrow \mathsf I\Sigma^0_n$) Let $\varphi \in \Sigma^0_n$ with $\varphi(0)$ and $\forall x\, (\varphi(x) \rightarrow \varphi(x+1))$, and suppose $\neg \varphi(a)$. By $\mathsf L\Pi^0_n$ applied to the $\Pi^0_n$ formula $\neg \varphi$, there is a least $m$ with $\neg \varphi(m)$. Then $m \neq 0$, so $m = m' + 1$ with $\varphi(m')$, hence $\varphi(m)$: a contradiction. The same argument gives $\mathsf L\Sigma^0_n \Rightarrow \mathsf I\Pi^0_n$.

($\mathsf I\Sigma^0_n \Rightarrow \mathsf L\Pi^0_n$) Let $\varphi \in \Pi^0_n$ with $\varphi(c)$, and suppose there is no least $x$ with $\varphi(x)$. Let $\theta(x) \equiv \forall y \leq x\ \neg \varphi(y)$. By Theorem 1.5, $\mathsf B\Sigma^0_n$ holds, so $\theta$ is equivalent to a $\Sigma^0_n$ formula by Lemma 1.3. If $\varphi(0)$, then $0$ is least; so $\theta(0)$. If $\theta(x)$ and $\varphi(x+1)$, then $x + 1$ is least; so $\theta(x)$ implies $\theta(x+1)$. By induction, $\theta(c)$ holds, contradicting $\varphi(c)$.

($\mathsf I\Pi^0_n \Rightarrow \mathsf L\Sigma^0_n$) The same argument, with $\varphi \in \Sigma^0_n$: the formula $\forall y \leq x\ \neg \varphi(y)$ is equivalent to a $\Pi^0_n$ formula, since $\mathsf I\Pi^0_n$ implies $\mathsf I\Sigma^0_n$ by Theorem 1.4, hence $\mathsf B\Sigma^0_n$.

Combined with Theorem 1.4, the four schemes are equivalent.

By induction on $n$. Assume $\mathsf B\Sigma^0_{n+1}$; it contains $\mathsf B\Sigma^0_n$ and $\mathsf B\Sigma^0_{n-1}$. When $n \geq 2$, the induction hypothesis (the theorem for $n - 1$, applied to $\mathsf B\Sigma^0_n$) gives $\mathsf I\Sigma^0_{n-1}$, hence also $\mathsf I\Pi^0_{n-1}$ by Theorem 1.4.

Let $\varphi(x) \equiv \exists y\, \psi(x, y)$ with $\psi \in \Pi^0_{n-1}$, suppose $\varphi(0)$ and $\forall x\, (\varphi(x) \rightarrow \varphi(x+1))$, and fix $a$. For every $x \leq a$ there is $u$ with $\forall y\, \neg \psi(x, y) \vee \psi(x + 1, u)$. This formula is equivalent to a $\Pi^0_n$ formula, hence is $\Sigma^0_{n+1}$, and $\mathsf B\Sigma^0_{n+1}$ gives a bound $b_0$. Let $y_0$ be such that $\psi(0, y_0)$, and $b = \max(b_0, y_0 + 1)$. Then for every $x < a$,

Indeed, if $\psi(x, y)$, the first disjunct fails, so $\psi(x + 1, u)$ for some $u < b_0 \leq b$. Let

For $n = 1$, $\theta$ is bounded; for $n \geq 2$, it is equivalent to a $\Pi^0_{n-1}$ formula by Lemma 1.3. We have $\theta(0)$, since $y_0 < b$, and $\theta(x) \rightarrow \theta(x+1)$ by the display. By $\mathsf I\Delta^0_0$ or $\mathsf I\Pi^0_{n-1}$, $\theta(a)$ holds, so $\varphi(a)$.