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