Premium
On a Theory for AC 0 and the Strength of the Induction Scheme
Author(s) -
Kuroda Satoru
Publication year - 1998
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19980440312
Subject(s) - primitive recursive function , axiom , mathematics , class (philosophy) , scheme (mathematics) , property (philosophy) , mathematical induction , fragment (logic) , discrete mathematics , algebra over a field , pure mathematics , algorithm , computer science , mathematical analysis , epistemology , philosophy , geometry , artificial intelligence
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 AC 0 . 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.