Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Maximal $ \alpha $-r.e. sets


Author: Manuel Lerman
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
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] R. M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symbolic Logic 23 (1958), 309-316. MR 22 #13; 22 #2545. MR 0109125 (22:13)
  • [2] R. Jensen, The fine structure of the constructible hierarchy, Ann. Math. Logic 4 (1972), 229-308. MR 0309729 (46:8834)
  • [3] G. Kreisel and G. E. Sacks, Metarecursive sets, J. Symbolic Logic 30 (1965), 318-338. MR 35 #4097. MR 0213233 (35:4097)
  • [4] S. Kripke, Transfinite recursions on admissible ordinals. I, II, (abstracts), J. Symbolic Logic 29 (1964), 161-162.
  • [5] A. H. Lachlan, The elementary theory of recursively enumerable sets, Duke Math. J. 35 (1968), 123-146. MR 37 #2593. MR 0227008 (37:2593)
  • [6] -, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1-37. MR 37 #2594. MR 0227009 (37:2594)
  • [7] M. Lerman, On suborderings of the $ \alpha $-recursively enumerable $ \alpha $-degrees, Ann. Math. Logic 4 (1972), 369-392. MR 0327493 (48:5835)
  • [8] M. Lerman and G. E. Sacks, Some minimal pairs of $ \alpha $-recursively enumerable degrees, Ann. Math. Logic 4 (1972), 415-442. MR 0439605 (55:12491)
  • [9] M. Lerman and S. Simpson, Maximal sets in $ \alpha $-recursion theory, Israel J. Math. 14 (1973), 236-247. MR 0319729 (47:8271)
  • [10] M. Machtey, Admissible ordinals and lattices of $ \alpha $-r.e. sets, Ann. Math. Logic 2 (1970/71), no. 4, 379-417. MR 43 #6090. MR 0280370 (43:6090)
  • [11] D. A. Martin and M. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205-209. MR 43 #6094. MR 0280374 (43:6094)
  • [12] J. Myhill, Problem 9, J. Symbolic Logic 21 (1956), 215. MR 0075894 (17:816c)
  • [13] J. C. Owings, Jr., Recursion, metarecursion, and inclusion, J. Symbolic Logic 32 (1967), 173-179. MR 36 #46. MR 0216951 (36:46)
  • [14] R. W. Robinson, Two theorems on hyperhypersimple sets, Trans. Amer. Math. Soc. 128 (1967), 531-538. MR 35 #6549. MR 0215714 (35:6549)
  • [15] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 0224462 (37:61)
  • [16] G. E. Sacks, Post's problem, admissible ordinals, and regularity, Trans. Amer. Math. Soc. 124 (1966), 1-23. MR 34 #1183. MR 0201299 (34:1183)
  • [17] G. E. Sacks and S. Simpson, The $ \alpha $-finite injury method, Ann. Math. Logic 4 (1972), 343-367. MR 0369041 (51:5277)
  • [18] R. A. Shore, Priority arguments in $ \alpha $-recursion theory, Ph.D. Dissertation, M.I.T., 1972.
  • [19] S. Simpson, Admissible ordinals and recursion theory, Ph.D. Dissertation, M.I.T., 1971.
  • [20] R. Soare, Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets, Ann. of Math. (to appear). MR 0360235 (50:12685)
  • [21] J. Stillwell, Reducibility in generalized recursion theory, Ph.D. Dissertation, M.I.T., 1970.
  • [22] C. E. M. Yates, Three theorems on the degree of recursively enumerable sets, Duke Math. J. 32 (1965), 461-468. MR 31 #4721. MR 0180486 (31:4721)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02F27

Retrieve articles in all journals with MSC: 02F27


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1974-0332458-X
Keywords: Admissible ordinal, $ \alpha $-finite set, $ \alpha $-recursive set, $ \alpha $-r.e. set, maximal set, lattice of $ \alpha $-r.e. sets
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society