On complexity reduction of \(\Sigma_1\) formulas (Q1407576)

It is an important open question whether there is a constant \(q\) such that, for every \(\Sigma_1\) formula \(\varphi\) of the language of arithmetic, there is a \(\Sigma_1\) formula \(\varphi'\) with exactly \(q\) blocks of bounded quantifiers which is equivalent to \(\varphi\) over \(I\Delta_0+\lnot\exp\). The paper gives the only known partial positive result. Let \(\varphi\) be a \(\Sigma_1\) formula such that \(\varphi(d,x)\) defines at most one element in any model of \(I\Delta_0\), for any fixed value of the parameter \(d\). It is shown that, if \(q\) is large enough, for every such \(\varphi\), there are a model \(M\) of \(I\Delta_0+\lnot\exp\) and a nonstandard element \(d\) such that \(\varphi(d,x)\) is equivalent over \(M\) to a \(\Delta_2\) formula with \(q\) blocks of bounded quantifiers. The model is constructed using the technique for models of theories extending \(I\Delta_0+\Omega_2\) developed previously [\textit{Z. Adamowicz}, Fundam. Math. 171, 279-292 (2002; Zbl 0995.03044); \textit{Z. Adamowicz} and \textit{P. Zbierski}, Arch. Math. Logic 40, 399-413 (2001; Zbl 1030.03043)].