Abstract
For a non-zero natural number n, we work with finitary \(\Sigma ^0_n\)-formulas \(\psi (x)\) without parameters. We consider computable structures \({\mathcal {S}}\) such that the domain of \({\mathcal {S}}\) has infinitely many \(\Sigma ^0_n\)-definable subsets. Following Goncharov and Kogabaev, we say that an infinite list of \(\Sigma ^0_n\)-formulas is a \(\Sigma ^0_n\)-classification for \({\mathcal {S}}\) if the list enumerates all \(\Sigma ^0_n\)-definable subsets of \({\mathcal {S}}\) without repetitions. We show that an arbitrary computable \({\mathcal {S}}\) always has a \({{\mathbf {0}}}^{(n)}\)-computable \(\Sigma ^0_n\)-classification. On the other hand, we prove that this bound is sharp: we build a computable structure with no \({{\mathbf {0}}}^{(n-1)}\)-computable \(\Sigma ^0_n\)-classifications.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Goncharov, S.S., Kogabaev, N.T.: On \(\Sigma ^0_1\)-classification of relations on computable structures. Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform. 8(4), 23–32 (2008). (In Russian)
Goncharov, S.S., Sorbi, A.: Generalized computable numerations and nontrivial Rogers semilattices. Algebra Logic 36(6), 359–369 (1997). https://doi.org/10.1007/BF02671553
Ershov, Y.L.: Theory of Numberings. Nauka, Moscow (1977). (In Russian)
Ershov, Y.L.: Theory of numberings. In: Griffor, E.R. (ed.) Handbook of Computability Theory. Stud. Logic Found. Math., vol. 140, pp. 473–503. North-Holland, Amsterdam (1999). https://doi.org/10.1016/S0049-237X(99)80030-5
Badaev, S.A., Goncharov, S.S.: The theory of numberings: open problems. In: Cholak, P., Lempp, S., Lerman, M., Shore, R. (eds.) Computability Theory and Its Applications. Contemp. Math., vol. 257, pp. 23–38. American Mathematical Society, Providence (2000). https://doi.org/10.1090/conm/257/04025
Friedberg, R.M.: Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication. J. Symb. Log. 23(3), 309–316 (1958). https://doi.org/10.2307/2964290
Matiyasevich, Y.V.: Hilbert’s Tenth Problem. MIT Press, Cambridge (1993)
Boyadzhiyska, S., Lange, K., Raz, A., Scanlon, R., Wallbaum, J., Zhang, X.: Classifications of definable subsets. Algebra Logic 58(5), 383–404 (2019). https://doi.org/10.1007/s10469-019-09559-7
Ershov, Y.L., Goncharov, S.S.: Constructive Models. Kluwer Academic/Plenum Publishers, New York (2000)
Ash, C.J., Knight, J.F.: Computable Structures and the Hyperarithmetical Hierarchy. Stud. Logic Found. Math., vol. 144. Elsevier, Amsterdam (2000)
Rosenstein, J.G.: Linear Orderings. Pure Appl. Math., vol. 98. Academic Press, New York (1982)
Ash, C.J.: A construction for recursive linear orderings. J. Symb. Log. 56(2), 673–683 (1991). https://doi.org/10.2307/2274709
Downey, R., Knight, J.F.: Orderings with \(\alpha \)-th jump degrees \(0^{(\alpha )}\). Proc. Amer. Math. Soc. 114(2), 545–552 (1992). https://doi.org/10.1090/S0002-9939-1992-1065942-0
Mwesigye, F., Truss, J.K.: Ehrenfeucht-Fraïssé games on ordinals. Ann. Pure Appl. Logic 169(7), 616–636 (2018). https://doi.org/10.1016/j.apal.2018.03.001
Moses, M.: \(n\)-Recursive linear orders without \((n+1)\)-recursive copies. In: Crossley, J.N., Remmel, J.B., Shore, R.A., Sweedler, M.E. (eds.) Logical Methods. Progress in Computer Science and Applied Logic, vol. 12, pp. 572–592. Birkhauser, Boston, MA (1993)
Harrison-Trainor, M.: There is no classification of the decidably presentable structures. J. Math. Log. 18(2), 1850010 (2018). https://doi.org/10.1142/S0219061318500101
Acknowledgements
The work of S. Aleksandrova was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. FWNF-2022-0011). The work of N. Bazhenov was supported by the Russian Science Foundation (project no. 18-11-00028). The work of M. Zubkov was supported by the Russian Science Foundation (project no. 18-11-00028) and performed under the development program of the Volga Region Mathematical Center (agreement no. 075-02-2020-1478). The authors are grateful to the referee for their helpful comments.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have no competing interests to declare that are relevant to the content of this article.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Aleksandrova, S., Bazhenov, N. & Zubkov, M. Complexity of \(\Sigma ^0_n\)-classifications for definable subsets. Arch. Math. Logic 62, 239–256 (2023). https://doi.org/10.1007/s00153-022-00842-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-022-00842-6