Publication Date:
2014-12-11
Description:
The elementary arithmetic operations \({+,\cdot,\le}\) on integers are well-known to be computable in the weak complexity class TC 0 , and it is a basic question what properties of these operations can be proved using only TC 0 -computable objects, i.e., in a theory of bounded arithmetic corresponding to TC 0 . We will show that the theory VTC 0 extended with an axiom postulating the totality of iterated multiplication (which is computable in TC 0 ) proves induction for quantifier-free formulas in the language \({\langle{+,\cdot,\le}\rangle}\) ( IOpen ), and more generally, minimization for \({\Sigma_{0}^{b}}\) formulas in the language of Buss’s S 2 .
Print ISSN:
0933-5846
Electronic ISSN:
1432-0665
Topics:
Mathematics
Permalink