Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-19T05:24:45.622Z Has data issue: false hasContentIssue false
  • English
  • Français

Recursively enumerable sets which are uniform for finite extensions1

Published online by Cambridge University Press:  12 March 2014

Donald A. Alton
Donald A. Alton*
Affiliation:
The University of Iowa, Iowa City, Iowa 52240
Get access Rights & Permissions [Opens in a new window]

Extract

Let W0, W1 … be one of the usual enumerations of recursively enumerable (r.e.) subsets of the set N of nonnegative integers. (Background information will be given later.) Suggestions of Anil Nerode led to the following

Definitions. Let B be a subset of N and let ψ be a partial recursive function.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 36 , Issue 2 , June 1971 , pp. 271 - 287
Copyright
Copyright © Association for Symbolic Logic 1971

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

Major portions of this paper appeared as part of the author's doctoral dissertation at Cornell University. Theorem 3 and related comments were added later. The author wishes to thank Anil Nerode, his advisor, for his encouragement and guidance, and George Metakides for his willingness to listen to the arguments in this paper in detail and for providing a language which makes the initial definitions more palatable. As a graduate student the author benefited from numerous conversations with Professor Robert I. Soare (University of Illinois at Chicago Circle) concerning the intricacies of priority arguments, although these conversations did not touch on the specific concepts in this paper. This research was done while the author held an NSF Graduate Fellowship.

References

[1]Dekker, James C. E., A theorem on hypersimple sets, Proceedings of the American Mathematical Society, vol. 5 (1954), pp. 791–796.CrossRefGoogle Scholar
[2]Friedberg, Richard M., Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem 1944), Proceedings of the National Academy of Sciences, vol. 43 (1957), pp. 236–238.CrossRefGoogle ScholarPubMed
[3]Lachlan, A. H., Complete recursively enumerable sets, Proceedings of the American Mathematical Society, vol. 19 (1968), pp. 99–102.CrossRefGoogle Scholar
[4]Lachlan, A. H., Degrees of recursively enumerable sets which have no maximal supersets, this Journal, vol. 33 (1968), pp. 431–443.Google Scholar
[5]Martin, Donald A., Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 295–310.CrossRefGoogle Scholar
[6]Martin, Donald A., Completeness, the recursion theorem, and effectively simple sets, Proceedings of the American Mathematical Society, vol. 17 (1966), pp. 838–842.CrossRefGoogle Scholar
[7]Muchnik, A. A., On the unsolvability of the problem of reducibility in the theory of algorithm (Russian), Doklady Akademii Nauk SSSR, N.S., vol. 108 (1956), pp. 194–197.Google Scholar
[8]Post, Emil L., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.CrossRefGoogle Scholar
[9]Robinson, Robert W., A dichotomy of the recursively enumerable sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 339–356.CrossRefGoogle Scholar
[10]Robinson, Robert W., Recursively enumerable sets not contained in any maximal set, Abstract 632–4, Notices of the American Mathematical Society, vol. 13 (1966), p. 325.Google Scholar
[11]Rogers, Hartley Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[12]Sacks, Gerald E., Degrees of unsolvability, Annals of Mathematics Studies, No. 55, Princeton, N.J., 1963.Google Scholar
[13]Shoenfield, J. R., On degrees of unsolvability, Annals of Mathematics, vol. 69 (1959), pp. 644–653.CrossRefGoogle Scholar
[14]Smullyan, R. M., Effectively simple sets. Proceedings of the American Mathematical Society, vol. 15 (1964), pp. 893–894.CrossRefGoogle Scholar
[15]Yates, C. E. M., Three theorems on the degrees of recursively enumerable sets. Duke Mathematical Journal, vol. 32 (1965), pp. 461–468.CrossRefGoogle Scholar