Hostname: page-component-7ccbd9845f-9nx8b Total loading time: 0.326 Render date: 2023-01-28T01:36:32.082Z Has data issue: true Feature Flags: { "useRatesEcommerce": false } hasContentIssue true
>Journals
>Mathematical Structures in Computer Science
>Volume 28 Special Issue 3: Mind, Mechanism and Mat...
>Autostability spectra for decidable structures
Mathematical Structures in Computer Science
Autostability spectra for decidable structures
Published online by Cambridge University Press: 14 October 2016
NIKOLAY BAZHENOV [Opens in a new window]
NIKOLAY BAZHENOV*
Sobolev Institute of Mathematics, Novosibirsk, Russia Novosibirsk State University, Novosibirsk, Russia Email: bazhenov@math.nsc.ru
Rights & Permissions[Opens in a new window]
We study autostability spectra relative to strong constructivizations (SC-autostability spectra). For a decidable structure $\mathcal{S}$, the SC-autostability spectrum of $\mathcal{S}$ is the set of all Turing degrees capable of computing isomorphisms among arbitrary decidable copies of $\mathcal{S}$. The degree of SC-autostability for $\mathcal{S}$ is the least degree in the spectrum (if such a degree exists).
We prove that for a computable successor ordinal α, every Turing degree c.e. in and above 0(α) is the degree of SC-autostability for some decidable structure. We show that for an infinite computable ordinal β, every Turing degree c.e. in and above 0(2β+1) is the degree of SC-autostability for some discrete linear order. We prove that the set of all PA-degrees is an SC-autostability spectrum. We also obtain similar results for autostability spectra relative to n-constructivizations.
Mathematical Structures in Computer Science , Volume 28 , Special Issue 3: Mind, Mechanism and Mathematics: Computability Unchained , March 2018 , pp. 392 - 411
DOI: https://doi.org/10.1017/S096012951600030X[Opens in a new window]
Copyright © Cambridge University Press 2016
Alaev, P.E. (2004). Hyperarithmetical Boolean algebras with a distinguished ideal. Siberian Mathematical Journal 45 (5) 795–805.CrossRefGoogle Scholar
Anderson, B.A. and Csima, B.F. (2016). Degrees that are not degrees of categoricity. Notre Dame Journal of Formal Logic 57 (3) 389–398.Google Scholar
Ash, C.J. (1986a). Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees. Transactions of the American Mathematical Society 298 497–514.CrossRefGoogle Scholar
Ash, C.J. (1986b). Stability of recursive structures in arithmetical degrees. Annals of Pure and Applied Logic 32 113–135.CrossRefGoogle Scholar
Ash, CJ. (1987). Categoricity in hyperarithmetical degrees. Annals of Pure and Applied Logic 34 (1) 1–14.CrossRefGoogle Scholar
Ash, C.J. and Knight, J.F. (1990). Pairs of recursive structures. Annals of Pure and Applied Logic 46 (3) 211–234.CrossRefGoogle Scholar
Ash, C.J. and Knight, J.F. (2000). Computable Structures and the Hyperarithmetical Hierarchy. Studies in Logic and the Foundations of Mathematics, volume 144, Elsevier Science B.V. Google Scholar
Ash, C., Knight, J., Manasse, M. and Slaman, T. (1989). Generic copies of countable structures. Annals of Pure and Applied Logic 42 (3) 195–205.CrossRefGoogle Scholar
Bazhenov, N.A. (2013). Degrees of categoricity for superatomic Boolean algebras. Algebra Logic 52 (3) 179–187.CrossRefGoogle Scholar
Bazhenov, N.A. (2014). Hyperarithmetical categoricity of Boolean algebras of type B(ωα × η). Journal of Mathematical Sciences 202 (1) 40–49.CrossRefGoogle Scholar
Bazhenov, N.A. (2015a). Autostability spectra for Boolean algebras. Algebra Logic 53 (6) 502–505.CrossRefGoogle Scholar
Bazhenov, N. (2015b). Prime model with no degree of autostability relative to strong constructivizations. In: Evolving Computability. Lecture Notes in Computer Science 9136, Springer, 117–126.CrossRefGoogle Scholar
Bazhenov, N.A. (to appear). Degrees of autostability for linear orderings and linearly ordered abelian groups. Algebra Logic Google Scholar
Bazhenov, N.A. (2016). Degrees of autostability relative to strong constructivizations for Boolean algebras. Algebra Logic 55 (2) 87–102.CrossRefGoogle Scholar
Chang, C.C. and Keisler, H.J. (1973). Model Theory. Elsevier, North-Holland.Google Scholar
Chisholm, J. (1990). Effective model theory vs. recursive model theory. The Journal of Symbolic Logic 55 (3) 1168–1191.CrossRefGoogle Scholar
Chisholm, J., Fokina, E.B., Goncharov, S.S., Harizanov, V.S., Knight, J.F. and Quinn, S. (2009). Intrinsic bounds on complexity and definability at limit levels. The Journal of Symbolic Logic 74 (3) 1047–1060.CrossRefGoogle Scholar
Csima, B.F., Franklin, J.N.Y. and Shore, R.A. (2013). Degrees of categoricity and the hyperarithmetic hierarchy. Notre Dame Journal of Formal Logic 54 (2) 215–231.CrossRefGoogle Scholar
Downey, R.G. (1998). Computability theory and linear orderings. In: Ershov, Yu.L., Goncharov, S.S., Nerode, A. and Remmel, J.B. (eds.) Handbook of Recursive Mathematics 2 Studies in Logic and the Foundations of Mathematics, volume 139, Elsevier Science B.V, 823–976.Google Scholar
Downey, R.G., Kach, A.M., Lempp, S., Lewis-Pye, A.E.M., Montalbán, A. and Turetsky, D.D. (2015). The complexity of computable categoricity. Advances in Mathematics 268 423–466.CrossRefGoogle Scholar
Ershov, Yu.L. (1964). Decidability of the elementary theory of distributive lattices with relative complements and the theory of filters. Algebra Logika 3 (3) 17–38.Google Scholar
Ershov, Yu.L. and Goncharov, S.S. (2000). Constructive Models. Kluwer Academic/Plenum Publishers.CrossRefGoogle Scholar
Fokina, E., Frolov, A. and Kalimullin, I. (2016). Categoricity spectra for rigid structures. Notre Dame Journal of Formal Logic 57 (1) 45–57.CrossRefGoogle Scholar
Fokina, E.B., Goncharov, S.S., Harizanov, V., Kudinov, O.V. and Turetsky, D. (2015). Index sets for n-decidable structures categorical relative to m-decidable presentations. Algebra Logic 54 (4) 336–341.CrossRefGoogle Scholar
Fokina, E.B., Kalimullin, I. and Miller, R. (2010). Degrees of categoricity of computable structures. Archive for Mathematical Logic 49 (1) 51–67.CrossRefGoogle Scholar
Fröhlich, A. and Shepherdson, J.C. (1956). Effective procedures in field theory. Philosophical Transactions of the Royal Society of London A 248 (950) 407–432.CrossRefGoogle Scholar
Frolov, A.N. (2012). Linear orderings. Coding theorems. Uchenye Zapiski Kazanskogo Universiteta, Seriya Fiziko-Matematicheskie Nauki. Kazan, 154 (2) 142–151. (In Russian).Google Scholar
Frolov, A.N. (2015). Effective categoricity of computable linear orderings. Algebra Logic 54 (5) 415–417.CrossRefGoogle Scholar
Goncharov, S.S. (1977). The quantity of nonautoequivalent constructivizations. Algebra Logic 16 (3) 169–185.CrossRefGoogle Scholar
Goncharov, S.S. (1997). Countable Boolean Algebras and Decidability. Consultants Bureau.Google Scholar
Goncharov, S.S. (2011). Degrees of autostability relative to strong constructivizations. Proceedings of the Steklov Institute of Mathematics 274 105–115.CrossRefGoogle Scholar
Goncharov, S.S., Bazhenov, N.A. and Marchuk, M.I. (2015a). Index sets of autostable relative to strong constructivizations constructive models for familiar classes. Doklady Mathematics 92 (2) 525–527.CrossRefGoogle Scholar
Goncharov, S.S., Bazhenov, N.A. and Marchuk, M.I. (2015b). The index set of Boolean algebras autostable relative to strong constructivizations. Siberian Mathematical Journal 56 (3) 393–404.CrossRefGoogle Scholar
Goncharov, S., Harizanov, V., Knight, J., McCoy, C., Miller, R. and Solomon, R. (2005). Enumerations in computable structure theory. Annals of Pure and Applied Logic 136 (3) 219–246.CrossRefGoogle Scholar
Goncharov, S.S. and Marchuk, M.I. (2015a). Index sets of constructive models of bounded signature that are autostable relative to strong constructivizations. Algebra Logic 54 (2) 108–126.CrossRefGoogle Scholar
Goncharov, S.S. and Marchuk, M.I. (2015b). Index sets of constructive models of nontrivial signature autostable relative to strong constructivizations. Doklady Mathematics 91 (2) 158–159.CrossRefGoogle Scholar
Hirschfeldt, D.R., Khoussainov, B., Shore, R.A. and Slinko, A.M. (2002). Degree spectra and computable dimensions in algebraic structures. Annals of Pure and Applied Logic 115 (1–3) 71–113.CrossRefGoogle Scholar
Jockusch, C.G. and Soare, R.I. (1972). Π0 1 classes and degrees of theories. Transactions of the American Mathematical Society 173 33–56.Google Scholar
Langford, C.H. (1926). Some theorems on deducibility. Annals of Mathematics (2) 28 16–40.CrossRefGoogle Scholar
Mal'tsev, A.I. (1961). Constructive algebras. I. Russian Mathematical Surveys 16 (3) 77–129.CrossRefGoogle Scholar
Mal'tsev, A.I. (1962). On recursive abelian groups. Soviet Mathematics – Doklady 32 1431–1434.Google Scholar
Miller, R. (2009). d-computable categoricity for algebraic fields. Journal of Symbolic Logic 74 (4) 1325–1351.CrossRefGoogle Scholar
Miller, R., Poonen, B., Schoutens, H. and Shlapentokh, A. (to appear). A computable functor from graphs to fields. arXiv:1510.07322Google Scholar
Miller, R. and Shlapentokh, A. (2015). Computable categoricity for algebraic fields with splitting algorithms. Transactions of the American Mathematical Society 367 (6) 3955–3980.CrossRefGoogle Scholar
Moses, M. (1984). Recursive linear orders with recursive successivities. Annals of Pure and Applied Logic 27 (3) 253–264.CrossRefGoogle Scholar
Rosenstein, J.G. (1982). Linear Orderings. Pure and Applied Mathematics, volume 98, Academic Press.Google Scholar
Scott, D. (1962). Algebras of sets binumerable in complete extensions of arithmetic. In: Proceedings of Symposia in Pure Mathematics, volume V, American Mathematical Society 117–121.Google Scholar
Simpson, S.G. (1977). Degrees of unsolvability: A survey of results. In: Barwise, J. (ed.) Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, volume 90, Elsevier, North-Holland 631–652.CrossRefGoogle Scholar
This article has been cited by the following publications. This list is generated based on data provided by Crossref.
Bazhenov, Nikolay 2017. Theory and Applications of Models of Computation. Vol. 10185, Issue. , p. 85.
Bazhenov, N. A. and Marchuk, M. I. 2018. Degrees of Autostability Relative to Strong Constructivizations of Graphs. Siberian Mathematical Journal, Vol. 59, Issue. 4, p. 565.
Bazhenov, Nikolay and Marchuk, Margarita 2018. Sailing Routes in the World of Computation. Vol. 10936, Issue. , p. 40.
Bazhenov, N. A. and Harrison-Trainor, M. 2019. Constructing Decidable Graphs from Decidable Structures. Algebra and Logic, Vol. 58, Issue. 5, p. 369.
Bazhenov, Nikolay Ganchev, Hristo and Vatev, Stefan 2019. Computing with Foresight and Industry. Vol. 11558, Issue. , p. 84.
Bazhenov, N. A. Kalimullin, I. Sh. and Yamaleev, M. M. 2020. Strong Degrees of Categoricity and Weak Density. Lobachevskii Journal of Mathematics, Vol. 41, Issue. 9, p. 1630.
Bazhenov, Nikolay Goncharov, Sergey and Melnikov, Alexander 2020. Decompositions of decidable abelian groups. International Journal of Algebra and Computation, Vol. 30, Issue. 01, p. 49.
Marchuk, M. I. 2021. On Decidable Categoricity for Almost Prime Models of the Signature of Graphs. Siberian Advances in Mathematics, Vol. 31, Issue. 4, p. 283.
Goncharov, S. S. and Marchuk, M. I. 2021. The Degree of Decidable Categoricity of a Model with Infinite Solutions for Complete Formulas. Algebra and Logic, Vol. 60, Issue. 3, p. 200.
Bazhenov, N. A. Ganchev, H. and Vatev, S. 2021. Computable Embeddings for Pairs of Linear Orders. Algebra and Logic, Vol. 60, Issue. 3, p. 163.
Bazhenov, N. Greenberg, N. Melnikov, A. Miller, R. and Ng, K. M. 2021. A Note on Computable Distinguishing Colorings. Lobachevskii Journal of Mathematics, Vol. 42, Issue. 4, p. 693.
Bazhenov, N. A. 2021. Categoricity Spectra of Computable Structures. Journal of Mathematical Sciences, Vol. 256, Issue. 1, p. 34.
View all Google Scholar citations for this article.
Save article to Kindle
To save this article to your Kindle, first ensure coreplatform@cambridge.org is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the 'name' part of your Kindle email address below. Find out more about saving to your Kindle.
Volume 28, Special Issue 3
NIKOLAY BAZHENOV (a1) (a2)
DOI: https://doi.org/10.1017/S096012951600030X
Save article to Dropbox
To save this article to your Dropbox account, please select one or more formats and confirm that you agree to abide by our usage policies. If this is the first time you used this feature, you will be asked to authorise Cambridge Core to connect with your Dropbox account. Find out more about saving content to Dropbox.
Save article to Google Drive
To save this article to your Google Drive account, please select one or more formats and confirm that you agree to abide by our usage policies. If this is the first time you used this feature, you will be asked to authorise Cambridge Core to connect with your Google Drive account. Find out more about saving content to Google Drive.
Reply to: Submit a response
Title * Please enter a title for your response.
Contents * Contents help
Close Contents help
- No HTML tags allowed
- Web page URLs will display as text only
- Lines and paragraphs break automatically
- Attachments, images or tables are not permitted
Please enter your response.
Email * Email help
Close Email help
Your email address will be used in order to notify you when your comment has been reviewed by the moderator and in case the author(s) of the article or the moderator need to contact you directly.
Occupation Please enter your occupation.
Affiliation Please enter any affiliation.
Conflicting interests
Do you have any conflicting interests? * Conflicting interests help
Close Conflicting interests help
Please list any fees and grants from, employment by, consultancy for, shared ownership in or any close relationship with, at any time over the preceding 36 months, any organisation whose interests may be affected by the publication of the response. Please also list any non-financial associations or interests (personal, professional, political, institutional, religious or other) that a reasonable reader would want to know about in relation to the submitted work. This pertains to all the authors of the piece, their spouses or partners.
More information *
Please enter details of the conflict of interest or select 'No'.
Please tick the box to confirm you agree to our Terms of use. *
Please accept terms of use.
Please tick the box to confirm you agree that your name, comment and conflicts of interest (if accepted) will be visible on the website and your comment may be printed in the journal at the Editor's discretion. *
Please confirm you agree that your details will be displayed.