SpringerLink
Log in

New Degree Spectra of Polish Spaces

  • Published:
Siberian Mathematical Journal Aims and scope Submit manuscript

Abstract

The main result is as follows: Fix an arbitrary prime \( q \). A \( q \)-divisible torsion-free (discrete, countable) abelian group \( G \) has a \( \Delta^{0}_{2} \)-presentation if, and only if, its connected Pontryagin–van Kampen Polish dual \( \widehat{G} \) admits a computable complete metrization (in which we do not require the operations to be computable). We use this jump-inversion/duality theorem to transfer the results on the degree spectra of torsion-free abelian groups to the results about the degree spectra of Polish spaces up to homeomorphism. For instance, it follows that for every computable ordinal \( \alpha>1 \) and each \( {\mathbf{a}}>0^{(\alpha)} \) there is a connected compact Polish space having proper \( \alpha^{th} \) jump degree \( {\mathbf{a}} \) (up to homeomorphism). Also, for every computable ordinal \( \beta \) of the form \( 1+\delta+2n+1 \), where \( \delta \) is zero or is a limit ordinal and \( n\in\omega \), there is a connected Polish space having an \( X \)-computable copy if and only if \( X \) is \( non \)-\( low_{\beta} \). In particular, there is a connected Polish space having exactly the \( non \)-\( low_{2} \) complete metrizations. The case when \( \beta=2 \) is an unexpected consequence of the main result of the author’s M.Sc. Thesis written under the supervision of Sergey S. Goncharov.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. By this we mean the metric completion of a countable metric space upon the domain of \( \omega \) in which the predicates \( D_{<}(i,j,k)\iff d(i,j)<2^{-k} \) and \( D_{>}(i,j,k)\iff d(i,j)>2^{-k} \) are uniformly primitive recursive.

  2. Recall that an oracle \( X \) is low if the halting problem \( X^{\prime} \) for Turing machines with oracle \( X \) can be computed using \( \varnothing^{\prime} \), the usual halting problem (with no oracles). The class low\( {}_{4} \) is defined similarly but on using \( X^{(4)} \) and \( \varnothing^{(4)} \). This is a degree-invariant property. We cite [23] for further background.

