Skip to main content
12 events
when toggle format what by license comment
Dec 2, 2016 at 18:40 comment added Erfan Khaniki @EmilJeřábek: You are right. I forgot to define oracle in theory. I edited my post.
Dec 2, 2016 at 18:40 history edited Erfan Khaniki CC BY-SA 3.0
added 165 characters in body
Dec 2, 2016 at 17:19 comment added Emil Jeřábek The new question does not make sense to me. I think you misunderstand how relativization works in bounded arithmetic. $I\Delta_0(\alpha)$ is not a family of theories parameterized by subsets of $\mathbb N$ or such, it is a single theory involving an uninterpreted predicate $\alpha(x)$. This $\alpha$ is just a symbol, it does not denote any particular oracle. Rather, witnessing theorems for relativized bounded arithmetic yield uniformly oracle algorithms that can be specialized to whatever oracle one needs. $I\Delta_0(\alpha)$ is not finitely axiomatizable, because $T_2(\alpha)$ is not.
Dec 2, 2016 at 16:57 history edited Erfan Khaniki CC BY-SA 3.0
added 191 characters in body
Dec 2, 2016 at 16:50 history edited Erfan Khaniki CC BY-SA 3.0
added 191 characters in body
Dec 2, 2016 at 16:43 comment added Erfan Khaniki @EmilJeřábek: Thank you very much for your explanation and papers. I updated my post with a new related question.
Dec 2, 2016 at 14:49 comment added Emil Jeřábek ... 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.
Dec 2, 2016 at 14:44 comment added Emil Jeřábek 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 ). ...
Dec 2, 2016 at 7:44 history edited Erfan Khaniki CC BY-SA 3.0
added 330 characters in body
Nov 22, 2016 at 13:24 comment added Erfan Khaniki @AJ.: See corollary 4.39 in chapter V of metamathematics of first order arithmetic. Notations are explained in that chapter.
Nov 22, 2016 at 11:59 comment added user94040 what is the reference for notations? what is the reference for this result?
Nov 22, 2016 at 8:44 history asked Erfan Khaniki CC BY-SA 3.0