Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-06T00:22:50.858Z Has data issue: false hasContentIssue false
  • English
  • Français

Weakly semirecursive sets

Published online by Cambridge University Press:  12 March 2014

Carl G. Jockusch Jr.  and
James C. Owings Jr.
Carl G. Jockusch Jr.
Affiliation:
Department of Mathematics, University of Illinois, Urbana, Illinois 61801
James C. Owings Jr.
Affiliation:
Department of Mathematics, University of Maryland, College Park, Maryland 20742
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce the notion of “semi-r.e.” for subsets of ω, a generalization of “semirecursive” and of “r.e.”, and the notion of “weakly semirecursive”, a generalization of “semi-r.e.”. We show that A is weakly semirecursive iff, for any n numbers x1, …,xn, knowing how many of these numbers belong to A is equivalent to knowing which of these numbers belong to A. It is shown that there exist weakly semirecursive sets that are neither semi-r.e. nor co-semi-r.e. On the other hand, we exhibit nonzero Turing degrees in which every weakly semirecursive set is semirecursive. We characterize the notion “A is weakly semirecursive and recursive in K” in terms of recursive approximations to A. We also show that if a finite Boolean combination of r.e. sets is semirecursive then it must be r.e. or co-r.e. Several open questions are raised.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 55 , Issue 2 , June 1990 , pp. 637 - 644
Copyright
Copyright © Association for Symbolic Logic 1990

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.)

References

REFERENCES

[1] Beigel, R., Gasarch, W., Gill, J., and Owings, J., Terse, superterse, and verbose sets, Information and Computation (to appear).Google Scholar
[2] Beigel, R., Gasarch, W., and Owings, J., Nondeterministic bounded query reducibilities, Annals of Pure and Applied Logic, vol. 41 (1989), pp. 107–118.CrossRefGoogle Scholar
[3] Jockusch, C. G., Semirecursive sets and positive reducibility, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 420–436.CrossRefGoogle Scholar
[4] Owings, J., A cardinality version of Beigel's nonspeedup theorem, this Journal, vol. 54 (1989), pp. 761–767.Google Scholar
[5] Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, New York, 1987.CrossRefGoogle Scholar