References

  1. Ershov Yu. L. and Goncharov S. S., Constructive Models, Consultants Bureau, New York, etc. (2000) (Siberian School of Algebra and Logic).

    Book  MATH  Google Scholar 

  2. Ash C. J. and Knight J. F., Computable Structures and the Hyperarithmetical Hierarchy, North-Holland, Amsterdam (2000) (Studies in Logic and the Foundations of Mathematics; Vol. 144).

    MATH  Google Scholar 

  3. Ershov Yu., Problems of Solubility and Constructive Models, Nauka, Moscow (1980) [Russian].

    Google Scholar 

  4. Brattka V., Hertling P., and Weihrauch K., “A tutorial on computable analysis,” in: New Computational Paradigms, Springer, New York (2008), 425–491.

  5. Weihrauch K., Computable Analysis, Springer, Berlin (2000) (Texts in Theoretical Computer Science. An EATCS Series).

    Book  MATH  Google Scholar 

  6. Pour-El M. B. and Richards J. I., Computability in Analysis and Physics, Springer, Berlin (1989) (Perspectives in Mathematical Logic).

    Book  MATH  Google Scholar 

  7. Turing A. M., “On computable numbers, with an application to the entscheidungsproblem,” Proc. London Math. Soc., vol. 42, 230–265 (1936).

    MathSciNet  MATH  Google Scholar 

  8. Turing A. M., “On computable numbers, with an application to the entscheidungsproblem. A correction,” Proc. London Math. Soc., vol. 43, 544–546 (1937).

    MathSciNet  MATH  Google Scholar 

  9. Banach S. and Mazur S., “Sur les fonctions calculables,” Ann. Soc. Pol. Math., vol. 16, 233 (1937).

    Google Scholar 

  10. Fröhlich A. and Shepherdson J., “Effective procedures in field theory,” Philos. Trans. Roy. Soc. London. Ser. A., vol. 248, no. 950, 407–432 (1956).

    Article  MathSciNet  MATH  Google Scholar 

  11. Maltsev A. I., “Constructive algebras. I,” Russian Math. Surveys, vol. 16, no. 3, 77–129 (1961).

    Article  MathSciNet  Google Scholar 

  12. Rabin M. O., “Computable algebra, general theory and theory of computable fields,” Trans. Amer. Math. Soc., vol. 95, 341–360 (1960).

    MathSciNet  MATH  Google Scholar 

  13. Melnikov A. G., “Computably isometric spaces,” J. Symb. Log., vol. 78, no. 4, 1055–1085 (2013).

    Article  MathSciNet  MATH  Google Scholar 

  14. Clanin J., McNicholl T. H., and Stull D. M., “Analytic computable structure theory and \( L^{p} \) spaces,” Fund. Math., vol. 244, no. 3, 255–285 (2019).

    Article  MathSciNet  MATH  Google Scholar 

  15. McNicholl T. H., “Computable copies of \( \ell^{p} \),” Computability, vol. 6, no. 4, 391–408 (2017).

    Article  MathSciNet  MATH  Google Scholar 

  16. Brown T., McNicholl T., and Melnikov A., “On the complexity of classifying Lebesgue spaces,” J. Symb. Log., vol. 85, no. 3, 1–35 (2020).

    MathSciNet  MATH  Google Scholar 

  17. Downey R. G. and Melnikov A. G., “Computable analysis and classification problems,” in: Beyond the Horizon of Computability: Proceedings of the 16th Conference on Computability in Europe, CiE 2020, Fisciano, Italy, June 29–July 3, 2020, Springer, Cham (2020), 100–111 (Lecture Notes in Computer Science; Vol. 12098).

  18. Lupini M., Melnikov A., and Nies A., Computable Topological Abelian Groups. ar**v:2105.12897 [math.LO] (2021).

    Google Scholar 

  19. Kalimullin I., Melnikov A., and Ng Keng Meng, “Algebraic structures computable without delay,” Theoret. Comput. Sci., vol. 674, 73–98 (2017).

    Article  MathSciNet  MATH  Google Scholar 

  20. Melnikov A. G., “Eliminating unbounded search in computable algebra,” in: Unveiling Dynamics and Complexity, Springer, Cham (2017), 77–87 (Lecture Notes in Comput. Sci.; Vol. 10307).

  21. Bazhenov N., Downey R., Kalimullin I., and Melnikov A., “Foundations of online structure theory,” Bull. Symb. Log., vol. 25, no. 2, 141–181 (2019).

    Article  MathSciNet  MATH  Google Scholar 

  22. Downey R., Melnikov A., and Ng Keng Meng, Foundations of Online Structure Theory. II: The Operator Approach. ar**v:2007.07401 [math.LO] (2021).

    Google Scholar 

  23. Soare R. I., Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer, Berlin, Heidelberg, New York, London, Paris, and Tokyo (1987) (Perspectives in Mathematical Logic).

    Book  MATH  Google Scholar 

  24. Downey R. and Jockusch C. G., “Every low boolean algebra is isomorphic to a recursive one,” Proc. Amer. Math. Soc., vol. 122, no. 3, 871–880 (1994).

    Article  MathSciNet  MATH  Google Scholar 

  25. Knight J. F. and Stob M., “Computable boolean algebras,” J. Symb. Log., vol. 65, no. 4, 1605–1623 (2000).

    Article  MathSciNet  MATH  Google Scholar 

  26. Richter L., “Degrees of structures,” J. Symb. Log., vol. 46, no. 4, 723–731 (1981).

    Article  MathSciNet  MATH  Google Scholar 

  27. Kalimullin I., Khoussainov B., and Melnikov A., “Limitwise monotonic sequences and degree spectra of structures,” Proc. Amer. Math. Soc., vol. 141, no. 9, 3275–3289 (2013).

    Article  MathSciNet  MATH  Google Scholar 

  28. Frolov A., Kalimullin I., Harizanov V., Kudinov O., and Miller R., “Spectra of high\( {}_{n} \) and non-low\( {}_{n} \) degrees,” J. Logic Comput., vol. 22, no. 4, 755–777 (2012).

    Article  MathSciNet  MATH  Google Scholar 

  29. Hirschfeldt D., Khoussainov B., Shore R., and Slinko A., “Degree spectra and computable dimensions in algebraic structures,” Ann. Pure Appl. Logic, vol. 115, no. 1, 71–113 (2002).

    Article  MathSciNet  MATH  Google Scholar 

  30. Frolov A., Kalimullin I., and Miller R., “Spectra of algebraic fields and subfields,” in: Mathematical Theory and Computational Practice: Proceedings of the 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19–24, Springer, Berlin (2009), 232–241 (Lecture Notes in Computer Science; Vol. 5635).

  31. Greenberg N., Montalbán A., and Slaman T., “Relative to any non-hyperarithmetic set,” J. Math. Log., vol. 13, no. 1 (2013) (Article ID 1250007, 26 p.).

  32. Wehner S., “Enumerations, countable structures and Turing degrees,” Proc. Amer. Math. Soc., vol. 126, no. 7, 2131–2139 (1998).

    Article  MathSciNet  MATH  Google Scholar 

  33. Slaman T., “Relative to any nonrecursive set,” Proc. Amer. Math. Soc., vol. 126, no. 7, 2117–2122 (1998).

    Article  MathSciNet  MATH  Google Scholar 

  34. Andrews U., Cai M., Kalimullin I. Sh., Lempp S., Miller J. S., and Montalbán A., “The complements of lower cones of degrees and the degree spectra of structures,” J. Symb. Log., vol. 81, no. 3, 997–1006 (2016).

    Article  MathSciNet  MATH  Google Scholar 

  35. Oates S., Jump Degrees of Groups. Ph.D. Thesis, University of Notre Dame, ProQuest LLC, Ann Arbor (1989).

    MATH  Google Scholar 

  36. Andersen B., Kach A., Melnikov A., and Solomon R., “Jump degrees of torsion-free abelian groups,” J. Symb. Log., vol. 77, no. 4, 1067–1100 (2012).

    Article  MathSciNet  MATH  Google Scholar 

  37. Coles R., Downey R., and Slaman T., “Every set has a least jump enumeration,” J. London Math. Soc. (2), vol. 62, no. 3, 641–649 (2000).

    Article  MathSciNet  MATH  Google Scholar 

  38. Downey R. and Knight J., “Orderings with \( \alpha \)th jump degree \( {\mathbf{0}}^{(\alpha)} \),” Proc. Amer. Math. Soc., vol. 114, no. 2, 545–552 (1992).

    MathSciNet  MATH  Google Scholar 

  39. Jockusch C. G. and Soare R., “Boolean algebras, Stone spaces, and the iterated Turing jump,” J. Symb. Log., vol. 59, no. 4, 1121–1138 (1994).

    Article  MathSciNet  MATH  Google Scholar 

  40. Selivanov V. L., “On degree spectra of topological spaces,” Lobachevskii J. Math., vol. 41, no. 2, 252–259 (2020).

    Article  MathSciNet  MATH  Google Scholar 

  41. Hoyrup M., Kihara T., and Selivanov V., “Degrees of non-computability of homeomorphism types of polish spaces,” in: Beyond the Horizon of Computability: Proceedings of the 16th Conference on Computability in Europe, CiE 2020, Fisciano, Italy, June 29–July 3, 2020, Springer, Cham (2020), 189–192 (Lecture Notes in Computer Science; Vol. 12098).

  42. Harrison-Trainor M., Melnikov A., and Ng Keng Meng, “Computability of Polish spaces up to homeomorphism,” J. Symb. Log., vol. 85, no. 4, 1–25 (2020).

    MathSciNet  MATH  Google Scholar 

  43. Hoyrup M., Kihara T., and Selivanov V., Degree Spectra of Homeomorphism Types of Polish Spaces (2020). https://hal.archives-ouvertes.fr/hal-02555111

    Google Scholar 

  44. Bazhenov N., Harrison-Trainor M., and Melnikov A., Computable Stone Spaces. ar**v:2107.01536 [math.LO] (2021).

    Google Scholar 

  45. Melnikov A., “New degree spectra of abelian groups,” Notre Dame J. Formal Logic, vol. 58, no. 4, 507–525 (2017).

    Article  MathSciNet  MATH  Google Scholar 

  46. Melnikov A., “Enumerations and completely decomposable torsion-free abelian groups,” Theory Comput. Syst., vol. 45, no. 4, 897–916 (2009).

    Article  MathSciNet  MATH  Google Scholar 

  47. Downey R., “On presentations of algebraic structures,” in: Complexity, Logic, and Recursion Theory, Dekker, New York (1997), 157–205 (Lecture Notes in Pure and Appl. Math.; Vol. 187).

  48. Melnikov A. G., “Computable Abelian groups,” Bull. Symb. Log., vol. 20, no. 3, 315–356 (2014).

    Article  MathSciNet  MATH  Google Scholar 

  49. Melnikov A., “Torsion-free abelian groups with optimal Scott families,” J. Math. Log., vol. 18, no. 1 (2018) (Article ID 1850002, 47 p.).

  50. Pontryagin L., “The theory of topological commutative groups,” Ann. of Math. (2), vol. 35, no. 2, 361–388 (1934).

    Article  MathSciNet  Google Scholar 

  51. Pontryagin L. S., Topological Groups, Gordon and Breach, New York, London, and Paris (1966).

    Google Scholar 

  52. Morris S. A., Pontryagin Duality and the Structure of Locally Compact Abelian Groups, Cambridge Univ., Cambridge, New York, and Melbourne (1977) (London Math. Soc. Lecture Note Ser.; No. 29).

    Book  MATH  Google Scholar 

  53. Hofmann K. H. and Morris S. A., The Structure of Compact Groups, De Gruyter, Berlin and New York (1998) (De Gruyter Studies in Mathematics; Vol. 25).

    MATH  Google Scholar 

  54. Hofmann K. H. and Mostert P. S., Cohomology Theories for Compact Abelian Groups, Springer, Berlin (1973).

    Book  MATH  Google Scholar 

  55. Munkres J. R., Elements of Algebraic Topology, Addison-Wesley, Menlo Park, CA (1984).

    MATH  Google Scholar 

  56. Fuchs L., Infinite Abelian Groups. Vol. 1, Academic, New York (1970) (Pure Appl. Math.; Vol. 36).

    MATH  Google Scholar 

  57. Khisamiev N., “Hierarchies of torsion-free abelian groups,” Algebra Logic, vol. 25, no. 2, 128–142 (1986).

    Article  MathSciNet  MATH  Google Scholar 

  58. Melnikov A., “Computable topological groups and Pontryagin duality,” Trans. Amer. Math. Soc., vol. 370, no. 12, 8709–8737 (2018).

    Article  MathSciNet  MATH  Google Scholar 

  59. Dobritsa V. P., “Some constructivizations of abelian groups,” Sib. Math. J., vol. 24, no. 2, 167–173 (1983).

    Article  MathSciNet  MATH  Google Scholar 

  60. Harrison-Trainor M., Melnikov A., and Montalbán A., “Independence in computable algebra,” J. Algebra, vol. 443, 441–468 (2015).

    Article  MathSciNet  MATH  Google Scholar 

  61. Hoyrup M., Rojas C., Selivanov V., and Stull D. M., “Computability on quasi-Polish spaces,” in: Descriptional Complexity of Formal Systems, Springer, Cham (2019), 171–183 (Lecture Notes in Comput. Sci.; Vol. 11612).

Download references

Funding

A. G. Melnikov was supported by the Mathematical Center in Akademgorodok under Agreement No. 075–15–2019–1613 with the Ministry of Science and Higher Education of the Russian Federation, and Rutherford Discovery Fellowship (Wellington) RDF-MAU1905, Royal Society Te Ap\( \bar{\mathrm{a}} \)rangi.

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Victoria University of Wellington, Wellington, New Zealand

    A. G. Melnikov

  2. Sobolev Institute of Mathematics, Novosibirsk, Russia

    A. G. Melnikov

Authors
  1. A. G. Melnikov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. G. Melnikov.

Additional information

Translated from Sibirskii Matematicheskii Zhurnal, 2021, Vol. 62, No. 5, pp. 1091–1108. https://doi.org/10.33048/smzh.2021.62.511

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Melnikov, A.G. New Degree Spectra of Polish Spaces. Sib Math J 62, 882–894 (2021). https://doi.org/10.1134/S0037446621050116

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0037446621050116

Keywords

UDC

Search

Navigation