Metric Bases and Computability of 1-Manifolds

Konrad Burnik (kburnik@gmail.com), Independent Researcher, The Netherlands

This talk is based on joint work with Zvonko Iljazović and Lucija Validžić (University of Zagreb).

In computable topology, semicomputability of a space together with computability of its boundary often implies computability of the whole space. It is known that connected 1-manifolds with or without boundary are each homeomorphic to exactly one of $\mathbb{S}^1$, $[0,1]$, $[0,\infty)$ and $\mathbb{R}$ [4]. It was proved in [2] that in a computable metric space $(X,d,\alpha)$ each semicomputable 1-manifold with finitely many connected components, possibly with boundary, whose boundary is computable must itself be computable. The relationship between the computability of an arc and that of its endpoints is well studied: Miller [3] constructed a computable arc in $\mathbb{R}^2$ with noncomputable endpoints, while a computable arc in $\mathbb{R}$ must be a segment $[a,b]$ with $a$ and $b$ computable. The following property makes the endpoints special: a point $x_0$ is a metric basis for a metric space $(X,d)$ if $d(x,x_0)=d(y,x_0)$ implies $x=y$. Generalizing this, let $S\subseteq X$, $S \neq \emptyset$, be such that for all $x,y \in X$ if $d(x,s) = d(y,s)$ for all $s \in S$, then $x=y$. Then we call $S$ a metric basis for $(X,d)$. We show that if a computable metric space $(X,d,\alpha)$ is effectively compact and $(X,d)$ has finitely many connected components, then every singleton metric basis is a computable point; the assumption of effective compactness cannot be omitted. We also go beyond the compact setting: if $(X,d,\alpha)$ has the effective covering property [1] and compact closed balls, and $(X,d)$ is a topological ray, then any singleton metric basis is again a computable point. We show that the existence of a computable metric basis in the case of an arc or a topological ray implies the existence of a computable homeomorphism between $(X,d,\alpha)$ and the model space $[0,1]$ or $[0,\infty)$ with its canonical computability structure, respectively. Finally, we will briefly comment on the cases of the topological circle and the topological line, where a metric basis of cardinality more than one, as well as additional computability assumptions on the space are required.

References

[1] V. Brattka and G. Presser, Computability on subsets of metric spaces, Theoretical Computer Science 305 (2003), 43–76. https://doi.org/10.1016/S0304-3975(02)00693-X

[2] K. Burnik and Z. Iljazović, Computability of 1-manifolds, Logical Methods in Computer Science 10(2:8) (2014), 1–28. https://doi.org/10.2168/LMCS-10(2:8)2014 (arXiv:1404.6487)

[3] J.S. Miller, Effectiveness for Embedded Spheres and Balls, Electronic Notes in Theoretical Computer Science 66 (2002), 127–138. https://doi.org/10.1016/S1571-0661(04)80384-0

[4] A.R. Shastri, Elements of Differential Topology, CRC Press, Taylor and Francis Group, 2011.