Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-26T23:20:30.689Z Has data issue: false hasContentIssue false
  • English
  • Français

Computably Isometric Spaces

Published online by Cambridge University Press:  12 March 2014

Alexander G. Melnikov
Alexander G. Melnikov*
Affiliation:
School of Mathematics, Statistics, and Operations Research, Victoria University of Wellington, Wellington, New Zealand, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We say that an uncountable metric space is computably categorical if every two computable structures on this space are equivalent up to a computable isometry. We show that Cantor space, the Urysohn space, and every separable Hilbert space are computably categorical, but the space [0, 1] of continuous functions on the unit interval with the supremum metric is not. We also characterize computably categorical subspaces of ℝn, and give a sufficient condition for a space to be computably categorical. Our interest is motivated by classical and recent results in computable (countable) model theory and computable analysis.

Keywords

Computable analysismetric space theory
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 78 , Issue 4 , December 2013 , pp. 1055 - 1085
Copyright
Copyright © Association for Symbolic Logic 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Ash, C. and Knight, J., Computable structures and the hyperarithmetical hyerarchy, Elsevier, Amsterdam, 2000.Google Scholar
[2] Bienvenu, L., Holzl, R, Miller, J., and Nies, A., The denjoy alternative for computable functions, Symposium on theoretical aspects of computer science, STACS 2012 (Dürr, Christoph and Wilke, Thomas, editors), LIPIcs, vol. 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 543–554.Google Scholar
[3] Brattka, V., Hertling, P., and Weihrauch, K., A tutorial on computable analysis, New computational paradigms: Changing conceptions of what is computable (Cooper, S. Barry, Löwe, Benedikt, and Sorbi, Andrea, editors), Springer, 2008, pp. 425–491.CrossRefGoogle Scholar
[4] Brouwer, L., Collected works. Vol. 1, North-Holland, Amsterdam, 1975, Philosophy and foundations of mathematics, Edited by Heyting, A..Google Scholar
[5] Brouwer, L., Collected works, Vol. 2, North-Holland, Amsterdam, 1976, Geometry, analysis, topology and mechanics, Edited by Freudenthal, Hans.Google Scholar
[6] Downey, R., Computability theory and linear orderings, Handbook of recursive mathematics, Vol. 2, Studies in Logic and the Foundation of Mathematics, vol. 139, North-Holland, Amsterdam, 1998, pp. 823–976.Google Scholar
[7] Downey, R., Kach, A., Lempp, S., and Turetsky, D., On computable categoricity, To appear.Google Scholar
[8] Downey, R. and Hirschfeldt, D., Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, 2010.CrossRefGoogle Scholar
[9] Ershov, Yu and Goncharov, S., Constructive models, Kluwer Academic Publications, 2000.CrossRefGoogle Scholar
[10] Ershov, Yuri L., Theory of numberings, Handbook of computability theory, Studies in Logic and the Foundations of Mathematics, vol. 140, North-Holland, Amsterdam, 1999, pp. 473–503.CrossRefGoogle Scholar
[11] Fröhlich, A. and Shepherdson, J., Effective procedures in field theory, Philosophical Transactions of the Royal Society of London. Series A., vol. 248 (1956), pp. 407–432.Google Scholar
[12] Goncharov, S., Autostability of models and abelian groups, Algebra and Logic, vol. 19 (1980), pp. 13–27, (English translation).CrossRefGoogle Scholar
[13] Goncharov, S., The problem of the number of nonautoequivalent constructivizations, Algebra and Logic, vol. 19 (1980), pp. 13–27, (English translation).CrossRefGoogle Scholar
[14] Goncharov, S., Countable boolean algebras and decidability, Siberian School of Algebra and Logic, Nauchnaya Kniga, Novosibirsk, 1996.Google Scholar
[15] Hertling, P., A real number structure that is effectively categorical, Mathematical Logic Quarterly, vol. 45 (1999), no. 2, pp. 147–182.CrossRefGoogle Scholar
[16] Iljazović, Z., Isometries and computability structures, Journal of Universal Computer Science, vol. 16 (2010), no. 18, pp. 2569–2596.Google Scholar
[17] Katětov, M., On universal metric spaces, General topology and its relations to modern analysis and algebra, VI (Frolik, Z., editor), vol. 16, Heldermann, Berlin, 1988, pp. 323–330.Google Scholar
[18] Kushner, B., Lectures on constructive mathematical analysis, Translations of Mathematical Monographs, vol. 60, American Mathematical Society, Providence, Rhode Island, 1984.CrossRefGoogle Scholar
[19] LaRoche, P., Recursively presented boolean algebras, Notices AMS, vol. 24 (1977), pp. 552–553.Google Scholar
[20] Mal′Cev, A., On recursive Abelian groups, Doklady Akademii Nauk SSSR, vol. 32 (1962), pp. 1431–1434.Google Scholar
[21] Melleray, J., Some geometric and dynamical properties of the Urysohn space, Topology and its Applications, vol. 155 (2008), no. 14, pp. 1531–1560.CrossRefGoogle Scholar
[22] Melnikov, A. and Ng, K.M., Computable structures and operations on the space of continuous functions, to appear.Google Scholar
[23] Metakides, G. and Nerode, A., Effective content of field theory, Annals of Mathematical Logic, vol. 17 (1979), pp. 289–320.CrossRefGoogle Scholar
[24] Miller, R. and Schoutens, H., Computably categoricalfields viafermat's last theorem, to appear.Google Scholar
[25] Myhill, J., A recursive function, defined on a compact interval and having a continuous derivative that is not recursive, The Michigan Mathematical Journal, vol. 18 (1971), pp. 97–98.CrossRefGoogle Scholar
[26] Nies, A., Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009.CrossRefGoogle Scholar
[27] Nies, A., Interactions of computability and randomness, Proceedings of the International Congress of Mathematicians. Volume II (New Delhi) (Ragunathan, S., editor), Hindustan Book Agency, 2010, pp. 30–57.Google Scholar
[28] Nurtazin, A.T., Computable classes and algebraic criteria of autostability, Summary of Scientific Schools, Mathematical Institute SB of USSR AS, Novosibirsk, 1974.Google Scholar
[29] Pour-El, M. and Richards, I., Computability and noncomputability in classical analysis, Transactions of the American Mathematical Society, vol. 275 (1983), no. 2, pp. 539–560.CrossRefGoogle Scholar
[30] Pour-El, M. and Richards, J., Computability in analysis and physics, Perspectives in Mathematical Logic, Volume 1, Springer, 1989.CrossRefGoogle Scholar
[31] Rabin, M., Computable algebra, general theory and theory of computable fields., Transactions of the American Mathematical Society, vol. 95 (1960), pp. 341–360.Google Scholar
[32] Remmel, J. B., Recursively categorical linear orderings, Proceedings of the American Mathematical Society, vol. 83 (1981), pp. 387–391.CrossRefGoogle Scholar
[33] Turing, A., On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, vol. 42 (1936), no. 2, pp. 230–265.Google Scholar
[34] Turing, A., On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction, Proceedings of the London Mathematical Society, vol. 43 (1937), no. 2, pp. 544–546.Google Scholar
[35] Urysohn, P., Sur un espace métrique universel, Bulletin des Sciences Mathématiques, vol. 51 (1927), pp. 43–64, 74–90.Google Scholar
[36] Uspenskij, V., The Urysohn universal metric space is homeomorphic to a Hilbert space, Topology and its Applications, vol. 139 (2004), pp. 145–149.CrossRefGoogle Scholar
[37] Weihrauch, K., Computable analysis, Springer, 2000.CrossRefGoogle Scholar
[38] White, W., On the complexity of categoricity in computable structures, Mathematical Logic Quarterly, vol. 49 (2003), no. 6, pp. 603–614.CrossRefGoogle Scholar