Deficiency sets and bounded information reducibilities

Sasso, Leonard P.

doi:10.1090/S0002-9947-1974-0469729-2

Deficiency sets and bounded information reducibilities
HTML articles powered by AMS MathViewer

by Leonard P. Sasso

Trans. Amer. Math. Soc. 200 (1974), 267-290

DOI: https://doi.org/10.1090/S0002-9947-1974-0469729-2

PDF | Request permission

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 \& 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

J. C. E. Dekker, Two notes on recursively enumerable sets, Proc. Amer. Math. Soc. 4 (1953), 495–501. MR 58533, DOI 10.1090/S0002-9939-1953-0058533-7
J. C. E. Dekker, A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791–796. MR 63995, DOI 10.1090/S0002-9939-1954-0063995-6
J. C. E. Dekker and J. Myhill, Retraceable sets, Canadian J. Math. 10 (1958), 357–373. MR 99292, DOI 10.4153/CJM-1958-035-x
Richard M. Friedberg and Hartley Rogers Jr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math. 5 (1959), 117–125. MR 112831, DOI 10.1002/malq.19590050703
Carl G. Jockusch Jr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420–436. MR 220595, DOI 10.1090/S0002-9947-1968-0220595-7
Richard E. Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic 38 (1973), 199–211. MR 342381, DOI 10.2307/2272056
Richard E. Ladner, A completely mitotic nonrecursive r.e. degree, Trans. Amer. Math. Soc. 184 (1973), 479–507 (1974). MR 398805, DOI 10.1090/S0002-9947-1973-0398805-7
Donald A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295–310. MR 224469, DOI 10.1002/malq.19660120125
Donald A. Martin, A theorem on hyperhypersimple sets, J. Symbolic Logic 28 (1963), 273–278. MR 177887, DOI 10.2307/2271305
John Myhill, Creative sets, Z. Math. Logik Grundlagen Math. 1 (1955), 97–108. MR 71379, DOI 10.1002/malq.19550010205
Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1
H. G. Rice, Recursive and recursively enumerable orders, Trans. Amer. Math. Soc. 83 (1956), 277–300. MR 83454, DOI 10.1090/S0002-9947-1956-0083454-0
Robert W. Robinson, A dichotomy of the recursively enumerable sets, Z. Math. Logik Grundlagen Math. 14 (1968), 339–356. MR 237334, DOI 10.1002/malq.19680142105
Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
Robert I. Soare, The Friedberg-Muchnik theorem re-examined, Canadian J. Math. 24 (1972), 1070–1078. MR 344096, DOI 10.4153/CJM-1972-110-4
C. E. M. Yates, Recursively enumerable sets and retracing functions, Z. Math. Logik Grundlagen Math. 8 (1962), 331–345. MR 146072, DOI 10.1002/malq.19620080313
C. E. M. Yates, Three theorems on the degrees of recursively enumerable sets, Duke Math. J. 32 (1965), 461–468. MR 180486