Automorphisms of the lattice of recursively enumerable sets: promptly simple sets

Cholak, P.; Downey, R.; Stob, M.

doi:10.1090/S0002-9947-1992-1097164-6

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

Automorphisms of the lattice of recursively enumerable sets

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

The relationship between the structure and degrees of recursively enumerable sets

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