Almost recursively enumerable sets
Author:
John W. Berry
Journal:
Trans. Amer. Math. Soc. 164 (1972), 241253
MSC:
Primary 02F25
MathSciNet review:
0363839
Fulltext 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.
 [1]
K.
I. Appel and T.
G. McLaughlin, On properties of regressive
sets, Trans. Amer. Math. Soc. 115 (1965), 83–93. MR 0230616
(37 #6176), http://dx.doi.org/10.1090/S00029947196502306160
 [2]
J.
C. E. Dekker, Infinite series of isols, Proc. Sympos. Pure
Math., Vol. V, American Mathematical Society, Providence, R.I., 1962,
pp. 77–96. MR 0142447
(26 #16)
 [3]
J.
C. E. Dekker and J.
Myhill, Retraceable sets, Canad. J. Math. 10
(1958), 357–373. MR 0099292
(20 #5733)
 [4]
J.
C. E. Dekker and J.
Myhill, Recursive equivalence types, Univ. California Publ.
Math. 3 (1960), 67–213. MR 0117155
(22 #7938)
 [5]
T.
G. McLaughlin, Strong reducibility on hypersimple sets, Notre
Dame J. Formal Logic 6 (1965), 229–234. MR 0193012
(33 #1234)
 [6]
Hartley
Rogers Jr., Theory of recursive functions and effective
computability, McGrawHill Book Co., New YorkToronto, Ont.London,
1967. MR
0224462 (37 #61)
 [7]
V.
D. Vučković, Almost recursive sets, Proc. Amer. Math. Soc. 23 (1969), 114–119. MR 0260593
(41 #5217), http://dx.doi.org/10.1090/S00029939196902605937
 [8]
C.
E. M. Yates, Recursively enumerable sets and retracing
functions, Z. Math. Logik Grundlagen Math. 8 (1962),
331–345. MR 0146072
(26 #3598)
 [9]
Paul
R. Young, Linear orderings under oneone reducibility, J.
Symbolic Logic 31 (1966), 70–85. MR 0231720
(38 #48)
 [1]
 K. I. Appel and T. G. McLaughlin, On properties of regressive sets, Trans. Amer. Math. Soc. 155 (1965), 8393. MR 37 #6176. MR 0230616 (37:6176)
 [2]
 J. C. E. Dekker, Infinite series of isols, Proc. Sympos. Pure Math., vol. 5, Amer. Math. Soc., Providence, R. I., 1962, pp. 7796. MR 26 #16. MR 0142447 (26:16)
 [3]
 J. C. E. Dekker and J. Myhill, Retraceable sets, Canad. J. Math. 10 (1958), 357373. MR 20 #5733. MR 0099292 (20:5733)
 [4]
 , Recursive equivalence types, Univ. California Publ. Math. 3 (1960), 67213. MR 22 #7938. MR 0117155 (22:7938)
 [5]
 T. G. McLaughlin, Strong reducibility on hypersimple sets, Notre Dame J. Formal Logic 6 (1965), 229234. MR 33 #1234. MR 0193012 (33:1234)
 [6]
 H. Rogers, Jr., Theory of recursive functions and effective computability, McGrawHill, New York, 1967. MR 37 #61. MR 0224462 (37:61)
 [7]
 V. D. Vuckovic, Almost recursive sets, Proc. Amer. Math. Soc. 23 (1969), 114119. MR 41 #5217. MR 0260593 (41:5217)
 [8]
 C. E. M. Yates, Recursively enumerable sets and retracing functions, Z. Math. Logik Grundlagen Math. 8 (1962), 331345. MR 26 #3598. MR 0146072 (26:3598)
 [9]
 P. R. Young, Linear orderings under oneone reducibility, J. Symbolic Logic 31 (1966), 7085. MR 38 #48. MR 0231720 (38:48)
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/S00029947197203638394
PII:
S 00029947(1972)03638394
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
