Transactions of the American Mathematical Society

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

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
Posted: March 1, 2006
MathSciNet review: 2216257
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We define , a substructure of $\mathcal{E}_\Pi$ (the lattice of $\Pi^0_1$ classes), and show that a quotient structure of , $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

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)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|