Algebra i logika
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Algebra Logika:

Personal entry:
Save password
Forgotten password?

Algebra Logika, 2006, Volume 45, Number 5, Pages 538–574 (Mi al159)  

This article is cited in 29 scientific papers (total in 29 papers)

Index sets of computable structures

W. Calverta, V. S. Harizanovab, J. F. Knightc, S. Millerc

a Murray State University
b George Washington University
c University of Notre Dame

Abstract: The index set of a computable structure $\mathcal A$ is the set of indices for computable copies of $\mathcal A$. We determine complexity of the index sets of various mathematically interesting structures including different finite structures, $\mathbb Q$-vector spaces, Archimedean real-closed ordered fields, reduced Abelian $p$-groups of length less than $\omega^2$, and models of the original Ehrenfeucht theory. The index sets for these structures all turn out to be $m$-complete $\Pi_n^0$, $d-\Sigma_n^0$, or $\Sigma_n^0$ , for various $n$. In each case the calculation involves finding an optimal sentence (i.e., one of simplest form) that describes the structure. The form of the sentence (computable $\Pi_n$, $d-\Sigma_n$, or $\Sigma_n$) yields a bound on the complexity of the index set. Whenever we show $m$-completeness of the index set, we know that the sentence is optimal. For some structures, the first sentence that comes to mind is not optimal, and another sentence of simpler form is shown to serve the purpose. For some of the groups, this involves Ramsey's theory.

Keywords: index set, computable structure, vector space, Archimedean real-closed ordered field, reduced Abelian $p$-group, Ehrenfeucht theory

Full text: PDF file (355 kB)
References: PDF file   HTML file

English version:
Algebra and Logic, 2006, 45:5, 306–325

Bibliographic databases:

UDC: 510.53
Received: 11.01.2006

Citation: W. Calvert, V. S. Harizanova, J. F. Knight, S. Miller, “Index sets of computable structures”, Algebra Logika, 45:5 (2006), 538–574; Algebra and Logic, 45:5 (2006), 306–325

