Maximal 𝛼-r.e. sets

Lerman, Manuel

doi:10.1090/S0002-9947-1974-0332458-X

Maximal $\alpha$-r.e. sets
HTML articles powered by AMS MathViewer

by Manuel Lerman PDF

Trans. Amer. Math. Soc. 188 (1974), 341-386 Request permission

Abstract:

Various generalizations of maximal sets from ordinary recursion theory to recursion theory on admissible ordinals are considered. A justification is given for choosing one of these definitions as superior to the rest. For all the definitions considered to be reasonable, a necessary and sufficient condition for the existence of such maximal $\alpha$-r.e. sets is obtained.

References

Richard M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symbolic Logic 23 (1958), 309–316. MR 109125, DOI 10.2307/2964290
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 recursions on admissible ordinals

29

A. H. Lachlan, The elementary theory of recursively enumerable sets, Duke Math. J. 35 (1968), 123–146. MR 227008, DOI 10.1215/S0012-7094-68-03513-8
A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1–37. MR 227009, DOI 10.1090/S0002-9947-1968-0227009-1
Manuel Lerman, On suborderings of the $\alpha$-recursively enumerable $\alpha$-degrees, Ann. Math. Logic 4 (1972), 369–392. MR 327493, DOI 10.1016/0003-4843(72)90005-8
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
M. Lerman and S. G. Simpson, Maximal sets in $\alpha$-recursion theory, Israel J. Math. 14 (1973), 236–247. MR 319729, DOI 10.1007/BF02764882
Michael Machtey, Admissible ordinals and lattices of $\alpha -\textrm {r}.\textrm {e}.$ sets, Ann. Math. Logic 2 (1970/71), no. 4, 379–417. MR 280370, DOI 10.1016/0003-4843(71)90002-7
D. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205–209. MR 280374, DOI 10.2307/2270510
John Myhill, Solution of a problem of Tarski, J. Symbolic Logic 21 (1956), 49–51. MR 75894, DOI 10.2307/2268485
James C. Owings Jr., Recursion, metarecursion, and inclusion, J. Symbolic Logic 32 (1967), 173–179. MR 216951, DOI 10.2307/2271654
Robert W. Robinson, Two theorems on hyperhypersimple sets, Trans. Amer. Math. Soc. 128 (1967), 531–538. MR 215714, DOI 10.1090/S0002-9947-1967-0215714-1
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
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

Priority arguments in

recursion theory

Admissible ordinals and recursion theory

Robert I. Soare, Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets, Ann. of Math. (2) 100 (1974), 80–120. MR 360235, DOI 10.2307/1970842

Reducibility in generalized recursion theory

C. E. M. Yates, Three theorems on the degrees of recursively enumerable sets, Duke Math. J. 32 (1965), 461–468. MR 180486