10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ what is the reference for notations? what is the reference for this result? $\endgroup$ – user94040 Nov 22 '16 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$ – Erfan Khaniki Nov 22 '16 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$ – Emil Jeřábek Dec 2 '16 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$ – Emil Jeřábek Dec 2 '16 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$ – Erfan Khaniki Dec 2 '16 at 16:43

Your Answer

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

Browse other questions tagged or ask your own question.