Citation in format AMSBIB
\by W.~Calvert, V.~S.~Harizanova, J.~F.~Knight, S.~Miller
\paper Index sets of computable structures
\jour Algebra Logika
\yr 2006
\vol 45
\issue 5
\pages 538--574
\jour Algebra and Logic
\yr 2006
\vol 45
\issue 5
\pages 306--325

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. E. B. Fokina, “Index sets of decidable models”, Siberian Math. J., 48:5 (2007), 939–948  mathnet  crossref  mathscinet  zmath  isi
    2. Calvert W., Fokina E., Goncharov S.S., Knight J.F., Kudinov O., Morozov A.S., Puzarenko V., “Index sets for classes of high rank structures”, J. Symbolic Logic, 72:4 (2007), 1418–1432  crossref  mathscinet  zmath  isi  elib  scopus
    3. Fokina E.B., “Index sets of computable structures with decidable theories”, Computation and Logic in the Real World, Proceedings, Lecture Notes in Computer Science, 4497, 2007, 290–296  crossref  mathscinet  zmath  isi  scopus
    4. E. N. Pavlovskii, “Estimation of the algorithmic complexity of classes of computable models”, Siberian Math. J., 49:3 (2008), 512–523  mathnet  crossref  mathscinet  zmath  isi
    5. E. B. Fokina, “Algoritmicheskie svoistva modelei signatury s dvumya odnomestnymi funktsionalnymi simvolami”, Vestn. NGU. Ser. matem., mekh., inform., 8:1 (2008), 90–101  mathnet
    6. Calvert W., Cenzer D., Harizanov V.S., Morozov A., “Effective categoricity of Abelian $p$-groups”, Ann. Pure Appl. Logic, 159:1-2 (2009), 187–197  crossref  mathscinet  zmath  isi  elib  scopus
    7. Fokina E.B., “Index sets for some classes of structures”, Ann. Pure Appl. Logic, 157:2-3 (2009), 139–147  crossref  mathscinet  zmath  isi  elib  scopus
    8. Carson J., Harizanov V., Knight J., Lange K., McCoy C., Morozov A., Quinn S., Safranski C., Wallbaum J., “Describing Free Groups”, Trans. Am. Math. Soc., 364:11 (2012), 5715–5728  crossref  mathscinet  zmath  isi  elib  scopus
    9. N. A. Bazhenov, “Computable numberings of the class of Boolean algebras with distinguished endomorphisms”, Algebra and Logic, 52:5 (2013), 355–366  mathnet  crossref  mathscinet  isi
    10. Knight J.F., McCoy C., “Index Sets and Scott Sentences”, Arch. Math. Log., 53:5-6 (2014), 519–524  crossref  mathscinet  zmath  isi  elib  scopus
    11. Fokina E.B., Harizanov V., Melnikov A., “Computable Model Theory”, Turing'S Legacy: Developments From Turing'S Ideas in Logic, Lecture Notes in Logic, 42, ed. Downey R., Cambridge Univ Press, 2014, 124–194  mathscinet  isi
    12. U. Andrews, D. I. Dushenin, C. Hill, J. F. Knight, A. G. Melnikov, “Comparing classes of finite sums”, Algebra and Logic, 54:6 (2016), 489–501  mathnet  crossref  crossref  mathscinet  isi
    13. Calvert W., “Pac Learning, Vc Dimension, and the Arithmetic Hierarchy”, Arch. Math. Log., 54:7-8 (2015), 871–883  crossref  mathscinet  zmath  isi  elib  scopus
    14. Hirschfeldt D.R., Kramer K., Miller R., Shlapentokh A., “Categoricity Properties For Computable Algebraic Fields”, Trans. Am. Math. Soc., 367:6 (2015), PII S0002-9947(2014)06094-7, 3981–4017  crossref  mathscinet  zmath  isi  elib
    15. Korovina M., Kudinov O., “Rice'S Theorem in Effectively Enumerable Topological Spaces”, Evolving Computability, Lecture Notes in Computer Science, 9136, eds. Beckmann A., Mitrana V., Soskova M., Springer-Verlag Berlin, 2015, 226–235  crossref  mathscinet  zmath  isi  scopus
    16. Korovina M., Kudinov O., “Index Sets as a Measure of Continuous Constraint Complexity”, Perspectives of System Informatics, Psi 2014, Lecture Notes in Computer Science, 8974, eds. Voronkov A., Virbitskaite I., Springer-Verlag Berlin, 2015, 201–215  crossref  mathscinet  zmath  isi  scopus
    17. Ho M.-Ch., “Describing Groups”, Proc. Amer. Math. Soc., 145:5 (2017), 2223–2239  crossref  mathscinet  zmath  isi  scopus
    18. Korovina M., Kudinov O., “Computable Elements and Functions in Effectively Enumerable Topological Spaces”, Math. Struct. Comput. Sci., 27:8 (2017), 1466–1494  crossref  mathscinet  zmath  isi  scopus
    19. Korovina M., Kudinov O., “The Rice-Shapiro Theorem in Computable Topology”, Log. Meth. Comput. Sci., 13:4 (2017), 30  crossref  mathscinet  zmath  isi  scopus
    20. Knight J.F., Saraph V., “Scott Sentences For Certain Groups”, Arch. Math. Log., 57:3-4 (2018), 453–472  crossref  mathscinet  zmath  isi  scopus
    21. Korovina M., Kudinov O., “Complexity For Partial Computable Functions Over Computable Polish Spaces”, Math. Struct. Comput. Sci., 28:3, SI (2018), 429–447  crossref  mathscinet  isi  scopus
    22. Lange K., Miller R., Steiner R.M., “Classifications of Computable Structures”, Notre Dame J. Form. Log., 59:1 (2018), 35–59  crossref  mathscinet  zmath  isi  scopus
    23. Harrison-Trainor M., Ho M.-Ch., “On Optimal Scott Sentences of Finitely Generated Algebraic Structures”, Proc. Amer. Math. Soc., 146:10 (2018), 4473–4485  crossref  mathscinet  zmath  isi  scopus
    24. Korovina M., Kudinov O., “Highlights of the Rice-Shapiro Theorem in Computable Topology”, Perspectives of System Informatics, Psi 2017, Lecture Notes in Computer Science, 10742, eds. Petrenko A., Voronkov A., Springer International Publishing Ag, 2018, 241–255  crossref  mathscinet  isi  scopus
    25. Quinn S.B., “Scott Sentences For Equivalence Structures”, Arch. Math. Log., 59:3-4 (2020), 453–460  crossref  mathscinet  zmath  isi  scopus
    26. N. Bazhenov, M. Marchuk, “A note on decidable categoricity and index sets”, Sib. elektron. matem. izv., 17 (2020), 1013–1026  mathnet  crossref
    27. Alvir R., Rossegger D., “the Complexity of Scott Sentences of Scattered Linear Orders”, J. Symb. Log., 85:3 (2020), 1079–1101  crossref  mathscinet  zmath  isi  scopus
    28. Brown T.A., Mcnicholl T.H., Melnikov A.G., “on the Complexity of Classifying Lebesgue Spaces”, J. Symb. Log., 85:3 (2020), PII S0022481220000638, 1254–1288  crossref  mathscinet  zmath  isi  scopus
    29. Bilanovic I., Chubb J., Roven S., “Detecting Properties From Descriptions of Groups”, Arch. Math. Log., 59:3-4 (2020), 293–312  crossref  mathscinet  zmath  isi  scopus
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:439
    Full text:105
    First page:2

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022