End-extensions of models of weak arithmetic from complexity-theoretic containments

Abstract

We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of ${\Pi }_1(\mathbb{N})+\neg {\Omega }_1$ has a proper end-extension to a model of ${\Pi }_1(\mathbb{N})$, and so ${\Pi }_1(\mathbb{N})+\neg {\Omega }_1⊢\mathrm{B}{\Sigma }_1$. Under an even stronger complexity-theoretic assumption which nevertheless seems hard to disprove using present-day methods, ${\Pi }_1(\mathbb{N})+\neg \mathrm{Exp}⊢\mathrm{B}{\Sigma }_1$. Both assumptions can be modified to versions which make it possible to replace ${\Pi }_1(\mathbb{N})$ by $\mathrm{I}{\Delta }_0$ as the base theory. We also show that any proof that $\mathrm{I}{\Delta }_0+\neg \exp$ does not prove a given finite fragment of $\mathrm{B}{\Sigma }_1$ has to be "non-relativizing", in the sense that it will not work in the presence of an arbitrary oracle.

arXiv comment19 pages