|
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 , 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 .
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
|