Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Global properties of the lattice of $\Pi^0_1$ classes

Authors: Douglas Cenzer and André Nies
Journal: Proc. Amer. Math. Soc. 132 (2004), 239-249
MSC (2000): Primary 03D25
Published electronically: May 7, 2003
MathSciNet review: 2021268
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $\mathcal{E}_\Pi$ be the lattice of $\Pi^0_1$ classes of reals. We show there are exactly two possible isomorphism types of end intervals, $[P,2^\omega]$. Moreover, finiteness is first order definable in $\mathcal{E}_\Pi$.

References [Enhancements On Off] (What's this?)

  • 1. D. Cenzer, R. Downey, C. J. Jockusch and R. Shore.
    Countable Thin $\Pi^0_1$ Classes.
    Ann. Pure Appl. Logic, 59:79-139, 1993. MR 93m:03075
  • 2. D. Cenzer and C. J. Jockusch.
    $\Pi^0_1$ Classes-Structure and Applications.
    Computability Theory and Its Applications, eds. P. Cholak, S. Lempp, M. Lerman and R. Shore, Contemporary Mathematics 257:39-59, 2000. MR 2001h:03074
  • 3. D. Cenzer and A. Nies.
    Initial segments of the lattice of $\Pi^0_1$ classes.
    Journal of Symbolic Logic, 66: 1749-1765, 2001. MR 2002k:03067
  • 4. D. Cenzer and J. B. Remmel. Index sets for $\Pi^0_1$ classes.
    Ann. Pure Appl. Logic, 93:3-61, 1998. MR 99m:03080
  • 5. D. Cenzer and J. B. Remmel. $\Pi^0_1$ Classes in Mathematics.
    Handbook of Recursive Mathematics, vol. 2, Stud. Logic Found. Math. 139:623-821, Elsevier, 1998. MR 2001d:03108
  • 6. P. Cholak, R. Coles, R. Downey and E. Hermann. Automorphisms of the Lattice of $\Pi^0_1$ Classes.
    Transactions Amer. Math. Soc., 353:4899-4924, 2001. MR 2002f:03080
  • 7. C. C. Chang and H. J. Keisler.
    Model Theory.
    North-Holland Publishing Co., Amsterdam, 1973. MR 53:12927
  • 8. R. Downey and J. B. Remmel.
    Questions in Computable Algebra and Combinatorics.
    Computability Theory and Its Applications, eds. P. Cholak, S. Lempp, M. Lerman and R. Shore, Contemporary Mathematics 257:95-125, 2000. MR 2001i:03094
  • 9. L. A. Harrington and A. Nies.
    Coding in the partial order of enumerable sets.
    Adv. Math., 133:133-162, 1998. MR 99c:03063
  • 10. A. Nies.
    Relativizations of structures arising from recursion theory.
    In Computability, Enumerability and Unsolvability (Proc. Leeds Logic Year, eds. S.B. Cooper, T.A. Slaman and S.S. Wainer, Cambridge University Press, London Math. Society Lecture Notes 224:219-232, 1996. MR 98g:03104
  • 11. A. Nies.
    Intervals of the lattice of computably enumerable sets and effective Boolean algebras.
    Bull. Lond. Math. Soc., 29:683-92, 1997. MR 98j:03057
  • 12. A. Nies.
    Effectively dense Boolean algebras and their applications.
    Trans. Amer. Math. Soc., 352:4989-5012, 2000. MR 2001i:03066

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03D25

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

Additional Information

Douglas Cenzer
Affiliation: Department of Mathematics, University of Florida, Gainesville, Florida 32611

André Nies
Affiliation: Department of Mathematics, The University of Chicago, 5734 S. University Ave., Chicago, Illinois 60637
Address at time of publication: Department of Computer Science, University of Auckland, Private Bag 92019, Auckland 1020, New Zealand

Keywords: $\Pi^0_1$ classes, definability, end segments
Received by editor(s): June 4, 2002
Received by editor(s) in revised form: August 19, 2002
Published electronically: May 7, 2003
Additional Notes: The second author was partially supported by NSF grant DMS–9803482
Communicated by: Carl G. Jockusch, Jr.
Article copyright: © Copyright 2003 American Mathematical Society