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)



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

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

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

American Mathematical Society