×

zbMATH — the first resource for mathematics

Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures. (English) Zbl 1048.03035
This article continues the work on degree spectra of relations on computable structures begun by C. J. Ash and A. Nerode [Aspects of effective algebra, 26–41 (1981; Zbl 0467.03041)], V. S. Harizanov [Ann. Pure Appl. Logic 55, No. 1, 51–65 (1991; Zbl 0756.03022)], and others. Suppose \(U\) is a relation on the domain of a computable structure \(\mathcal M\). \(U\) is intrinsically \(\Sigma_\alpha\) on \(\mathcal M\) if the image of \(U\) in each computable presentation of \(\mathcal M\) is in \(\Sigma_\alpha\). If \(s\) is a reducibility (e.g. \(m\)-reducibility) the \(s\)-degree spectrum of \(U\) on \(\mathcal M\), DgSp\(^s_{\mathcal M} (U)\), is the set of \(s\)-degrees of images of \(U\) in all computable presentations of \(\mathcal M\).
The central result of the article states that all levels of the hyperarithmetic hierarchy can be realized as degree spectra. That is, given any computable ordinal \(\alpha\) and any reducibility \(s\) which is at least as strong as \(m\)-reducibility, there is an intrinsically \(\Sigma_\alpha\) invariant relation \(U\) on a computably presentable structure \(\mathcal M\) such that DgSp\(^s_{\mathcal M} (U)\) consists of all nontrivial \(\Sigma_\alpha\) \(s\)-degrees. In this statement, \(\Sigma_\alpha\) may be replaced by \(\Pi_\alpha\) or \(\Delta_\alpha\).

