Transactions of the American Mathematical Society

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

Author(s): Peter Cholak; Richard Coles; Rod Downey; Eberhard Herrmann
Journal: Trans. Amer. Math. Soc. 353 (2001), 4899-4924.
MSC (2000): Primary 03D30; Secondary 03D25, 03D45
Posted: July 12, 2001
Retrieve article in: PDF
This article is available free of charge

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.

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 , 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

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

Peter Cholak
Affiliation: Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556-5683
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
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

DOI: 10.1090/S0002-9947-01-02821-5
PII: S 0002-9947(01)02821-5
Received by editor(s): March 12, 1999
Received by editor(s) in revised form: January 8, 2001
Posted: 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 of article: Copyright 2001, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS