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

P i_{1} (m a t h b b N) + e g O m e g a_{1}

has a proper end-extension to a model of

P i_{1} (m a t h b b N)

, and so

P i_{1} (m a t h b b N) + e g O m e g a_{1} v d a s h m a t h r m B S i g m a_{1}

. Under an even stronger complexity-theoretic assumption which nevertheless seems hard to disprove using present-day methods,

P i_{1} (m a t h b b N) + e g m a t h r m E x p v d a s h m a t h r m B S i g m a_{1}

. Both assumptions can be modified to versions which make it possible to replace

P i_{1} (m a t h b b N)

by

m a t h r m I D e l t a_{0}

as the base theory. We also show that any proof that

m a t h r m I D e l t a_{0} + e g e x p

does not prove a given finite fragment of

m a t h r m B S i g m a_{1}

has to be "non-relativizing", in the sense that it will not work in the presence of an arbitrary oracle.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: End-extensions of models of weak arithmetic from complexity-theoretic containments