Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets

Author: Wolfgang Maass
Journal: Trans. Amer. Math. Soc. 279 (1983), 311-336
MSC: Primary 03D25
MathSciNet review: 704618
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that the lattice of supersets of a recursively enumerable (r.e.) set $ A$ is effectively isomorphic to the lattice of all r.e. sets if and only if the complement $ \bar A$ of $ A$ is infinite and $ \{ e\vert{W_e} \cap \bar A\;{\text{finite}}\}\;{\leqslant_{1}}\emptyset''$ (i.e. $ \bar A$ is semilow$ _{1.5}$). It is obvious that the condition `` $ \bar{A}\;$   semilow$ _{1.5}$'' is necessary. For the other direction a certain uniform splitting property (the "outer splitting property") is derived from semilow$ _{1.5}$ and this property is used in an extension of Soare's automorphism machinery for the construction of the effective isomorphism. Since this automorphism machinery is quite complicated we give a simplified proof of Soare's Extension Theorem before we add new features to this argument.

References [Enhancements On Off] (What's this?)

  • [1] V. L. Bennison and R. I. Soare, Some lowness properties and computational complexity sequences, Theoret. Comput. Sci. 6 (1978), 233-254. MR 0479982 (58:183)
  • [2] W. Maass, Recursively enumerable generic sets, J. Symbolic Logic 47 (1982), 809-823. MR 683156 (84e:03051)
  • [3] W. Maass, R. A. Shore and M. Stob, Splitting properties and jump classes, Israel J. Math. 39 (1981), 210-224. MR 636890 (84i:03083)
  • [4] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 0224462 (37:61)
  • [5] R. A. Shore, Nowhere simple sets and the lattice of recursively enumerable sets, J. Symbolic Logic 43 (1978), 322-330. MR 0491089 (58:10362)
  • [6] R. I. Soare, Automorphisms of the lattice of recursively enumerable sets. Part I: Maximal sets, Ann. of Math. (2) 100 (1974), 80-120. MR 0360235 (50:12685)
  • [7] -, Computational complexity, speedable and levelable sets, J. Symbolic Logic 42 (1978), 545-563. MR 0485278 (58:5125)
  • [8] -, Recursively enumerable sets and degrees, Bull. Amer. Math. Soc. 84 (1978), 1149-1181. MR 508451 (81g:03050)
  • [9] -, Automorphisms of the lattice of recursively enumerable sets. Part II: Low sets (to appear).

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D25

Retrieve articles in all journals with MSC: 03D25

Additional Information

Article copyright: © Copyright 1983 American Mathematical Society

American Mathematical Society