Available in electronic format
Available in print format
Transacrions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
     

Isomorphism of lattices of recursively enumerable sets

Author(s): Todd Hammond
Journal: Trans. Amer. Math. Soc. 349 (1997), 2699-2719.
MSC (1991): Primary 03D25
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract | References | Similar articles | Additional information

Abstract: Let $\omega = \{\,0,1,2,\ldots \,\}$, and for $A\subseteq \omega$, let $\mathcal E^A$ be the lattice of subsets of $\omega $ which are recursively enumerable relative to the ``oracle'' $A$. Let $(\mathcal E^A)^*$ be $\mathcal E^A/\mathcal I$, where $\mathcal I$ is the ideal of finite subsets of $\omega $. It is established that for any $A,B\subseteq \omega$, $(\mathcal E^A)^*$ is effectively isomorphic to $(\mathcal E^B)^*$ if and only if $A'\equiv _T B'$, where $A'$ is the Turing jump of $A$. A consequence is that if $A'\equiv _T B'$, then $\mathcal E^A\cong \mathcal E^B$. A second consequence is that $(\mathcal E^A)^*$ can be effectively embedded into $(\mathcal E^B)^*$ preserving least and greatest elements if and only if $A'\leq _T B'$.


References:

1.
L. Feiner, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1970), 365-374. MR 44:39

2.
T Hammond, Nonisomorphism of lattices of recursively enumerable sets, J. Symbolic Logic 58 (1993), 1177-1188. MR 95c:03100

3.
A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1-37. MR 37:2594

4.
W. Maass, Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets, Trans. Amer. Math. Soc. 279 (1983), 311-336. MR 85e:03099

5.
H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967. MR 37:61

6.
R. M. Smullyan, Theory of formal systems, Annals of Mathematics Studies, no. 47, Princeton, N. J., 1961. MR 22:12042; MR 27:2409

7.
R. I. Soare, Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets, Ann. of Math. (2) 100 (1974), 80-120. MR 50:12685

8.
R. I. Soare, Automorphisms of the lattice of recursively enumerable sets, Part II: Low sets, Ann. Math. Logic 22 (1982), 69-107. MR 83k:03048

9.
R. I. Soare, Recursively enumerable sets and degrees: a study of computable functions and computably generated sets, Springer-Verlag, Berlin, Heidelberg, New York, London, Paris, Tokyo, 1987. MR 88m:03003


Similar Articles:

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

Retrieve articles in all Journals with MSC (1991): 03D25


Additional Information:

Todd Hammond
Affiliation: Division of Mathematics and Computer Science, Truman State University, Kirksville, Missouri 63501
Email: thammond@math.nemostate.edu

DOI: 10.1090/S0002-9947-97-01604-8
PII: S 0002-9947(97)01604-8
Keywords: Effective isomorphism, effectively isomorphic, recursively enumerable, oracle, Turing jump, effective embedding, effectively embeddable.
Received by editor(s): December 17, 1991
Received by editor(s) in revised form: August 3, 1995
Additional Notes: This paper is based primarily on part of the author's Ph.D. thesis, written under the supervision of Professor Robert Vaught.
Copyright of article: Copyright 1997, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google