World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Computable embeddability for algebraic structures

    https://doi.org/10.1142/S1793557122501261Cited by:0 (Source: Crossref)

    In computability theory, the standard tool to classify preorders is provided by the computable reducibility. If R and S are preorders with domain ω, then R is computably reducible to S if and only if there is a computable function f such that for all x and y, xRyf(x)Sf(y). We study the complexity of preorders which arise in a natural way in computable structure theory. We prove that the relation of computable isomorphic embeddability among computable torsion abelian groups is a Σ30 complete preorder. A similar result is obtained for computable distributive lattices. We show that the relation of primitive recursive embeddability among punctual structures (in the setting of Kalimullin et al.) is a Σ20 complete preorder.

    Communicated by M. Arslanov

    AMSC: 03C57, 03D45, 03D30

    References

    • 1. P. E. Alaev and V. L. Selivanov, Polynomial computability of fields of algebraic numbers, Dokl. Math. 98(1) (2018) 341–343. Crossref, Web of ScienceGoogle Scholar
    • 2. U. Andrews, S. Badaev and A. Sorbi, A survey on universal computably enumerable equivalence relations, in Computability and Complexity, Lecture Notes in Computer Science, eds. A. DayM. FellowsN. GreenbergB. KhoussainovA. MelnikovF. Rosamond, Vol. 10010 (Springer, 2017), pp. 418–451. CrossrefGoogle Scholar
    • 3. U. Andrews, S. Lempp, J. S. Miller, K. M. Ng, L. San Mauro and A. Sorbi, Universal computably enumerable equivalence relations, J. Symb. Logic 79(1) (2014) 60–88. Crossref, Web of ScienceGoogle Scholar
    • 4. U. Andrews, N. Schweber and A. Sorbi, The theory of ceers computes true arithmetic, Ann. Pure Appl. Logic 171(8) (2020), Article ID: 102811. Crossref, Web of ScienceGoogle Scholar
    • 5. U. Andrews and A. Sorbi, Joins and meets in the structure of ceers, Computability 8(3–4) (2019) 193–241. Crossref, Web of ScienceGoogle Scholar
    • 6. C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, Vol. 144 (Elsevier Science B.V., 2000). Google Scholar
    • 7. S. Badaev and A. Sorbi, Weakly precomplete computably enumerable equivalence relations, Math. Log. Q. 62(1–2) (2016) 111–127. Crossref, Web of ScienceGoogle Scholar
    • 8. N. Bazhenov, R. Downey, I. Kalimullin and A. Melnikov, Foundations of online structure theory, Bull. Symb. Log. 25(2) (2019) 141–181. Crossref, Web of ScienceGoogle Scholar
    • 9. N. A. Bazhenov, E. B. Fokina, D. Rossegger and L. San Mauro, Computable bi-embeddable categoricity, Algebra Logic 57(5) (2018) 392–396. Crossref, Web of ScienceGoogle Scholar
    • 10. N. Bazhenov, E. Fokina, D. Rossegger and L. San Mauro, Degrees of bi-embeddable categoricity of equivalence structures, Arch. Math. Logic 58(5–6) (2019) 543–563. Crossref, Web of ScienceGoogle Scholar
    • 11. N. Bazhenov, E. Fokina, D. Rossegger and L. San Mauro, Degrees of bi-embeddable categoricity, Computability 10(1) (2021) 1–16. Crossref, Web of ScienceGoogle Scholar
    • 12. N. Bazhenov, M. Harrison-Trainor, I. Kalimullin, A. Melnikov and K. M. Ng, Automatic and polynomial-time algebraic structures, J. Symb. Log. 84(4) (2019) 1630–1669. Crossref, Web of ScienceGoogle Scholar
    • 13. N. A. Bazhenov and B. S. Kalmurzaev, Weakly precomplete equivalence relations in the Ershov hierarchy, Sib. Math. J. 58(3) (2019) 199–213. Google Scholar
    • 14. N. Bazhenov, M. Mustafa, L. San Mauro, A. Sorbi and M. Yamaleev, Classifying equivalence relations in the Ershov hierarchy, Arch. Math. Logic 59(7–8) (2020) 835–864. Crossref, Web of ScienceGoogle Scholar
    • 15. N. A. Bazhenov, M. Mustafa, L. San Mauro and M. M. Yamaleev, Minimal equivalence relations in hyperarithmetical and analytical hierarchies, Lobachevskii J. Math. 41(2) (2020) 145–150. Crossref, Web of ScienceGoogle Scholar
    • 16. N. Bazhenov, M. Mustafa and M. Yamaleev, Computable isomorphisms of distributive lattices, in Theory and Applications of Models of Computation, Lecture Notes in Computer Science, eds. T. V. GopalJ. Watada, Vol. 11436 (Springer, 2019), pp. 28–41. CrossrefGoogle Scholar
    • 17. C. Bernardi, On the relation provable equivalence and on partitions in effectively inseparable sets, Stud. Log. 40(1) (1981) 29–37. CrossrefGoogle Scholar
    • 18. C. Bernardi and A. Sorbi, Classifying positive equivalence relations, J. Symb. Logic 48(3) (1983) 529–538. Crossref, Web of ScienceGoogle Scholar
    • 19. F. Calderoni, H. Mildenberger and L. Motto Ros, Uncountable structures are not classifiable up to bi-embeddability, J. Math. Log. 20(1) (2020), Article ID: 2050001. Link, Web of ScienceGoogle Scholar
    • 20. F. Calderoni and S. Thomas, The bi-embeddability relation for countable abelian groups, Trans. Am. Math. Soc. 371 (2019) 2237–2254. Crossref, Web of ScienceGoogle Scholar
    • 21. D. Cenzer, R. G. Downey, J. B. Remmel and Z. Uddin, Space complexity of Abelian groups, Arch. Math. Log. 48(1) (2009) 115–140. Crossref, Web of ScienceGoogle Scholar
    • 22. D. Cenzer and J. Remmel, Polynomial-time versus recursive models, Ann. Pure Appl. Logic 54(1) (1991) 17–58. Crossref, Web of ScienceGoogle Scholar
    • 23. D. A. Cenzer and J. B. Remmel, Polynomial-time Abelian groups, Ann. Pure Appl. Logic 56(1–3) (1992) 313–363. Crossref, Web of ScienceGoogle Scholar
    • 24. D. Cenzer and J. B. Remmel, Complexity theoretic model theory and algebra, in Handbook of Recursive Mathematics, Vol. 1, Studies in Logic and the Foundations of Mathematics, eds. Yu. L. ErshovS. S. GoncharovA. NerodeJ. B. Remmel, Vol. 138 (North-Holland, 1998), pp. 381–513. CrossrefGoogle Scholar
    • 25. R. Downey, N. Greenberg, A. Melnikov, K. M. Ng and D. Turetsky, Punctual categoricity and universality, J. Symb. Log. 85(4) (2020) 1427–1466. Crossref, Web of ScienceGoogle Scholar
    • 26. R. Downey, A. Melnikov and K. M. Ng, Foundations of online structure theory II: The operator approach, Log. Methods Comput. Sci. 17(3) (2021) 6:1–6:35. Google Scholar
    • 27. Ju. L. Eršov, Theorie der Numerierungen I, Z. Math. Logik Grundl. Math. 19(19–25) (1973) 289–388. CrossrefGoogle Scholar
    • 28. Yu. L. Ershov, Positive equivalences, Algebra Logic 10(6) (1971) 378–394. CrossrefGoogle Scholar
    • 29. Yu. L. Ershov, Theory of Numberings (Nauka, Moscow, 1977). (in Russian). Google Scholar
    • 30. Yu. L. Ershov and S. S. Goncharov, Constructive Models (Consultants Bureau, New York, 2000). CrossrefGoogle Scholar
    • 31. E. Fokina, S. Friedman and A. Nies, Equivalence relations that are Σ30 complete for computable reducibility, in Logic, Language, Information and Computation, Lecture Notes in Computer Science, eds. L. OngR. de Queiroz, Vol. 7456 (Springer, 2012), pp. 26–33. CrossrefGoogle Scholar
    • 32. E. B. Fokina, S.-D. Friedman, V. Harizanov, J. F. Knight, C. McCoy and A. Montalbán, Isomorphism relations on computable structures, J. Symb. Logic 77(1) (2012) 122–132. Crossref, Web of ScienceGoogle Scholar
    • 33. H. Friedman and L. Stanley, A Borel reducibility theory for classes of countable structures, J. Symb. Log. 54(3) (1989) 894–914. Crossref, Web of ScienceGoogle Scholar
    • 34. S. Gao, Invariant Descriptive Set Theory (CRC Press, Boca Raton, FL, 2009). Google Scholar
    • 35. S. Gao and P. Gerdes, Computably enumerable equivalence relations, Stud. Log. 67(1) (2001) 27–59. CrossrefGoogle Scholar
    • 36. S. S. Goncharov and J. F. Knight, Computable structure and non-structure theorems, Algebra Logic 41(6) (2002) 351–373. CrossrefGoogle Scholar
    • 37. S. Grigorieff, Every recursive linear ordering has a copy in DTIME-SPACE (n,log(n)), J. Symb. Log. 55(1) (1990) 260–276. Crossref, Web of ScienceGoogle Scholar
    • 38. G. Hjorth, Borel equivalence relations, in Handbook of Set Theory, eds. M. ForemanA. Kanamori, Vol. 1 (Springer, 2010), pp. 297–332. CrossrefGoogle Scholar
    • 39. G. Hjorth and A. S. Kechris, Recent developments in the theory of Borel reducibility, Fundam. Math. 170(1–2) (2001) 21–52. Crossref, Web of ScienceGoogle Scholar
    • 40. E. Ianovski, Computable component-wise reducibility, preprint, arXiv:1301.7112. Google Scholar
    • 41. E. Ianovski, R. Miller, K. M. Ng and A. Nies, Complexity of equivalence relations and preorders from computability theory, J. Symb. Logic 79(3) (2014) 859–881. Crossref, Web of ScienceGoogle Scholar
    • 42. I. Kalimullin, A. Melnikov and K. M. Ng, Algebraic structures computable without delay, Theor. Comput. Sci. 674 (2017) 73–98. Crossref, Web of ScienceGoogle Scholar
    • 43. N. G. Khisamiev, Arithmetic hierarchy of abelian groups, Sib. Math. J. 29(6) (1988) 987–999. Crossref, Web of ScienceGoogle Scholar
    • 44. N. G. Khisamiev, Constructive abelian groups, in Handbook of Recursive Mathematics, Vol. 2, Studies in Logic and the Foundations of Mathematics, eds. Yu. L. ErshovS. S. GoncharovA. NerodeJ. B. Remmel, Vol. 139 (North-Holland, 1998), pp. 1177–1231. CrossrefGoogle Scholar
    • 45. A. Louveau and C. Rosendal, Complete analytic equivalence relations, Trans. Am. Math. Soc. 357 (2005) 4839–4866. Crossref, Web of ScienceGoogle Scholar
    • 46. A. G. Melnikov, Computable abelian groups, Bull. Symb. Logic 20(3) (2014) 315–356. Crossref, Web of ScienceGoogle Scholar
    • 47. A. G. Melnikov, Eliminating unbounded search in computable algebra, in Unveiling Dynamics and Complexity, Lecture Notes in Computer Science, eds. J. KariF. ManeaI. Petre, Vol. 10307 (Springer, 2017), pp. 77–87. CrossrefGoogle Scholar
    • 48. A. G. Melnikov and K. M. Ng, The back-and-forth method and computability without delay, Isr. J. Math. 234(2) (2019) 959–1000. Crossref, Web of ScienceGoogle Scholar
    • 49. A. G. Melnikov and K. M. Ng, A structure of punctual dimension two, Proc. Am. Math. Soc. 148 (2020) 3113–3128. Crossref, Web of ScienceGoogle Scholar
    • 50. A. Nerode and J. B. Remmel, Polynomial time equivalence types, in Logic and Computation, Contemporary Mathematics, ed. W. Sieg, Vol. 106 (American Mathematical Society, 1990), pp. 221–249. CrossrefGoogle Scholar
    • 51. K. M. Ng and H. Yu, On the degree structure of equivalence relations under computable reducibility, Notre Dame J. Formal Logic 60(4) (2019) 733–761. Crossref, Web of ScienceGoogle Scholar
    • 52. H. Rogers, Theory of Recursive Functions and Effective Computability (MIT Press, 1987). Google Scholar
    • 53. V. L. Selivanov, Algorithmic complexity of algebraic systems, Math. Notes 44(6) (1988) 944–950. Crossref, Web of ScienceGoogle Scholar
    • 54. A. Turlington, Computability of Heyting algebras and distributive lattices, Ph.D. thesis, University of Connecticut (2010). Google Scholar
    • 55. A. Visser, Numerations, λ-calculus and arithmetic, in To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, eds. J. P. SeldinJ. R. Hindley (Academic Press, 1980), pp. 259–284. Google Scholar
    • 56. J. Williams, Universal countable Borel quasi-orders, J. Symb. Log. 79(3) (2014) 928–954. Crossref, Web of ScienceGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out our Mathematics books for inspirations & up-to-date information in your research area today!