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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much, Emil. Is there any similar argument for $IE_i+EXP$ and $I\Delta_0+EXP$? $\endgroup$
    – Erfan Khaniki
    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$
    – Emil Jeřábek
    Commented Mar 10, 2017 at 11:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .