-complete sets are not necessarily -complete

Author:
A. H. Lachlan

Journal:
Proc. Amer. Math. Soc. **48** (1975), 429-434

DOI:
https://doi.org/10.1090/S0002-9939-1975-0357087-X

MathSciNet review:
0357087

Full-text PDF

Abstract | References | Additional Information

Abstract: A recursively enumerable set is constructed which is complete with respect to weak truth-table reducibility but not with respect to truth-table reducibility. In contrast it is also shown that, when bounded weak truth-table reducibility is defined in the natural way, completeness with respect to this reducibility is the same as that with respect to bounded truth-table reducibility.

**[1]**R. M. Friedberg and H.Rogers, Jr.,*Reducibility and completeness for sets of integers*, Z. Math. Logik Grundlagen Math.**5**(1959), 117-125. MR**22**#3682. MR**0112831 (22:3682)****[2]**A. H. Lachlan,*Some notions of reducibility and productiveness*, Z. Math. Logik Grundlagen Math.**11**(1965), 17-44. MR**30**#3014. MR**0172795 (30:3014)****[3]**-,*A note on universal sets*, J. Symbolic Logic**31**(1966), 573-574. MR**35**#2732. MR**0211857 (35:2732)****[4]**R. E. Ladner and L. P. Sasso, Jr.,*The weak truth-table degrees of recursively enumerable sets*(preprint).**[5]**D. A. Martin,*Completeness, the recursion theorem, and effectively simple sets*, Proc. Amer. Math. Soc.**17**(1966), 838-842. MR**36**#45. MR**0216950 (36:45)****[6]**E. L. Post,*Recursively enumerable sets of positive integers and their decision problems*, Bull. Amer. Math. Soc.**50**(1944), 284-316. MR**6**, 29. MR**0010514 (6:29f)****[7]**H. Rogers, Jr.*Theory of recursive functions and effective computability*, McGraw-Hill, New York, 1967. MR**37**#61. MR**0224462 (37:61)**

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1975-0357087-X

Article copyright:
© Copyright 1975
American Mathematical Society