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)

 
 

 

Deficiency sets and bounded information reducibilities


Author: Leonard P. Sasso
Journal: Trans. Amer. Math. Soc. 200 (1974), 267-290
MSC: Primary 02F25; Secondary 02F30
DOI: https://doi.org/10.1090/S0002-9947-1974-0469729-2
MathSciNet review: 0469729
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For recursively enumerable sets $ A$ and $ H$ of natural numbers $ H$ is a deficiency set of $ A$ if there is a one-one, recursive function $ f$ with $ A = \operatorname{Rng} (f)$ and $ H = \{ i:(\exists j)[i < j \mathrel{\&} f(j) < f(i)]\} $. The relation between recursively enumerable sets and their deficiency sets under bounded information reducibilities (i.e. weak truth table, truth table, bounded truth table, many-one, and one-one reducibility) is investigated.


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

  • [1] J. C. E. Dekker, Two notes on recursively enumerable sets, Proc. Amer. Math. Soc. 4 (1953), 495-501. MR 15, 385. MR 0058533 (15:385a)
  • [2] -, A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791-796. MR 16, 209. MR 0063995 (16:209b)
  • [3] J. C. E. Dekker and J. Myhill, Retraceable sets, Canad. J. Math. 10 (1958), 357-373. MR 20 #5733. MR 0099292 (20:5733)
  • [4] R. M. Friedberg and H. R. Rogers, Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math. 5 (1959), 117-125. MR 22 #3682. MR 0112831 (22:3682)
  • [5] C. G. Jockusch, Jr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420-436. MR 36 #3649. MR 0220595 (36:3649)
  • [6] R. E. Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic 38 (1973), 199-211. MR 0342381 (49:7127)
  • [7] -, A completely mitotic non-recursive r.e. degree, Trans. Amer. Math. Soc. 184 (1973), 479-507. MR 0398805 (53:2656)
  • [8] D. A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295-310. MR 37 #68. MR 0224469 (37:68)
  • [9] -, A theorem on hyperhypersimple sets, J. Symbolic Logic 28 (1963), 273-278. MR 31 #2145. MR 0177887 (31:2145)
  • [10] J. Myhill, Creative sets, Z. Math. Logik Grundlagen Math. 1 (1955), 97-108. MR 17, 118. MR 0071379 (17:118g)
  • [11] 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)
  • [12] H. G. Rice, Recursive and recursively enumerable orders, Trans. Amer. Math. Soc. 83 (1956), 277-300. MR 18, 712. MR 0083454 (18:712a)
  • [13] R. W. Robinson, A dichotomy of the recursively enumerable sets, Z. Math. Logik Grundlagen Math. 14 (1968), 339-356. MR 38 #5623. MR 0237334 (38:5623)
  • [14] G. E. Sacks, Degrees of unsolvability, Princeton Univ. Press, Princeton, N. J., 1963. MR 32 #4013. MR 0186554 (32:4013)
  • [15] R. I. Soare, The Friedberg-Muchnik theorem re-examined, Canad. J. Math. 24 (1972), 1070-1078. MR 0344096 (49:8836)
  • [16] C. E. M. Yates, Recursively enumerable sets and retracing functions, Z. Math. Logik Grundlagen Math. 8 (1962), 331-345. MR 26 #3598. MR 0146072 (26:3598)
  • [17] -, Three theorems on the degrees 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: 02F25, 02F30

Retrieve articles in all journals with MSC: 02F25, 02F30


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1974-0469729-2
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society