Invariance in $\boldsymbol {\mathcal {E}^*}$ and $\boldsymbol {\mathcal {E}_\Pi }$
HTML articles powered by AMS MathViewer
- by Rebecca Weber PDF
- Trans. Amer. Math. Soc. 358 (2006), 3023-3059 Request permission
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
- Douglas Cenzer, $\Pi ^0_1$ classes in computability theory, Handbook of computability theory, Stud. Logic Found. Math., vol. 140, North-Holland, Amsterdam, 1999, pp. 37–85. MR 1720779, DOI 10.1016/S0049-237X(99)80018-4
- Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare, and Stanley S. Wainer, Members of countable $\Pi ^0_1$ classes, Ann. Pure Appl. Logic 31 (1986), no. 2-3, 145–163. Special issue: second Southeast Asian logic conference (Bangkok, 1984). MR 854290, DOI 10.1016/0168-0072(86)90067-9
- Douglas Cenzer and Carl G. Jockusch Jr., $\Pi _1^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 1770733, DOI 10.1090/conm/257/04026
- Douglas Cenzer and André Nies, Global properties of the lattice of $\Pi ^0_1$ classes, Proc. Amer. Math. Soc. 132 (2004), no. 1, 239–249. MR 2021268, DOI 10.1090/S0002-9939-03-06984-3
- D. Cenzer and J. B. Remmel, $\Pi ^0_1$ classes in mathematics, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 623–821. MR 1673586, DOI 10.1016/S0049-237X(98)80046-3
- Peter Cholak, Automorphisms of the lattice of recursively enumerable sets, Mem. Amer. Math. Soc. 113 (1995), no. 541, viii+151. MR 1227497, DOI 10.1090/memo/0541
- Peter Cholak, Richard Coles, Rod Downey, and Eberhard Herrmann, Automorphisms of the lattice of $\Pi ^0_1$ classes: perfect thin classes and anc degrees, Trans. Amer. Math. Soc. 353 (2001), no. 12, 4899–4924. MR 1852086, DOI 10.1090/S0002-9947-01-02821-5
- 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 1938925, DOI 10.1142/S0219061302000151
- R. G. Downey, Undecidability of $L(F_\infty )$ and other lattices of r.e. substructures, Ann. Pure Appl. Logic 32 (1986), no. 1, 17–26. MR 857704, DOI 10.1016/0168-0072(86)90041-2
- Rod Downey, Correction to: “Undecidability of $L(F_\infty )$ and other lattices of r.e. substructures” [Ann. Pure Appl. Logic 32 (1986), no. 1, 17–26; MR0857704 (88b:03064)], Ann. Pure Appl. Logic 48 (1990), no. 3, 299–301. MR 1073224, DOI 10.1016/0168-0072(90)90025-W
- 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 1071516, DOI 10.1007/BFb0086116
- Leo Harrington and Robert I. Soare, The $\Delta ^0_3$-automorphism method and noninvariant classes of degrees, J. Amer. Math. Soc. 9 (1996), no. 3, 617–666. MR 1311821, DOI 10.1090/S0894-0347-96-00181-6
- J. 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 1673566, DOI 10.1016/S0049-237X(98)80008-6
- G. 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) (English, with Russian summary). MR 0118673
- G. Metakides and A. Nerode, Recursion theory and algebra, Algebra and logic (Fourteenth Summer Res. Inst., Austral. Math. Soc., Monash Univ., Clayton, 1974) Lecture Notes in Math., Vol. 450, Springer, Berlin, 1975, pp. 209–219. MR 0371580
- A. Nerode and J. 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 791067, DOI 10.1090/pspum/042/791067
- J. B. Remmel, Recursion theory on algebraic structures with independent sets, Ann. Math. Logic 18 (1980), no. 2, 153–191. MR 578542, DOI 10.1016/0003-4843(80)90016-9
- Linda Jean Richter, Degrees of structures, J. Symbolic Logic 46 (1981), no. 4, 723–731. MR 641486, DOI 10.2307/2273222
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
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
- Email: rweber@math.dartmouth.edu
- 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.
- © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 358 (2006), 3023-3059
- MSC (2000): Primary 03D25, 03D28
- DOI: https://doi.org/10.1090/S0002-9947-06-03984-5
- MathSciNet review: 2216257