Mathematical Logic Quarterly 53 (4‐5):381-395 (2007)

Every second-countable regular topological space X is metrizable. For a given “computable” topological space satisfying an axiom of computable regularity M. Schröder [10] has constructed a computable metric. In this article we study whether this metric space can be considered computationally as a subspace of some computable metric space [15]. While Schröder's construction is “pointless”, i. e., only sets of a countable base but no concrete points are known, for a computable metric space a concrete dense set of computable points is needed. But there may be no computable points in X. By converging sequences of basis sets instead of Cauchy sequences of points we construct a metric completion of a space together with a canonical representation equation image, equation image. We show that there is a computable embedding of in with computable inverse. Finally, we construct a notation of a dense set of points in with computable mutual distances and prove that the Cauchy representation of the resulting computable metric space is equivalent to equation image. Therefore, every computably regular space has a computable homeomorphic embedding in a computable metric space, which topologically is its completion. By the way we prove a computable Urysohn lemma
Keywords computable metrization  TTE  Computable Analysis  computable embedding  computable metric space
Categories (categorize this paper)
DOI 10.1002/malq.200710009
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,307
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

How Incomputable Is the Separable Hahn-Banach Theorem?Guido Gherardi & Alberto Marcone - 2009 - Notre Dame Journal of Formal Logic 50 (4):393-425.
Algorithmic Randomness Over General Spaces.Kenshi Miyabe - 2014 - Mathematical Logic Quarterly 60 (3):184-204.
Computable de Finetti Measures.Cameron E. Freer & Daniel M. Roy - 2012 - Annals of Pure and Applied Logic 163 (5):530-546.

Add more citations

Similar books and articles

Embeddings of Computable Structures.Asher M. Kach, Oscar Levin & Reed Solomon - 2010 - Notre Dame Journal of Formal Logic 51 (1):55-68.
Finite Computable Dimension Does Not Relativize.Charles F. D. McCoy - 2002 - Archive for Mathematical Logic 41 (4):309-320.
Recursive Approximability of Real Numbers.Xizhong Zheng - 2002 - Mathematical Logic Quarterly 48 (S1):131-156.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.
Computable Embeddings and Strongly Minimal Theories.J. Chisholm, J. F. Knight & S. Miller - 2007 - Journal of Symbolic Logic 72 (3):1031 - 1040.
Effectively Closed Sets and Enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
Uncomputably Noisy Ergodic Limits.Jeremy Avigad - 2012 - Notre Dame Journal of Formal Logic 53 (3):347-350.


Added to PP index

Total views
8 ( #1,006,872 of 2,507,700 )

Recent downloads (6 months)
1 ( #416,820 of 2,507,700 )

How can I increase my downloads?


My notes