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 Free Access

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|{W_e} \cap \bar A\;{\text {finite}}\}\;{\leqslant _{1}}\emptyset ''$ (i.e. $\bar A$ is $\text {semilow}_{1.5}$). It is obvious that the condition “$\bar {A}\; \text {semilow}_{1.5}$” is necessary. For the other direction a certain uniform splitting property (the "outer splitting property") is derived from $\text {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?)

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