The $\Delta _3^0$-automorphism method and noninvariant classes of degrees

Authors:
Leo Harrington and Robert I. Soare

Journal:
J. Amer. Math. Soc. **9** (1996), 617-666

MSC (1991):
Primary 03D25

DOI:
https://doi.org/10.1090/S0894-0347-96-00181-6

MathSciNet review:
1311821

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

- 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

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (1991):
03D25

Retrieve articles in all journals with MSC (1991): 03D25

Additional Information

**Leo Harrington**

Affiliation:
Department of Mathematics University of California at Berkeley Berkeley, California 94720

Email:
leo@math.berkeley.edu

**Robert I. Soare**

Affiliation:
Department of Mathematics University of Chicago 5734 University Avenue Chicago, Illinois 60637-1538;
*World Wide Web address*: http://www.cs.uchicago.edu/~soare

Email:
soare@math.uchicago.edu

Received by editor(s):
December 13, 1993

Additional Notes:
The first author was supported by National Science Foundation Grants DMS 89-10312 and DMS 92-14048, and the second author by National Science Foundation Grants DMS 91-06714 and DMS 95-00825

Article copyright:
© Copyright 1996
American Mathematical Society