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

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?)

  • 1. Bell, J., and Slomson, A., Models and Ultraproducts, North-Holland, 1969. MR 42:4381
  • 2. Cenzer, D., $\Pi_1^0$ classes in computability theory, in Handbook of Computability, Elsevier, Amsterdam, 1999, 37-85. MR 2001d:03110
  • 3. Cenzer, D., Downey, R., Jockusch C., and Shore, R. A., Countable thin $\Pi_1^0$ classes, Annals of Pure and Applied Logic, 59 (1993) 79-139, MR 93m:03075
  • 4. 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. CMP 2000:16
  • 5. Cenzer, D., and Remmel, J., $\Pi_1^0$ classes in mathematics, in Handbook of Recursive Mathematics, Vol II (ed. Y. Ershov, S. Goncharov, A. Nerode, and J. Remmel), Elsevier, Amsterdam, (1998), 623-822. MR 2001d:03108
  • 6. Cholak, P., Downey, R., and Harrington, L., Automorphisms of the lattice of recursively enumerable sets: $\Sigma_1^1$ completeness, in preparation.
  • 7. Cholak, P., Downey, R. and Stob, M., Automorphisms of the lattice of recursively enumerable sets: Promptly simple sets, Trans. Amer. Math. Soc., 332 (1992) 555-570. MR 92j:03039
  • 8. Downey, R., Abstract Dependence, Recursion Theory and the Lattice of Recursively Enumerable Filters Thesis, Monash University, Clayton, Victoria, Australia, (1982).
  • 9. Downey, R., Maximal theories, Annals of Pure and Applied Logic, 33 (1987) 245-282. MR 89c:03069
  • 10. Downey, R., On presentations of algebraic structures, in Complexity, Logic and Recursion Theory (ed. Sorbi), Marcel Dekker, 1997, 157-205. MR 98k:03099
  • 11. Downey, R. and Jockusch, C., Effective presentability of Boolean algebras of Cantor-Bendixson rank $1$, Journal of Symbolic Logic, 64 (1999), 45-52. MR 2000e:03126
  • 12. Downey, R., Jockusch, C. and Stob, M., Array nonrecursice sets and multiple permitting arguments, In K. Ambos-Spies, G. H. Muller and G.E. Sacks, eds. Recursion Theory Week, Proceedings, 1989, Lecture Notes in Math. 1432 (Springer, Berlin, 1990) 141-174. MR 91k:03110
  • 13. Downey, R., Jockusch, C. and Stob, M., Array nonrecursive degrees and genericity, in Computability, Enumerability, Unsolvability, (ed. Cooper, Slaman, and Wainer), London Mathematical Society Lecture Notes Series Vol 224, Cambridge University Press (1996), 93-105. MR 97f:03060
  • 14. Feiner, L. J., Hierarchies of boolean algebras, J. Symb. Logic, vol. 35 (1970), 365-373. MR 44:39
  • 15. Guichard, D. Automorphisms of substructure lattices in effective algebra, Ann. Pure and Applied Logic 25 (1983), 47-58. MR 85e:03104
  • 16. Harrington, L. and Soare, R. I., Posts's program and incomplete recursively enumerable sets, Proc. Nat. Acad. Sci U.S.A., 88 (1991) 10242-10246. MR 92k:03019
  • 17. Herrmann, E., Automorphisms of the lattice of recursively enumerable sets and hyperhypersimple sets, In J.E. Fenstad, I.T. Frolov and R. Hilpinen, eds., Logic, Methodology and Philosphy of Science VIII, Studies in Logic and the Foundations of Mathematics, 126 (1989) 179-190 (Elsevier Science). MR 91f:03086
  • 18. Jockusch, C. and Soare, R. I., $\Pi_1^0$ classes and degrees of theories, Trans. Amer. Math. Soc. 142 (1969) 229-237. MR 47:4775
  • 19. Kreisel, G. A note on arithmetic models for consistent formulae of the predicate calculus, Fund. Math. Vol. 37, (1950) 265-285. MR 12:790a
  • 20. Lachlan, A. H., Theorem XV 2.2 in Soare [29].
  • 21. Martin, D., Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlag. Math. 12 (1966) 295-310. MR 37:68
  • 22. Martin, D. A. and Pour-El, M., Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970) 205-209. MR 43:6094
  • 23. Post, E., Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944) 284-316. MR 6:291
  • 24. Remmel, J., Private communication.
  • 25. Rogers, H. Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967. MR 37:61
  • 26. Sacks, G., A maximal set which is not complete, Michigan Math. J., Vol. 11 (1964), 193-205. MR 29:3368
  • 27. Slaman, T., and H. Woodin, in Questions in Recursion Theory, notes 1995.
  • 28. Soare, R. I., Automorphisms of the lattice of recursively enumerable sets I: maximal sets, Annals of Math. (2), 100 (1974) 80-120. MR 50:12685
  • 29. Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag New York (1987). MR 88m:03003

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

American Mathematical Society