Automorphisms of the lattice of recursively enumerable sets: promptly simple sets
HTML articles powered by AMS MathViewer
- by P. Cholak, R. Downey and M. Stob PDF
- Trans. Amer. Math. Soc. 332 (1992), 555-570 Request permission
Abstract:
We show that for every coinfinite r.e. set $A$ there is a complete r.e. set $B$ such that ${\mathcal {L}^{\ast } }(A){ \approx _{{\text {eff}}}}{\mathcal {L}^{\ast } }(B)$ and that every promptly simple set is automorphic (in ${\mathcal {E}^{\ast } }$) to a complete set.References
-
P. Cholak, Automorphisms of the lattice of recursively enumerable sets (in preparation).
—, Automorphisms of the lattice of recursively enumerable sets, Ph.D. Dissertation, Univ. of Wisconsin, 1991.
- J. C. E. Dekker and J. Myhill, Retraceable sets, Canadian J. Math. 10 (1958), 357–373. MR 99292, DOI 10.4153/CJM-1958-035-x
- R. G. Downey and Michael Stob, Automorphisms of the lattice of recursively enumerable sets: orbits, Adv. Math. 92 (1992), no. 2, 237–265. MR 1155466, DOI 10.1016/0001-8708(92)90065-S
- Leo Harrington and Robert I. Soare, Post’s program and incomplete recursively enumerable sets, Proc. Nat. Acad. Sci. U.S.A. 88 (1991), no. 22, 10242–10246. MR 1133585, DOI 10.1073/pnas.88.22.10242
- Carl G. Jockusch Jr., Uniformly introreducible sets, J. Symbolic Logic 33 (1968), 521–536. MR 237330, DOI 10.2307/2271359
- A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1–37. MR 227009, DOI 10.1090/S0002-9947-1968-0227009-1
- 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, DOI 10.1090/S0002-9947-1983-0704618-2
- Wolfgang Maass, On the orbits of hyperhypersimple sets, J. Symbolic Logic 49 (1984), no. 1, 51–62. MR 736602, DOI 10.2307/2274090
- 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
- S. S. Marčenkov, A certain class of incomplete sets, Mat. Zametki 20 (1976), no. 4, 473–478 (Russian). MR 479983
- Donald A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295–310. MR 224469, DOI 10.1002/malq.19660120125 D. Miller, The relationship between the structure and degrees of recursively enumerable sets, Ph.D. Dissertation, Univ. of Chicago, 1981.
- Piergiorgio Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland Publishing Co., Amsterdam, 1989. The theory of functions and sets of natural numbers; With a foreword by G. E. Sacks. MR 982269
- 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, Automorphisms of the lattice of recursively enumerable sets. II. Low sets, Ann. Math. Logic 22 (1982), no. 1, 69–108. MR 661478, DOI 10.1016/0003-4843(82)90016-X
- 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, DOI 10.1007/978-3-662-02460-7
- C. E. M. Yates, Three theorems on the degrees of recursively enumerable sets, Duke Math. J. 32 (1965), 461–468. MR 180486
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 332 (1992), 555-570
- MSC: Primary 03D25
- DOI: https://doi.org/10.1090/S0002-9947-1992-1097164-6
- MathSciNet review: 1097164