End Extensions of Models of Linearly Bounded Arithmetic
Domenico Zambella
Abstract:
We show that every model of I-\Delta_0 has an end extension to a model of a
theory (extending Buss' S^0_2) where logspace computable function are
formalizable. We also show the existence of an isomorphism between models of
I-\Delta_0 and models of linear arithmetic LA (i.e., secondĀorder Presburger
arithmetic with finite comprehension for bounded formulas).