END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS
Leszek Aleksander Kołodziejczyk · Journal of Symbolic Logic · 2016
Abstract We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of Π1(ℕ) + ¬Ω1has a proper end-extension to a model of Π1(ℕ), and so Π1(ℕ) + ¬Ω ⊢ BΣ1. Under an even stronger complexity-theoretic assumption which nevertheless seems hard to disprove using present-day methods, Π1(ℕ) + ¬Exp ⊢ BΣ1. Both assumptions can be modified to versions which make it possible to replace Π1(ℕ) by IΔ0as the base theory. We also show that any proof that IΔ0+ ¬Exp does not prove a given finite fragment of BΣ1has to be “nonrelativizing”, in the sense that it will not work in the presence of an arbitrary oracle.