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