Isomorphism of lattices of

recursively enumerable sets

Author:
Todd Hammond

Journal:
Trans. Amer. Math. Soc. **349** (1997), 2699-2719

MSC (1991):
Primary 03D25

DOI:
https://doi.org/10.1090/S0002-9947-97-01604-8

MathSciNet review:
1348861

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let , and for , let be the lattice of subsets of which are recursively enumerable relative to the ``oracle'' . Let be , where is the ideal of finite subsets of . It is established that for any , is effectively isomorphic to if and only if , where is the Turing jump of . A consequence is that if , then . A second consequence is that can be effectively embedded into preserving least and greatest elements if and only if .

**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**

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:
https://doi.org/10.1090/S0002-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.

Article copyright:
© Copyright 1997
American Mathematical Society