Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Automorphisms of the lattice of $\Pi_1^0$ classes; perfect thin classes and anc degrees

Authors: Peter Cholak, Richard Coles, Rod Downey and Eberhard Herrmann
Journal: Trans. Amer. Math. Soc. 353 (2001), 4899-4924
MSC (2000): Primary 03D30; Secondary 03D25, 03D45
Published electronically: July 12, 2001
MathSciNet review: 1852086
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03D30, 03D25, 03D45

Retrieve articles in all journals with MSC (2000): 03D30, 03D25, 03D45

Additional Information

Peter Cholak
Affiliation: Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556-5683

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

Eberhard Herrmann
Affiliation: Mathematisch-Naturwiss. Fakultät II, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany

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.
Article copyright: © Copyright 2001 American Mathematical Society