Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Almost recursively enumerable sets


Author: John W. Berry
Journal: Trans. Amer. Math. Soc. 164 (1972), 241-253
MSC: Primary 02F25
MathSciNet review: 0363839
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: An injective function on N, the nonnegative integers, taking values in N, is called almost recursive (abbreviated a.r.) if its inverse has a partial recursive extension. The range of an a.r. function f is called an almost recursively enumerable set in general; an almost recursive set if in addition f is strictly increasing. These are natural generalizations of regressive and retraceable sets respectively. We show that an infinite set is almost recursively enumerable iff it is point decomposable in the sense of McLaughlin. This leads us to new characterizations of certain classes of immune sets. Finally, in contrast to the regressive case, we show that a.r. functions and sets are rather badly behaved with respect to recursive equivalence.


References [Enhancements On Off] (What's this?)


Similar Articles

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

Retrieve articles in all journals with MSC: 02F25


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1972-0363839-4
PII: S 0002-9947(1972)0363839-4
Keywords: Almost recursive set, almost recursively enumerable set, retraceable set, regressive set, hyperhyperimmune set, recursively enumerable sequences, discrete arrays, recursive equivalence types
Article copyright: © Copyright 1972 American Mathematical Society