3
$\begingroup$

By famous KPT theorem, if $\mathsf{T^i_2}\vdash \mathsf{T^j_2}$ for some $0<i<j$, then the polynomial hierarchy collapses. So it seems this bounded arithmetic hierarchy does not collapse. Also, conservative results for some classes of formulas lead to collapsing complexity classes which is not expected. My question is about the $ \mathsf{T^i_2+EXP}$ theories.

Q1. What is the relationship between $\mathsf{T^i_2+EXP}$ and $\mathsf{T^j_2+EXP}$ for $i<j$? Is it true that $\mathsf{T^i_2+EXP\vdash T_2}$?

Separating these theories implies separating bounded arithmetics which it seems to be hard.

Q2. What about conservative results? For example does $\mathsf{T^i_2+EXP}$ proves every $\Pi_2$ sentences of $\mathsf{T_2+EXP}$?

Thanks in advance.

$\endgroup$

1 Answer 1

4
$\begingroup$

All these theories coincide: if exponentiation is total, a bounded formula is equivalent on any bounded domain to a sharply bounded formula (with an exponentially large parameter), hence bounded induction follows from sharply bounded induction, i.e., $T^0_2+\mathrm{EXP}=T_2+\mathrm{EXP}$.

$\endgroup$
2
  • $\begingroup$ Thank you very much, Emil. Is there any similar argument for $IE_i+EXP$ and $I\Delta_0+EXP$? $\endgroup$ Commented Mar 10, 2017 at 11:51
  • $\begingroup$ Yes, the same argument basically works. The only problem is to settle on a good definition of EXP in the first place, but other than that, $IE_1$ should work as a base theory. $\endgroup$ Commented Mar 10, 2017 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.