𝛽-recursion theory

Friedman, Sy D.

doi:10.1090/S0002-9947-1979-0542876-7

$\beta$-recursion theory
HTML articles powered by AMS MathViewer

by Sy D. Friedman

Trans. Amer. Math. Soc. 255 (1979), 173-200

DOI: https://doi.org/10.1090/S0002-9947-1979-0542876-7

PDF | Request permission

Abstract:

We define recursion theory on arbitrary limit ordinals using the J-hierarchy for L. This generalizes $\alpha$-recursion theory, where the ordinal is assumed to be ${\Sigma _1}$-admissible. The notion of tameness for a recursively enumerable set is defined and the degrees of tame r.e. sets are studied. Post’s Problem is solved when ${\Sigma _1}\operatorname {cf} \beta \beta {\ast }$. Lastly, simple sets are constructed for all $\beta$ with the aid of a $\beta$-recursive version of Fodor’s Theorem.

References

Keith J. Devlin, Aspects of constructibility, Lecture Notes in Mathematics, Vol. 354, Springer-Verlag, Berlin-New York, 1973. MR 0376351, DOI 10.1007/BFb0059290
Richard M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post’s problem, 1944), Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 236–238. MR 84474, DOI 10.1073/pnas.43.2.236

Recursion on inadmissible ordinals

Post’s Problem without admissibility

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

Consistency proof for the generalized continuum hypothesis

25

R. Björn Jensen, The fine structure of the constructible hierarchy, Ann. Math. Logic 4 (1972), 229–308; erratum, ibid. 4 (1972), 443. With a section by Jack Silver. MR 309729, DOI 10.1016/0003-4843(72)90001-0
G. Kreisel and Gerald E. Sacks, Metarecursive sets, J. Symbolic Logic 30 (1965), 318–338. MR 213233, DOI 10.2307/2269621

Transfinite recursion on admissible ordinals

29

Manuel Lerman, Maximal $\alpha$-r.e. sets, Trans. Amer. Math. Soc. 188 (1974), 341–386. MR 332458, DOI 10.1090/S0002-9947-1974-0332458-X
Manuel Lerman and Gerald E. Sacks, Some minimal pairs of $\alpha$-recursively enumerable degrees, Ann. Math. Logic 4 (1972), 415–442. MR 439605, DOI 10.1016/0003-4843(72)90007-1
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

Negative answer to the problem of reducibility of the theory of algorithms

108

Foundations of recursion theory

Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1
Gerald E. Sacks, Post’s problem, admissible ordinals, and regularity, Trans. Amer. Math. Soc. 124 (1966), 1–23. MR 201299, DOI 10.1090/S0002-9947-1966-0201299-1
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
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

The r.e

degrees are dense

9

Admissible ordinals and recursion theory

Degree theory on admissible ordinals