| Autor: |
DORAIS, FRANÇOIS G., HIRST, JEFFRY L., SHAFER, PAUL |
| Předmět: |
|
| Zdroj: |
Journal of Symbolic Logic; Dec2015, Vol. 80 Issue 4, p1211-1235, 25p |
| Abstrakt: |
We prove that the statement “there is a k such that for every f there is a k-bounded diagonally nonrecursive function relative to f” does not imply weak König’s lemma over ${\rm{RC}}{{\rm{A}}_0} + {\rm{B\Sigma }}_2^0$. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that every k-bounded diagonally nonrecursive function computes a 2-bounded diagonally nonrecursive function may fail in the absence of ${\rm{I\Sigma }}_2^0$. [ABSTRACT FROM PUBLISHER] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
