Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-09T15:07:57.166Z Has data issue: false hasContentIssue false
  • English
  • Français

On the orbits of hyperhypersimple sets

Published online by Cambridge University Press:  12 March 2014

Wolfgang Maass
Wolfgang Maass*
Affiliation:
University of Illinois at Chicago, Chicago, Illinois 60680
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper contributes to the question of under which conditions recursively enumerable sets with isomorphic lattices of recursively enumerable-supersets are automorphic in the lattice of all recursively enumerable sets. We show that hyperhypersimple sets (i.e. sets where the recursively enumerable supersets form a Boolean algebra) are automorphic if there is a -definable isomorphism between their lattices of supersets. Lerman, Shore and Soare have shown that this is not true if one replaces by .

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 49 , Issue 1 , March 1984 , pp. 51 - 62
Copyright
Copyright © Association for Symbolic Logic 1984

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]Lachlan, A. H., On the lattice of recursively enumerable sets, Transactions of the American Mathematical Society, vol. 130 (1968), pp. 1–37.CrossRefGoogle Scholar
[2]Lerman, M., Shore, R. A. and Soare, R. I., r-maximal major subsets, Israel Journalof Mathematics, vol. 31 (1978), pp. 1–18.CrossRefGoogle Scholar
[3]Maass, W., Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets, Transactions of the American Mathematical Society, vol. 279 (1983), pp. 311–336.CrossRefGoogle Scholar
[4]Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift für Mathematische Logik and Grundlagen der Mathematik, vol. 12 (1966), pp. 295–310.CrossRefGoogle Scholar
[5]Soare, R. I., Automorphisms of the lattice of recursively enumerable sets. Part I: Maximal sets, Annals of Mathematics, ser. 2, vol. 100 (1974), pp. 80–120.CrossRefGoogle Scholar
[6]Soare, R. I., Computational complexity, speedable and levelable sets, this Journal, vol. 42 (1977), pp. 545–563.Google Scholar
[7]Soare, R. I., Recursively enumerable sets and degrees, Bulletin of the American Mathematical Society, vol. 84 (1978), pp. 1149–1181.CrossRefGoogle Scholar