Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-30T12:24:08.948Z Has data issue: false hasContentIssue false
  • English
  • Français

Nonisomorphism of lattices of recursively enumerable sets

Published online by Cambridge University Press:  12 March 2014

John Todd Hammond
John Todd Hammond*
Affiliation:
Department of Mathematics, University of Chicago, Chicago, Illinois 60637, E-mail: hammond@zaphod.uchicago.edu
Get access Rights & Permissions [Opens in a new window]

Extract

Let ω be the set of natural numbers, let be the lattice of recursively enumerable subsets of ω, and let A be the lattice of subsets of ω which are recursively enumerable in A. If U, V ⊆ ω, put U =* V if the symmetric difference of U and V is finite.

A natural and interesting question is then to discover what the relation is between the Turing degree of A and the isomorphism class of A. The first result of this form was by Lachlan, who proved [6] that there is a set A ⊆ ω such that A ≇ . He did this by finding a set A ⊆ ω and a set C ϵ A such that the structure ({W ϵ A∣W ⊇ C},∪,∩)/=* is a Boolean algebra and is not isomorphic to the structure ({W ϵ ∣W ⊇ D},∪,∩)/=* for any D ϵ . There is a nonrecursive ordinal which is recursive in the set A which he constructs, so his set A is not (see, for example, Shoenfield [11] for a definition of what it means for a set A ⊆ ω to be ). Feiner then improved this result substantially by proving [1] that for any B ⊆ ω, B′ ≇ B, where B′ is the Turing jump of B. To do this, he showed that for each X ⊆= ω there is a Boolean algebra which is but not and then applied a theorem of Lachlan [6] (definitions of and Boolean algebras will be given in §2). Feiner's result is of particular interest for the case B = ⊘, for it shows that the set A of Lachlan can actually be chosen to be arithmetical (in fact, ⊘′), answering a question that Lachlan posed in his paper. Little else has been known.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 58 , Issue 4 , December 1993 , pp. 1177 - 1188
Copyright
Copyright © Association for Symbolic Logic 1993

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]Feiner, L., Hierarchies of Boolean algebras, this Journal, vol. 35 (1970), pp. 365–374.Google Scholar
[2]Feiner, L., Degrees of nonrecursive presentability, Proceedings of the American Mathematical Society, vol. 38 (1973), pp. 621–624.CrossRefGoogle Scholar
[3]Hammond, T., Isomorphism of lattices of recursively enumerable sets (to appear).Google Scholar
[4]Harrington, L., The lattice of r.e. sets is undecidable (again), 1983 (handwritten notes).Google Scholar
[5]Koppelberg, S., Special classes of Boolean algebras, Handbook of Boolean algebras (Monk, J. Donald, editor), North-Holland, Amsterdam, New York, Oxford, Tokyo, 1989, pp. 239–284.Google Scholar
[6]Lachlan, A. H., On the lattice of recursively enumerable sets, Transactions of the American Mathematical Society, vol. 130 (1968), pp. 1–37.CrossRefGoogle Scholar
[7]Lerman, M., Degrees of unsolvability, Perspectives in Mathematical Logic, Omega Series, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1983.CrossRefGoogle Scholar
[8]Odintsov, S. P. and Selivanov, V. L., Arithmetical hierarchy and ideals of numbered Boolean algebras, Siberian Mathematical Journal, vol. 30 (1989), no. 6, pp. 952–960.CrossRefGoogle Scholar
[9]Remmel, J. B., Recursive Boolean algebras, Handbook of Boolean algebras (Monk, J. Donald, editor), North-Holland, Amsterdam, New York, Oxford, Tokyo, 1989, pp. 1097–1165.Google Scholar
[10]Rosenstein, J. G., Linear orderings, Academic Press, New York, 1982.Google Scholar
[11]Shoenfield, J. R., Mathematical logic, Addison-Wesley, Reading, Massachusetts, 1967.Google Scholar
[12]Soare, R. I., Recursively enumerable sets and degrees: a study of computable functions and computably generated sets. Springer-Verlag, Berlin, Heidelberg, New York, London, Paris, Tokyo, 1987.CrossRefGoogle Scholar