Isomorphism of lattices of

recursively enumerable sets

Author:
Todd Hammond

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

MSC (1991):
Primary 03D25

MathSciNet review:
1348861

Full-text PDF Free Access

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.**Lawrence Feiner,*Hierarchies of Boolean algebras*, J. Symbolic Logic**35**(1970), 365–374. MR**0282805****2.**John Todd Hammond,*Nonisomorphism of lattices of recursively enumerable sets*, J. Symbolic Logic**58**(1993), no. 4, 1177–1188. MR**1253915**, 10.2307/2275136**3.**A. H. Lachlan,*On the lattice of recursively enumerable sets*, Trans. Amer. Math. Soc.**130**(1968), 1–37. MR**0227009**, 10.1090/S0002-9947-1968-0227009-1**4.**Wolfgang Maass,*Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets*, Trans. Amer. Math. Soc.**279**(1983), no. 1, 311–336. MR**704618**, 10.1090/S0002-9947-1983-0704618-2**5.**Hartley Rogers Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462****6.**Raymond M. Smullyan,*Theory of formal systems*, Annals of Mathematics Studies, No. 47, Princeton University Press, Princeton, N.J., 1961. MR**0121300**

Raymond M. Smullyan,*Theory of formal systems*, Revised edition, Princeton University Press, Princeton, N. J., 1961. MR**0152429****7.**Robert I. Soare,*Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets*, Ann. of Math. (2)**100**(1974), 80–120. MR**0360235****8.**Robert I. Soare,*Automorphisms of the lattice of recursively enumerable sets. II. Low sets*, Ann. Math. Logic**22**(1982), no. 1, 69–108. MR**661478**, 10.1016/0003-4843(82)90016-X**9.**Robert I. Soare,*Recursively enumerable sets and degrees*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR**882921**

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:
http://dx.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