Inverting the half-jump

Homer, S.; Sacks, G. E.

doi:10.1090/S0002-9947-1983-0697077-X

Inverting the half-jump
HTML articles powered by AMS MathViewer

by S. Homer and G. E. Sacks PDF

Trans. Amer. Math. Soc. 278 (1983), 317-331 Request permission

Abstract:

Assume $\beta$ is weakly admissible over $0$ and ${0^{1 / 2}}$. It follows that the $\beta$-recursively enumerable degrees are dense. In addition each $\beta$-recursively enumerable degree above ${0^{1 / 2}}$ is the half-jump of some tamely $\beta$-recursively enumerable degree below ${0^{1 / 2}}$.

References

Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159–160. MR 98025, DOI 10.2307/2964177
Gerald E. Sacks, Recursive enumerability and the jump operator, Trans. Amer. Math. Soc. 108 (1963), 223–239. MR 155747, DOI 10.1090/S0002-9947-1963-0155747-3
Wolfgang Maass, Inadmissibility, tame r.e. sets and the admissible collapse, Ann. Math. Logic 13 (1978), no. 2, 149–170. MR 486628, DOI 10.1016/0003-4843(78)90002-5
S. D. Friedman and G. E. Sacks, Inadmissible recursion theory, Bull. Amer. Math. Soc. 83 (1977), no. 2, 255–256. MR 505378, DOI 10.1090/S0002-9904-1977-14289-4

Recursion on inadmissibile ordinals

Wolfgang Maass, On $\alpha$- and $\beta$-recursively enumerable degrees, Ann. Math. Logic 16 (1979), no. 3, 205–231. MR 548474, DOI 10.1016/0003-4843(79)90002-0
G. E. Sacks and S. G. Simpson, The $\alpha$-finite injury method, Ann. Math. Logic 4 (1972), 343–367. MR 369041, DOI 10.1016/0003-4843(72)90004-6
Stephen G. Simpson, Degree theory on admissible ordinals, Generalized recursion theory (Proc. Sympos., Univ. Oslo, Oslo, 1972) Studies in Logic and the Foundations of Math., Vol. 79, North-Holland, Amsterdam, 1974, pp. 165–193. MR 0537203
Richard A. Shore, Splitting an $\alpha$-recursively enumerable set, Trans. Amer. Math. Soc. 204 (1975), 65–77. MR 379154, DOI 10.1090/S0002-9947-1975-0379154-1
Richard A. Shore, On the jump of an $\alpha$-recursively enumerable set, Trans. Amer. Math. Soc. 217 (1976), 351–363. MR 424544, DOI 10.1090/S0002-9947-1976-0424544-2
Wolfgang Maass, Contributions to $\alpha$- and $\beta$-recursion theory, Minerva-Fachserie Naturwissenschaften. [Minerva Technical Series in Science], Minerva Publikation, Munich, 1978. MR 576409
Richard A. Shore, The recursively enumerable $\alpha$-degrees are dense, Ann. Math. Logic 9 (1976), no. 1-2, 123–155. MR 381963, DOI 10.1016/0003-4843(76)90007-3

Priority arguments in

recursion theory