The Δ₃⁰-automorphism method and noninvariant classes of degrees

Harrington, Leo; Soare, Robert

doi:10.1090/S0894-0347-96-00181-6

The $\Delta _3^0$-automorphism method and noninvariant classes of degrees
HTML articles powered by AMS MathViewer

by Leo Harrington and Robert I. Soare PDF

J. Amer. Math. Soc. 9 (1996), 617-666 Request permission

Abstract:

A set $A$ of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let $\mathcal {E}$ denote the structure of the computably enumerable sets under inclusion, $\mathcal {E} = ( \{ W_e \}_{e\in \omega }, \subseteq )$. Most previously known automorphisms $\Phi$ of the structure $\mathcal {E}$ of sets were effective (computable) in the sense that $\Phi$ has an effective presentation. We introduce here a new method for generating noneffective automorphisms whose presentation is $\Delta ^0_3$, and we apply the method to answer a number of long open questions about the orbits of c.e. sets under automorphisms of $\mathcal {E}$. For example, we show that the orbit of every noncomputable ( i.e., nonrecursive) c.e. set contains a set of high degree, and hence that for all $n>0$ the well-known degree classes $\mathbf {L}_n$ (the low$_n$ c.e. degrees) and $\overline {\mathbf {H}}_n = \mathbf {R} - \mathbf {H}_n$ (the complement of the high$_n$ c.e. degrees) are noninvariant classes.

References

Klaus Ambos-Spies and André Nies, Cappable recursively enumerable degrees and Post’s program, Arch. Math. Logic 32 (1992), no. 1, 51–56. MR 1186466, DOI 10.1007/BF01270394
P. A. Cholak, Automorphisms of the lattice of recursively enumerable sets, Ph.D. dissertation, Univ. of Wisconsin-Madison, 1991.
Peter Cholak, Automorphisms of the lattice of recursively enumerable sets, Mem. Amer. Math. Soc. 113 (1995), no. 541, viii+151. MR 1227497, DOI 10.1090/memo/0541
P. Cholak, R. Downey, and M. Stob, Automorphisms of the lattice of recursively enumerable sets: promptly simple sets, Trans. Amer. Math. Soc. 332 (1992), no. 2, 555–570. MR 1097164, DOI 10.1090/S0002-9947-1992-1097164-6
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
T. Hammond, The Lattice of Sets Recursively Enumerable in an Oracle, University of California at Berkeley, Berkeley, California, 1990.
L. Harrington, A. H. Lachlan, W. Maass, and R. I. Soare, Algebraic properties of low$_2$ computably enumerable sets, in preparation.
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
Leo Harrington and Robert I. Soare, Games in recursion theory and continuity properties of capping degrees, Set theory of the continuum (Berkeley, CA, 1989) Math. Sci. Res. Inst. Publ., vol. 26, Springer, New York, 1992, pp. 39–62. MR 1233810, DOI 10.1007/978-1-4613-9754-0_{4}
L. Harrington and R. I. Soare, Codable sets and orbits of computably enumerable sets, J. Symbolic Logic, to appear.
L. Harrington and R. I. Soare, Dynamic properties of computably enumerable sets, in: Computability, Enumerability, Unsolvability: Directions in Recursion Theory (eds. S. B. Cooper, T. A. Slaman, S. S. Wainer), Proceedings of the Recursion Theory Conference, University of Leeds, July, 1994, London Math. Soc. Lecture Notes Series, Cambridge University Press, 1996.
L. Harrington and R. I. Soare, Definable properties of the computably enumerable sets, in preparation.
L. Harrington and R. I. Soare, Martin’s Invariance Conjecture and low sets, in preparation.
A. H. Lachlan, Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grundlagen Math. 14 (1968), 457–472. MR 237331, DOI 10.1002/malq.19680143002
A. H. Lachlan, On some games which are relevant to the theory of recursively enumerable sets, Ann. of Math. (2) 91 (1970), 291–310. MR 284333, DOI 10.2307/1970579
Alistair H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1976), no. 4, 307–365. MR 409150, DOI 10.1016/0003-4843(76)90016-4
Manuel Lerman and Robert I. Soare, $d$-simple sets, small sets, and degree classes, Pacific J. Math. 87 (1980), no. 1, 135–155. MR 590872, DOI 10.2140/pjm.1980.87.135
Wolfgang Maass, Recursively enumerable generic sets, J. Symbolic Logic 47 (1982), no. 4, 809–823 (1983). MR 683156, DOI 10.2307/2273100
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, Variations on promptly simple sets, J. Symbolic Logic 50 (1985), no. 1, 138–148. MR 780532, DOI 10.2307/2273796
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
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
Albert Eagle, Series for all the roots of the equation $(z-a)^m=k(z-b)^n$, Amer. Math. Monthly 46 (1939), 425–428. MR 6, DOI 10.2307/2303037
J. R. Shoenfield, Degrees of classes of RE sets, J. Symbolic Logic 41 (1976), no. 3, 695–696. MR 485293, DOI 10.2307/2272046
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