JUCS - Journal of Universal Computer Science 16(18): 2569-2596, doi: 10.3217/jucs-016-18-2569

Isometries and Computability Structures

‡ University of Zagreb, Zagreb, Croatia

Corresponding author: Zvonko Iljazović ( zilj@math.hr ) Citation:
Iljazović Z (2010) Isometries and Computability Structures. JUCS - Journal of Universal Computer Science 16(18): 2569-2596. https://doi.org/10.3217/jucs-016-18-2569 |

Abstract

We investigate the relationship between computable metric spaces (Χ, d, α) and (Χ, d, β), where (Χ, d) is a given metric space. In the case of Euclidean space, α and β are equivalent up to isometry, which does not hold in general. We introduce the notion of effectively dispersed metric space and we use it in the proof of the following result: if (Χ, d, α) is effectively totally bounded, then (Χ, d, β) is also effectively totally bounded. This means that the property that a computable metric space is effectively totally bounded (and in particular effectively compact) depends only on the underlying metric space. In the final section of this paper we examine compact metric spaces (Χ, d) such that there are only finitely many isometries Χ → Χ. We prove that in this case a stronger result holds than the previous one: if (Χ, d, α) is effectively totally bounded, then α and β are equivalent. Hence if (Χ, d, α) is effectively totally bounded, then (Χ, d) has a unique computability structure.

Keywords

computable metric space, computability structure, effective total boundedness, effective dispersion, effective compactness, isometry