MSC:
03D45 Theory of numerations, effectively presented structures
03C57 Computable structure theory, computable model theory
03D55 Hierarchies of computability and definability
03D30 Other degrees and reducibilities in computability and recursion theory
03C15 Model theory of denumerable and separable structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ash, C. J., ”Generalizations of enumeration reducibility using recursive infinitary propositional sentences”, Annals of Pure and Applied Logic , vol. 58 (1992), pp. 173–84. špace3pt · Zbl 0769.03025 · doi:10.1016/0168-0072(92)90026-V
[2] Ash, C. J., P. Cholak, and J. F. Knight, ”Permitting, forcing, and copying of a given recursive relation”, Annals of Pure and Applied Logic , vol. 86 (1997), pp. 219–36. špace3pt · Zbl 0883.03029 · doi:10.1016/S0168-0072(96)00011-5
[3] Ash, C. J., and J. Knight, Computable Structures and the Hyperarithmetical Hierarchy , Elsevier, Amsterdam, 2000. špace3pt · Zbl 0960.03001
[4] Ash, C. J., and J. F. Knight, ”Pairs of recursive structures”, Annals of Pure and Applied Logic , vol. 46 (1990), pp. 211–34. špace3pt · Zbl 0712.03020 · doi:10.1016/0168-0072(90)90004-L
[5] Ash, C. J., and J. F. Knight, ”Relatively recursive expansions”, Fundamenta Mathematicae , vol. 140 (1992), pp. 137–55. špace3pt · Zbl 0809.03023 · matwbn.icm.edu.pl · eudml:211934
[6] Ash, C. J., and J. F. Knight, ”A completeness theorem for certain classes of recursive infinitary formulas”, Mathematical Logic Quarterly , vol. 40 (1994), pp. 173–81. špace3pt · Zbl 0810.03037 · doi:10.1002/malq.19940400204
[7] Ash, C. J., and J. F. Knight, ”Ramified systems”, Annals of Pure and Applied Logic , vol. 70 (1994), pp. 205–21. špace3pt · Zbl 0819.03024 · doi:10.1016/S0168-0072(94)90009-4
[8] Ash, C. J., and J. F. Knight, ”Possible degrees in recursive copies”, Annals of Pure and Applied Logic , vol. 75 (1995), pp. 215–21. špace3pt · Zbl 0837.03036 · doi:10.1016/0168-0072(94)00043-3
[9] Ash, C. J., and J. F. Knight, ”Possible degrees in recursive copies. II”, Annals of Pure and Applied Logic , vol. 87 (1997), pp. 151–65. špace3pt · Zbl 0877.03022 · doi:10.1016/S0168-0072(96)00026-7
[10] Ash, C. J., and A. Nerode, ”Intrinsically recursive relations”, pp. 26–41 in Aspects of Effective Algebra (Clayton, 1979) , edited by J. N. Crossley, Upside Down A Book Co., Yarra Glen, 1981. špace3pt · Zbl 0467.03041
[11] Epstein, R. L., R. Haas, and R. L. Kramer, ”Hierarchies of sets and degrees below \(\mathbf 0^\prime \)”, pp. 32–48 in Logic Year 1979–80 (Proceedings of Seminars and Conferences in Mathematical Logic, University of Connecticut) , edited by M. Lerman, J. H. Schmerl, and R. I. Soare, Springer, Berlin, 1981. špace3pt · Zbl 0467.03046
[12] Harizanov, V. S., Degree Spectrum of a Recursive Relation on a Recursive Structure , Ph.D. thesis, University of Wisconsin, Madison, 1987.špace3pt
[13] Harizanov, V. S., ”Some effects of Ash-Nerode and other decidability conditions on degree spectra”, Annals of Pure and Applied Logic , vol. 55 (1991), pp. 51–65. špace3pt · Zbl 0756.03022 · doi:10.1016/0168-0072(91)90097-6
[14] Harizanov, V. S., ”Turing degrees of certain isomorphic images of computable relations”, Annals of Pure and Applied Logic , vol. 93 (1998), pp. 103–13. špace3pt · Zbl 0946.03051 · doi:10.1016/S0168-0072(97)00056-0
[15] Hirschfeldt, D. R., ”Degree spectra of relations on computable structures”, The Bulletin of Symbolic Logic , vol. 6 (2000), pp. 197–212. špace3pt JSTOR: · Zbl 0968.03038 · doi:10.2307/421207 · www.math.ucla.edu
[16] Hirschfeldt, D. R., ”Degree spectra of relations on computable structures in the presence of \(\Delta_ 2^ 0\)” isomorphisms, The Journal of Symbolic Logic , vol. 67 (2002), pp. 697–720. špace3pt · Zbl 1010.03033 · doi:10.2178/jsl/1190150105
[17] Hirschfeldt, D. R., B. Khoussainov, R. A. Shore, and A. M. Slinko, ”Degree spectra and computable dimensions in algebraic structures”, Annals of Pure and Applied Logic , vol. 115 (2002), pp. 71–113. špace3pt · Zbl 1016.03034 · doi:10.1016/S0168-0072(01)00087-2
[18] Khoussainov, B., and R. A. Shore, ”Effective model theory: The number of models and their complexity”, pp. 193–239 in Models and Computability (Leeds, 1997) , edited by S. B. Cooper and J. K. Truss, Cambridge University Press, Cambridge, 1999. špace3pt · Zbl 0940.03045
[19] Knight, J. F., ”Coding a family of sets”, Annals of Pure and Applied Logic , vol. 94 (1998), pp. 127–42. špace3pt · Zbl 0924.03083 · doi:10.1016/S0168-0072(97)00070-5
[20] Sacks, G. E., Higher Recursion Theory , Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. špace3pt · Zbl 0716.03043
[21] Shore, R. A., ”Computable structures: Presentations matter”, pp. 81–95 in In the Scope of Logic, Methodology and Philosophy of Science (Vol. 1 of the Eleventh International Congress of Logic, Methodology and Philosophy of Science, Cracow, August 1999) , vol. 315 of Synthese Library , edited by P. Gärdenfors, J. Woleński, and K. Kijania-Placek, Kluwer Academic Publishers, Dordrecht, 2002. špace3pt · Zbl 1035.03016
[22] Soare, R. I., Recursively Enumerable Sets and Degrees , Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. špace3pt Zentralblatt MATH: · Zbl 0667.03030 · www.zentralblatt-math.org
[23] Soskov, I. N., and V. Baleva, ”Ash’s theorem for abstract structures”, preprint, 2001.špace-1pt · Zbl 1107.03054
[24] Soskov, I. N., and V. Baleva, ”Regular enumerations”, The Journal of Symbolic Logic , vol. 67 (2002), pp. 1323–43. špace3pt · Zbl 1053.03024
[25] White, W. M., Characterizations for Computable Structures , Ph.D. thesis, Cornell University, Ithaca, 2000.špace3pt
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.