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

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 André Nies, Global properties of the lattice of Π⁰₁ classes, Proc. Amer. Math. Soc. 132 (2004), no. 1, 239–249. MR 2021268,
  • 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,
  • 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 Harrington and Robert I. Soare, The Δ⁰₃-automorphism method and noninvariant classes of degrees, J. Amer. Math. Soc. 9 (1996), no. 3, 617–666. MR 1311821,
  • 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. G. Metakides and A. 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
  • 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