Maximal $\alpha$-r.e. sets
HTML articles powered by AMS MathViewer
- by Manuel Lerman
- Trans. Amer. Math. Soc. 188 (1974), 341-386
- DOI: https://doi.org/10.1090/S0002-9947-1974-0332458-X
- PDF | 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 S. Kripke, Transfinite recursions on admissible ordinals. I, II, (abstracts), J. Symbolic Logic 29 (1964), 161-162.
- 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-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 R. A. Shore, Priority arguments in $\alpha$-recursion theory, Ph.D. Dissertation, M.I.T., 1972. S. Simpson, Admissible ordinals and recursion theory, Ph.D. Dissertation, M.I.T., 1971.
- 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 J. Stillwell, Reducibility in generalized recursion theory, Ph.D. Dissertation, M.I.T., 1970.
- C. E. M. Yates, Three theorems on the degrees of recursively enumerable sets, Duke Math. J. 32 (1965), 461–468. MR 180486
Bibliographic Information
- © Copyright 1974 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 188 (1974), 341-386
- MSC: Primary 02F27
- DOI: https://doi.org/10.1090/S0002-9947-1974-0332458-X
- MathSciNet review: 0332458