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)



Invariance in $ \boldsymbol{\mathcal{E}^*}$ and $ \boldsymbol{\mathcal{E}_\Pi}$

Author: Rebecca Weber
Journal: Trans. Amer. Math. Soc. 358 (2006), 3023-3059
MSC (2000): Primary 03D25, 03D28
Published electronically: March 1, 2006
MathSciNet review: 2216257
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We define $ G$, a substructure of $ \mathcal{E}_\Pi$ (the lattice of $ \Pi^0_1$ classes), and show that a quotient structure of $ G$, $ G^\diamondsuit$, is isomorphic to $ \mathcal{E}^*$. The result builds on the $ \Delta^0_3$ isomorphism machinery, and allows us to transfer invariant classes from $ \mathcal{E}^*$ to $ \mathcal{E}_\Pi$, though not, in general, orbits. Further properties of $ G^\diamondsuit$ and ramifications of the isomorphism are explored, including degrees of equivalence classes and degree invariance.

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

  • 1. Douglas Cenzer, $ \Pi\sp 0\sb 1$ classes in computability theory, Handbook of computability theory, Stud. Logic Found. Math., vol. 140, North-Holland, Amsterdam, 1999, pp. 37-85. MR 2001d:03110
  • 2. Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare, and Stanley S. Wainer, Members of countable $ \Pi\sp 0\sb 1$ classes, Ann. Pure Appl. Logic 31 (1986), no. 2-3, 145-163, Special issue: second Southeast Asian logic conference (Bangkok, 1984). MR 88e:03064
  • 3. Douglas Cenzer and Carl G. Jockusch, Jr., $ \Pi\sb 1\sp 0$ classes--structure and applications, Computability theory and its applications (Boulder, CO, 1999), Contemp. Math., vol. 257, Amer. Math. Soc., Providence, RI, 2000, pp. 39-59. MR 2001h:03074
  • 4. Douglas Cenzer and Andre Nies, Global properties of the lattice of $ \Pi\sb 1\sp 0$ classes, Proc. Amer. Math. Soc. 132 (2004), 239-249. MR 2021268 (2004k:03079)
  • 5. Douglas Cenzer and Jeffrey B. Remmel, $ \Pi\sp 0\sb 1$ classes in mathematics, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 623-821. MR 2001d:03108
  • 6. Peter Cholak, Automorphisms of the lattice of recursively enumerable sets, Mem. Amer. Math. Soc. 113 (1995), no. 541, viii+151. MR 1227497 (95f:03064)
  • 7. Peter Cholak, Richard Coles, Rod Downey, and Eberhard Herrmann, Automorphisms of the lattice of $ \Pi\sp 0\sb 1$ classes: perfect thin classes and anc degrees, Trans. Amer. Math. Soc. 353 (2001), no. 12, 4899-4924 (electronic). MR 2002f:03080
  • 8. Peter A. Cholak and Leo A. Harrington, On the definability of the double jump in the computably enumerable sets, J. Math. Log. 2 (2002), no. 2, 261-296. MR 2003h:03063
  • 9. Rod Downey, Undecidability of $ L(F\sb \infty)$ and other lattices of r.e. substructures, Ann. Pure Appl. Logic 32 (1986), no. 1, 17-26. MR 0857704 (88b:03064)
  • 10. -, Correction to: ``Undecidability of $ L(F\sb \infty)$ and other lattices of r.e. substructures'' [Ann. Pure Appl. Logic 32 (1986), no. 1, 17-26], Ann. Pure Appl. Logic 48 (1990), no. 3, 299-301. MR 91g:03089
  • 11. 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 91k:03110
  • 12. Leo A. Harrington and Robert I. Soare, The $ {\Delta}\sp 0\sb 3$-automorphism method and noninvariant classes of degrees, J. Amer. Math. Soc. 9 (1996), no. 3, 617-666. MR 1311821 (96j:03060)
  • 13. Julia F. Knight, Degrees of models, Handbook of recursive mathematics, Vol. 1, Stud. Logic Found. Math., vol. 138, North-Holland, Amsterdam, 1998, pp. 289-309. MR 2000e:03106
  • 14. Georg Kreisel, Analysis of the Cantor-Bendixson theorem by means of the analytic hierarchy, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astr. Phys. 7 (1959), 621-626. (unbound insert). MR 22:9444
  • 15. George Metakides and Anil Nerode, Recursion theory and algebra, Algebra and logic (Fourteenth Summer Res. Inst., Austral. Math. Soc., Monash Univ., Clayton, 1974), Springer, Berlin, 1975, pp. 209-219. Lecture Notes in Math., Vol. 450. MR 0371580 (51:7798)
  • 16. Anil Nerode and Jeffrey Remmel, A survey of lattices of r.e. substructures, Recursion theory (Ithaca, N.Y., 1982), Proc. Sympos. Pure Math., vol. 42, Amer. Math. Soc., Providence, RI, 1985, pp. 323-375. MR 87b:03097
  • 17. Jeffrey B. Remmel, Recursion theory on algebraic structures with independent sets, Ann. Math. Logic 18 (1980), no. 2, 153-191. MR 81j:03076
  • 18. Linda Jean Richter, Degrees of structures, J. Symbolic Logic 46 (1981), no. 4, 723-731. MR 83d:03048
  • 19. Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Omega Series, Springer-Verlag, Heidelberg, 1987. MR 0882921 (88m:03003)

Similar Articles

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

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

Additional Information

Rebecca Weber
Affiliation: Department of Mathematics, 255 Hurley Hall, University of Notre Dame, Notre Dame, Indiana 46556
Address at time of publication: Department of Mathematics, 6188 Bradley Hall, Dartmouth College, Hanover, New Hampshire 03755

Received by editor(s): June 16, 2004
Published electronically: March 1, 2006
Additional Notes: This work is the author’s Ph.D. research under the direction of Peter Cholak, University of Notre Dame, to whom many thanks are due. The author was partially supported by a Clare Boothe Luce graduate fellowship and National Science Foundation Grant No. 0245167.
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society