JUCS - Journal of Universal Computer Science 15(6): 1206-1235, doi: 10.3217/jucs-015-06-1206

Chainable and Circularly Chainable Co-r.e. Sets in Computable Metric Spaces

‡ University of Zagreb, Zagreb, Croatia

Corresponding author: Zvonko Iljazović ( zilj@math.hr ) Citation:
Iljazović Z (2009) Chainable and Circularly Chainable Co-r.e. Sets in Computable Metric Spaces. JUCS - Journal of Universal Computer Science 15(6): 1206-1235. https://doi.org/10.3217/jucs-015-06-1206 |

Abstract

We investigate under what conditions a co-recursively enumerable set S in a computable metric space (Χ, d, α) is recursive. The topological properties of S play an important role in view of this task. We first study some properties of computable metric spaces such as the effective covering property. Then we examine co-r.e. sets with disconnected complement, and finally we focus on study of chainable and circularly chainable continua which are co-r.e. as subsets of Χ. We prove that, under some assumptions on Χ, each co-r.e. circularly chainable continuum which is not chainable must be recursive. This means, for example, that each co-r.e. set in Rn or in the Hilbert cube which has topological type of the Warsaw circle or the dyadic solenoid must be recursive. We also prove that for each chainable continuum S which is decomposable and each ε > 0 there exists a recursive subcontinuum of S which is ε-close to S.

Keywords

computable metric space, recursive set, co-r.e. set, chainable continuum, circularly chainable continuum, the effective covering property