Strengths and Weaknesses of LH Arithmetic
Chris Pollett, Randall J. Pruim · Mathematical logic quarterly · 2002
In this paper we provide a new arithmetic characterization of the levels of the og-time hierarchy (LH). We define arithmetic classes and that correspond to -LOGTIME and -LOGTIME, respectively. We break and into natural hierarchies of subclasses and . We then define bounded arithmetic deduction systems ′ whose -definable functions are precisely B(-LOGTIME). We show these theories are quite strong in that (1) LIOpen proves for any fixed m that , (2) TAC, a theory that is slightly stronger than ′ whose (LH)-definable functions are LH, proves LH is not equal to -TIME(s) for any m> 0, where 2s ∈L, s(n) ∈ ω(log n), and (3) TAC proves LH ≠ for all k and m. We then show that the theory TAC cannot prove the collapse of the polynomial hierarchy. Thus any such proof, if it exists, must be argued in a stronger systems than ours.