Automorphisms of the lattice of $\Pi _1^0$ classes; perfect thin classes and anc degrees
HTML articles powered by AMS MathViewer
- by Peter Cholak, Richard Coles, Rod Downey and Eberhard Herrmann PDF
- Trans. Amer. Math. Soc. 353 (2001), 4899-4924 Request permission
Abstract:
$\Pi _1^0$ classes are important to the logical analysis of many parts of mathematics. The $\Pi _1^0$ classes form a lattice. As with the lattice of computably enumerable sets, it is natural to explore the relationship between this lattice and the Turing degrees. We focus on an analog of maximality, or more precisely, hyperhypersimplicity, namely the notion of a thin class. We prove a number of results relating automorphisms, invariance, and thin classes. Our main results are an analog of Martin’s work on hyperhypersimple sets and high degrees, using thin classes and anc degrees, and an analog of Soare’s work demonstrating that maximal sets form an orbit. In particular, we show that the collection of perfect thin classes (a notion which is definable in the lattice of $\Pi _1^0$ classes) forms an orbit in the lattice of $\Pi _1^0$ classes; and a degree is anc iff it contains a perfect thin class. Hence the class of anc degrees is an invariant class for the lattice of $\Pi _1^0$ classes. We remark that the automorphism result is proven via a $\Delta _3^0$ automorphism, and demonstrate that this complexity is necessary.References
- J. L. Bell and A. B. Slomson, Models and ultraproducts: An introduction, North-Holland Publishing Co., Amsterdam-London, 1969. MR 0269486
- Douglas Cenzer, $\Pi ^0_1$ classes in computability theory, Handbook of computability theory, Stud. Logic Found. Math., vol. 140, North-Holland, Amsterdam, 1999, pp. 37–85. MR 1720779, DOI 10.1016/S0049-237X(99)80018-4
- Douglas Cenzer, Rodney Downey, Carl Jockusch, and Richard A. Shore, Countable thin $\Pi ^0_1$ classes, Ann. Pure Appl. Logic 59 (1993), no. 2, 79–139. MR 1197208, DOI 10.1016/0168-0072(93)90001-T
- Cenzer, D., and Jockusch, C., $\Pi _1^0$-Classes-Structure and applications, in Computability Theory and its Applications, (ed. P. Cholak, S. Lempp, M. Lerman, and R. Shore) Contemporary Mathematics, Vol. 257, AMS Publications, Rhode Island, 2000, 39-60.
- D. Cenzer and J. B. Remmel, $\Pi ^0_1$ classes in mathematics, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 623–821. MR 1673586, DOI 10.1016/S0049-237X(98)80046-3
- Cholak, P., Downey, R., and Harrington, L., Automorphisms of the lattice of recursively enumerable sets: $\Sigma _1^1$ completeness, in preparation.
- 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
- Downey, R., Abstract Dependence, Recursion Theory and the Lattice of Recursively Enumerable Filters Thesis, Monash University, Clayton, Victoria, Australia, (1982).
- R. G. Downey, Maximal theories, Ann. Pure Appl. Logic 33 (1987), no. 3, 245–282. MR 879490, DOI 10.1016/0168-0072(87)90083-2
- Rodney G. Downey, On presentations of algebraic structures, Complexity, logic, and recursion theory, Lecture Notes in Pure and Appl. Math., vol. 187, Dekker, New York, 1997, pp. 157–205. MR 1455136
- Rod Downey and Carl G. Jockusch Jr., Effective presentability of Boolean algebras of Cantor-Bendixson rank $1$, J. Symbolic Logic 64 (1999), no. 1, 45–52. MR 1683893, DOI 10.2307/2586749
- Rod Downey, Carl Jockusch, and Michael Stob, Array nonrecursive sets and multiple permitting arguments, Recursion theory week (Oberwolfach, 1989) Lecture Notes in Math., vol. 1432, Springer, Berlin, 1990, pp. 141–173. MR 1071516, DOI 10.1007/BFb0086116
- Rod Downey, Carl G. Jockusch, and Michael Stob, Array nonrecursive degrees and genericity, Computability, enumerability, unsolvability, London Math. Soc. Lecture Note Ser., vol. 224, Cambridge Univ. Press, Cambridge, 1996, pp. 93–104. MR 1395876, DOI 10.1017/CBO9780511629167.005
- Lawrence Feiner, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1970), 365–374. MR 282805, DOI 10.2307/2270692
- David R. Guichard, Automorphisms of substructure lattices in recursive algebra, Ann. Pure Appl. Logic 25 (1983), no. 1, 47–58. MR 722168, DOI 10.1016/0168-0072(83)90053-2
- 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
- Eberhard Herrmann, Automorphisms of the lattice of recursively enumerable sets and hyperhypersimple sets, Logic, methodology and philosophy of science, VIII (Moscow, 1987) Stud. Logic Found. Math., vol. 126, North-Holland, Amsterdam, 1989, pp. 179–190. MR 1034561, DOI 10.1016/S0049-237X(08)70044-2
- Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
- Charles Hopkins, Rings with minimal condition for left ideals, Ann. of Math. (2) 40 (1939), 712–730. MR 12, DOI 10.2307/1968951
- Lachlan, A. H., Theorem XV 2.2 in Soare [Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag New York (1987)].
- 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. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205–209. MR 280374, DOI 10.2307/2270510
- 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
- Remmel, J., Private communication.
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Gerald E. Sacks, A maximal set which is not complete, Michigan Math. J. 11 (1964), 193–205. MR 166090
- Slaman, T., and H. Woodin, in Questions in Recursion Theory, notes 1995.
- 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, 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
Additional Information
- Peter Cholak
- Affiliation: Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556-5683
- MR Author ID: 290865
- ORCID: 0000-0002-6547-5408
- Email: Peter.Cholak.1@nd.edu
- Richard Coles
- Affiliation: Cramer Systems, 8 Riverside Court, Bath, BA2 3DZ, UK
- Rod Downey
- Affiliation: School of Mathematical and Computing Sciences, Victoria University, P. O. Box 600, Wellington, New Zealand
- MR Author ID: 59535
- Email: Rod.Downey@vuw.ac.nz
- Eberhard Herrmann
- Affiliation: Mathematisch-Naturwiss. Fakultät II, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany
- Email: herrmann@mathematik.hu-berlin.de
- Received by editor(s): March 12, 1999
- Received by editor(s) in revised form: January 8, 2001
- Published electronically: July 12, 2001
- Additional Notes: The authors wish to thank the referee and Carl Jockusch for many very helpful comments which have greatly improved the readability and length of this paper. This research was supported by the Marsden Fund of New Zealand and the National Science Foundation.
- © Copyright 2001 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 353 (2001), 4899-4924
- MSC (2000): Primary 03D30; Secondary 03D25, 03D45
- DOI: https://doi.org/10.1090/S0002-9947-01-02821-5
- MathSciNet review: 1852086