Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-23T07:36:46.352Z Has data issue: false hasContentIssue false
  • English
  • Français

Analytic sets having incomparable kleene degrees

Published online by Cambridge University Press:  12 March 2014

Galen Weitkamp
Galen Weitkamp*
Affiliation:
Western Illinois University, Macomb, Illinois 61455
Get access Rights & Permissions [Opens in a new window]

Extract

One concern of descriptive set theory is the classification of definable sets of reals. Taken loosely ‘definable’ can mean anything from projective to formally describable in the language of Zermelo-Fraenkel set theory (ZF). Recursiveness, in the case of Kleene recursion, can be a particularly informative notion of definability. Sets of integers, for example, are categorized by their positions in the upper semilattice of Turing degrees, and the algorithms for computing their characteristic functions may be taken as their defining presentations. In turn it is interesting to position the common fauna of descriptive set theory in the upper semilattice of Kleene degrees. In so doing not only do we gain a perspective on the complexity of those sets common to the study of descriptive set theory but also a refinement of the theory of analytic sets of reals. The primary concern of this paper is to calculate the relative complexity of several notable coanalytic sets of reals and display (under suitable set theoretic hypothesis) several natural solutions to Post's problem for Kleene recursion.

For sets of reals A and B one says A is Kleene recursive in B (written A ≤KB) iff there is a real y so that the characteristic function XA of A is recursive (in the sense of Kleene [1959]) in y, XB and the existential integer quantifier ∃; i.e. there is an integer e so that XA(x) ≃ {e}(x, y, XB, ≃). Intuitively, membership of a real x ϵ ωω in A can be decided from an oracle for x, y and B using a computing machine with a countably infinite memory and an ability to search and manipulate that memory in finite time. A set is Kleene semirecursive in B if it is the domain of an integer valued partial function recursive in y, XB and ≃ for some real y.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 47 , Issue 4 , December 1982 , pp. 860 - 868
Copyright
Copyright © Association for Symbolic Logic 1982

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

[1975]Barwise, J., Admissible sets and structures: An approach to definability theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-Heidelberg-New York, 1975.Google Scholar
[1968]Boolos, J. and Putnam, H., Degrees of unsolvability of constructible sets of integers, this Journal, vol. 33 (1968), pp. 497–513.Google Scholar
[1971]Friedman, H., Determinacy in the low projective hierarchy, Fundamenta Mathematicae, vol. 72 (1971), pp. 79–84.CrossRefGoogle Scholar
[1978]Harrington, L., Analytic determinacy and O #, this Journal, vol. 43 (1978), pp. 685–693.Google Scholar
[1978]Hrbacek, K., On the complexity of analytic sets, Zeitsckrift für Mathematische Logik mud Grundlagen der Matkematik, vol. 24 (1978), pp. 419–425.CrossRefGoogle Scholar
[1980]Hrbacek, K. and Simpson, S., On Kleene degrees of analytic sets, The Kleene Symposium, North-Holland, Amsterdam, 1980, pp. 347–352.CrossRefGoogle Scholar
[1959]Kleene, S., Recursive functionals and quantifiers of finite types. I, Transactions of the American Mathematical Society, vol. 61 (1959), pp. 193–213.Google Scholar
[19xx]Mansfield, R. and Weitkamp, G., Recursive aspects of descriptive set theory, Oxford Logic Guide Series, Oxford University Press (to appear).Google Scholar
[1976]Sacks, G., Countable admissible ordinals and hyper degrees, Advances in Mathematics, vol. 20 (1976), pp. 213–262.CrossRefGoogle Scholar
[1967]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[19xx]Simpson, S. and Weitkamp, G., Analytic sets with neither high nor low Kleene degree (to appear).Google Scholar
[1971]Solovay, R., Determinacy and type-2 recursion (abstract), this Journal, vol. 36 (1971), p. 374.Google Scholar
[1976]Steel, J., Ph.D. Thesis, University of California, Berkeley, 1976.Google Scholar
[1980]Weitkamp, G., Ph.D. Thesis, Pennsylvania State University, University Park, 1980.Google Scholar