Recursion in second order bounded arithmetic

Abstract

Se muestra que algunos esquemas recursivos pueden ser ejecutados en las teorías U2i ( i ≥1) de aritmética acotada de segundo orden introducidas por S. Buss. En particular, se demuestra que la clase de las funciones ∑ 11,b - definibles en U2i es cerrada bajo recursión acotada, o, equivalentemente, que U2i puede ∑11,b - definir E2, la segunda clase de Grzegorczyk .

It is shown that some recursion schemes can be carried out in the second order theories of Bounded Arithmetic U2i ( i ≥1) introduced by S. Buss in [2]. In particular, we prove that the class of ∑11,b - definable functions in U2i is closed under bounded recursion, or, equivalently, that U2i can ∑11,b - define the functions in the second class of Grzegorczyk, E2 .