Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-13T01:10:33.134Z Has data issue: false hasContentIssue false
  • English
  • Français

Some nondistributive lattices as initial segments of the degrees of unsolvability1

Published online by Cambridge University Press:  12 March 2014

Manuel Lerman
Manuel Lerman*
Affiliation:
Cornell University
Get access Rights & Permissions [Opens in a new window]

Extract

The question, “What do initial segments of the degrees of unsolvability look like?” has interested recursive function theorists for several years. Sacks [4] hypothesized that Sis a finite initial segment of degrees if and only if S is order-isomorphic to a finite initial segment of some upper semilattice with a least element. Lachlan [2] suggested the generalization, S is an initial segment of degrees if S is order-isomorphic to some countable upper semilattice with both least and greatest elements.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 34 , Issue 1 , 29 May 1969 , pp. 85 - 98
Copyright
Copyright © Association for Symbolic Logic 1969

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

This work was partly supported by NSF grant GP 8732. We are grateful to A. Nerode for many helpful discussions on this problem.

References

[1]Birkhoff, G., Lattice theory, American Mathematical Society Colloquium Publications, vol. XXV, American Mathematical Society, Providence, R.I., 1948.Google Scholar
[2]Hugill, D. F. and Lachlan, A. H., Distributive initial segments of the degrees of unsolvability (to appear).Google Scholar
[3]Ryser, H. J., Combinatorial mathematics, The Carus Mathematical Monographs, number 14, Mathematical Association of America, Wiley, New York, 1963.Google Scholar
[4]Sacks, G. E., Degrees of unsolvability, Annals of mathematics studies, number 55, Princeton Univ. Press, Princeton, N.J., 1963.Google Scholar
[5]Spector, C., On degrees of recursive unsolvability, Annals of mathematics, vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar