On a Theory for AC0and the Strength of the Induction Scheme
Satoru Kuroda · Mathematical logic quarterly · 1998
Abstract We define a fragment of Primitive Recursive Arithmetic by replacing the defining axioms for primitive recursive functions by those for functions in some specific complexity class. In this note we consider such theory for AC0. We present a model‐theoretical property of this theory, by means of which we are able to characterize its provably total functions. Next we consider the problem of how strong the induction scheme can be in this theory.