End extensions of models of linearly bounded arithmetic

Models of arithmetic and set theory (03C62) Second- and higher-order arithmetic and fragments (03F35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

The paper is about the end extension problem for bounded second order arithmetic, linear arithmetic LA and \(\Sigma^{p}_{0}\) first-order recursion schema, denoted \(\Sigma^{p}_{0}\)-rec -- both subsystems (the second one possibly not proper) of second order bounded arithmetic BA. \(\Sigma^{p}_{0}\) is the class of bounded polynomial formulas (no second order quantifiers). Axioms of LA consist of the usual ordered semiring axioms plus statements expressing that every set is bounded and has a least upper bound, and the comprehension schema for formulas of the language of bounded Presburger arithmetic (no multiplication). \(\Sigma^{p}_{0}\)-rec is axiomatized by \(\Sigma^{p}_{0}\)-comprehension schema and the recursion schema \[ \forall<a\exists a\varphi(x,y)\rightarrow\exists Z \forall w<b\varphi(Z(w),Z(w+1)), \] where \(\varphi\in\Sigma^{p}_{0}\) and \(Z(x)\) is the value at \(x\) of the function coded by \(Z\). In section 2 an argument is offered to show that functions computable in polynomial time are provably total in \(\Sigma^{p}_{0}\)-rec. The rest of the paper is devoted to the proof of the main result: every model of LA has an end extension to a model of \(\Sigma^{p}_{0}\). The article concludes with results concerning the relative strength of \(\Sigma^{p}_{0}\)-rec and \(\Sigma^{p}_{0}\)-(rec+choice).

Recommendations

Cites work

Cited in

(5)

This page was built for publication: End extensions of models of linearly bounded arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377910)