Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-25T18:17:32.501Z Has data issue: false hasContentIssue false
  • English
  • Français

Noninitial segments of the α-degrees1

Published online by Cambridge University Press:  12 March 2014

John M. Macintyre
John M. Macintyre*
Affiliation:
State University of New York at Buffalo, Amherst, New York 14226
Get access Rights & Permissions [Opens in a new window]

Extract

Let α be an admissible ordinal and let L be the first order language with equality and a single binary relation ≤. The elementary theory of the α-degrees is the set of all sentences of L which are true in the universe of the α-degrees when ≤ is interpreted as the partial ordering of the α-degrees. Lachlan [6] showed that the elementary theory of the ω-degrees is nonaxiomatizable by proving that any countable distributive lattice with greatest and least members can be imbedded as an initial segment of the degrees of unsolvability. This paper deals with the extension of these results to α-recursion theory for an arbitrary countable admissible α > ω. Given α, we construct a set A with α-degree a such that every countable distributive lattice with greatest and least member is order isomorphic to a segment of α-degrees {d ∣ a ≤αd≤αb} for some α-degree b. As in [6] this implies that the elementary theory of the α-degrees is nonaxiomatizable and hence undecidable.

A is constructed in §2. A is a set of integers which is generic with respect to a suitable notion of forcing. Additional applications of such sets are summarized at the end of the section. In §3 we define the notion of a tree and construct a particular tree T0 which is weakly α-recursive in A. Using T0 we can apply the techniques of [6] and [2] to α-recursion theory. In §4 we reduce our main results to three technical lemmas concerning systems of trees. These lemmas are proved in §5.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 38 , Issue 3 , September 1973 , pp. 368 - 388
Copyright
Copyright © Association for Symbolic Logic 1973

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

Most of the material in this paper appears in the author's Ph.D. Thesis (M.I.T., 1968) supervised by Gerald E. Sacks whose help and enthusiasm were indispensable.

References

BIBLIOGRAPHY

[1]Grzegorczyk, A., Undecidability of some topological theories, Fundamenta Mathematicae, vol. 38 (1951), pp. 137–152.CrossRefGoogle Scholar
[2]Hugill, D. F., Initial segments of Turing degrees, Proceedings of the London Mathematical Society, vol. 19 (1969), pp. 1–16.CrossRefGoogle Scholar
[3]Kleene, S. C., Introduction to metamathematics, Van Nostrand, Princeton, N.J., 1952.Google Scholar
[4]Kreisel, G. and Sacks, G. E., Metarecursive sets, this Journal, vol. 30 (1965), pp. 318–338.Google Scholar
[5]Kripke, S., Transfinite recursions on the admissible ordinals. I. II, Admissible ordinals and the analytic hierarchy, this Journal, vol. 29 (1964), pp. 161–162. AbstractsGoogle Scholar
[6]Lachlan, A. H., Distributive initial segments of the degrees of unsoloability, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 457–472.CrossRefGoogle Scholar
[7]MacIntyre, J. M., Contributions to metarecursion theory, Ph.D. Thesis, M.I.T., Cambridge, Mass., 1968.Google Scholar
[8]Sacks, G. E., Post's problem, admissible ordinals and regularity, Transactions of the American Mathematical Society, vol. 124 (1966), pp. 1–23.Google Scholar
[9]Sacks, G. E., Metarecursion theory, Sets, models, and recursion theory (Crossley, J. N., Editor), North-Holland, Amsterdam, 1967.Google Scholar
[10]Simpson, S. G., Admissible ordinals and recursion theory, Ph.D. Thesis, M.I.T., Cambridge, Mass., 1971.Google Scholar
[11]Spector, C., On degrees of recursive unsolvability, Annals of Mathematics, vol. 64 (1956), pp. 581–592.Google Scholar