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.

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

0

Reset to default

You must log in to answer this question.