Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets
HTML articles powered by AMS MathViewer
- by Wolfgang Maass PDF
- Trans. Amer. Math. Soc. 279 (1983), 311-336 Request permission
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
- Victor L. Bennison and Robert I. Soare, Some lowness properties and computational complexity sequences, Theoret. Comput. Sci. 6 (1978), no. 3, 233–254. MR 479982, DOI 10.1016/0304-3975(78)90007-5
- Wolfgang Maass, Recursively enumerable generic sets, J. Symbolic Logic 47 (1982), no. 4, 809–823 (1983). MR 683156, DOI 10.2307/2273100
- Wolfgang Maass, Richard A. Shore, and Michael Stob, Splitting properties and jump classes, Israel J. Math. 39 (1981), no. 3, 210–224. MR 636890, DOI 10.1007/BF02760850
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Richard A. Shore, Nowhere simple sets and the lattice of recursively enumerable sets, J. Symbolic Logic 43 (1978), no. 2, 322–330. MR 491089, DOI 10.2307/2272830
- Robert I. Soare, Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets, Ann. of Math. (2) 100 (1974), 80–120. MR 360235, DOI 10.2307/1970842
- Robert I. Soare, Computational complexity, speedable and levelable sets, J. Symbolic Logic 42 (1977), no. 4, 545–563. MR 485278, DOI 10.2307/2271876
- Robert I. Soare, Recursively enumerable sets and degrees, Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181. MR 508451, DOI 10.1090/S0002-9904-1978-14552-2 —, Automorphisms of the lattice of recursively enumerable sets. Part II: Low sets (to appear).
Additional Information
- © Copyright 1983 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 279 (1983), 311-336
- MSC: Primary 03D25
- DOI: https://doi.org/10.1090/S0002-9947-1983-0704618-2
- MathSciNet review: 704618