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

Original · EN

We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of Π₁(N) + Ω₁ has a proper end-extension to a model of Π₁(N), and so Π₁(N) + Ω₁ BΣ₁. Under an even stronger complexity-theoretic assumption which nevertheless seems hard to disprove using present-day methods, Π₁(N) + Exp BΣ₁. Both assumptions can be modified to versions which make it possible to replace Π₁(N) by IΔ₀ as the base theory. We also show that any proof that IΔ₀ + does not prove a given finite fragment of BΣ₁ has to be "non-relativizing", in the sense that it will not work in the presence of an arbitrary oracle.