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

A topological analog to the Rice-Shapiro index theorem

Published online by Cambridge University Press:  12 March 2014

Louise Hay  and
Douglas Miller
Louise Hay
Affiliation:
University of Illinoisat Chicago Circle, Chicago, Illinois 60680
Douglas Miller
Affiliation:
University of Illinoisat Chicago Circle, Chicago, Illinois 60680
Get access Rights & Permissions [Opens in a new window]

Extract

Ever since Craig-Beth and Addison-Kleene proved their versions of the Lusin-Suslin theorem, work in model theory and recursion theory has demonstrated the value of classical descriptive set theory as a source of ideas and inspirations. During the sixties in particular, J.W. Addison refined the technique of “conjecture by analogy” and used it to generate a substantial number of results in both model theory and recursion theory (see, e.g., Addison [1], [2], [3]).

During the past 15 years, techniques and results from recursion theory and model theory have played an important role in the development of descriptive set theory. (Moschovakis's book [6] is an excellent reference, particularly for the use of recursion-theoretic tools.) The use of “conjecture by analogy” as a means of transferring ideas from model theory and recursion theory to descriptive set theory has developed more slowly. Some notable recent examples of this phenomenon are in Vaught [9], where some results in invariant descriptive set theory reflecting and extending model-theoretic results are obtained and others are left as conjectures (including a version of the well-known conjecture on the number of countable models) and in Hrbacek and Simpson [4], where a notion analogous to that of Turing reducibility is used to study Borel isomorphism types. Moschovakis [6] describes in detail an effective descriptive set theory based in large part on classical recursion theory.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 47 , Issue 4 , December 1982 , pp. 824 - 832
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

BIBLIOGRAPHY

[1]Addison, J.W., The theory of hierarchies, Logic, Methodology and Philosophy of Science (Proceedings of the International Congress, 1960), Stanford Unversity Press, Stanford, 1962, pp. 26–37.Google Scholar
[2]Addison, J.W., Some problems in hierarchy theory, Proceedings of the Symposia in Pure Mathematics, vol. 5, American Mathematical Society, Providence, R.I., 1962, pp. 123–130.Google Scholar
[3]Addison, J.W., Current problems in descriptive set theory, Proceedings of the Symposia in Pure Mathematics, vol. 13, Part II, American Mathematical Society, Providence, R.I., 1974, pp. 1–10.Google Scholar
[4]Hrbacek, K. and Simpson, S., On Kleene degrees of analytic sets, Proceedings of Kleene Conference, Madison, 1978 (Barwise, , Keisler, , Kunen, , Editors), North-Holland, Amsterdam, 1980, pp. 347–353.Google Scholar
[5]Miller, D., Remarks on topological index sets (in preparation).Google Scholar
[6]Moschovakis, Y., Descriptive set theory, North-Holland, Amsterdam, 1980.Google Scholar
[7]Rice, H.G., Classes of recursively enumerable sets and their decision problems, this Journal, vol. 74 (1953), pp. 358–366.Google Scholar
[8]Rogers, H., Theory of recursive functions, McGraw-Hill, New York, 1967.Google Scholar
[9]Vaught, R.L., Invariant sets in topology and logic, Fundamenta Mathematicae, vol. 82 (1974), pp. 269–294.CrossRefGoogle Scholar