COUNTING SMALL SETS IN WEAK BOUNDED ARITHMETIC
Satoru Kurota · Institutional Repositories DataBase (IRDB) · 1997
We define a weak first order theory for $\mathrm{A}\mathrm{C}^{0}$ with an auxiliary axiom scheme which counts the cardinality of small sets defined by some $\mathrm{A}\mathrm{C}^{0}$ relation.The main result is that definable functions of this theory is exactly those which are $\mathrm{A}\mathrm{C}^{0}$ reducible to the binary counting function.Our tool is Herbrand-type witnessing method for universal theories.