It is well known that if ${\bf T_2}$ (or $I\Delta_0+\Omega_1$) is finitely axiomatizable, then the Polynomial Hierarchy collapses.

Q. Is there any similar relation between $I\Delta_0$ and Linear Time Hierarchy?

Edit: related questions

Q'. Why standard proof (like corollary 4.39 in chapter V of Metamathematics of first-order arithmetic) of

Finite axiomatizability of ${\bf T_2}$ $\Rightarrow$ PH collapse.

does not work for proving

Finite axiomatizability of ${\bf {\bf I}\Delta_0}$ $\Rightarrow$ LiH collapse ?

Relativized Case

Q''. Is there any formula $\phi(x)$ in the language of arithmetic with following properties?

I. $\mathbb{N} \models\forall x(\phi(x)\leftrightarrow \alpha(x))\to$ "LiH($\alpha$) does not colapse",

II. there exists $i\in \mathbb{N}$ such that, ${\bf I}E_i(\alpha)+\forall x(\phi(x)\leftrightarrow \alpha(x))\vdash {\bf I}\Delta_0(\alpha)$.

Thanks in advance.

  • 1
    $\begingroup$ what is the reference for notations? what is the reference for this result? $\endgroup$
    – user94040
    Nov 22, 2016 at 11:59
  • 2
    $\begingroup$ @AJ.: See corollary 4.39 in chapter V of metamathematics of first order arithmetic. Notations are explained in that chapter. $\endgroup$ Nov 22, 2016 at 13:24
  • $\begingroup$ Well, the main problem with the original Krajíček–Pudlák–Takeuti argument is Lemma 4.43: even if all the input data is linear, the function with polynomial advice constructed near the end of the proof has superlinear (quadratic) advice, hence it cannot be used in the linear hierarchy setting. There have been several improvements of the result, but most of the proofs elaborate the original argument, hence they suffer from the same problem (this includes the currently best results: Thm. 4.6 and Cor. 4.7 from my paper users.math.cas.cz/~jerabek/papers/hash.pdf ). ... $\endgroup$ Dec 2, 2016 at 14:44
  • 1
    $\begingroup$ ... An exception is Buss’s paper math.ucsd.edu/~sbuss/ResearchWeb/collapseBAPH/index.html , which uses a more light-weight argument to get a weaker collapse. On a quick look in the paper, I didn’t notice anything that would require genuinely polynomial growth, so there is a nontrivial chance it may actually be adapted to $I\Delta_0$ and the linear hierarchy, but the devil is in the detail. $\endgroup$ Dec 2, 2016 at 14:49
  • $\begingroup$ @EmilJeřábek: Thank you very much for your explanation and papers. I updated my post with a new related question. $\endgroup$ Dec 2, 2016 at 16:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy