Skip to main content
1 of 2

Does this hierarchy of fragments of $I \Sigma_1$ collapse?

Does anyone know whether the following hierarchy of fragments of $\mathrm{I} \Sigma_1$ (or rather $\mathrm{I} \Pi_1$) collapses or not?

Let $\Sigma^b_n$ denote formulas in the language of arithmetic with $n-1$ alternations of bounded quantifiers where the front quantifier is a bounded existential. Let $\forall \Sigma^b_n$ denote $\Sigma^b_n$ formulas with some potentially unbounded universal quantifiers in front.

Let $\mathrm{I} \forall \Sigma^b_n$ be the fragment of $\mathrm{I} \Pi_1$ that only has induction on $\forall \Sigma^b_n$ formulas.

Does the hierarchy $\mathrm{I} \forall \Sigma^b_1 \subseteq \mathrm{I} \forall \Sigma^b_2 \subseteq \ ... $ collapse at a finite level?

(The question could just as well be asked for the theories $\mathrm{I} \exists \Pi^b_n $ but it was the hierarchy of $\mathrm{I} \forall \Sigma^b_n$ theories that I ran into in my research.)

At first glance, it seemed to me that this hierarchy would collapse due to the existence of a universal $\Pi_1$ formula $U(x,y)$. Since $U \in \forall \Sigma^b_k$ for some $k$ any instance of $\forall \Sigma^b_n$ induction with $n \geq k$ is equivlanet to $\forall \Sigma^b_k$ induction on $U(m,y)$ for some $m$. But the problem is, that I don't know how strong a theory is needed to prove $\forall x ( U(m,x) \iff \phi(x) ) $ for a given $\phi$. I am pretty sure that for any $\phi \in \Pi_1$ we have $\mathrm{I} \Pi_1 \vdash \forall x ( U(m,x) \iff \phi(x) )$ for some $m$ but for all I know this proof might only go through in a fragment $\mathrm{I} \forall \Sigma^b_n$ of $\mathrm{I} \Pi_1$ such that $\phi \in \forall \Sigma^b_n$ (i.e. the amount of bounded quanitifers needed to prove this in $\mathrm{I} \Pi_1$ might depend on the amount of bounded quantifiers in $\phi$)

Maybe someone here can help shed light on this?