Computable intersection points

Abstract

In this paper we consider a computable metric space $(X, d, α)$ , a computable continuum K and disjoint computably enumerable open sets U and V in this space such that K intersects both U and V. We examine conditions under which the set $K \cap S$ contains a computable point, where $S = X ∖ (U \cup V)$ . We prove that a sufficient condition for this is that K is an arc. Moreover, we consider the more general case when K is a chainable continuum and prove that $K \cap S$ contains a computable point under the assumption that $K \cap S$ is totally disconnected. We also prove that $K \cap S$ contains a computable point if K is a chainable continuum and S is any co-computably enumerable closed set such that $K \cap S$ has an isolated and decomposable connected component. Related to this, we examine semi-computable chainable continua and we get some results regarding approximations of such continua by computable subcontinua.

Keywords

Computable metric space chainable continuum computable compact set computably enumerable open set computable point

1. Introduction

Let us take a nonnegative computable function $f : [0, 1] \to R$ which has zero-points, but none of them is computable. Such a function exists by [18]. Let $Γ (f)$ be the graph of f, i.e. $Γ (f) = {(x, f (x)) ∣ x \in [0, 1]}$ and let $S = R \times {0}$ . Then $Γ (f)$ and S are computable subsets of $R^{2}$ and since their intersection $Γ (f) \cap S$ consists of the points $(x, 0)$ , where x is a zero-point of f, $Γ (f) \cap S$ is a nonempty set which contains no computable point. Hence $Γ (f)$ and S are computable sets, but $Γ (f) \cap S$ is a nonempty set which contains no computable point, in particular $Γ (f) \cap S$ is not a computable set. Note that the complement of S in $R^{2}$ has two connected components – the upper and the lower open half-plane and $Γ (f)$ does not intersect the lower one.

On the other hand, if $f : [0, 1] \to R$ is a computable function such that $f (0) < 0$ and $f (1) > 0$ , then f has a computable zero-point [17]. Therefore $Γ (f)$ intersects S in a computable point. Note that in this case $Γ (f)$ intersects both components of $R^{2} ∖ S$ .

Suppose K is a connected subset of $R^{2}$ which intersects both components of $R^{2} ∖ S$ . Then K certainly intersects S. In view of the previous facts, the question is, whether the following implication holds: $\begin{matrix} (1) & K computable \Rightarrow K intersects S in a computable point . \end{matrix}$ The following simple example shows that (1) does not hold in general. Let $f : [0, 1] \to R$ be a nonnegative computable function which has zero-points, but none of them is computable. Let $K = Γ (f) \cup Γ (- f)$ . Then K is a connected and computable subset of the plane, it intersects both components of $R^{2} ∖ S$ , but K does not intersect S in a computable point.

Nevertheless, there are possibly some additional assumptions under which (1) holds. In this paper we examine certain conditions under which (1) holds even in a more general context and we get a result which generalizes the case when $K = Γ (f)$ , where $f : [0, 1] \to R$ is a computable function such that $f (0) < 0$ and $f (1) > 0$ .

If $f : [0, 1] \to R$ is a continuous function, then $Γ (f)$ is an arc in $R^{2}$ with endpoints $(0, f (0))$ and $(1, f (1))$ . Suppose K is any computable compact subset of $R^{2}$ which is (topologically) an arc and suppose that the endpoints of K lie in different half-planes determined by $R \times {0}$ . Does K intersect $R \times {0}$ in a computable point?

More generally, let us suppose that K is a continuum chainable from a to b, where a and b lie in different half-planes determined by $R \times {0}$ . That K is a chainable continuum (from a to b) means that K is compact and connected and for each $ε > 0$ there exist finitely many open sets $C_{0}, \dots, C_{m}$ whose diameters are less than ε, which cover K and such that for $i < j$ we have $C_{i} \cap C_{j} \neq \emptyset$ only if $j = i + 1$ (and $a \in C_{0}$ , $b \in C_{m}$ ). The question is whether implication (1) holds, i.e. if K is computable (as a subset of $R^{2}$ ), does it intersect $R \times {0}$ in a computable point?

Furthermore, let us generalize the ambient space. Suppose $(X, d, α)$ is a computable metric space. Let U and V be disjoint and computably enumerable open sets in this space and let $S = X ∖ (U \cup V)$ . Suppose $K \subseteq X$ is a chainable continuum which intersects U and V. Does (1) hold? We will prove that (1) holds under the additional assumption that $K \cap S$ is totally disconnected. This result will imply the following: if A is a computable arc which intersects U and V, then A intersects S in a computable point. The idea how to prove these results is to cover K by $(U, V)$ -chains; these are chains which have the property that for each two adjacent links at least one lies in U or V. The necessity for the assumption of total disconnectedness of $K \cap S$ is closely related to the technique of $(U, V)$ -chains.

We will also examine the case when $K \cap S$ is not totally disconnected. We will prove that (1) holds under the assumption that $K \cap S$ has an isolated and decomposable connected component. In particular, (1) holds if $K \cap S$ is connected and decomposable. Actually, these two results hold without the assumption that K intersects both U and V. In other words, they hold for any co-computably enumerable closed set S.

What is the meaning of the latter two results? Let us suppose that K is an arc. If $K \cap S$ is not totally disconnected, then there is a connected subset of $K \cap S$ having at least two elements and it is easily seen that such a set must have a nonempty interior in the arc K; since computable points are dense in K, that subset contains a computable point, hence $K \cap S$ contains a computable point. However, if K is not an arc, but a general chainable continuum, then a connected subset of K which has at least two elements may have an empty interior in K, as we will see. So in context of chainable continua we have certain phenomena which are not present in the case of arcs and the mentioned results make sense. The assumption in these results that the continuum K is decomposable simply means that K is the union of two proper subcontinua. Since “usual” continua are decomposable, this assumption seems reasonable.

Actually, we will see that if K is a computable chainable continuum and S is a co-c.e. closed set and if $K \cap S$ is connected, then $K \cap S$ is a semi-computable chainable continuum. So the general question will be: what can be said about computable points and computability of semi-computable chainable continua? There are results in [8,9] by which a decomposable semi-computable chainable continuum contains computable points, moreover it can be approximated by a computable subcontinuum with arbitrary precision (in the sense of the Hausdorff metric). Furthermore, there are results in [8,9] which give sufficient conditions that a semi-computable (circularly) chainable continuum is computable. However, all these results were proved under some additional assumptions on the ambient computable metric space $(X, d, α)$ (compact closed balls, effective covering property, local computability). In this paper we will generalize the mentioned results by showing that they hold without any assumption on the ambient space. We will also give some other results about semi-computable chainable continua.

The problem that we study in this paper and which includes the assumption that K intersects both U and V can be viewed in the following way. First, we can note the following simple topological fact, which is a pure consequence of the definition of connectedness: if K is a connected set (in some metric space X) and U and V are open disjoint sets in X such that $K \cap U \neq \emptyset$ and $K \cap V \neq \emptyset$ , then K cannot be contained in $U \cup V$ , hence K intersects $X ∖ (U \cup V)$ . The natural question is: what can be said about the computable version of this topological result, i.e. if K, U and V are (in some sense) computable, does K intersect $X ∖ (U \cup V)$ in a computable point? What we provide in this paper is an answer to this question.

Finally, let us mention that some results regarding the relationship between computable sets, semi-computable sets and computable points can also be found in [6,11–13].

2. Preliminaries

A function $f : N^{k} \to Q$ is said to be computable if there exist computable (i.e. recursive) functions $a, b, c : N^{k + 1} \to N$ such that $\begin{matrix} f (x) = {(- 1)}^{c (x)} \frac{a (x)}{b (x) + 1} \end{matrix}$ for each $x \in N^{k}$ . A function $f : N^{k} \to R$ is said to be computable if there exists a computable function $F : N^{k + 1} \to Q$ such that $\begin{matrix} | f (x) - F (x, i) | < 2^{- i} \end{matrix}$ for all $x \in N^{k}$ and $i \in N$ .

In the following proposition we state some basic facts about computable functions of type $N^{k} \to R$ .

Proposition 2.1.

If $f, g : N^{k} \to R$ are computable functions, then $f + g$ and $f - g$ are computable.

If $f, g : N^{k} \to R$ are computable functions, then the set ${x \in N^{k} ∣ f (x) > g (x)}$ is c.e.

A tuple $(X, d, α)$ is said to be a computable metric space if $(X, d)$ is a metric space and $α : N \to X$ is a sequence whose range is dense in $(X, d)$ such that the function $N^{2} \to R$ , $\begin{matrix} (i, j) \mapsto d (α_{i}, α_{j}) \end{matrix}$ is computable (we use the notation $α = (α_{i})$ ).

If $(X, d, α)$ is a computable metric space, then a point $a \in X$ is said to be computable in $(X, d, α)$ if there exists a computable function $f : N \to N$ such that $d (a, α_{f (k)}) < 2^{- k}$ for each $k \in N$ .

Furthermore, we say that a sequence ${(x_{i})}_{i \in N}$ in X is computable in $(X, d, α)$ if there exists a computable function $f : N^{2} \to N$ such that $d (x_{i}, α_{f (i, k)}) < 2^{- k}$ for all $i, k \in N$ .

If $(X, d, α)$ is a computable metric space, $i \in N$ and $q \in Q$ , $q > 0$ , then we say that $B (α_{i}, q)$ is a rational ball in this space. Here, for $x \in X$ and $r > 0$ , we denote by $B (x, r)$ the open ball of radius r centered at x, i.e. $B (x, r) = {y \in X ∣ d (x, y) < r}$ . By $\overline{B} (x, r)$ (for $x \in X$ and $r ⩾ 0$ ) we will denote the corresponding closed ball ${y \in X ∣ d (x, y) ⩽ r}$ .

Let $q : N \to Q$ be some fixed computable function whose image is the set of all positive rational numbers and let $τ_{1}, τ_{2} : N \to N$ be some fixed computable functions such that ${(τ_{1} (i), τ_{2} (i)) ∣ i \in N} = N^{2}$ .

Suppose $(X, d, α)$ is a computable metric space. Let ${(λ_{i})}_{i \in N}$ be the sequence of points in X defined by $λ_{i} = α_{τ_{1} (i)}$ and let ${(ρ_{i})}_{i \in N}$ be the sequence of rational numbers defined by $ρ_{i} = q_{τ_{2} (i)}$ . For $i \in N$ we define $\begin{matrix} I_{i} = B (λ_{i}, ρ_{i}) . \end{matrix}$ Note that $I_{i}$ , $i \in N$ , are rational balls in $(X, d, α)$ . Hence the sequence ${(I_{i})}_{i \in N}$ represents an effective enumeration of all rational balls.

If $(X, d, α)$ is a computable metric space and $B_{1}, \dots, B_{n}$ , $n ⩾ 1$ , rational balls in this space, then the union $B_{1} \cup \dots \cup B_{n}$ will be called a rational open set.

Let $σ : N^{2} \to N$ and $η : N \to N$ be some fixed computable functions with the following property: each finite nonempty sequence in $N$ is equal to $(σ (j, 0), \dots, σ (j, η (j)))$ for some $j \in N$ . We use the following notation: ${(j)}_{i}$ instead of $σ (j, i)$ and $\overline{j}$ instead of $η (j)$ . Hence $\begin{matrix} {({(j)}_{0}, \dots, {(j)}_{\overline{j}}) ∣ j \in N} \end{matrix}$ is the set of all finite nonempty sequences in $N$ . For $j \in N$ let $\begin{matrix} (2) & [j] = {{(j)}_{i} ∣ 0 ⩽ i ⩽ \overline{j}} . \end{matrix}$ Then each finite nonempty subset of $N$ is equal to $[j]$ for some $j \in N$ .

Suppose $(X, d, α)$ is a computable metric space. For $j \in N$ we define $\begin{matrix} J_{j} = ⋃_{i \in [j]} I_{i} . \end{matrix}$ Then $(J_{j})$ is an effective enumeration of all rational open sets in $(X, d, α)$ .

For $a, b \in R \cup {- \infty, \infty}$ we will denote by $⟨ a, b ⟩$ the open interval determined by a and b, hence $⟨ a, b ⟩ = {x \in R ∣ a < x < b}$ .

Let $(X, d)$ be a metric space, let $n \in N$ and $x_{0}, \dots, x_{n} \in X$ , $r_{0}, \dots, r_{n} \in ⟨ 0, \infty ⟩$ . Let $\begin{matrix} D = max_{0 ⩽ i, j ⩽ n} d (x_{i}, x_{j}) + 2 max_{0 ⩽ i ⩽ n} r_{i} . \end{matrix}$ We say that the number D is a formal diameter associated to the finite sequence $(x_{0}, r_{0}), \dots, (x_{n}, r_{n})$ . Note the following: $\begin{matrix} diam (B (x_{0}, r_{0}) \cup \dots \cup B (x_{n}, r_{n})) ⩽ D . \end{matrix}$ Let $(X, d, α)$ be a computable metric space. We define a function $fdiam : N \to R$ such that for $j \in N$ the number $fdiam (j)$ is the formal diameter of the finite sequence: $\begin{matrix} (λ_{{(j)}_{0}}, ρ_{{(j)}_{0}}), \dots, (λ_{{(j)}_{\overline{j}}}, ρ_{{(j)}_{\overline{j}}}) . \end{matrix}$ Note that $diam (J_{j}) ⩽ fdiam (j)$ . It is not hard to prove the following proposition (see Proposition 13 in [8]).
Proposition 2.2.
The function $fdiam : N \to R$ is computable.

Suppose $(X, d, α)$ is a computable metric space. We define a function $fmesh : N \to R$ by $\begin{array}{l} fmesh (l) = max_{0 ⩽ p ⩽ \overline{l}} fdiam ({(l)}_{p}) . \end{array}$ It is easy to conclude that fmesh is a computable function (see [8]).

Let $(X, d, α)$ be a computable metric space and let S be a closed set in $(X, d)$ . We say that S is a computably enumerable (c.e.) closed set in $(X, d, α)$ if $\begin{matrix} {i \in N ∣ I_{i} \cap S \neq \emptyset} \end{matrix}$ is a c.e. subset of $N$ . Hence, we may say that S is c.e. closed if we can effectively enumerate all rational balls which intersect S.

A compact subset S of $(X, d)$ is said to be semi-computable in $(X, d, α)$ if the set $\begin{matrix} {j \in N ∣ S \subseteq J_{j}} \end{matrix}$ is c.e. Hence S is semi-computable if we can effectively enumerate all rational open sets which contain S.

We say that S is a computable set in $(X, d, α)$ if S is both c.e. closed and semi-computable in $(X, d, α)$ [2,19].

If $(X, d)$ is a metric space, $A, B \subseteq X$ and $ε > 0$ , we write $A \approx_{ε} B$ if for each $x \in A$ there exists $y \in B$ such that $d (x, y) < ε$ and for each $y \in B$ there exists $x \in A$ such that $d (y, x) < ε$ . If $H$ is the set of all nonempty compact subsets of $(X, d)$ , then the Hausdorff metric on $H$ is the metric ϱ on $H$ defined by $\begin{matrix} ϱ (A, B) = inf {ε > 0 ∣ A \approx_{ε} B} . \end{matrix}$

A nonempty compact set S in a computable metric space $(X, d, α)$ is computable if and only if for each $k \in N$ we can effectively find finitely many points $α_{i_{0}}, \dots, α_{i_{k}}$ which approximate S up to $2^{- k}$ in the sense of the Hausdorff metric, i.e. such that $ρ (S, {α_{i_{0}}, \dots, α_{i_{k}}}) < 2^{- k}$ . More precisely, for each $i \in N$ we can define $Λ_{i} = {α_{{(i)}_{0}}, \dots, α_{(i) \overline{i}}}$ and we have the following result [10].
Proposition 2.3.
Let $(X, d, α)$ be a computable metric space and let S be a nonempty compact set in $(X, d)$ . Then S is computable in $(X, d, α)$ if and only if there exists a computable function $f : N \to N$ such that $\begin{matrix} ρ (S, Λ_{f (k)}) < 2^{- k} \end{matrix}$ for each $k \in N$ .

Let $(X, d, α)$ be a computable metric space and let U be an open set in $(X, d)$ . We say that U is computably enumerable open set in $(X, d, α)$ if $\begin{matrix} U = ⋃_{i \in A} I_{i}, \end{matrix}$ where A is a c.e. subset of $N$ . Hence U is c.e. open if it can be effectively exhausted by rational balls.

If X is a set, let $P (X)$ denote the set of all subsets of X.

For $m \in N$ let $N_{m} = {0, \dots, m}$ . For $n ⩾ 1$ let $\begin{matrix} N_{m}^{n} = {(x_{1}, \dots, x_{n}) ∣ x_{1}, \dots, x_{n} \in N_{m}} . \end{matrix}$

We say that a function $Φ : N^{k} \to P (N^{n})$ is effectively finitely valued or e.f.v. if the function $\overline{Φ} : N^{k + n} \to N$ defined by $\begin{matrix} \overline{Φ} (x, y) = χ_{Φ (x)} (y), x \in N^{k}, y \in N^{n}, \end{matrix}$ is computable (where $χ_{S} : N^{n} \to N$ denotes the characteristic function of $S \subseteq N^{n}$ ) and if there exists a computable function $φ : N^{k} \to N$ such that $\begin{matrix} Φ (x) \subseteq N_{φ (x)}^{n}, \forall x \in N^{k} . \end{matrix}$ In the following proposition we state some elementary facts about e.f.v. functions.
Proposition 2.4.

Let $Φ : N^{k} \to P (N^{n})$ and $Ψ : N^{n} \to P (N^{m})$ be e.f.v. functions. Let $Λ : N^{k} \to P (N^{m})$ be defined by: $\begin{matrix} Λ (x) = ⋃_{z \in Φ (x)} Ψ (z), \forall x \in N^{k} . \end{matrix}$ Then Λ is an e.f.v. function.

Let $Φ : N^{k} \to P (N^{n})$ be e.f.v. and let $T \subseteq N^{n}$ be c.e. Then the set $S = {x \in N^{k} ∣ Φ (x) \subseteq T}$ is c.e.

If $Φ, Ψ : N^{k} \to P (N^{n})$ are e.f.v. functions, then the sets ${x \in N^{k} ∣ Φ (x) = Ψ (x)}$ and ${x \in N^{k} ∣ Φ (x) \subseteq Ψ (x)}$ are computable.

We will also use the following basic facts about computable functions $N^{k} \to N$ . Proposition 2.5.

(Projection theorem) Let $T \subseteq N^{k + n}$ be a computably enumerable set. Then the set $S = {x \in N^{k} ∣ \exists y \in N^{n} (x, y) \in T}$ is computably enumerable.

(Single-valuedness theorem) If $T \subseteq N^{k + n}$ , $S_{1} \subseteq N^{k}$ and $S_{2} \subseteq N^{n}$ are c.e. sets such that for each $x \in S_{1}$ there exists $y \in S_{2}$ such that $(x, y) \in T$ , then there exists a partial computable (partial recursive) function $f : S_{1} \to N^{n}$ such that $f (S_{1}) \subseteq S_{2}$ and $(x, f (x)) \in T$ for each $x \in S_{1}$ .

If $S \subseteq N^{n}$ is a c.e. set and $f : N^{k} \to N^{n}$ is a computable function, then the set $f^{- 1} (S)$ is c.e.

3. Zero-dimensionality and $(U, V)$ -chains

A finite sequence $C_{0}, \dots, C_{m}$ of nonempty subsets of some set X is said to be a chain in X if for all $i, j \in {0, \dots, m}$ $\begin{matrix} | i - j | > 1 ⟹ C_{i} \cap C_{j} = \emptyset . \end{matrix}$ We say that $C_{i}$ ( $0 ⩽ i ⩽ m$ ) is a link of the chain $C_{0}, \dots, C_{m}$ .

A chain $C_{0}, \dots, C_{m}$ is said to be a simple chain if $C_{i} \cap C_{i + 1} \neq \emptyset$ for each $i \in {0, \dots, m - 1}$ ([5]).

If $A = (A_{0}, \dots, A_{m})$ is a finite sequence of nonempty bounded subsets of some metric space $(X, d)$ , we define $\begin{matrix} mesh (A) = max_{0 ⩽ i ⩽ m} diam (A_{i}) . \end{matrix}$

If ε is a positive real number and $C$ is a chain in a metric space $(X, d)$ , we say that $C$ is an ε-chain if $mesh (C) < ε$ .

A (simple) chain in some metric space $(X, d)$ is said to be an open (simple) chain in $(X, d)$ if each of its links is an open set in $(X, d)$ . The notion of a compact (simple) chain in $(X, d)$ is defined in an analogous way.

Suppose X is a set, $S \subseteq X$ and $C = (C_{0}, \dots, C_{m})$ a finite sequence of subsets of X. We say that $C$ covers S if $S \subseteq C_{0} \cup \dots \cup C_{m}$ . Furthermore, we say that $C$ properly covers S if $C$ covers S and $C_{0} \cap S \neq \emptyset$ , $C_{m} \cap S \neq \emptyset$ . If $a, b \in X$ , we say that $C$ covers S from a to b if $C$ covers S and $a \in C_{0}$ , $b \in C_{m}$ .

Let $(X, d)$ be a continuum (i.e. compact and connected metric space). We say that $(X, d)$ is a chainable continuum if for each $ϵ > 0$ there exists an open simple ϵ-chain $C_{0}, \dots, C_{m}$ in $(X, d)$ which covers X. If $a, b \in X$ , we say that $(X, d)$ is a continuum chainable from a to b if for each $ϵ > 0$ there exists an open simple ϵ-chain $C_{0}, \dots, C_{m}$ in $(X, d)$ which covers X from a to b (see [5,16]).

Lemma 3.1.
Let $(X, d)$ be a metric space, $k \in N$ and $ϵ > 0$ . Let $D_{0}, \dots, D_{k}$ be nonempty compact sets in $(X, d)$ such that $diam (D_{i}) < \frac{ϵ}{2}$ for each $i \in {0, \dots, k}$ . Then there exist open sets $C_{0}, \dots, C_{k}$ with the following properties: $\begin{array}{l} diam (C_{i}) < ϵ and D_{i} \subseteq C_{i} for each i \in {0, \dots, k}; \\ C_{i} \cap C_{j} = \emptyset for all i, j \in {0, \dots, n} such that D_{i} \cap D_{j} = \emptyset . \end{array}$
Proof.
If $D_{i} \cap D_{j} \neq \emptyset$ for all $i, j \in {0, \dots, n}$ , let $μ = 1$ , otherwise let $\begin{matrix} μ = min {d (D_{i}, D_{j}) ∣ i, j \in {0, \dots, k}, D_{i} \cap D_{j} = \emptyset} . \end{matrix}$ Because the sets $D_{0}, \dots, D_{k}$ are compact we have that $μ > 0$ . Now we define $\begin{matrix} λ = min {μ, \frac{ϵ}{4}} . \end{matrix}$ For $i \in {0, \dots, k}$ let $\begin{matrix} C_{i} = ⋃_{x \in D_{i}} B (x, \frac{λ}{2}) . \end{matrix}$ For each $i \in {0, \dots, k}$ the set $C_{i}$ is clearly open.

Suppose $i, j \in {0, \dots, m}$ are such that $D_{i} \cap D_{j} = \emptyset$ . Then $C_{i} \cap C_{j} = \emptyset$ . Indeed, if there exists some $x \in C_{i} \cap C_{j}$ , then there exist $a \in D_{i}$ and $b \in D_{j}$ such that $x \in B (a, \frac{λ}{2})$ and $x \in B (b, \frac{λ}{2})$ and therefore $\begin{array}{l} λ ⩽ μ ⩽ d (a, b) ⩽ d (a, x) + d (x, b) < \frac{λ}{2} + \frac{λ}{2} = λ, \end{array}$ a contradiction.

Furthermore, $diam (C_{i}) < ϵ$ for each $i \in {0, \dots, k}$ . Indeed, if $x, y \in C_{i}$ , then there exist $a, b \in D_{i}$ such that $x \in B (a, \frac{λ}{2})$ and $y \in B (b, \frac{λ}{2})$ and $\begin{array}{l} d (x, y) ⩽ d (x, a) + d (a, b) + d (b, y) < \frac{λ}{2} + diam (D_{i}) + \frac{λ}{2} = λ + diam (D_{i}) ⩽ \frac{ϵ}{4} + \frac{ϵ}{2} = \frac{3 ϵ}{4} . \end{array}$ So $\begin{matrix} diam (C_{i}) ⩽ \frac{3 ϵ}{4} < ϵ . \end{matrix}$

It is obvious that $D_{i} \subseteq C_{i}$ for each $i \in {0, \dots, k}$ . □
Proposition 3.2.
Let $(X, d)$ be a continuum and $a, b \in X$ . Then the following statements are equivalent:
$(X, d)$ is chainable from a to b;

for each $ϵ > 0$ there exists an open ϵ-chain $C_{0}, \dots, C_{m}$ in $(X, d)$ which covers X from a to b;

for each $ϵ > 0$ there exists a compact ϵ-chain $K_{0}, \dots, K_{m}$ in $(X, d)$ which covers X from a to b.

Proof.
It is obvious that (i) implies (ii). Conversely, if $ε > 0$ and $C_{0}, \dots, C_{m}$ is an open ε-chain in $(X, d)$ which covers X from a to b, then $C_{0}, \dots, C_{m}$ is a simple chain: if $i \in {0, \dots, m - 1}$ is such that $C_{i} \cap C_{i + 1} = \emptyset$ , then $(C_{0} \cup \dots \cup C_{i}, C_{i + 1} \cup \dots \cup C_{m})$ is a separation of $(X, d)$ which contradicts the fact that $(X, d)$ is connected. Hence (ii) implies (i).

Suppose that (iii) holds. Let $ε > 0$ . Then there exists a compact $\frac{ε}{2}$ -chain $D_{0}, \dots, D_{k}$ in $(X, d)$ which covers X from a to b. Let $C_{0}, \dots, C_{k}$ be as in Lemma 3.1. Then $C_{0}, \dots, C_{m}$ is an open ε-chain in $(X, d)$ which covers X from a to b. Hence (ii) holds.

Suppose that (ii) holds. Let $ε > 0$ . Then there exists an open ε-chain $C_{0}, \dots, C_{m}$ in $(X, d)$ which covers X from a to b. Then ${C_{0}, \dots, C_{m}}$ is an open cover of $(X, d)$ and since $(X, d)$ is compact, there exists $λ > 0$ such that λ is a Lebesgue number for this open cover. Compactness of $(X, d)$ implies that there exist finitely many points $x_{0}, \dots, x_{N} \in X$ such that $\begin{matrix} X = B (x_{0}, \frac{λ}{3}) \cup \dots \cup B (x_{N}, \frac{λ}{3}) . \end{matrix}$ Let $\begin{matrix} D = {\overline{B} (x_{0}, \frac{λ}{3}), \dots, \overline{B} (x_{N}, \frac{λ}{3})} . \end{matrix}$ Then $D$ is a finite family of sets which are compact and whose diameters are less than λ. Consequently, each member of $D$ is contained in some of the sets $C_{0}, \dots, C_{m}$ .

For $i \in {0, \dots, m}$ let $K_{i}$ be the union of those members of $D$ which are contained in $C_{i}$ . Then $\begin{matrix} K_{0} \cup {a}, K_{1}, \dots, K_{m - 1}, K_{m} \cup {b} \end{matrix}$ is a compact ε-chain in $(X, d)$ which covers X from a to b. Hence (iii) holds. □

In the same way we prove the following proposition.
Proposition 3.3.
Let $(X, d)$ be a continuum. Then the following statements are equivalent:
$(X, d)$ is chainable;

for each $ϵ > 0$ there exists an open ϵ-chain $C_{0}, \dots, C_{m}$ in $(X, d)$ which covers X;

for each $ϵ > 0$ there exists a compact ϵ-chain $K_{0}, \dots, K_{m}$ in $(X, d)$ which covers X.

Let X be a set and let $U, V$ , $C_{0}, \dots, C_{m}$ be subsets of X. We say that the finite sequence $C_{0}, \dots, C_{m}$ is a $(U, V)$ -sequence if for each $i \in {0, \dots, m - 1}$ $\begin{array}{l} (3) & C_{i} \subseteq U or C_{i} \subseteq V or C_{i + 1} \subseteq U or C_{i + 1} \subseteq V . \end{array}$ Furthermore, if this holds and if $C_{0}, \dots, C_{m}$ is a (simple) chain, we will say that $C_{0}, \dots, C_{m}$ is a (simple) $(U, V)$ -chain.

Suppose $(X, d)$ is a metric space and U and V are disjoint open sets in this space. Let $K \subseteq X$ be a continuum chainable from a to b, where $a \in U$ and $b \in V$ . The question is: under what conditions for each $ε > 0$ there exists a compact/open $(U, V)$ -ε-chain in $(X, d)$ which covers K? We will give an answer to this question, but first we need the notion of topological dimension.

Let $A$ be a family of sets and $n \in N ∖ {0}$ . We say that $A$ has order n if there exist distinct elements $A_{1}, \dots, A_{n}$ of $A$ such that $A_{1} \cap \dots \cap A_{n} \neq \emptyset$ and there exist no distinct elements $A_{1}, \dots, A_{n + 1}$ of $A$ such that $A_{1} \cap \dots \cap A_{n + 1} \neq \emptyset$ .

Suppose $A$ and $B$ are families of sets. We say that $B$ refines $A$ if for each $B \in B$ there exists $A \in A$ such that $B \subseteq A$ .

Let X be a topological space. Let S be the set of all $n \in N$ with the following property: for each open cover $U$ of X there exists an open cover $V$ of X which refines $U$ and has order at most $n + 1$ . If $S \neq \emptyset$ , then the smallest element of S is called the topological dimension of X [15].

Note the following: a family of sets $A$ has order 1 if and only if $A$ contains a nonempty element and every two distinct element of $A$ are disjoint. Therefore, a nonempty topological space X has topological dimension 0 if and only if for each open cover $U$ of X there exists an open cover $V$ of X which refines $U$ and whose distinct elements are disjoint.

Of course, a metric space $(X, d)$ is said to have topological dimension n if $(X, T_{d})$ has topological dimension n, where $T_{d}$ is topology induced by d.

A metric (or topological) space is said to be zero-dimensional if it has topological dimension 0.
Proposition 3.4.
Let $(X, d)$ be a compact metric space. Then $(X, d)$ is zero-dimensional if and only if for each $ε > 0$ there exist finitely many mutually disjoint open sets $D_{0}, \dots, D_{k}$ in $(X, d)$ such that $diam D_{i} < ε$ for each $i \in {0, \dots, k}$ and $X = D_{0} \cup \dots \cup D_{k}$ .
Proof.
Suppose $(X, d)$ is zero-dimensional. Let $ε > 0$ . Let $\begin{matrix} U = {B (x, \frac{ε}{3}) | x \in X} . \end{matrix}$ Then $U$ is an open cover of $(X, d)$ and therefore there exists an open cover $V$ of $(X, d)$ which refines $U$ and whose distinct elements are disjoint. Compactness of $(X, d)$ implies that there exist finitely many elements $D_{0}, \dots, D_{k}$ of $V$ such that $\begin{matrix} X = D_{0} \cup \dots \cup D_{k} . \end{matrix}$ Clearly, we may assume that the sets $D_{0}, \dots, D_{k}$ are mutually distinct and nonempty. Therefore, these sets are mutually disjoint. If $i \in {0, \dots, k}$ , then $D_{i} \subseteq B (x, \frac{ε}{3})$ for some $x \in X$ and consequently $diam D_{i} ⩽ 2 \frac{ε}{3} < ε$ .

Conversely, suppose that for each $ε > 0$ there exist finitely many mutually disjoint open sets $D_{0}, \dots, D_{k}$ in $(X, d)$ which cover X and whose diameters are less than ε. Let $U$ be an open cover of $(X, d)$ . Since $(X, d)$ is compact, there exists a Lebesgue number λ for $U$ . Let $D_{0}, \dots, D_{k}$ be mutually disjoint open sets which cover X and whose diameters are less than λ. Then ${D_{0}, \dots, D_{k}}$ is an open cover of $(X, d)$ which refines $U$ . Hence $(X, d)$ is zero-dimensional. □

Suppose $(X, d)$ is a metric space and $K \subseteq X$ a continuum chainable from $a \in U$ to $b \in V$ , where U and V are disjoint open sets in $(X, d)$ . Let $S = X ∖ (U \cup V)$ . Suppose $D_{0}, \dots, D_{m}$ is a compact $(U, V)$ -chain in $(X, d)$ which covers K. Let $i_{0} < \dots < i_{k}$ be all $i \in {0, \dots, m}$ such that $D_{i} \cap (K \cap S) \neq \emptyset$ . Then the sets $D_{i_{0}}, \dots, D_{i_{k}}$ are mutually disjoint and cover $K \cap S$ . From this, Lemma 3.1 and Proposition 3.4 we conclude the following: if for each $ε > 0$ there exists a compact $(U, V)$ -ε-chain in $(X, d)$ which covers K, then $K \cap S$ is zero-dimensional.

Now we show that the converse of the latter statement is also true.
Proposition 3.5.
Let $(X, d)$ be a metric space, U and V open and disjoint sets in $(X, d)$ and let $\begin{matrix} S = X ∖ (U \cup V) . \end{matrix}$ Let $K \subseteq X$ . Suppose K, as a subspace of $(X, d)$ , is a continuum chainable from a to b, where $a \in U$ and $b \in V$ . Then $S \cap K$ is zero-dimensional (as a subspace of $(X, d)$ ) if and only if for each $ϵ > 0$ there exists a compact $(U, V)$ -ϵ-chain $C_{0}, \dots, C_{n}$ which covers K from a to b, such that $C_{0} \subseteq U$ and $C_{n} \subseteq V$ and such that $C_{0} \subseteq K$ , …, $C_{n} \subseteq K$ (note that such a chain must be simple).
Proof.
Suppose $K \cap S$ is zero-dimensional. Let $ϵ > 0$ . Let us define $\begin{matrix} μ = min {d (a, S), d (b, S)}, \end{matrix}$ where $d (x, S) = inf {d (x, s) ∣ s \in S}$ for $x \in X$ . By Proposition 3.4 there exist finitely many nonempty mutually disjoint open sets $D_{0}, \dots, D_{k}$ in $S \cap K$ such that $\begin{matrix} diam (D_{i}) < \frac{min {ϵ, μ}}{2} \end{matrix}$ for each $i \in {0, \dots, k}$ and such that $\begin{matrix} S \cap K = D_{0} \cup \dots \cup D_{k} . \end{matrix}$ Note that the sets $D_{0}, \dots, D_{k}$ are also closed in $S \cap K$ . Because $S \cap K$ is closed in X and contained in K, we have that $S \cap K$ is compact and it follows that $D_{0}, \dots, D_{k}$ are compact.

By Lemma 3.1 there exist open, mutually disjoint sets ${\tilde{D}}_{0}, \dots, {\tilde{D}}_{k}$ such that $diam ({\tilde{D}}_{i}) < min {ϵ, μ}$ and $D_{i} \subseteq {\tilde{D}}_{i}$ for each $i \in {0, \dots, k}$ . Let $\begin{matrix} U = {{\tilde{D}}_{0}, \dots, {\tilde{D}}_{k}, U, V} . \end{matrix}$

Then $U$ is an open cover of K. Because K is compact, there exist $λ > 0$ such that λ is a Lebesgue number of $U$ for K, i.e. such that every nonempty subset of K whose diameter is less than λ is contained in some member of $U$ .

Because K is a continuum chainable from a to b, there exist compact $min {ϵ, λ}$ -chain $F_{0}, \dots, F_{m}$ in K such that $a \in F_{0}$ , $b \in F_{m}$ and $K \subseteq F_{0} \cup \dots \cup F_{m}$ . For each $i \in {0, \dots, m}$ we have $diam (F_{i}) < λ$ and therefore $\begin{matrix} F_{i} \subseteq U or F_{i} \subseteq V or F_{i} \subseteq {\tilde{D}}_{j} for some j \in {0, \dots, k} . \end{matrix}$

Note that $F_{0} \subseteq U$ . Indeed, otherwise we have $F_{0} \subseteq V$ , or $F_{0} \subseteq {\tilde{D}}_{j}$ for some $j \in {1, \dots, k}$ . If $F_{0} \subseteq V$ , then $a \in V$ because $a \in F_{0}$ and this implies $U \cap V \neq \emptyset$ , which is impossible. If $F_{0} \subseteq {\tilde{D}}_{j}$ for some $j \in {1, \dots, k}$ , then $a \in {\tilde{D}}_{j}$ and if we pick some $x \in D_{j}$ , then $x \in S$ and $\begin{matrix} d (a, S) ⩽ d (a, x) ⩽ diam ({\tilde{D}}_{j}) < min {ϵ, μ} ⩽ μ ⩽ d (a, S), \end{matrix}$ a contradiction.

Similarly we can see that b does not lie in any ${\tilde{D}}_{j}$ . So $F_{m} \subseteq V$ .

Let $i \in {0, \dots, m - 1}$ . Then $F_{i} \cap F_{i + 1} \neq \emptyset$ . Otherwise, the sets $F_{0} \cup \dots \cup F_{i}$ and $F_{i + 1} \cup \dots \cup F_{m}$ are disjoint closed sets which cover K and this is impossible because K is connected.

We claim that there exist $p \in N ∖ {0}$ and numbers $i_{1}, \dots, i_{p}$ and $j_{1}, \dots, j_{p}$ such that the following holds:
$0 ⩽ i_{1} < j_{1} < i_{2} < j_{2} < \dots < i_{p} < j_{p} < m$ ;

all links among $F_{0}, \dots, F_{m}$ with indices $0, \dots, i_{1}$ are contained in U;

all links among $F_{0}, \dots, F_{m}$ with indices $j_{p} + 1, \dots, m$ are contained in V;

for each $v \in {1, \dots, p}$ the links with indices $i_{v} + 1, \dots, j_{v}$ are all contained in some ${\tilde{D}}_{j}$ ( $j \in {1, \dots, k}$ );

for each $v \in {1, \dots, p - 1}$ the links with indices $j_{v} + 1, \dots, i_{v + 1}$ are all contained in U or all contained in V.

Let $\begin{matrix} l = min {i \in {0, \dots, m} ∣ F_{i} ⊈ U} . \end{matrix}$ Note that $l ⩾ 1$ , $F_{l - 1} \subseteq U$ and $F_{l} ⊈ U$ . It follows $F_{l} \subseteq V$ or $F_{l} \subseteq {\tilde{D}}_{j}$ for some $j \in {1, \dots, k}$ . Note that $F_{l} ⊈ V$ because $F_{l} \subseteq V$ , together with $F_{l - 1} \subseteq U$ , implies $U \cap V \neq \emptyset$ . Hence $F_{l} \subseteq {\tilde{D}}_{j}$ for some $j \in {1, \dots, k}$ .

Since $b \in F_{m}$ and $b \notin {\tilde{D}}_{j}$ , we have $l < m$ .

Let $\begin{matrix} l^{'} = min {i \in {l + 1, \dots, m} ∣ F_{i} ⊈ {\tilde{D}}_{j}} . \end{matrix}$ Then each of the sets $F_{l}, F_{l + 1}, \dots, F_{l^{'} - 1}$ is a subset of ${\tilde{D}}_{j}$ , but $F_{l^{'}} ⊈ {\tilde{D}}_{j}$ .

Suppose $F_{l^{'}} \subseteq {\tilde{D}}_{j^{'}}$ for some $j^{'} \in {1, \dots, k}$ , $j^{'} \neq j$ . Since ${\tilde{D}}_{j} \cap {\tilde{D}}_{j^{'}} = \emptyset$ we have $F_{l^{'} - 1} \cap F_{l^{'}} = \emptyset$ , which is impossible. Hence $F_{l^{'}} \subseteq U$ or $F_{l^{'}} \subseteq V$ .

Let $\begin{matrix} i_{1} = l - 1, j_{1} = l^{'} - 1 . \end{matrix}$ Then $0 ⩽ i_{1} < j_{1} < m$ and we have $\begin{matrix} F_{0}, \dots, F_{i_{1}} \subseteq U, F_{i_{1} + 1}, \dots, F_{j_{1}} \subseteq {\tilde{D}}_{j} and F_{j_{1} + 1} \subseteq U or F_{j_{1} + 1} \subseteq V . \end{matrix}$ If $F_{i} \subseteq V$ for each $i \in {j_{1} + 1, \dots, m}$ , then we take $p = 1$ and the numbers $i_{1}$ and $j_{1}$ satisfy relations (1)–(5).

Otherwise there exists $i \in {j_{1} + 1, \dots, m}$ such that $F_{i} ⊈ V$ . We have two cases. Case 1.
$F_{j_{1} + 1} \subseteq V$ .

Let $\begin{matrix} l = min {i \in {j_{1} + 1, \dots, m} ∣ F_{i} ⊈ V} . \end{matrix}$ Then $F_{j_{1} + 1}, \dots, F_{l - 1}$ are all contained in V and $F_{l} ⊈ V$ . As before we conclude that $F_{l} ⊈ U$ , so $F_{l} \subseteq {\tilde{D}}_{j^{'}}$ for some $j^{'} \in {1, \dots, k}$ . Let $\begin{matrix} l^{'} = min {i \in {l, \dots, m} ∣ F_{i} ⊈ {\tilde{D}}_{j^{'}}} . \end{matrix}$ As before we conclude that $F_{l^{'}} \subseteq U$ or $F_{l^{'}} \subseteq V$ . Now let $\begin{matrix} i_{2} = l - 1, j_{2} = l^{'} - 1 . \end{matrix}$ The following holds: $\begin{matrix} F_{0}, \dots, F_{i_{1}} \subseteq U, F_{i_{1} + 1}, \dots, F_{j_{1}} \subseteq {\tilde{D}}_{j}, F_{j_{1} + 1}, \dots, F_{i_{2}} \subseteq V, F_{i_{2} + 1}, \dots, F_{j_{2}} \subseteq {\tilde{D}}_{j^{'}}, \end{matrix}$ and $\begin{matrix} F_{j_{2} + 1} \subseteq U or F_{j_{2} + 1} \subseteq V . \end{matrix}$
Case 2.
$F_{j_{1} + 1} \subseteq U$ .

In the same way we get numbers $i_{2}$ , $j_{2}$ such that $j_{1} < i_{2} < j_{2} < m$ , $\begin{matrix} F_{0}, \dots, F_{i_{1}} \subseteq U, F_{i_{1} + 1}, \dots, F_{j_{1}} \subseteq {\tilde{D}}_{j}, F_{j_{1} + 1}, \dots, F_{i_{2}} \subseteq U, F_{i_{2} + 1}, \dots, F_{j_{2}} \subseteq {\tilde{D}}_{j^{'}} \end{matrix}$ and $\begin{matrix} F_{j_{2} + 1} \subseteq U or F_{j_{2} + 1} \subseteq V . \end{matrix}$

If $F_{i} \subseteq V$ for each $i \in {j_{2} + 1, \dots, m}$ then we take $p = 2$ and the numbers $j_{1} < i_{2} < j_{2} < m$ satisfy relations (1)–(5).

Otherwise we repeat the procedure and get numbers $i_{3}$ and $j_{3}$ such that $j_{2} < i_{3} < j_{3} < m$ and such that the links with indices $j_{2} + 1, \dots, i_{3}$ are all contained in U or all contained in V and links with indices $i_{3} + 1, \dots, j_{3}$ are all contained in some ${\tilde{D}}_{j}$ ( $j \in {1, \dots, k}$ ), and the link $F_{j_{3} + 1}$ is contained in U or is contained in V.

It is clear that in finitely many steps we get the required numbers $p \in N ∖ {0}$ , $i_{1}, \dots, i_{p}$ and $j_{1}, \dots, j_{p}$ such that (1)–(5) hold.

Consider now the following sequence of sets: $\begin{array}{l} F_{0}, \dots, F_{i_{1}}, F_{i_{1} + 1} \cup \dots \cup F_{j_{1}}, F_{j_{1} + 1}, \dots, F_{i_{2}}, \dots, F_{i_{v} + 1} \cup \dots \cup F_{j_{v}}, \\ (4) & F_{j_{v} + 1}, \dots, F_{i_{v + 1}}, \dots, F_{i_{p} + 1} \cup \dots \cup F_{j_{p}}, F_{j_{p} + 1}, \dots, F_{m} . \end{array}$ For each $v \in {1, \dots, p}$ the union $F_{i_{v} + 1} \cup \dots \cup F_{j_{v}}$ is a subset of ${\tilde{D}}_{j}$ for some $j \in {1, \dots, k}$ and so $diam ({\tilde{D}}_{j}) < ϵ$ implies $\begin{matrix} diam (F_{i_{v} + 1} \cup \dots \cup F_{j_{v}}) < ϵ . \end{matrix}$

We conclude that by (4) a compact $(U, V)$ -ϵ-chain from a to b is given, which covers K. □
Corollary 3.6.
Let $(X, d)$ be a metric space, U and V open disjoint sets in X and let $S = X ∖ (U \cup V)$ . Suppose $K \subseteq X$ is a continuum chainable from a to b, where $a \in U$ and $b \in V$ . Then $S \cap K$ is zero-dimensional if and only if for each $ϵ > 0$ there exists an open $(U, V)$ -ϵ-chain $C_{0}, \dots, C_{n}$ which covers K from a to b and such that $C_{0} \subseteq U$ and $C_{n} \subseteq V$ .
Proof.
If for each $ε > 0$ there exists such a chain, then we conclude that $K \cap S$ is zero-dimensional in the same way as in the case of Proposition 3.5.

Suppose $K \cap S$ is zero-dimensional. Let $ϵ > 0$ . By the previous proposition, there exists a compact $(U, V)$ - $\frac{ϵ}{2}$ -chain $F_{0}, \dots, F_{n}$ which covers K from a to b and such that $F_{0} \subseteq U$ and $F_{n} \subseteq V$ . By Lemma 3.1 there exists an open ϵ-chain ${\tilde{C}}_{0}, \dots, {\tilde{C}}_{n}$ such that $F_{i} \subseteq {\tilde{C}}_{i}$ for each $i \in {0, \dots, n}$ . Now, we are going to define a required chain $C_{0}, \dots, C_{n}$ in the following way:
if $F_{i} \subseteq U$ then we define $C_{i} = {\tilde{C}}_{i} \cap U$ ;

if $F_{i} \subseteq V$ then we define $C_{i} = {\tilde{C}}_{i} \cap V$ ;

if $F_{i} \cap S \neq \emptyset$ then we define $C_{i} = {\tilde{C}}_{i}$ .
Clearly $C_{0}, \dots, C_{n}$ is an ϵ-open chain which covers K from a to b. Furthermore, $C_{0}, \dots, C_{n}$ is a $(U, V)$ -chain because for each $i \in {0, \dots, n}$ we have: if $F_{i} \subseteq U$ then $C_{i} = {\tilde{C}}_{i} \cap U \subseteq U$ and if $F_{i} \subseteq V$ then $C_{i} = {\tilde{C}}_{i} \cap V \subseteq V$ . □
Proposition 3.7.
Let X be a set and let U and V be disjoint subsets of X. Let $C_{0}, \dots, C_{n}$ be a simple $(U, V)$ -chain in X such that $C_{0} \subseteq U$ and $C_{n} \subseteq V$ . Then there exists $i_{0} \in {0, \dots, n - 2}$ such that $C_{i_{0}} \subseteq U$ and $C_{i_{0} + 2} \subseteq V$ .
Proof.
Let $i_{0}$ be defined by $\begin{matrix} i_{0} = max {i \in {0, \dots, n} ∣ C_{i} \subseteq U} . \end{matrix}$ Since $C_{i_{0}} \subseteq U$ and $C_{n} \subseteq V$ , we have $i_{0} < n$ and also $C_{i_{0} + 1} ⊈ U$ . It follows from $U \cap V = \emptyset$ and $C_{i_{0}} \cap C_{i_{0} + 1} \neq \emptyset$ that $C_{i_{0} + 1} ⊈ V$ . Therefore $i_{0} + 1 < n$ , hence $i_{0} ⩽ n - 2$ .

Since $C_{0}, \dots, C_{n}$ is a $(U, V)$ -chain, we have $C_{i_{0} + 2} \subseteq U$ or $C_{i_{0} + 2} \subseteq V$ . However $C_{i_{0} + 2} \subseteq U$ cannot hold by definition of the number $i_{0}$ . Thus $C_{i_{0} + 2} \subseteq V$ . □

Let X be a set and let $C = (C_{0}, \dots, C_{m})$ and $D = (D_{0}, \dots, D_{k})$ be finite sequences of a subsets in X. We say that $D$ refines $C$ if for each $i \in {0, \dots, k}$ there exists $j \in {0, \dots, m}$ such that $D_{i} \subseteq C_{j}$ . Lemma 3.8.
Let X be a set and let $C_{0}, \dots, C_{m}$ and $D_{0}, \dots, D_{m^{'}}$ be two simple chains in X such that $D_{0}, \dots, D_{m^{'}}$ refines $C_{0}, \dots, C_{m}$ . Furthermore, suppose that $i, j, k \in {0, \dots, m}$ and $p, q \in {0, \dots, m^{'}}$ are such that $i < k < j$ , $p < q$ and $\begin{matrix} D_{p} \subseteq C_{i} and D_{q} \subseteq C_{j} . \end{matrix}$ Then there exists $r \in {0, \dots, m^{'}}$ such that $p < r < q$ and $\begin{matrix} D_{r} \subseteq C_{k} . \end{matrix}$
Proof.
Let l be the greatest number in ${p, \dots, q}$ such that $D_{l}$ is contained in some of the following sets: $\begin{matrix} C_{0}, \dots, C_{i}, \dots, C_{k - 1} . \end{matrix}$ Note that the number l is well-defined because $D_{p} \subseteq C_{i}$ .

The set $C_{j}$ is disjoint with each of the sets $C_{0}, \dots, C_{i}, \dots, C_{k - 1}$ . Consequently, $D_{q}$ is disjoint with each of these sets. Now we have that $D_{q}$ is disjoint with $D_{l}$ . Thus $p < l + 1 < q$ . Let $\begin{matrix} r = l + 1 . \end{matrix}$ Then $D_{r}$ is not contained in any of the sets $C_{0}, \dots, C_{i}, \dots, C_{k - 1}$ , so it is contained in some of the sets $C_{k}, \dots, C_{m}$ .

Suppose that $D_{r} \subseteq C_{v}$ for some $v \in {k + 1, \dots, m}$ . Note that $C_{v}$ is disjoint with each of the sets $C_{0}, \dots, C_{k - 1}$ . Therefore, $D_{r}$ is disjoint with each of the sets $C_{0}, \dots, C_{k - 1}$ and it follows that $D_{r}$ is disjoint with $D_{l}$ , i.e. with $D_{r - 1}$ . This is impossible since $D_{0}, \dots, D_{m^{'}}$ is a simple chain.

Hence $D_{r} \subseteq C_{k}$ . □
Proposition 3.9.
Let X be a set and U and V disjoint subsets of X. Suppose $C = (C_{0}, \dots, C_{n})$ and $D = (D_{0}, \dots, D_{m})$ are simple $(U, V)$ -chains in X such that $D$ refines $C$ . Let us assume that $D_{0} \subseteq C_{0} \subseteq U$ , $D_{m} \subseteq C_{n} \subseteq V$ and that $i_{0} \in {0, \dots, n - 2}$ is such that $\begin{matrix} C_{i_{0}} \subseteq U and C_{i_{0 + 2}} \subseteq V . \end{matrix}$ Then there exists $j_{0} \in {0, \dots, m - 2}$ such that $\begin{matrix} D_{j_{0}} \subseteq U, D_{j_{0} + 2} \subseteq V, \end{matrix}$ and $\begin{matrix} D_{j_{0}} \cup D_{j_{0} + 1} \cup D_{j_{0} + 2} \subseteq C_{i_{0}} \cup C_{i_{0} + 1} \cup C_{i_{0} + 2} . \end{matrix}$
Proof.
First, we claim the following: $\begin{array}{l} (5) & there exists j \in {0, \dots, m} such that D_{j} \subseteq C_{i_{0}} . \end{array}$ This is clear if $i_{0} = 0$ since $D_{0} \subseteq C_{0}$ . If $i_{0} \neq 0$ then $0 < i_{0} < n$ . By Lemma 3.8 there exists $j \in {0, \dots, m}$ such that $D_{j} \subseteq C_{i_{0}}$ .

Let $\begin{matrix} j_{0} = max {j \in {0, \dots, m} ∣ D_{j} \subseteq U and (D_{j} \subseteq C_{i_{0}} or D_{j} \subseteq C_{i_{0} + 1})} . \end{matrix}$ Note that $j_{0}$ is well defined because (5) holds. Now we have $\begin{matrix} D_{j_{0}} \subseteq U and (D_{j_{0}} \subseteq C_{i_{0}} or D_{j_{0}} \subseteq C_{i_{0} + 1}) . \end{matrix}$ Since $D_{m} \subseteq V$ and U and V are disjoint, we have $j_{0} < m - 1$ , i.e. $j_{0} ⩽ m - 2$ .

Let us prove that $\begin{matrix} (6) & D_{j_{0} + 1} \subseteq C_{i_{0} + 1} . \end{matrix}$ Suppose the contrary. Note that $D_{j_{0} + 1} ⊈ C_{i_{0}}$ (by definition of $j_{0}$ ). Now we have that $\begin{matrix} D_{j_{0} + 1} \subseteq C_{i} \end{matrix}$ for some $i \in {0, \dots, m}$ such that $\begin{matrix} i ⩽ i_{0} - 1 or i ⩾ i_{0} + 2 . \end{matrix}$ If $i < i_{0} - 1$ , then $C_{i} \cap (C_{i_{0}} \cup C_{i_{0} + 1}) = \emptyset$ and that is a contradiction to $\begin{matrix} D_{j_{0} + 1} \subseteq C_{i}, D_{j_{0}} \subseteq C_{i_{0}} \cup C_{i_{0} + 1} and D_{j_{0}} \cap D_{j_{0} + 1} \neq \emptyset . \end{matrix}$ In the same way we get that i cannot be greater than $i_{0} + 2$ . Hence $\begin{matrix} i = i_{0} - 1 or i = i_{0} + 2 . \end{matrix}$

Suppose $i = i_{0} + 2$ . Then $D_{j_{0} + 1} \subseteq C_{i_{0} + 2}$ and since, by the assumption of the proposition, $C_{i_{0} + 2} \subseteq V$ , we have $\begin{matrix} D_{j_{0} + 1} \subseteq V . \end{matrix}$ But $D_{j_{0}} \subseteq U$ and since $D_{j_{0}} \cap D_{j_{0} + 1} \neq \emptyset$ it follows $U \cap V \neq \emptyset$ . A contradiction.

Hence, $i = i_{0} - 1$ , i.e. $\begin{matrix} D_{j_{0} + 1} \subseteq C_{i_{0} - 1} . \end{matrix}$ Since $D_{m} \subseteq C_{n}$ and $j_{0} + 1 < m$ , by Lemma 3.8 there exists $j \in {0, \dots, m}$ such that $j_{0} + 1 < j < m$ and such that $\begin{matrix} D_{j} \subseteq C_{i_{0}} . \end{matrix}$ Since $C_{i_{0}} \subseteq U$ , we have $D_{j} \subseteq U$ and hence $\begin{matrix} D_{j} \subseteq U, D_{j} \subseteq C_{i_{0}} and j_{0} + 1 < j . \end{matrix}$ But this is a contradiction to the definition of $j_{0}$ . So we have proved that (6) holds.

Note now that $D_{j_{0} + 1} ⊈ U$ ; otherwise we would have a contradiction to the definition of $j_{0}$ . Furthermore, $\begin{matrix} D_{j_{0} + 1} ⊈ V \end{matrix}$ since $D_{j_{0}} \subseteq U$ . Because $D$ is $(U, V)$ -sequence it follows that $\begin{matrix} D_{j_{0} + 2} \subseteq U or D_{j_{0} + 2} \subseteq V . \end{matrix}$

Suppose that $D_{j_{0} + 2} \subseteq U$ . Since $D$ refines $C$ , there exists some $i \in {0, \dots, m}$ such that $D_{j_{0} + 2} \subseteq C_{i}$ . We have $D_{j_{0} + 1} \cap D_{j_{0} + 2} \neq \emptyset$ and, by (6), $D_{j_{0} + 1} \subseteq C_{i_{0} + 1}$ , so $C_{i} \cap C_{i_{0} + 1} \neq \emptyset$ and it follows $\begin{matrix} i = i_{0} or i = i_{0} + 1 or i = i_{0} + 2 . \end{matrix}$ If $i = i_{0} + 2$ , then $D_{j_{0} + 2} \subseteq C_{i_{0} + 2}$ and this, together with the assumption of the proposition that $C_{i_{0} + 2} \subseteq V$ , gives $D_{j_{0} + 2} \subseteq V$ which is impossible since $D_{j_{0} + 2} \subseteq U$ . Hence $i = i_{0}$ or $i = i_{0} + 1$ . Now we have: $\begin{matrix} D_{j_{0} + 2} \subseteq U and (D_{j_{0} + 2} \subseteq C_{i_{0}} or D_{j_{0} + 2} \subseteq C_{i_{0} + 1}) \end{matrix}$ which contradicts the definition of $j_{0}$ . Hence we have $\begin{matrix} D_{j_{0} + 2} \subseteq V . \end{matrix}$

Let us prove now the following: $\begin{matrix} (7) & D_{j_{0} + 2} \subseteq C_{i_{0} + 1} \cup C_{i_{0} + 2} . \end{matrix}$ Certainly, $D_{j_{0} + 2} \subseteq C_{i}$ for some $i \in {0, \dots, n}$ . Since $D_{j_{0} + 1} \subseteq C_{i_{0} + 1}$ , we have $C_{i_{0} + 1} \cap C_{i} \neq \emptyset$ . This implies $i = i_{0}$ , $i = i_{0} + 1$ or $i = i_{0} + 2$ . However, $i = i_{0}$ would give $D_{j_{0} + 2} \subseteq C_{i} \subseteq U$ which contradicts $D_{j_{0} + 2} \subseteq V$ . Hence (7) holds.

To summarise, we have $j_{0} \in {0, \dots, m - 2}$ such that the following hold: $\begin{array}{l} D_{j_{0}} \subseteq U; \\ D_{j_{0} + 2} \subseteq V; \\ D_{j_{0}} \subseteq C_{i_{0}} \cup C_{i_{0} + 1}; \\ D_{j_{0} + 1} \subseteq C_{i_{0} + 1}; \\ D_{j_{0} + 2} \subseteq C_{i_{0} + 1} \cup C_{i_{0} + 2} . \end{array}$ Thus we have proved the claim of the proposition. □
Proposition 3.10.
Let $(X, d)$ be a metric space, U and V open and disjoint sets in $(X, d)$ and let $\begin{matrix} S = X ∖ (U \cup V) . \end{matrix}$ Let $K \subseteq X$ . Suppose K, as a subspace of $(X, d)$ , is a continuum chainable from a to b, where $a \in U$ and $b \in V$ . Suppose $S \cap K$ is zero-dimensional. Let $C_{0}, \dots, C_{n}$ be an open chain that covers K from a to b and let $ϵ > 0$ . Then there exists a compact $(U, V)$ -ϵ-chain $D_{0}, \dots, D_{m}$ which covers K from a to b, refines the chain $C_{0}, \dots, C_{n}$ and is such that $D_{0} \subseteq C_{0}$ and $D_{m} \subseteq C_{n}$ .
Proof.
Because K is a compact set and ${C_{0}, \dots, C_{n}}$ is an open cover of it, there exists $δ > 0$ such that δ is a Lebesgue number of this open cover for K. Since $a \in C_{0}$ and $b \in C_{m}$ , there exist $r_{1}, r_{2} > 0$ such that $B (a, r_{1}) \subseteq C_{0}$ and $B (b, r_{2}) \subseteq C_{n}$ . Let μ be defined by $\begin{matrix} μ = min {ϵ, δ, r_{1}, r_{2}} . \end{matrix}$ Then, by Proposition 3.5 there exists a compact $(U, V)$ -μ-chain $D_{0}, \dots, D_{m}$ in K which covers K from a to b and such that $D_{0} \subseteq U$ and $D_{m} \subseteq V$ . If $i \in {0, \dots, m}$ , then $diam (D_{i}) < μ ⩽ δ$ and therefore there exists $j \in {0, \dots, n}$ such that $\begin{matrix} D_{i} \subseteq C_{j} . \end{matrix}$ Hence the finite sequence $D_{0}, \dots, D_{m}$ refines the finite sequence $C_{0}, \dots, C_{n}$ .

We have $a \in D_{0}$ and $diam (D_{0}) < r_{1}$ , therefore $d (x, a) < r_{1}$ for each $x \in D_{0}$ . Hence $D_{0} \subseteq B (a, r_{1})$ and $D_{0} \subseteq C_{0}$ . In the same way we get $D_{m} \subseteq C_{n}$ . □
Lemma 3.11.
Let $(X, d)$ be a metric space and let U and V be open disjoint sets in $(X, d)$ . Let $a \in U$ and $b \in V$ and let $S = X ∖ (U \cup V)$ . Let K be a connected set in $(X, d)$ such that $a, b \in K$ and let $C_{0}, \dots, C_{m}$ be a chain in $(X, d)$ which covers K from a to b. Suppose that $i \in {0, \dots, m - 2}$ is such that $C_{i} \subseteq U$ and $C_{i + 2} \subseteq V$ . Then $C_{i + 1} \cap S \neq \emptyset$ .
Proof.
Suppose the contrary, that $C_{i + 1} \cap S = \emptyset$ . Then we have $C_{i + 1} \subseteq U \cup V$ , and it follows that $\begin{matrix} C_{i + 1} = (C_{i + 1} \cap U) \cup (C_{i + 1} \cap V) . \end{matrix}$ We can now consider the following sets: $\begin{matrix} (8) & C_{0}, \dots, C_{i - 1}, C_{i}, C_{i + 1} \cap U \end{matrix}$ and $\begin{matrix} (9) & C_{i + 1} \cap V, C_{i + 2}, \dots, C_{m} . \end{matrix}$ Each of the sets in (8) is disjoint with each of the sets in (9). Furthermore, each of these sets is open and they all together cover K.

Let $W_{1}$ be a union of sets in (8) and let $W_{2}$ be a union of sets in (9). Then $W_{1}$ and $W_{2}$ are disjoint and open sets such that $K \subseteq W_{1} \cup W_{2}$ . Note that $W_{1}$ intersects K because $a \in W_{1}$ and that $W_{2}$ intersects K because $b \in W_{2}$ . But this is a contradiction to the assumption that K is connected. □

4. Separators, augmentators and locators

Let $(X, d, α)$ be a computable metric space and let $a \in X$ be a computable point in this space. Using Proposition 2.1 it is easy to conclude that the set ${i \in N ∣ a \in I_{i}}$ is c.e. This implies that the set ${j \in N ∣ a \in J_{j}}$ is also c.e. and consequently we have the following proposition.

Proposition 4.1.
Let $(X, d, α)$ be a computable metric space and let $a \in X$ be a computable point in this space. Then $\begin{matrix} {l \in N ∣ a \in J_{{(l)}_{0}}} and {l \in N ∣ a \in J_{{(l)}_{\overline{l}}}} \end{matrix}$ are c.e. sets.

Let $(X, d, α)$ be a computable metric space and let $v, w \in N$ . We say that $I_{v}$ is formally contained in $I_{w}$ and we write $I_{v} \subset_{F} I_{w}$ if $\begin{matrix} d (λ_{v}, λ_{w}) + ρ_{v} < ρ_{w} . \end{matrix}$ Note that this is a relation between numbers v and w not between the sets $I_{v}$ and $I_{w}$ . Furthermore, if $I_{v} \subset_{F} I_{w}$ then $I_{v} \subseteq I_{w}$ .

Let $(X, d, α)$ be a computable metric space and let $U \subseteq X$ be a c.e. open set. Let $A \subseteq N$ be a computably enumerable set such that $U = ⋃_{i \in A} I_{i}$ and let $v \in N$ . We say that $I_{v}$ is A-contained in U and we write $\begin{matrix} I_{v} \subseteq_{A} U \end{matrix}$ if there exist $i \in A$ such that $I_{v} \subset_{F} I_{i}$ . Clearly, $I_{v} \subseteq_{A} U$ implies $I_{v} \subseteq U$ . Furthermore, for $j \in N$ we say that $J_{j}$ is A-contained in U and we write $\begin{matrix} J_{j} \subseteq_{A} U \end{matrix}$ if $I_{v} \subseteq_{A} U$ for each $v \in [j]$ .

Let $a, u, v, w \in N$ . We say that $J_{a}$ is formally contained in $J_{u, v, w}$ and we write $\begin{matrix} J_{a} \subset_{F} J_{u, v, w} \end{matrix}$ if for each $i \in [a]$ there exists $j \in [u] \cup [v] \cup [w]$ such that $I_{i} \subset_{F} I_{j}$ . If $a, b, c, u, v, w \in N$ , then we say that $J_{a, b, c}$ is formally contained in $J_{u, v, w}$ and we write $\begin{matrix} J_{a, b, c} \subset_{F} J_{u, v, w} \end{matrix}$ if $J_{a} \subset_{F} J_{u, v, w}$ , $J_{b} \subset_{F} J_{u, v, w}$ and $J_{c} \subset_{F} J_{u, v, w}$ .
Proposition 4.2.
Let $(X, d, α)$ be a computable metric space. Let $\begin{matrix} Ω = {(v, w) \in N^{2} ∣ I_{v} \subset_{F} I_{w}} . \end{matrix}$ Then Ω is a c.e. subset of $N^{2}$ .
Proof.
Let $v, w \in N$ . Then $\begin{matrix} (v, w) \in Ω ⟺ I_{v} \subset_{F} I_{w} ⟺ d (λ_{v}, λ_{w}) + ρ_{v} < ρ_{w} \end{matrix}$ and the claim follows from Proposition 2.1. □
Proposition 4.3.
Let $(X, d, α)$ be a computable metric space, A a computably enumerable subset of $N$ and $U = ⋃_{i \in A} I_{i}$ . Let Γ be the subset of $N$ defined by $\begin{matrix} Γ = {v \in N ∣ I_{v} \subseteq_{A} U} . \end{matrix}$ Then Γ is c.e.
Proof.
Let Ω be the set from Proposition 4.2. Then for each $v \in N$ $\begin{matrix} v \in Γ ⟺ I_{v} \subseteq_{A} U ⟺ \exists i \in A such that I_{v} \subset_{F} I_{i} ⟺ \exists i \in A such that (v, i) \in Ω . \end{matrix}$ Hence $\begin{matrix} Γ = {v \in N ∣ \exists i \in N such that (v, i) \in Ω and i \in A} . \end{matrix}$ The fact that Γ is c.e. follows now from Proposition 2.5(i). □
Proposition 4.4.
Let $(X, d, α)$ be a computable metric space, $A \subseteq N$ a c.e. set and $U = ⋃_{i \in A} I_{i}$ . Let $\begin{matrix} \tilde{Γ} = {j \in N ∣ J_{j} \subseteq_{A} U} . \end{matrix}$ Then $\tilde{Γ}$ is a c.e. set.
Proof.
Let Γ be the set from Proposition 4.3. For $j \in N$ we have $\begin{matrix} j \in \tilde{Γ} ⟺ J_{j} \subseteq_{A} U ⟺ I_{v} \subseteq_{A} U for each v \in [j] ⟺ [j] \subseteq Γ . \end{matrix}$ Hence $\begin{matrix} \tilde{Γ} = {j \in N ∣ [j] \subseteq Γ} . \end{matrix}$ That $\tilde{Γ}$ is c.e. follows now from Proposition 2.4(ii) and the fact that the function $N \to P (N)$ , $j \mapsto [j]$ is e.f.v. □
Proposition 4.5.
Let $(X, d, α)$ be a computable metric space. Then the set $\begin{matrix} Θ = {(a, b, c, u, v, w) \in N^{6} ∣ J_{a, b, c} \subset_{F} J_{u, v, w}} \end{matrix}$ is c.e.
Proof.
Let Ω be the set from Proposition 4.2. Let $\begin{matrix} Γ = {(a, u, v, w) \in N^{4} ∣ J_{a} \subset_{F} J_{u, v, w}} . \end{matrix}$ Let $\begin{matrix} Γ^{'} = {(i, u, v, w) \in N^{4} ∣ \exists j \in N such that (i, j) \in Ω and j \in [u] \cup [v] \cup [w]} . \end{matrix}$ Using the fact that the function $N^{3} \to P (N)$ , $(u, v, w) \mapsto [u] \cup [v] \cup [w]$ is e.f.v., we easily conclude from Proposition 2.5(i) that $Γ^{'}$ is c.e. For all $a, u, v, w \in N$ we have $\begin{matrix} (a, u, v, w) \in Γ ⟺ (i, u, v, w) \in Γ^{'} for each i \in [a] ⟺ [a] \times {u} \times {v} \times {w} \subseteq Γ^{'} . \end{matrix}$ It follows from Proposition 2.4 that Γ is c.e.

Finally, we have $\begin{matrix} Θ = A^{- 1} (Γ) \cap B^{- 1} (Γ) \cap C^{- 1} (Γ), \end{matrix}$ where $A, B, C : N^{6} \to N^{4}$ are the functions defined by $A (a, b, c, u, v, w) = (a, u, v, w)$ , $B (a, b, c, u, v, w) = (b, u, v, w)$ , $C (a, b, c, u, v, w) = (c, u, v, w)$ . Thus Θ is c.e. by Proposition 2.5(i). □

Let $(X, d, α)$ be a computable metric space and let $i, j \in N$ . We say that $I_{i}$ and $I_{j}$ are formally disjoint, and we write $I_{i} \cap_{FD} I_{j}$ , if $\begin{matrix} d (λ_{i}, λ_{j}) > ρ_{i} + ρ_{j} . \end{matrix}$ Note the following: if $I_{i}$ and $I_{j}$ are formally disjoint then $I_{i} \cap I_{j} = \emptyset$ . Also note that formal disjointness is not a relation between the sets $I_{i}$ and $I_{j}$ , but between the numbers i and j.

Let $a, b \in N$ . We say that $J_{a}$ and $J_{b}$ are formally disjoint, and we write $J_{a} \cap_{FD} J_{b}$ , if $I_{i}$ and $I_{j}$ are formally disjoint for all $i \in [a]$ and $j \in [b]$ . If $J_{a}$ and $J_{b}$ are formally disjoint, then $J_{a} \cap J_{b} = \emptyset$ .

Let $l \in N$ . We define $\begin{matrix} H_{l} = (J_{{(l)}_{0}}, \dots, J_{{(l)}_{\overline{l}}}) . \end{matrix}$ We say that l represents a formal chain or, shortly, that $H_{l}$ is a formal chain if $J_{{(l)}_{i}}$ and $J_{{(l)}_{j}}$ are formally disjoint for all $i, j \in {0, \dots, \overline{l}}$ such that $| i - j | > 1$ .

Using Propositions 2.1, 2.4 and 2.5, it is not hard to prove the following proposition. For details, see [8], Proposition 8, and [10], Proposition 5.4.
Proposition 4.6.
Let $(X, d, α)$ be a computable metric space. The following sets are computably enumerable: $\begin{array}{l} {(i, j) \in N^{2} ∣ I_{i} and I_{j} are formally disjoint}, \\ {(a, b) \in N^{2} ∣ J_{a} and J_{b} are formally disjoint}, \\ {l \in N ∣ H_{l} is a formal chain} . \end{array}$
Proposition 4.7.
Let $(X, d, α)$ be a computable metric space and let K be a computable set in this space. Let $\begin{matrix} Ω = {l \in N ∣ H_{l} properly covers K} . \end{matrix}$ Then Ω is c.e.
Proof.
We have $\begin{matrix} (10) & Ω = {i \in N ∣ H_{l} covers K} \cap {i \in N ∣ J_{{(l)}_{0}} \cap K \neq \emptyset} \cap {i \in N ∣ J_{{(l)}_{\overline{l}}} \cap K \neq \emptyset} . \end{matrix}$ By Proposition 5.3 in [10] the set ${l \in N ∣ H_{l} covers K}$ is c.e. On the other hand, let $Γ = {j \in N ∣ J_{j} \cap K \neq \emptyset}$ . Then $\begin{matrix} Γ = {j \in N ∣ \exists i \in N such that I_{i} \cap K \neq \emptyset and i \in [j]} . \end{matrix}$ The fact that K is c.e. closed in $(X, d, α)$ , together with the projection theorem, implies that Γ is c.e. It is now easy to conclude from (10) that Ω, as the intersection of c.e. sets, is c.e. □

Let $(X, d, α)$ be a computable metric space and let $A \subseteq X$ , $j \in N$ and $μ > 0$ . We are going to write $\begin{matrix} A \subseteq_{μ} J_{j} \end{matrix}$ if the following holds: $\begin{array}{l} A \subseteq J_{j}, \\ I_{i} \cap A \neq \emptyset, for each i \in [j], \\ ρ_{i} < μ, for each i \in [j] . \end{array}$
Lemma 4.8.
Let $(X, d, α)$ be a computable metric space, let K be a nonempty compact set in $(X, d)$ and let $r > 0$ . Then there exists $l \in N$ such that $K \subseteq_{r} J_{l}$ .
Proof.
See [4], Lemma 4.6. □

Let $(X, d, α)$ be a computable metric space, let $A, B \subseteq X$ and $μ > 0$ . We say that the number μ is an $(A, B)$ -separator if for all $i, j \in N$ the following implication holds: $\begin{matrix} (A \subseteq_{μ} J_{i} and B \subseteq_{μ} J_{j}) ⟹ J_{i} \underset{FD}{\cap} J_{j} . \end{matrix}$ Note that if A, B are compact sets in $(X, d)$ , μ is an $(A, B)$ -separator and $μ^{'} \in ⟨ 0, μ ⟩$ , then $μ^{'}$ is also an $(A, B)$ -separator.
Lemma 4.9.
Let $(X, d, α)$ be a computable metric space and let A and B be nonempty subsets of X. Let r be a positive real number such that $\begin{matrix} r ⩽ \frac{1}{4} d (A, B) . \end{matrix}$ Then r is an $(A, B)$ -separator.
Proof.
Let $j, j^{'} \in N$ be such that $A \subseteq_{r} J_{j}$ and $B \subseteq_{r} J_{j^{'}}$ . Let $i \in [j]$ and $i^{'} \in [j^{'}]$ . We prove the following: $\begin{matrix} d (λ_{i}, λ_{i^{'}}) > ρ_{i} + ρ_{i^{'}} . \end{matrix}$ Suppose the contrary. Then we have $d (λ_{i}, λ_{i^{'}}) ⩽ ρ_{i} + ρ_{i^{'}}$ . Note that $I_{i} \cap A \neq \emptyset$ and $I_{i^{'}} \cap B \neq \emptyset$ and $ρ_{i}, ρ_{i^{'}} < r$ , because by assumption we have $A \subseteq_{r} J_{j}$ and $B \subseteq_{r} J_{j^{'}}$ . Let $a \in A \cap I_{i}$ and let $b \in B \cap I_{i^{'}}$ . Then we have: $\begin{array}{l} d (A, B) & ⩽ d (a, b) ⩽ \overset{< ρ_{i}}{\overset{︷}{d (a, λ_{i})}} + \overset{⩽ ρ_{i} + ρ_{i^{'}}}{\overset{︷}{d (λ_{i}, λ_{i^{'}})}} + \overset{< ρ_{i^{'}}}{\overset{︷}{d (λ_{i^{'}}, b)}} \\ < \overset{< r}{\overset{︷}{ρ_{i}}} + (ρ_{i} + ρ_{i^{'}}) + \overset{< r}{\overset{︷}{ρ_{i^{'}}}} < 4 r ⩽ d (A, B) . \end{array}$ Hence $d (A, B) < d (A, B)$ , a contradiction.

Thus we have $d (λ_{i}, λ_{i^{'}}) > ρ_{i} + ρ_{i^{'}}$ , and so $I_{i} \cap_{FD} I_{i^{'}}$ . Because $i \in [j]$ and $i^{'} \in [j^{'}]$ are arbitrary elements we can conclude that $J_{j} \cap_{FD} J_{j^{'}}$ . □
Proposition 4.10.
Let $(X, d, α)$ be a computable metric space and let $A, B$ be disjoint nonempty compact sets in $(X, d)$ . Then there exists $μ > 0$ such that μ is an $(A, B)$ -separator.
Proof.
Let $μ = d (A, B)$ . Then $μ > 0$ because A and B are compact and disjoint. By Lemma 4.9 $\frac{μ}{4}$ is an $(A, B)$ -separator. □
Lemma 4.11.
Let $(X, d, α)$ be a computable metric space, let $A \subseteq X$ , $j \in N$ and $r > 0$ such that $A \subseteq_{r} J_{j}$ . Then $\begin{matrix} fdiam (j) < diam (A) + 4 r . \end{matrix}$
Proof.
See [4], Lemma 4.8. □

Let $(X, d, α)$ be a computable metric space. Let $A \subseteq N$ be computably enumerable and let $U = ⋃_{i \in A} I_{i}$ . Let K be a compact set in $(X, d)$ and $μ > 0$ . We say that μ is a $(K, A, U)$ -augmentator if for every $j \in N$ the following implication holds: $\begin{matrix} K \subseteq_{μ} J_{j} ⟹ J_{j} \subseteq_{A} U . \end{matrix}$ Note that if λ is a $(K, A, U)$ -augmentator and $μ^{'} \in ⟨ 0, μ ⟩$ , then the number $μ^{'}$ is also a $(K, A, U)$ -augmentator.
Lemma 4.12.
Let $(X, d, α)$ be a computable metric space, let $A \subseteq N$ be a c.e. set and let $U = ⋃_{i \in A} I_{i}$ . Let K be a compact set in $(X, d)$ such that $K \subseteq U$ . Then there exist $μ > 0$ such that for all $i \in N$ the following implication holds: $\begin{matrix} (11) & (I_{i} \cap K \neq \emptyset and ρ_{i} < μ) ⟹ I_{i} \subseteq_{A} U . \end{matrix}$
Proof.
Suppose, to the contrary, that for each $μ > 0$ there exist $i \in N$ such that $I_{i} \cap K \neq \emptyset$ and $ρ_{i} < μ$ but such that $I_{i} ⊈_{A} U$ , i.e. $I_{i} \subseteq_{A} U$ does not hold. Then $\begin{array}{l} (12) & (\forall n \in N) (\exists i_{n} \in N) such that I_{i_{n}} \cap K \neq \emptyset and ρ_{i_{n}} < \frac{1}{2^{n}}, but I_{i_{n}} ⊄_{F} U . \end{array}$ For each $n \in N$ choose some point $y_{n} \in I_{i_{n}} \cap K$ . Then ${(y_{n})}_{n \in N}$ is a sequence in K and since K is compact, this sequence has a subsequence ${(y_{n_{m}})}_{m \in N}$ which converges to some point $z \in K$ . It follows $z \in U$ and so there exists $a \in A$ such that $z \in I_{a}$ . We have $d (λ_{a}, z) < ρ_{a}$ . Therefore there exists $ε > 0$ such that $\begin{matrix} (13) & d (λ_{a}, z) + ε < ρ_{a} . \end{matrix}$

Let $k \in N$ . Then $\begin{array}{l} ρ_{i_{n_{k}}} + d (λ_{i_{n_{k}}}, λ_{a}) & ⩽ ρ_{i_{n_{k}}} + \overset{y_{n_{k}} \in B (λ_{i_{n_{k}}}, ρ_{i_{n_{k}}})}{\overset{︷}{d (λ_{i_{n_{k}}}, y_{n_{k}})}} + d (y_{n_{k}}, z) + d (z, λ_{a}) \\ ⩽ ρ_{i_{n_{k}}} + ρ_{i_{n_{k}}} + d (y_{n_{k}}, z) + d (z, λ_{a}) \\ (14) & < 2 \frac{1}{2^{n_{k}}} + d (y_{n_{k}}, z) + d (z, λ_{a}) . \end{array}$ Choose $k \in N$ so that $2 \frac{1}{2^{n_{k}}} + d (y_{n_{k}}, z) < ε$ . Then by (14) and (13) $\begin{matrix} ρ_{i_{n_{k}}} + d (λ_{i_{n_{k}}}, λ_{a}) < ρ_{a} \end{matrix}$ and this means that $I_{i_{n_{k}}} \subseteq_{A} U$ , which is a contradiction to (12). □
Proposition 4.13.
Let $(X, d, α)$ be a computable metric space, let $A \subseteq N$ be a c.e. set and let $U = ⋃_{i \in A} I_{i}$ . Let K be a compact set in $(X, d)$ such that $K \subseteq U$ . Then there exists $μ > 0$ such that μ is a $(K, A, U)$ -augmentator.
Proof.
By Lemma 4.12 there exists $μ > 0$ such that (11) holds for each $i \in N$ .

Suppose $j \in N$ is such that $K \subseteq_{μ} J_{j}$ . Then for each $i \in [j]$ we have $I_{i} \cap K \neq \emptyset$ and $ρ_{i} < μ$ and therefore $I_{i} \subseteq_{A} U$ . Thus $J_{j} \subseteq_{A} U$ . This means that μ is a $(K, A, U)$ -augmentator. □

Let $(X, d, α)$ be a computable metric space and let A and B be c.e. subsets of $N$ . Let $U = ⋃_{i \in A} I_{i}$ and $V = ⋃_{j \in B} I_{j}$ . Let $l \in N$ . We say that $H_{l}$ is a formal $(U, A, V, B)$ -sequence if for each $i \in N$ such that $i < \overline{l}$ the following holds: $\begin{array}{l} (15) & J_{{(l)}_{i}} \subseteq_{A} U or J_{{(l)}_{i}} \subseteq_{B} V or J_{{(l)}_{i + 1}} \subseteq_{A} U or J_{{(l)}_{i + 1}} \subseteq_{B} V . \end{array}$ Note that if $H_{l}$ is a formal $(U, A, V, B)$ -sequence, then $H_{l}$ is a $(U, V)$ -sequence.
Proposition 4.14.
Let $(X, d, α)$ be a computable metric space and let A and B be c.e. subsets of $N$ . Let $U = ⋃_{i \in A} I_{i}$ and $V = ⋃_{j \in B} I_{j}$ . Then the set $\begin{matrix} Ω = {l \in N ∣ H_{l} is a formal (U, A, V, B) -sequence} \end{matrix}$ is c.e.
Proof.
By Proposition 4.4 the set $\begin{matrix} \tilde{Γ} = {j \in N ∣ J_{j} \subseteq_{A} U} \end{matrix}$ is c.e. Let $Γ_{1}$ , $Γ_{2}$ , $Γ_{3}$ and $Γ_{4}$ be the sets defined by $\begin{array}{l} Γ_{1} & = {(l, i) ∣ J_{{(l)}_{i}} \subseteq_{A} U} \\ Γ_{2} & = {(l, i) ∣ J_{{(l)}_{i}} \subseteq_{B} V} \\ Γ_{3} & = {(l, i) ∣ J_{{(l)}_{i + 1}} \subseteq_{A} U} \\ Γ_{4} & = {(l, i) ∣ J_{{(l)}_{i + 1}} \subseteq_{B} V} . \end{array}$ We have $\begin{matrix} Γ_{1} = {(l, i) ∣ {(l)}_{i} \in \tilde{Γ}} = {(l, i) ∣ σ (l, i) \in \tilde{Γ}} = σ^{- 1} (\tilde{Γ}) . \end{matrix}$ (Recall that ${(l)}_{i}$ by definition means $σ (l, i)$ .) It follows from Proposition 2.5(iii) that $Γ_{1}$ is c.e. In the same way we get that $Γ_{2}$ , $Γ_{3}$ and $Γ_{4}$ are c.e.

For each $l \in N$ we have $\begin{array}{l} l \in Ω & ⟺ H_{l} is a formal (U, V) -sequence \\ ⟺ \forall i \in {0, \dots, \overline{l} - 1} (l, i) \in Γ_{1} \cup Γ_{2} \cup Γ_{3} \cup Γ_{4} \\ (16) & ⟺ {(l, i) \in N^{2} ∣ i < \overline{l}} \subseteq Γ_{1} \cup Γ_{2} \cup Γ_{3} \cup Γ_{4} . \end{array}$ Let $Φ : N \to P (N^{2})$ be the function defined by $\begin{matrix} Φ (l) = {(l, i) \in N^{2} ∣ i < \overline{l}} . \end{matrix}$ Clearly, Φ is e.f.v. and by (16) $\begin{matrix} Ω = {l \in N ∣ Φ (l) \subseteq Γ_{1} \cup Γ_{2} \cup Γ_{3} \cup Γ_{4}} \end{matrix}$ which, together with Proposition 2.4(ii), implies that Ω is c.e. □

Let $(X, d, α)$ be a computable metric space and let A and B be c.e. subsets of $N$ . Let $U = ⋃_{i \in A} I_{i}$ and $V = ⋃_{j \in B} I_{j}$ . Furthermore, let $K \subseteq X$ . Let $l, i_{0} \in N$ . We say that the ordered pair $(l, i_{0})$ is an $(A, B)$ -locator (with respect to K) if the following holds: $\begin{array}{l} H_{l} is a formal chain, \\ H_{l} is a formal (U, A, V, B) -sequence, \\ H_{l} properly covers K, \\ i_{0} ⩽ \overline{l} - 2, \\ J_{{(l)}_{i_{0}}} \subseteq_{A} U and J_{{(l)}_{i_{0} + 2}} \subseteq_{B} V, \\ J_{{(l)}_{0}} \subseteq_{A} U and J_{{(l)}_{\overline{l}}} \subseteq_{B} V . \end{array}$

Furthermore, we say that a locator $(l, i_{0})$ is an ϵ-locator, where $ϵ > 0$ , if $\begin{matrix} fmesh (l) < ϵ . \end{matrix}$
Proposition 4.15.
Let $(X, d, α)$ be a computable metric space, let A and B be c.e. subsets of $N$ and let $U = ⋃_{i \in A} I_{i}$ and $V = ⋃_{j \in B} I_{j}$ . Suppose U and V are disjoint and let $\begin{matrix} S = X ∖ (U \cup V) . \end{matrix}$ Suppose that $K \subseteq X$ is a continuum chainable from a to b, where $a \in U$ and $b \in V$ . Suppose $(l, i_{0})$ is an $(A, B)$ -locator. Then $\begin{matrix} J_{{(l)}_{i_{0} + 1}} \cap S \neq \emptyset . \end{matrix}$
Proof.
Since $H_{l}$ properly covers K, there exist $a^{'}, b^{'} \in K$ such that $H_{l}$ covers K from $a^{'}$ to $b^{'}$ . It follows $a^{'} \in U$ and $b^{'} \in V$ . We have that $H_{l}$ is a chain, $i_{0} \in {0, \dots, \overline{l} - 2}$ , $J_{{(l)}_{i_{0}}} \subseteq_{A} U$ and $J_{{(l)}_{i_{0} + 2}} \subseteq_{B} V$ . Hence, $J_{{(l)}_{i_{0}}} \subseteq U$ and $J_{{(l)}_{i_{0} + 2}} \subseteq V$ . It follows from Lemma 3.11 that $\begin{matrix} J_{{(l)}_{i_{0} + 1}} \cap S \neq \emptyset . \end{matrix}$ □
Proposition 4.16.
Let $(X, d, α)$ be a computable metric space, let A and B be c.e. subsets of $N$ and let $U = ⋃_{i \in A} I_{i}$ and $V = ⋃_{j \in B} I_{j}$ . Let K be a computable set in $(X, d, α)$ . Then the set $\begin{matrix} T = {(l, i_{0}) \in N^{2} ∣ (l, i_{0}) is an (A, B) -locator} \end{matrix}$ is c.e.
Proof.
Let $\begin{array}{l} T_{1} & = {(l, i_{0}) \in N^{2} ∣ H_{l} is a formal chain} \\ T_{2} & = {(l, i_{0}) \in N^{2} ∣ H_{l} is a formal (U, A, V, B) -sequence} \\ T_{3} & = {(l, i_{0}) \in N^{2} ∣ H_{l} properly covers K} \\ T_{4} & = {(l, i_{0}) \in N^{2} ∣ i_{0} ⩽ \overline{l} - 2} \\ T_{5} & = {(l, i_{0}) \in N^{2} ∣ J_{{(l)}_{i_{0}}} \subseteq_{A} U and J_{{(l)}_{i_{0} + 2}} \subseteq_{B} V} \\ T_{6} & = {(l, i_{0}) \in N^{2} ∣ J_{{(l)}_{0}} \subseteq_{A} U and J_{{(l)}_{\overline{l}}} \subseteq_{B} V} . \end{array}$ Using Proposition 2.5(iii), we conclude from Proposition 4.6, Proposition 4.14, Proposition 4.7, Proposition 4.1 and Proposition 4.4 that $T_{1}$ , $T_{2}$ , $T_{3}$ , $T_{4}$ , $T_{5}$ and $T_{6}$ are c.e. sets. Since $\begin{matrix} T = T_{1} \cap T_{2} \cap T_{3} \cap T_{4} \cap T_{5} \cap T_{6}, \end{matrix}$ the claim of the proposition follows. □
Proposition 4.17.
Let $(X, d, α)$ be a computable metric space, let A and B be c.e. subsets of $N$ and let $U = ⋃_{i \in A} I_{i}$ and $V = ⋃_{j \in B} I_{j}$ . Let $S = X ∖ (U \cup V)$ . Suppose that $K \subseteq X$ is a continuum chainable from a to b, where $a \in U$ and $b \in V$ . Let us assume that $K \cap S$ is zero-dimensional. Then for every $ϵ > 0$ there exist $l, i_{0} \in N$ such that $(l, i_{0})$ is an ϵ- $(A, B)$ -locator.
Proof.
By Proposition 3.5 there exists a compact $(U, V)$ - $\frac{ϵ}{2}$ -chain $K_{0}, \dots, K_{n}$ which covers K from a to b and which satisfies $K_{0} \subseteq U$ and $K_{n} \subseteq V$ . Let $K = {K_{0}, \dots, K_{n}}$ and let $\begin{array}{l} D = {(L, L^{'}) ∣ L, L^{'} \in K, L \cap L^{'} = \emptyset}, \\ U = {L \in K ∣ L \subseteq U}, \\ V = {L \in K ∣ L \subseteq V} . \end{array}$ For each $(L, L^{'}) \in D$ there exits $μ_{(L, L^{'})} > 0$ such that $μ_{(L, L^{'})}$ is a $(L, L^{'})$ -separator by Proposition 4.10. For each $L \in U$ there exists $δ_{L} > 0$ such that $δ_{L}$ is a $(L, A, U)$ -augmentator by Proposition 4.13. By the same proposition for each $L \in V$ there exists $ν_{L} > 0$ such that $ν_{L}$ is a $(L, B, V)$ -augmentator. Let $\begin{array}{l} μ = min {μ_{(L, L^{'})} ∣ (L, L^{'}) \in D} \\ δ = min {δ_{L} ∣ L \in U} \\ ν = min {ν_{L} ∣ L \in V} . \end{array}$ Let $\begin{matrix} r = min {μ, δ, ν, \frac{ε}{8}} . \end{matrix}$ By Lemma 4.8 for every $i \in {0, \dots, n}$ there exists $j_{i} \in N$ such that $\begin{matrix} (17) & K_{i} \subseteq_{r} J_{j_{i}} . \end{matrix}$ Suppose $v, w \in {0, \dots, n}$ are such that $| v - w | > 1$ . Then $K_{v} \cap K_{w} = \emptyset$ and since r is a $(K_{v}, K_{w})$ -separator it follows that $\begin{array}{l} (18) & J_{j_{v}} \underset{FD}{\cap} J_{j_{w}} . \end{array}$

Suppose $i \in {0, \dots, n}$ is such that $K_{i} \subseteq U$ . Since $μ_{K_{i}}$ is a $(K_{i}, A, U)$ -augmentator, $K_{i} \subseteq_{r} J_{j_{i}}$ and $r ⩽ μ_{K_{i}}$ , we have that $J_{j_{i}} \subseteq_{A} U$ .

In the same way, if $i \in {0, \dots, n}$ is such that $K_{i} \subseteq V$ , then $J_{j_{i}} \subseteq_{B} V$ .

So, for each $i \in {0, \dots, n}$ the following implications hold: $\begin{array}{l} K_{i} \subseteq U ⟹ J_{j_{i}} \subseteq_{A} U \\ (19) & K_{i} \subseteq V ⟹ J_{j_{i}} \subseteq_{B} V . \end{array}$ Let now $l \in N$ be a number such that: $\begin{matrix} ({(l)}_{0}, \dots, {(l)}_{\overline{l}}) = (j_{0}, \dots, j_{n}) . \end{matrix}$ It follows from (18) that $H_{l}$ is a formal chain. By (17), $H_{l}$ covers K from a to b. Furthermore, relation (19) gives that $H_{l}$ is a formal $(U, A, V, B)$ -sequence and that $J_{{(l)}_{0}} \subseteq_{A} U$ and $J_{{(l)}_{\overline{l}}} \subseteq_{B} V$ .

Because K is connected, $K_{0}, \dots, K_{n}$ is a simple chain and therefore by Proposition 3.7 there exists $i_{0} \in {0, \dots, n - 2}$ such that $K_{i_{0}} \subseteq U$ and $K_{i_{0} + 2} \subseteq V$ . So $i_{0} \in {0, \dots, \overline{l} - 2}$ and by (19) we have $\begin{matrix} J_{{(l)}_{i_{0}}} \subseteq_{A} U and J_{{(l)}_{i_{0} + 2}} \subseteq_{B} V . \end{matrix}$ By Lemma 4.11 for each $i \in {0, \dots, n}$ we have $\begin{matrix} fdiam (j_{i}) ⩽ diam (K_{i}) + 4 r < \frac{ϵ}{2} + 4 \cdot \frac{ϵ}{8} = ϵ . \end{matrix}$ Hence $\begin{matrix} fmesh (l) < ϵ \end{matrix}$ and we conclude that $(l, i_{0})$ is an ϵ- $(A, B)$ -locator. □

Let $(X, d, α)$ be a computable metric space and $a, b, c \in N$ some numbers. Let K be a compact set in X such that $K \subseteq J_{a} \cup J_{b} \cup J_{c}$ . We say that a number $μ > 0$ is a $(K, a, b, c)$ -augmentator if for every $j \in N$ the following holds: $\begin{matrix} K \subseteq_{μ} J_{j} ⟹ J_{j} \subset_{F} J_{a, b, c} . \end{matrix}$
Lemma 4.18.
Let $(X, d, α)$ be a computable metric space and $a, b, c \in N$ . Let K be a compact set in X such that $K \subseteq J_{a} \cup J_{b} \cup J_{c}$ . Then there exists some positive real number $μ > 0$ which is a $(K, a, b, c)$ -augmentator.
Proof.
Let $\begin{matrix} A = [a] \cup [b] \cup [c] \subseteq N . \end{matrix}$ Clearly, A is a c.e. set (A is finite). Let $U = ⋃_{i \in A} I_{i}$ . Let $j \in N$ . Then $\begin{matrix} J_{j} \subset_{F} J_{a, b, c} ⟺ J_{j} \subseteq_{A} U . \end{matrix}$ Note that $U = J_{a} \cup J_{b} \cup J_{c}$ . Therefore $K \subseteq U$ and Proposition 4.13 imply that there exists $μ > 0$ such that μ is a $(K, A, U)$ -augmentator. Hence, if $j \in N$ is such that $K \subseteq_{μ} J_{j}$ , then $J_{j} \subseteq_{A} U$ , i.e. if $j \in N$ is such that $K \subseteq_{μ} J_{j}$ , then $J_{j} \subset_{F} J_{a, b, c}$ . This means that μ is a $(K, a, b, c)$ -augmentator. □

Let $(X, d, α)$ be a computable metric space and let A and B be c.e. subsets of $N$ . Let $U = ⋃_{i \in A} I_{i}$ and $V = ⋃_{j \in B} I_{j}$ . Furthermore, let $K \subseteq X$ , $l, i_{0}, p, j_{0} \in N$ and $ε > 0$ . We say that the ordered pair $(p, j_{0})$ is an ϵ-locator for the ordered pair $(l, i_{0})$ (with respect to $A, B, K$ ) and we write $\begin{matrix} {(p, j_{0})}_{ϵ} ⪯ (l, i_{0}) \end{matrix}$ if $(l, i_{0})$ is a $2 ϵ$ -locator, $(p, j_{0})$ is an ϵ-locator and $\begin{matrix} J_{{(p)}_{j_{0}}, {(p)}_{j_{0} + 1}, {(p)}_{j_{0} + 2}} \subset_{F} J_{{(l)}_{i_{0}}, {(l)}_{i_{0} + 1}, {(l)}_{i_{0} + 2}} . \end{matrix}$ Proposition 4.19.
Let $(X, d, α)$ be a computable metric space, A and B c.e. subsets of $N$ , $U = ⋃_{i \in A} I_{i}$ , $V = ⋃_{j \in B} I_{j}$ , $a, b \in X$ , $K \subseteq X$ , $l, i_{0} \in N$ and $ε > 0$ . Suppose K is a continuum chainable from a to b and $(l, i_{0})$ is an ε-locator. Then there exist $p, j_{0} \in N$ such that ${(p, j_{0})}_{\frac{ϵ}{2}} ⪯ (l, i_{0})$ .
Proof.
Since $(l, i_{0})$ is an ϵ-locator, $J_{{(l)}_{0}}, \dots, J_{{(l)}_{\overline{l}}}$ is an open chain which covers K from a to b. Specially, the family $\begin{matrix} F = {J_{{(l)}_{0}}, \dots, J_{{(l)}_{\overline{l}}}} \end{matrix}$ is an open cover of K. Let λ be a Lebesgue number of $F$ for K. Let $s > 0$ be such that $\begin{matrix} (20) & B (a, s) \subseteq J_{{(l)}_{0}} and B (b, s) \subseteq J_{{(l)}_{\overline{l}}} . \end{matrix}$ Let $K_{0}, \dots, K_{m}$ be a compact $(U, V)$ - $min {λ, s, \frac{ϵ}{4}}$ -chain which covers K from a to b and such that $K_{0} \subseteq U$ and $K_{m} \subseteq V$ . Such a chain exists by Proposition 3.5. Note that $K_{0}, \dots, K_{m}$ refines $J_{{(l)}_{0}}, \dots, J_{{(l)}_{\overline{l}}}$ because $diam K_{i} < λ$ for each $i \in {0, \dots, m}$ . It follows from (20) and $diam K_{0} < s$ , $diam K_{m} < s$ that $\begin{matrix} K_{0} \subseteq J_{{(l)}_{0}} and K_{m} \subseteq J_{{(l)}_{\overline{l}}} . \end{matrix}$ Note that $K_{0}, \dots, K_{m}$ and $J_{{(l)}_{0}}, \dots, J_{{(l)}_{\overline{l}}}$ are simple chains because K is connected. Since $J_{{(l)}_{0}} \subseteq_{A} U$ and $J_{{(l)}_{\overline{l}}} \subseteq_{B} V$ , we have $K_{0} \subseteq U$ and $K_{m} \subseteq V$ . By Proposition 3.9 there exists $j_{0} \in {0, \dots, m - 2}$ such that $\begin{matrix} K_{j_{0}} \subseteq U, K_{j_{0} + 2} \subseteq V \end{matrix}$ and such that $\begin{matrix} K_{j_{0}} \cup K_{j_{0} + 1} \cup K_{j_{0} + 2} \subseteq J_{{(l)}_{i_{0}}} \cup J_{{(l)}_{i_{0} + 1}} \cup J_{{(l)}_{i_{0} + 2}} . \end{matrix}$ By Lemma 4.18 there exist $μ_{0}$ which is a $(K_{j_{0}}, {(l)}_{i_{0}}, {(l)}_{i_{0} + 1}, {(l)}_{i_{0} + 2})$ -augmentator, $μ_{1}$ which is a $(K_{j_{0} + 1}, {(l)}_{i_{0}}, {(l)}_{i_{0} + 1}, {(l)}_{i_{0} + 2})$ -augmentator and $μ_{2}$ which is a $(K_{j_{0} + 2}, {(l)}_{i_{0}}, {(l)}_{i_{0} + 1}, {(l)}_{i_{0} + 2})$ -augmentator. Let $\begin{matrix} μ = min {μ_{0}, μ_{1}, μ_{2}} . \end{matrix}$ In the same way as in the proof of Proposition 4.17 we can find $r > 0$ such that for all $i, j \in {0, \dots, m}$ the following implications hold: $\begin{array}{l} K_{i} \cap K_{j} = \emptyset ⟹ r is a (K_{i}, K_{j}) -separator \\ K_{i} \subseteq U ⟹ r is a (K_{i}, A, U) -augmentator \\ K_{i} \subseteq V ⟹ r is a (K_{i}, B, V) -augmentator \\ r < min {μ, \frac{ε}{16}} . \end{array}$

By Lemma 4.8 for each $i \in {0, \dots, m}$ we can choose $k_{i} \in N$ such that $\begin{matrix} K_{i} \subseteq_{r} J_{k_{i}} . \end{matrix}$ Let $p \in N$ be a number such that: $\begin{matrix} ({(p)}_{0}, \dots, {(p)}_{\overline{p}}) = (k_{0}, \dots, k_{m}) . \end{matrix}$ As in the proof of Proposition 4.17, we conclude that $(p, j_{0})$ is an $\frac{ϵ}{2}$ -locator. Since r is a $(K_{j_{0}}, {(l)}_{i_{0}}, {(l)}_{i_{0} + 1}, {(l)}_{i_{0} + 2})$ -augmentator and $K_{j_{0}} \subseteq_{r} J_{k_{j_{0}}}$ , i.e. $K_{j_{0}} \subseteq_{r} J_{{(p)}_{j_{0}}}$ , we have $\begin{matrix} J_{{(p)}_{j_{0}}} \subset_{F} J_{{(l)}_{i_{0}}, {(l)}_{i_{0} + 1}, {(l)}_{i_{0} + 2}} . \end{matrix}$ In the same way we conclude that $\begin{array}{l} J_{{(p)}_{j_{0} + 1}} \subset_{F} J_{{(l)}_{i_{0}}, {(l)}_{i_{0} + 1}, {(l)}_{i_{0} + 2}} \\ J_{{(p)}_{j_{0} + 2}} \subset_{F} J_{{(l)}_{i_{0}}, {(l)}_{i_{0} + 1}, {(l)}_{i_{0} + 2}} . \end{array}$ Hence $\begin{matrix} J_{{(p)}_{j_{0}}, {(p)}_{j_{0} + 1}, {(p)}_{j_{0} + 2}} \subset_{F} J_{{(l)}_{i_{0}}, {(l)}_{i_{0} + 1}, {(l)}_{i_{0} + 2}} \end{matrix}$ and we have proved that $(p, j_{0})$ is an $\frac{ϵ}{2}$ -locator for $(l, i_{0})$ . □

5. Totally disconnected intersection

A topological space X is said to be totally disconnected if every connected component of X is a one-point set. In other words, X is totally disconnected if the only connected subsets of X are one-point sets.

Let $(X, d, α)$ be a computable metric space, let U and V be disjoint computably enumerable open sets in this space and let $K \subseteq X$ be a continuum chainable from a to b, where $a \in U$ and $b \in V$ . Let $S = X ∖ (U \cup V)$ . In this section we will prove that implication (1) from Section 1 holds under the assumption that $K \cap S$ is totally disconnected. We will also see how this result implies that (1) holds if K is an arc (without the assumption that $K \cap S$ is totally disconnected).

The idea how to get this is to use $(U, V)$ -chains. More precisely, the idea is to use the fact that for each $ε > 0$ there exists a compact $(U, V)$ -ε-chain in $(X, d)$ which covers K. And this is the reason why we need the assumption that $K \cap S$ is totally disconnected. Namely, by Proposition 3.5 and Corollary 3.6, it is possible for any $ε > 0$ to cover K by a compact/open $(U, V)$ -ε-chain if and only if $K \cap S$ is zero-dimensional; however, zero-dimensionality of the set $K \cap S$ is equivalent to its total disconnectedness. This is a consequence of the following fact.

Proposition 5.1.
Let $(X, d)$ be a compact metric space. Then $(X, d)$ is zero-dimensional if and only if it is totally disconnected.

Indeed, if $(X, d)$ is zero-dimensional, then by Proposition 3.4 for each $ε > 0$ there exist finitely many mutually disjoint open sets whose diameters are less than ε and which cover X and this means that for any $ε > 0$ and any $x \in X$ there exists a separation $(A, B)$ of $(X, d)$ such that $x \in A$ and $diam A < ε$ . This clearly implies that the only connected subsets of $(X, d)$ are one-point sets. Conversely, it is not obvious that the total disconnectedness of $(X, d)$ implies its zero-dimensionality. We can conclude this from Theorem (6.C.4) in [5] (see also [7]). Namely, by that theorem for each $ε > 0$ there exist finitely many mutually disjoint open sets whose diameters are less than ε and which cover X, hence $(X, d)$ is zero-dimensional (Proposition 3.4).

Thus Proposition 5.1, Proposition 3.5 and Corollary 3.6 show that the assumption of total disconnectedness of the set $K \cap S$ is necessary if we want to use the fact that for any $ε > 0$ we can cover K by a compact/open $(U, V)$ -ε-chain.

Before the main result of this section, we state the following simple fact from the theory of computable functions.
Proposition 5.2.
Let $k \in N ∖ {0}$ , $T \subseteq N^{k}$ and $a \in T$ . Suppose $φ : T \to N^{k}$ is a partial computable function such that $φ (T) \subseteq T$ . Let $f : N \to N^{k}$ be the function defined by $\begin{matrix} f (0) = a, f (y + 1) = φ (f (y)) . \end{matrix}$ Then f is computable.
Theorem 5.3.
Let $(X, d, α)$ be a computable metric space and let U and V be disjoint c.e. open sets in X. Let $S = X ∖ (U \cup V)$ . Suppose K is a continuum in X chainable from a to b, where $a \in U$ and $b \in V$ . Suppose K is a computable set and $K \cap S$ is totally disconnected. Then $K \cap S$ contains a computable point.
Proof.
Let A and B be c.e. subsets of $N$ such that $U = ⋃_{i \in A} I_{i}$ and $V = ⋃_{i \in B} I_{i}$ . Let $\begin{matrix} T = {(l, i_{0}) \in N^{2} ∣ (l, i_{0}) is a locator}, \end{matrix}$ and let Ω be the set of all $(l, i_{0}, p, j_{0}) \in N^{4}$ such that $\begin{array}{l} (l, i_{0}) and (p, j_{0}) are locators, \\ J_{{(p)}_{j_{0}}, {(p)}_{j_{0} + 1}, {(p)}_{j_{0} + 2}} \subset_{F} J_{{(l)}_{i_{0}}, {(l)}_{i_{0} + 1}, {(l)}_{i_{0} + 2}}, \\ fmesh (p) < \frac{3}{4} fmesh (l) . \end{array}$

If $(l, i_{0}) \in T$ then $(l, i_{0})$ is a locator and in particular $(l, i_{0})$ is a $\frac{3}{2} fmesh (l)$ -locator. By Proposition 4.19 there exists some $(p, j_{0}) \in N^{2}$ such that ${(p, j_{0})}_{\frac{3}{4} fmesh (l)} ⪯ (l, i_{0})$ . Then we have that $(p, j_{0})$ is a $\frac{3}{4} fmesh (l)$ -locator and in particular $\begin{matrix} fmesh (p) < \frac{3}{4} fmesh (l) . \end{matrix}$

Hence, for each $x = (l, i_{0}) \in T$ there exists some $y = (p, j_{0}) \in T$ such that $(x, y) \in Ω$ . Then, by Proposition 2.5(ii), there exists a partial computable function $φ : T \to N^{2}$ such that $φ (T) \subseteq T$ and such that $(x, φ (x)) \in Ω$ for each $x \in T$ .

Fix some $(a_{0}, b_{0}) \in T$ . We can do this because by Proposition 4.17 and Proposition 5.1 the set T is not empty. Let $f : N \to N^{2}$ be defined by $\begin{matrix} f (0) = (a_{0}, b_{0}), f (k + 1) = φ (f (k)) . \end{matrix}$ By Proposition 5.2 f is a computable function. For each $k \in N$ we have $\begin{matrix} (f (k), φ (f (k))) \in Ω, \end{matrix}$ i.e. $\begin{matrix} (21) & (f (k), f (k + 1)) \in Ω . \end{matrix}$ Let $l : N \to N$ and $i : N \to N$ be the component functions of f. Then l and i are computable functions. By (21) for each $k \in N$ we have $\begin{matrix} (l (k), i (k), l (k + 1), i (k + 1)) \in Ω \end{matrix}$ and therefore $\begin{array}{l} (l (k), i (k)) and (l (k + 1), i (k + 1)) are locators, \\ J_{{(l (k + 1))}_{i (k + 1)}, {(l (k + 1))}_{i (k + 1) + 1}, {(l (k + 1))}_{i (k + 1) + 2}} \subset_{F} J_{{(l (k))}_{i (k)}, {(l (k))}_{i (k) + 1}, {(l (k))}_{i (k) + 2}}, \\ (22) & fmesh (l (k + 1)) < \frac{3}{4} fmesh (l (k)) . \end{array}$ For $k \in N$ let $E (k)$ be the set defined by $\begin{array}{l} E (k) = J_{{(l (k))}_{i (k)}} \cup J_{{(l (k))}_{i (k) + 1}} \cup J_{{(l (k))}_{i (k) + 2}} . \end{array}$ By Lemma 4.15 we have $\begin{matrix} (23) & J_{{(l (k))}_{i (k) + 1}} \cap S \neq \emptyset . \end{matrix}$ Also note that for each $k \in N$ we have $\begin{matrix} diam (E (k)) ⩽ 3 fmesh (l (k)) \end{matrix}$ and since $fmesh (l (k)) ⩽ {(\frac{3}{4})}^{k} fmesh (l (0))$ , which follows from (22), we have $\begin{matrix} (24) & diam (E (k)) ⩽ 3 {(\frac{3}{4})}^{k} fmesh (l (0)) . \end{matrix}$ Therefore $\begin{matrix} (25) & diam (E (k)) \to 0 as k \to \infty . \end{matrix}$ We have $\begin{matrix} Cl (E (k + 1)) \subseteq Cl (E (k)) \end{matrix}$ since $E (k + 1) \subseteq E (k)$ and therefore $\begin{matrix} K \cap Cl (E (k + 1)) \subseteq K \cap Cl (E (k)) . \end{matrix}$

In general, if $(p, j_{0})$ is a locator, then each of the sets $J_{{(p)}_{0}}$ , …, $J_{{(p)}_{\overline{p}}}$ intersects K, which follows easily from the fact that K is connected. Therefore the set $K \cap Cl (E (k))$ is nonempty and closed in K for each $k \in N$ and $diam (K \cap Cl (E (k))) \to 0$ as $k \to \infty$ . Since K is compact, the sets $K \cap Cl (E (k))$ , $k \in N$ , have nonempty intersection (we can conclude this from Cantor’s intersection theorem). Hence there exists $x \in X$ such that $\begin{matrix} x \in ⋂_{k \in N} K \cap Cl (E (k)) . \end{matrix}$

We claim that $x \in S$ . Otherwise, since S is closed, there exists $r > 0$ such that $B (x, r) \subseteq S^{c}$ . By (25) there exists $k \in N$ such that $diam (Cl (E (k))) < r$ and since $x \in Cl (E (k))$ we have $\begin{array}{l} Cl (E (k)) \subseteq B (x, r) \subseteq S^{c}, \end{array}$ so $\begin{matrix} E (k) \cap S = \emptyset . \end{matrix}$ But this is a contradiction to (23).

Hence $x \in K \cap S$ . But x is a computable point. Namely, it is obvious from the definition of the sets $E (k)$ , $J_{j}$ and $I_{i}$ that there exists a computable function $f : N \to N$ such that $α_{f (k)} \in E (k)$ for each $k \in N$ . It follows from (24) that $\begin{matrix} d (x, α_{f (k)}) ⩽ 3 {(\frac{3}{4})}^{k} fmesh (l (0)), \end{matrix}$ for each $k \in N$ . Choose $M \in N$ so that $3 {(\frac{3}{4})}^{M} fmesh (l (0)) < 1$ . Then $\begin{matrix} d (x, α_{f (3 k + M)}) < 2^{- k} \end{matrix}$ for each $k \in N$ and we have that x is a computable point. Thus $K \cap S$ contains a computable point. □

In the following result the assumption of total disconnectedness disappears.
Theorem 5.4.
Let $(X, d, α)$ be a computable metric space and let U and V be disjoint c.e. open sets in X. Let $S = X ∖ (U \cup V)$ . Suppose A is an arc in X with endpoints a and b such that $a \in U$ and $b \in V$ . Suppose A is a computable set. Then $A \cap S$ contains a computable point.
Proof.
Since A is an arc with endpoints a and b, A is a continuum chainable from a to b ([16]). If $A \cap S$ is totally disconnected, then $A \cap S$ contains a computable point by Theorem 5.3.

Suppose $A \cap S$ is not totally disconnected. Then there exists a set C which is connected in $A \cap S$ and such that C has more than one point. Then C is also connected in A and we claim that there exists an open set W in A such that $W \neq \emptyset$ and $W \subseteq C$ .

However, this follows from the fact that A is homeomorphic to $[0, 1]$ : if D is a connected set in $[0, 1]$ which contains more than one point, then for any $x, y \in D$ , $x < y$ , we have $[x, y] \subseteq D$ and therefore the open interval $⟨ x, y ⟩$ is a nonempty open set in $[0, 1]$ contained in D.

Since A is a computable set, there exists a computable sequence in $(X, d, α)$ which is dense in A (see e.g. Proposition 3.3. in [9]). In particular, the set of all computable points in $(X, d, α)$ which lie in A is dense in A and therefore there exists a computable point c such that $c \in W$ . It follows $c \in C$ and since $C \subseteq A \cap S$ , we have $c \in A \cap S$ . □

We will see in the next section that the assumption of Theorem 5.3 that K is chainable from a to b, where $a \in U$ and $b \in V$ and the assumption of Theorem 5.4 that such a and b are endpoints of A can be weakened by assuming only that K and A intersect both U and V (Theorem 6.14).

The technique of $(U, V)$ -chains used in the proof of Theorem 5.3 justifies the assumption of the theorem that $K \cap S$ is totally disconnected (Proposition 5.1, Proposition 3.5 and Corollary 3.6). Theorem 5.4 shows that this assumption can be dropped if K is an arc; the key in the proof of that theorem was the fact that any connected subset of K having at least two points has a nonempty interior in K, hence if $K \cap S$ is not totally disconnected, then the interior of $K \cap S$ in K is nonempty (and therefore it contains a computable point).

In general, however, the fact that $K \cap S$ is not totally disconnected does not imply that the interior of $K \cap S$ in K is nonempty, as the following example shows. Example 5.5.
Let $\begin{matrix} L = {(x, sin \frac{1}{x}) | x \in [- 1, 0 ⟩}, M = {0} \times [- 1, 1], R = {(x, sin \frac{1}{x}) | x \in ⟨ 0, 1]} . \end{matrix}$ Let $a = (- 1, sin (- 1))$ , $b = (1, sin 1)$ and $K = L \cup M \cup R$ . Then K is a continuum in $R^{2}$ chainable from a to b. Let $\begin{matrix} U = ⟨ - \infty, 0 ⟩ \times R, V = ⟨ 0, \infty ⟩ \times R and S = R^{2} ∖ (U \cup V) . \end{matrix}$ Then U and V are disjoint open sets in $R^{2}$ and $a \in U$ , $b \in V$ .

Clearly $K \cap S = M$ . For each $x \in M$ and each $ε > 0$ there exist $y \in L$ and $z \in R$ such that $d (x, y) < ε$ and $d (x, z) < ε$ (where d is the Euclidean metric), which shows that the interior of M in K is empty.

Hence $K \cap S$ is not totally disconnected, but the interior of $K \cap S$ in K is empty.

Note that we get the same conclusion if we take $L = [- 1, 0] \times {- 1}$ and $a = (- 1, - 1)$ .

6. Connected intersection and semi-computability

Let $(X, d, α)$ be a computable metric space, U and V disjoint c.e. open sets and K a computable set in this space. Let $S = X ∖ (U \cup V)$ . Suppose K is chainable from $a \in U$ to $b \in V$ . The main result of the previous section says that $K \cap S$ contains a computable point if $K \cap S$ is totally disconnected. In this section we seek for some other conditions under which $K \cap S$ contains a computable point.

Let us take the completely opposite assumption, that $K \cap S$ is connected. What can be said in this case about $K \cap S$ and computable points in $K \cap S$ ?

Since $K \cap S$ is compact, we have that $K \cap S$ is a continuum and, as a subcontinuum of the chainable continuum K, $K \cap S$ is also a chainable continuum.

Since arcs are natural representatives of chainable continua, the following question arises: what can we say about computable points in $K \cap S$ in the case when $K \cap S$ is an arc? In contrast to the case when K is an arc (Theorem 5.4), in the case when $K \cap S$ is an arc we cannot conclude that $K \cap S$ contains a computable point simply because they are dense in K, namely the interior of $K \cap S$ in K may be empty (Example 5.5).

Nevertheless, we are going to prove that $K \cap S$ contains a computable point if $K \cap S$ is an arc. Actually, we are going the prove a more general result. This generalization will have two directions:

the claim holds not just when $K \cap S$ is an arc, but when $K \cap S$ is any decomposable continuum;

the claim holds not just for sets A of the form $K \cap S$ , but for any semi-computable set A; hence every semi-computable set A which is a decomposable chainable continuum contains a computable point (we will see that $K \cap S$ is always a semi-computable set).

Let $(X, d, α)$ be a computable metric space and let $S \subseteq X$ . We say that S is a co-computably enumerable (co-c.e.) set in $(X, d, α)$ if $X ∖ S$ is a c.e. open set in $(X, d, α)$ .

Note that co-c.e. sets are closed. Also note that $X ∖ (U \cup V)$ is a co-c.e. set if U and V are c.e. open.

There is a connection between semi-computable sets and co-c.e. sets. Each semi-computable set is co-c.e. [10]. On the other hand, a co-c.e. set need not be semi-computable even if it is compact: there is a computable metric space $(X, d, α)$ and a point $x \in X$ such that ${x}$ is a co-c.e. set, but x is not a computable point (see e.g. Example 3.2. in [9]) which easily implies that ${x}$ is not a semi-computable set. However, if we assume that the ambient computable metric space is locally computable, then each compact co-c.e. set is semi-computable [10]. A computable metric space $(X, d, α)$ is locally computable if for each compact set A in $(X, d)$ there exists a computable set K in $(X, d, α)$ such that $A \subseteq K$ [1].

Lemma 6.1.
Let $(X, d, α)$ be a computable metric space and let K be a semi-computable set in $(X, d, α)$ . Then the sets ${(i, j) \in N^{2} ∣ K \subseteq J_{i} \cup J_{j}}$ and ${(i, j, k) \in N^{3} ∣ K \subseteq J_{i} \cup J_{j} \cup J_{k}}$ are c.e.
Proof.
It is easy to conclude from Proposition 2.4 that there exist computable functions $f : N^{2} \to N$ and $g : N^{3} \to N$ such that $J_{f (i, j)} = J_{i} \cup J_{j}$ and $J_{g (i, j, k)} = J_{i} \cup J_{j} \cup J_{k}$ for all $i, j, k \in N$ . The claim of the lemma now follows from Proposition 2.5(iii). □
Proposition 6.2.
Let $(X, d, α)$ be a computable metric space, let K be a semi-computable set and let S be a co-c.e. set in $(X, d, α)$ . Then $K \cap S$ is semi-computable.
Proof.
If $S = X$ , the claim is obvious. Suppose $S \neq X$ . Using Proposition 2.4 and the definition of a c.e. open set we conclude that there exists a computable function $f : N \to N$ such that $\begin{matrix} (26) & X ∖ S = ⋃_{i \in N} J_{f (i)} and J_{f (i)} \subseteq J_{f (i + 1)} for each i \in N . \end{matrix}$

Let $j \in N$ . Suppose $K \cap S \subseteq J_{j}$ . Then $K ∖ J_{j} \subseteq X ∖ S$ . This and the fact that $K ∖ J_{j}$ is compact imply, together with (26), that there exists $i \in N$ such that $K ∖ J_{j} \subseteq J_{f (i)}$ . Hence $\begin{matrix} (27) & K \subseteq J_{f (i)} \cup J_{j} . \end{matrix}$ Conversely, if $i \in N$ is such that (27) holds, then $K \cap S \subseteq J_{j}$ since $S \cap J_{f (i)} = \emptyset$ . So we have the conclusion that $K \cap S \subseteq J_{j}$ if and only if there exists $i \in N$ such that (27) holds. Since the set of all $(j, i) \in N^{2}$ such that (27) holds is c.e. (Lemma 6.1 and Proposition 2.5(iii)), the projection theorem implies that the set ${j \in N ∣ K \cap S \subseteq J_{j}}$ is c.e. □

What can be said in general about computability of semi-computable sets? The discussion in the introduction now shows that there exist nonempty semi-computable sets which do not contain any computable point. In particular, a semi-computable set need not be computable. However, there are certain conditions under which semi-computable sets are computable or at least contain computable points [1,4,8,10,14]. We are here in particular interested in the case that a semi-computable set is a chainable continuum. Such a set need not be computable, even if it is an arc [14]. The results from [8] give certain conditions under which a semi-computable chainable continuum is computable or has a computable point. These results are given in [9] in a somewhat more general form and they can be expressed in the following way: if $(X, d, α)$ is a computable metric space which is locally computable and if S is a semi-computable chainable continuum in $(X, d, α)$ , then
if S is decomposable, then for each $ε > 0$ there exists a computable subcontinuum $S^{'}$ of S such that $ρ (S, S^{'}) < ε$ , where ρ is the Hausdorff metric (in particular, S contains computable points);

if S is chainable from a to b, where a and b are computable points, then S is computable.
That a continuum K is decomposable means that there exist proper subcontinua $K_{1}$ and $K_{2}$ of K such that $K_{1} \cup K_{2} = K$ (proper means $K_{1} \neq K$ and $K_{2} \neq K$ ). If a continuum is not decomposable, we say that it is indecomposable. For example, $[0, 1]$ is clearly a decomposable continuum and consequently any arc is decomposable; the continuum K from Example 5.5 is also decomposable. On the other hand, it is much harder to find an example of an indecomposable continuum (apart from a point); such an example can be found in [16] (Example 1.10).

Result (9-1) is important in view of the problem that we study in this paper, the problem under what conditions $K \cap S$ contains a computable point if K is computable chainable continuum and $S = X ∖ (U \cup V)$ , where U and V are c.e. open. In the special case when $K \cap S$ is a decomposable continuum, claim (9-1) (together with Proposition 6.2) gives that $K \cap S$ contains a computable point, however only if the computable metric space is locally computable.

Our goal now is to show that the assumption that $(X, d, α)$ is locally computable can be removed from the above results, i.e. to show that (9-1) and (9-2) hold in any computable metric space. To do this, we will rely on ideas from [8] (Theorem 42 and Theorem 44).

Suppose A and B are sets. A finite sequence of sets $C_{0}, \dots, C_{m}$ is said to be $(A, B)$ -directed if there exist $i, j \in {0, \dots, m}$ such that $C_{i} \cap A \neq \emptyset$ , $B \cap C_{j} \neq \emptyset$ and $\begin{matrix} max {i \in {0, \dots, m} ∣ C_{i} \cap A \neq \emptyset} + 1 < min {j \in {0, \dots, m} ∣ C_{j} \cap B \neq \emptyset} . \end{matrix}$
Lemma 6.3.
Let $(K, d)$ be a chainable continuum and let $K_{1}$ and $K_{2}$ be its subcontinua such that $K = K_{1} \cup K_{2}$ . Suppose A and B are nonempty closed sets in $(K, d)$ such that $A \subseteq K_{1} ∖ K_{2}$ and $B \subseteq K_{2} ∖ K_{1}$ . Then for each $ε > 0$ there exists a compact ε-chain in $(K, d)$ which covers K and which is $(A, B)$ -directed.
Proof.
The sets A, B, $K_{1}$ and $K_{2}$ are compact and $A \cap K_{2} = \emptyset$ , $B \cap K_{1} = \emptyset$ . Therefore the numbers $r_{1} = d (A, K_{2})$ and $r_{2} = d (B, K_{1})$ are positive. Let $r = min {r_{1}, r_{2}}$ . Then for every $S \subseteq K$ such that $diam S < r$ the following implications hold: $\begin{matrix} (28) & (S \cap A \neq \emptyset \Rightarrow S \cap K_{2} = \emptyset) and (S \cap B \neq \emptyset \Rightarrow S \cap K_{1} = \emptyset) . \end{matrix}$ Let $ε > 0$ . By Proposition 3.3 there exists a compact $min {ε, r}$ -chain $D_{0}, \dots, D_{m}$ in $(K, d)$ which covers K. The connectedness of $(K, d)$ implies that $D_{0}, \dots, D_{m}$ is a simple chain. Let $i_{0}$ be the smallest $i \in {0, \dots, m}$ such that $D_{i}$ intersects A or B. We have two cases: $D_{i_{0}} \cap A \neq \emptyset$ or $D_{i_{0}} \cap B \neq \emptyset$ .

Suppose $D_{i_{0}} \cap A \neq \emptyset$ . We claim that $D_{0}, \dots, D_{m}$ is $(A, B)$ -directed. Suppose the opposite. Let $v = max {i \in {0, \dots, m} ∣ D_{i} \cap A \neq \emptyset}$ and $w = min {j \in {0, \dots, m} ∣ D_{j} \cap B \neq \emptyset}$ . Then $w ⩽ v + 1$ . By (28) we have $\begin{matrix} (29) & D_{i_{0}} \cap K_{2} = \emptyset, D_{v} \cap K_{2} = \emptyset and D_{w} \cap K_{1} = \emptyset . \end{matrix}$ This gives $w \neq v + 1$ ; namely $w = v + 1$ implies $D_{v} \cap D_{w} \neq \emptyset$ , hence by (29) there is a point in K which lies neither in $K_{1}$ nor in $K_{2}$ . So $w < v + 1$ , i.e. $w ⩽ v$ . However, the same argument shows that $w < v$ . By definition of $i_{0}$ we have $i_{0} ⩽ w$ and again $i_{0} < w$ . Thus $i_{0} < w < v$ and it follows that $\begin{matrix} D_{0} \cup \dots \cup D_{w - 1} and D_{w + 1} \cup \dots \cup D_{v} \end{matrix}$ are disjoint closed sets in $(K, d)$ which cover $K_{1}$ (by (29)) and such that each of these sets intersects $K_{1}$ (since $D_{i_{0}} \cap A \neq \emptyset$ and $D_{v} \cap A \neq \emptyset$ ). This is impossible since $K_{1}$ is connected. Hence $D_{0}, \dots, D_{m}$ is $(A, B)$ -directed.

Suppose now $D_{i_{0}} \cap B \neq \emptyset$ . In the same way we get that $D_{0}, \dots, D_{m}$ is $(B, A)$ -directed. But then $D_{m}, \dots, D_{0}$ is $(A, B)$ -directed and this is a desired compact ε-chain. □

Let $(X, d, α)$ be a computable metric space. Let $u, v \in N$ . We say that $J_{u}$ is formally contained in $J_{v}$ and we write $J_{u} \subset_{F} J_{v}$ if for each $i \in [u]$ there exists $j \in [v]$ such that $I_{i} \subset_{F} I_{j}$ . Note that $J_{u} \subset_{F} J_{v}$ if and only if $J_{u} \subseteq_{[v]} U$ , where $U = J_{v}$ . Furthermore, if $l, v \in N$ , then we say that $H_{l}$ if formally contained in $J_{v}$ and we write $H_{l} \subset_{F} J_{v}$ if $J_{u} \subset_{F} J_{v}$ for each $v \in [l]$ . Finally, if $l, l^{'} \in N$ , we say that $H_{l}$ formally refines $H_{l^{'}}$ and we write $H_{l} ⩽ H_{l^{'}}$ if for each $i \in [l]$ there exits $j \in [l^{'}]$ such that $J_{i} \subset_{F} J_{j}$ . We easily prove the following proposition.
Proposition 6.4.
Let $(X, d, α)$ be a computable metric space. The sets ${(u, v) \in N^{2} ∣ J_{u} \subset_{F} J_{v}}$ , ${(l, v) \in N^{2} ∣ H_{l} \subset_{F} J_{v}}$ and ${(l, l^{'}) \in N^{2} ∣ H_{l} ⩽ H_{l^{'}}}$ are c.e.

Let $(X, d, α)$ be a computable metric space. For $i \in N$ we define ${\hat{I}}_{i} = \overline{B} (λ_{i}, ρ_{i})$ . For $j \in N$ we define $\begin{matrix} {\hat{J}}_{j} = ⋃_{i \in [j]} {\hat{I}}_{i} . \end{matrix}$ Note this: if $i, j \in N$ are such that $I_{i}$ and $I_{j}$ are formally disjoint, then ${\hat{I}}_{i} \cap {\hat{I}}_{j} = \emptyset$ . Consequently, if $u, v \in N$ are such that $J_{u}$ and $J_{v}$ are formally disjoint, then ${\hat{J}}_{u} \cap {\hat{J}}_{v} = \emptyset$ . Furthermore, if $I_{i} \subset_{F} I_{j}$ , then ${\hat{I}}_{i} \subseteq I_{j}$ . So if $J_{u} \subset_{F} J_{v}$ , then ${\hat{J}}_{u} \subseteq J_{v}$ .

Clearly, for each $j \in N$ the set ${\hat{J}}_{j}$ is closed in $(X, d)$ and since $J_{j} \subseteq {\hat{J}}_{j}$ we have $Cl (J_{j}) \subseteq {\hat{J}}_{j}$ . Therefore, we have the following conclusion.
Proposition 6.5.
Let $(X, d, α)$ be a computable metric space. Let $l, l^{'}, u, v \in N$ . The following statements hold:
if $J_{u} \subset_{F} J_{v}$ , then $Cl (J_{u}) \subseteq J_{v}$ .

if $H_{l} ⩽ H_{l^{'}}$ , then the finite sequence $Cl (J_{{(l)}_{0}}), \dots, Cl (J_{{(l)}_{\overline{l}}})$ refines the finite sequence $J_{{(l^{'})}_{0}}, \dots, J_{{(l^{'})}_{\overline{l^{'}}}}$ .

Lemma 6.6.
Let $(X, d, α)$ be a computable metric space and let S be a nonempty compact set in $(X, d)$ . Suppose there exists a computable function $f : N \to N$ such that, for each $k \in N$ , $fdiam (f (k)) < 2^{- k}$ , $S \subseteq ⋃ H_{f (k)}$ and each of the sets in the finite sequence $H_{f (k)}$ intersects S. Then S is a computable set.
Proof.
It is immediate from definition of the sequence of sets $(J_{j})$ that there exists a computable function $g : N \to N$ such that $α_{g (j)} \in J_{j}$ for each $j \in N$ . The function $N \to P (N)$ , $l \mapsto {g ({(l)}_{0}), \dots, g ({(l)}_{\overline{l}})} = g ([l])$ is e.f.v. and therefore there exists a computable function $φ : N \to N$ such that $[φ (l)] = g ([l])$ for each $l \in N$ (Proposition 2.4). Recall the definition of the sequence of sets $(Λ_{l})$ (Proposition 2.3). Let $l \in N$ . We have $\begin{matrix} Λ_{φ (l)} = {α_{g ({(l)}_{0})}, \dots, α_{g ({(l)}_{\overline{l}})}} \end{matrix}$ and we conclude the following: $Λ_{φ (l)} \subseteq ⋃ H_{l}$ and each set in the finite sequence $H_{l}$ intersects $Λ_{φ (l)}$ . It follows from the assumption of the proposition that for each $k \in N$ the following holds: for each $x \in S$ there exists $y \in Λ_{φ (f (k))}$ such that $d (x, y) < 2^{- k}$ and for each $y \in Λ_{φ (f (k))}$ there exists $x \in S$ such that $d (y, x) < 2^{- k}$ . Therefore $ρ (S, Λ_{f (k)}) ⩽ 2^{- k}$ for each $k \in N$ , where ρ is the Hausdorff metric and it follows from Proposition 2.3 that S is computable. □

Let $(X, d, α)$ be a computable metric space. Suppose $S \subseteq X$ is a semi-computable chainable continuum, $K_{1}$ and $K_{2}$ subcontinua of S whose union is S and $a \in K_{1} ∖ K_{2}$ , $b \in K_{2} ∖ K_{1}$ . Theorem 42 in [8] says that we can find computable points $a^{'}$ and $b^{'}$ arbitrary close to a and b and a computable subcontinuum of S chainable from $a^{'}$ to $b^{'}$ . However, the assumption of that theorem is that the ambient space $(X, d, α)$ has compact closed balls and the effective covering property. That $(X, d, α)$ has the effective covering property means that the set ${(i, j) \in N^{2} ∣ {\hat{I}}_{i} \subseteq J_{j}}$ is c.e. If $(X, d, α)$ has compact closed balls and the effective covering property, then $(X, d, α)$ is locally computable [9]. Now we show that these assumptions on the ambient space can be removed. This is the contents of the next theorem. In its proof we will use ideas from the proof of Theorem 42 in [8] and we will rely on techniques from Section 4. First we need the following definition.

Let $(X, d, α)$ be a computable metric space and let $p, l, q \in N$ . We say that the triple $(p, l, q)$ is a formal chain if
$J_{p}$ and $J_{{(l)}_{i}}$ are formally disjoint for each $i \in {1, \dots, \overline{l}}$ ;

$H_{l}$ is a formal chain;

$J_{{(l)}_{i}}$ and $J_{q}$ are formally disjoint for each $i \in {0, \dots, \overline{l} - 1}$ .
If $(p, l, q)$ is a formal chain, then $\begin{matrix} J_{p}, J_{{(l)}_{0}}, \dots, J_{{(l)}_{\overline{l}}}, J_{q} \end{matrix}$ is clearly a chain. It is easy to conclude that the set of all triples $(p, l, q)$ , which are formal chains, is c.e.
Theorem 6.7.
Let $(X, d, α)$ be a computable metric space and let S be a semi-computable set in this space such that S, as a subspace of $(X, d)$ , is a chainable continuum. Let $K_{1}$ and $K_{2}$ be subcontinua of S such that $S = K_{1} \cup K_{2}$ and let $a \in K_{1} ∖ K_{2}$ and $b \in K_{2} ∖ K_{1}$ . Then for each $ε > 0$ there exist computable points $a^{'}, b^{'} \in S$ such that $d (a, a^{'}) < ε$ , $d (b, b^{'}) < ε$ and a computable subcontinuum of S chainable from $a^{'}$ to $b^{'}$ .
Proof.
Let $ε > 0$ . Let $\begin{matrix} r = \frac{1}{4} min {ε, d (a, K_{2}), d (b, K_{1}), 1} . \end{matrix}$ For each $x \in S ∖ B (a, 2 r)$ there exists $i \in N$ such that $x \in I_{i}$ and $I_{i} \cap B (a, r) = \emptyset$ . Since $S ∖ B (a, 2 r)$ is compact, we conclude that there exist finitely many rational balls which cover $S ∖ B (a, 2 r)$ and such that none of these balls intersects $B (a, r)$ . Hence there exists $\tilde{b} \in N$ such that $\begin{matrix} (30) & S ∖ B (a, 2 r) \subseteq J_{\tilde{b}} and J_{\tilde{b}} \cap B (a, r) = \emptyset . \end{matrix}$ In the same way we get $\tilde{a} \in N$ such that $\begin{matrix} (31) & S ∖ B (b, 2 r) \subseteq J_{\tilde{a}} and J_{\tilde{a}} \cap B (b, r) = \emptyset . \end{matrix}$ Since $B (a, 2 r) \cap K_{2} = \emptyset$ , we have $K_{2} \subseteq J_{\tilde{b}}$ . Similarly, $K_{1} \subseteq J_{\tilde{a}}$ . We conclude that $\begin{matrix} (32) & S ∖ J_{\tilde{b}} \subseteq K_{1} ∖ K_{2} and S ∖ J_{\tilde{a}} \subseteq K_{2} ∖ K_{1} . \end{matrix}$ We also conclude from (30) and (31) that $a \in S ∖ J_{\tilde{b}}$ and $b \in S ∖ J_{\tilde{a}}$ .

The idea how to get a desired subcontinuum is to consider chains which cover S and which are $(S ∖ J_{\tilde{b}}, S ∖ J_{\tilde{a}})$ -directed. If $C$ is such a chain, then $C$ is of the form $U_{0}, \dots, U_{p}, C_{0}, \dots, C_{m}, V_{0}, \dots, V_{q}$ , where $U_{0}, \dots, U_{p}, C_{0}, \dots, C_{m}$ are contained in $J_{\tilde{a}}$ and $C_{0}, \dots, C_{m}, V_{0}, \dots, V_{q}$ are contained in $J_{\tilde{b}}$ . We will construct a sequence of such chains and prove that the intersection of the union of middle links $C_{0} \cup \dots \cup C_{m}$ is a desired subcontinuum. To simplify the construction, we will consider chains of the form $U, C_{0}, \dots, C_{m}, V$ .

Let $Ω_{1}$ be the set of all $(p, l, q) \in N^{3}$ such that $\begin{matrix} (33) & S \subseteq J_{p} \cup (⋃ H_{l}) \cup J_{q} . \end{matrix}$ Then $Ω_{1}$ is c.e. Namely, by Lemma 33 from [8] there exists a computable function $ζ : N \to N$ such that $J_{ζ (l)} = ⋃ H_{l}$ for each $l \in N$ . So $(p, l, q) \in Ω_{1}$ if and only if $S \subseteq J_{p} \cup J_{ζ (l)} \cup J_{q}$ and the fact that $Ω_{1}$ is c.e. follows from Lemma 6.1.

Let $Ω_{2}$ be the set of all $(p, l, q) \in N^{3}$ such that $(p, l, q)$ is a formal chain. Let $Ω_{3}$ be the set of all $(p, l, q) \in N^{3}$ such that $\begin{matrix} (34) & J_{p} \subset_{F} J_{\tilde{a}}, H_{l} \subset_{F} J_{\tilde{a}}, H_{l} \subset_{F} J_{\tilde{b}} and J_{q} \subset_{F} J_{\tilde{b}} . \end{matrix}$ By Proposition 6.4 $Ω_{3}$ is c.e.

Let Ω be the set of all $l \in N$ for which there exist $p, q \in N$ such that $(p, l, q) \in Ω_{1} \cap Ω_{2} \cap Ω_{3}$ . By the projection theorem Ω is c.e. Finally, let Γ be the set of all $(l, l^{'}) \in N^{2}$ such that
$l, l^{'} \in Ω$ ;

$H_{l^{'}} ⩽ H_{l}$ ;

$J_{{(l^{'})}_{0}} \subset_{F} J_{{(l)}_{0}}$ , $J_{{(l^{'})}_{\overline{l^{'}}}} \subset_{F} J_{{(l)}_{\overline{l}}}$ ;

$fmesh (l^{'}) < \frac{1}{2} fmesh (l)$ .
By Proposition 6.4 and Proposition 2.1 Γ is c.e.

We first prove that there exists $l \in N$ such that $\begin{matrix} (35) & l \in Ω, fmesh (l) < r, d (a, J_{{(l)}_{0}}) < 3 r and d (b, J_{{(l)}_{\overline{l}}}) < 3 r . \end{matrix}$ By Lemma 6.3 and (32) there exists a simple compact $\frac{r}{2}$ -chain $D_{0}, \dots, D_{m}$ in S which covers S and which is $(S ∖ J_{\tilde{b}}, S ∖ J_{\tilde{a}})$ -directed. Let $\begin{matrix} (36) & v = max {i \in {0, \dots, m} ∣ D_{i} \cap (S ∖ J_{\tilde{b}}) \neq \emptyset} and w = min {j \in {0, \dots, m} ∣ D_{j} \cap (S ∖ J_{\tilde{a}}) \neq \emptyset} . \end{matrix}$ It follows that the links $D_{0}, \dots, D_{w - 1}$ are contained in $J_{\tilde{a}}$ and the links $D_{v + 1}, \dots, D_{m}$ are contained in $J_{\tilde{b}}$ . In particular $D_{v + 1}, \dots, D_{w - 1}$ are contained in both $J_{\tilde{a}}$ and $J_{\tilde{b}}$ . Consider the chain $\begin{matrix} D_{0} \cup \dots \cup D_{v}, D_{v + 1}, \dots, D_{w - 1}, D_{w} \cup \dots \cup D_{m} . \end{matrix}$ Using the technique of separators and augmentators (Proposition 4.10, Proposition 4.13 and also Lemma 4.11) we easily get that there exist $p, t_{1}, \dots, t_{w - v - 1}, q \in N$ such that
$D_{0} \cup \dots \cup D_{v} \subseteq J_{p}$ , $D_{v + 1} \subseteq J_{t_{1}}$ , …, $D_{w - 1} \subseteq J_{t_{w - v - 1}}$ , $D_{w} \cup \dots \cup D_{m} \subseteq J_{q}$ ,

$J_{p} \subset_{F} J_{\tilde{a}}$ , $J_{q} \subset_{F} J_{\tilde{b}}$ and each of the links $J_{t_{1}}$ , …, $J_{t_{w - v - 1}}$ is formally contained in both $J_{\tilde{a}}$ and $J_{\tilde{a}}$ ,

$each of the links J_{t_{1}}, \dots, J_{t_{w - v - 1}} has the formal diameter less than r$ ,

$nonadjacent elements in the finite sequence J_{p}, J_{t_{1}}, \dots, J_{t_{w - v - 1}}, J_{q} are formally disjoint$ .
Now we take $l \in N$ such that $(t_{1}, \dots, t_{w - v - 1}) = ({(l)}_{0}, \dots, {(l)}_{\overline{l}})$ and we have $(p, l, q) \in Ω_{1} \cap Ω_{2} \cap Ω_{3}$ , hence $l \in Ω$ . Clearly, $fmesh (l) < r$ . It remains to check that $d (a, J_{{(l)}_{0}}) < 3 r$ and $d (b, J_{{(l)}_{\overline{l}}}) < 3 r$ . It suffice to prove that $d (a, D_{v + 1}) < 3 r$ and $d (b, D_{w - 1}) < 3 r$ .

We have $D_{v} \cap (S ∖ J_{\tilde{b}}) \neq \emptyset$ (by definition of v) and $S ∖ J_{\tilde{b}} \subseteq B (a, 2 r)$ by (30). Thus $D_{v} \cap B (a, 2 r) \neq \emptyset$ . This, together with $D_{v} \cap D_{v + 1} \neq \emptyset$ and $diam D_{v} < r$ , gives $d (a, D_{v + 1}) < 3 r$ . In the same way we get $d (b, D_{w - 1}) < 3 r$ .

Now we prove the following: for each $l \in Ω$ there exists $l^{'} \in Ω$ such that $(l, l^{'}) \in Γ$ .

Let $l \in Ω$ . There exist $p, q \in N$ such that $(p, l, q) \in Ω_{1} \cap Ω_{2} \cap Ω_{3}$ . Let $λ > 0$ be a Lebesgue number of the open cover $\begin{matrix} {J_{p}, J_{{(l)}_{0}}, \dots, J_{{(l)}_{\overline{l}}}, J_{q}} \end{matrix}$ for S. There exists a simple compact $min {λ, \frac{fmesh (l)}{4}}$ -chain $D_{0}, \dots, D_{m}$ in S which covers S and which is $(S ∖ J_{\tilde{b}}, S ∖ J_{\tilde{a}})$ -directed. Let v and w be the numbers defined by (36). We have that $D_{v}$ intersects $S ∖ J_{\tilde{b}}$ ; since $diam D_{v} < λ$ , $D_{v}$ is contained in some of the sets $J_{p}$ , $J_{{(l)}_{0}}$ , …, $J_{{(l)}_{\overline{l}}}$ , $J_{q}$ . However, by (34) all of these sets, except the first one, are contained in $J_{\tilde{b}}$ . Therefore $D_{v} \subseteq J_{p}$ . In the same way we conclude that $D_{w} \subseteq J_{q}$ .

Since $a \notin J_{\tilde{b}}$ , we conclude from (33) and (34) that $a \in J_{p}$ . Also $b \in J_{q}$ . This means that the sets $J_{p}$ and $J_{q}$ intersect S and the connectedness of S now implies that $J_{p}, J_{{(l)}_{0}}, \dots, J_{{(l)}_{\overline{l}}}, J_{q}$ is a simple chain (and each link of this chain intersects S; in fact $J_{p} \cap S, J_{{(l)}_{0}} \cap S, \dots, J_{{(l)}_{\overline{l}}} \cap S, J_{q} \cap S$ is a simple chain).

We have $v < w$ , $D_{v} \subseteq J_{p}$ and $D_{w} \subseteq J_{q}$ . It follows from Lemma 3.8 that there exists $i \in {0, \dots, m}$ such that $v < i < w$ and such that $D_{i} \subseteq J_{{(l)}_{0}}$ . Let $v^{'}$ be the largest such i. Now $v^{'} < w$ , $D_{v^{'}} \subseteq J_{{(l)}_{0}}$ , $D_{w} \subseteq J_{q}$ and it follows from Lemma 3.8 that there exists $i \in {0, \dots, m}$ such that $v^{'} ⩽ i < w$ and such that $D_{i} \subseteq J_{{(l)}_{\overline{l}}}$ . Let $w^{'}$ be the smallest such i. We have the following conclusion: $v < v^{'} ⩽ w^{'} < w$ , $\begin{matrix} D_{v^{'}} \subseteq J_{{(l)}_{0}} and D_{w^{'}} \subseteq J_{{(l)}_{\overline{l}}} . \end{matrix}$ Let $i \in {0, \dots m}$ be such that $v^{'} < i < w^{'}$ . We claim that $D_{i}$ is contained in one of the sets $J_{{(l)}_{0}}, \dots, J_{{(l)}_{\overline{l}}}$ . Otherwise, we have $D_{i} \subseteq J_{p}$ or $D_{i} \subseteq J_{q}$ . If $D_{i} \subseteq J_{p}$ , an application of Lemma 3.8 gives a number j such that $i < j ⩽ w^{'}$ and $D_{j} \subseteq J_{{(l)}_{0}}$ . This and $v^{'} < j$ contradict the choice of the number $v^{'}$ . In the same way we get that $D_{i} \subseteq J_{q}$ yields a contradiction.

Hence the chain $D_{v^{'}}, \dots, D_{w^{'}}$ refines the chain $J_{{(l)}_{0}}, \dots, J_{{(l)}_{\overline{l}}}$ . Consider the chain $\begin{matrix} D_{0} \cup \dots \cup D_{v^{'} - 1}, D_{v^{'}}, \dots, D_{w^{'}}, D_{w^{'} + 1} \cup \dots \cup D_{m} . \end{matrix}$ We proceed now in a similar way as before and we get numbers $p^{'}, l^{'}, q^{'} \in N$ such that $(p^{'}, l^{'}, q^{'}) \in Ω_{1} \cap Ω_{2} \cap Ω_{3}$ , $H_{l^{'}} ⩽ H_{l}$ , $J_{{(l^{'})}_{0}} \subset_{F} J_{{(l)}_{0}}$ , $J_{{(l^{'})}_{\overline{l^{'}}}} \subset_{F} J_{{(l)}_{\overline{l}}}$ and $fmesh (l^{'}) < \frac{1}{2} fmesh (l)$ . Hence $(l, l^{'}) \in Γ$ .

Also note that we obtain the following simple conclusion: $\begin{matrix} (37) & if l \in Ω, then J_{{(l)}_{0}} \cap S, \dots, J_{{(l)}_{\overline{l}}} \cap S is a simple chain . \end{matrix}$

So for each $l \in Ω$ there exists $l^{'} \in Ω$ such that $(l, l^{'}) \in Γ$ and by the single-valuedness theorem there exists a partial computable function $φ : Ω \to N$ such that $φ (Ω) \subset Ω$ and $(x, φ (x)) \in Γ$ for each $x \in Ω$ .

Fix some $l \in N$ such that (35) holds. Let $f : N \to N$ be defined by $\begin{matrix} f (0) = l, f (k + 1) = φ (f (k)) . \end{matrix}$ Then f is computable by Proposition 5.2. For each $k \in N$ we have $(f (k), f (k + 1)) \in Γ$ and so $\begin{matrix} (38) & H_{f (k + 1)} ⩽ H_{f (k)}, J_{{(f (k + 1))}_{0}} \subset_{F} J_{{(f (k))}_{0}}, J_{{(f (k + 1))}_{\overline{f (k + 1)}}} \subset_{F} J_{{(f (k))}_{\overline{f (k)}}} \end{matrix}$ and $fmesh (f (k + 1)) < \frac{1}{2} fmesh (f (k))$ . Since $fmesh (f (0)) = fmesh (l) < r < 1$ , we get $\begin{matrix} fmesh (f (k)) < 2^{- k} \end{matrix}$ for each $k \in N$ . For $k \in N$ let $m_{k} \in N$ and $C_{0}^{k}, \dots, C_{m_{k}}^{k}$ be such that $\begin{matrix} H_{f (k)} = (C_{0}^{k}, \dots, C_{m_{k}}^{k}) . \end{matrix}$ For each $k \in N$ we have that $H_{f (k)}$ is a chain which covers S (since $f (k) \in Ω$ ), $mesh H_{f (k)} < 2^{- k}$ and it follows from (38) and Proposition 6.5 that $\begin{matrix} (Cl (C_{0}^{k + 1}), \dots, Cl (C_{m_{k + 1}}^{k + 1})) refines (C_{0}^{k}, \dots, C_{m_{k}}^{k}), Cl (C_{0}^{k + 1}) \subseteq C_{0}^{k} and Cl (C_{m_{k + 1}}^{k + 1}) \subseteq C_{m_{k}}^{k} . \end{matrix}$

By (37) we have that $\begin{matrix} {((C_{0}^{k} \cap S, \dots, C_{m_{k}}^{k} \cap S))}_{k \in N} \end{matrix}$ is a sequence of (open) simple chains in S. Note that the closed balls in S are compact since S is compact. It follows from Lemma 41 in [8] that the set K defined by $\begin{matrix} (39) & K = ⋂_{k \in N} (Cl (C_{0}^{k} \cap S) \cup \dots \cup Cl (C_{m_{k}}^{k} \cap S)) \end{matrix}$ is a continuum in S chainable from $a^{'}$ to $b^{'}$ , where $a^{'} \in ⋂_{k \in N} (C_{0}^{k} \cap S)$ and $b^{'} \in ⋂_{k \in N} (C_{m_{k}}^{k} \cap S)$ .

So $a^{'} \in J_{{(f (k))}_{0}}$ , $b^{'} \in J_{{(f (k))}_{\overline{f (k)}}}$ for each $k \in N$ and we easily conclude (using the function g from the proof of Lemma 6.6) that $a^{'}$ and $b^{'}$ are computable points. On the other hand, for each $k \in N$ by (39) we have $K \subseteq H_{f (k)}$ and since K is connected and the first and the last link of the chain $H_{f (k)}$ intersect K (in the points $a^{'}$ and $b^{'}$ ), we conclude that each link of this chain intersects K. Thus K is computable (Lemma 6.6).

It remains to prove that $d (a, a^{'}) < ε$ and $d (b, b^{'}) < ε$ . We have $a^{'} \in J_{{(f (0))}_{0}} = J_{{(l)}_{0}}$ and $diam J_{{(l)}_{0}} < r$ since $fdiam (l) < r$ (by (35)). Furthermore, by (35), $d (a, J_{{(l)}_{0}}) < 3 r$ and we conclude that $d (a, a^{'}) < 4 r$ . Hence $d (a, a^{'}) < ε$ . We similarly get $d (b, b^{'}) < ε$ . □

The following is an immediate consequence of Theorem 6.7 (see Corollary 43 in [8]).
Corollary 6.8.
Let $(X, d, α)$ be a computable metric space and let S be a semi-computable arc in this space. Then for all $a, b \in S$ and $ε > 0$ there exist distinct computable points $a^{'}, b^{'} \in S$ such that $d (a, a^{'}) < ε$ , $d (b, b^{'}) < ε$ and such that the subarc of S determined by $a^{'}$ and $b^{'}$ is computable.

In general, a semi-computable chainable continuum need not be computable: there exists a semi-computable arc in $R$ which is not computable [14]. However, a semi-computable arc always contains computable points, moreover they are dense in it and this also holds for any semi-computable chainable continuum which is decomposable. The latter fact follows from the next theorem and that theorem is the main result of this section. It is a consequence of Theorem 6.7 and it can be now proved in the same way as Theorem 44 in [8].
Theorem 6.9.
Let $(X, d, α)$ be a computable metric space and let S be a semi-computable set in this space. Suppose S is a decomposable chainable continuum. Then for each $ε > 0$ there exists a computable subcontinuum K of S such that $ρ (S, K) < ε$ . Moreover, K can be chosen so that it is chainable from a to b, where a and b are computable points.

Let X be a topological space and let C be a connected component of X. Then C is a closed set in X (see [5]). If C is also an open set, we say that C is an isolated component of X.

If X is a compact topological space, then each connected component of X is a continuum (decomposable or indecomposable).
Theorem 6.10.
Let $(X, d, α)$ be a computable metric space, let $S \subseteq X$ be a co-c.e. set and let $K \subseteq X$ be a semi-computable chainable continuum. Suppose $K \cap S$ has an isolated decomposable component C. Then C contains a computable point. Moreover, C can be approximated with arbitrary precision by a computable subcontinuum (in particular, computable points are dense in C).
Proof.
Since C is isolated, we have that C and $(K \cap S) ∖ C$ are closed in $K \cap S$ , hence these sets are compact in $(X, d)$ . It follows that there exists $j \in N$ such that $(K \cap S) ∖ C \subseteq J_{j}$ and $J_{j} \cap C = \emptyset$ . This implies $\begin{matrix} (40) & C = (K \cap S) ∖ J_{j} . \end{matrix}$ In general, if T is a semi-computable set, then $T ∖ J_{j}$ is semi-computable, see Lemma 3.3 in [10]. Thus (40) and Proposition 6.2 imply that C is semi-computable in $(X, d, α)$ . As a subcontinuum of K, C is chainable and the claim of the theorem follows from Theorem 6.9. □

In particular, if S is a co-c.e. set and K a semi-computable chainable continuum such that $K \cap S$ is a decomposable continuum, then $K \cap S$ contains a computable point.

Theorem 6.9 is a generalization of claim (9-1). Let us now show that claim (9-2) can also be generalized to any computable metric space. Moreover, let us show that an analogue generalization holds for circularly chainable continua.

A finite sequence $C_{0}, \dots, C_{m}$ of nonempty subsets of some set X is said to be a circular chain in X if for all $i, j \in {0, \dots, m}$ $\begin{matrix} 1 < | i - j | < m ⟹ C_{i} \cap C_{j} = \emptyset . \end{matrix}$ Note that a circular chain $C_{0}, \dots, C_{m}$ is a chain if and only if $C_{0} \cap C_{m} = \emptyset$ . Also note the following: if $C_{0}, \dots, C_{m}$ is a circular chain (where $m ⩾ 1$ ) and $i \in {0, \dots, m}$ , then $C_{i + 1}, \dots, C_{m}, C_{0}, \dots, C_{i - 1}$ is a chain.

A finite sequence $C_{0}, \dots, C_{m}$ of subsets of X is said to be a simple circular chain in X if $1 < | i - j | < m$ if and only if $C_{i} \cap C_{j} = \emptyset$ for all $i, j \in {0, \dots, m}$ .

If $(X, d)$ is a metric space and $ε > 0$ , the notions of a (simple) circular ε-chain, compact (simple) circular chain and open (simple) circular chain are defined analogously as before for chains.

A continuum $(X, d)$ is said to be circularly chainable if for each $ε > 0$ there exists an open simple circular ε-chain in $(X, d)$ which covers X [3,16].

The following proposition can be proved in a similar way as Proposition 3.2.
Proposition 6.11.
Let $(X, d)$ be a continuum. Then $(X, d)$ is circularly chainable if and only if for each $ε > 0$ there exists a compact simple circular ε-chain in $(X, d)$ which covers X.

The unit circle $S^{1} = {(x, y) \in R^{2} ∣ x^{2} + y^{2} = 1}$ is an example of a circularly chainable continuum. Any topological circle (a space homeomorphic to $S^{1}$ ) is clearly also a circularly chainable continuum.

If S is a semi-computable topological circle in a computable metric space $(X, d, α)$ , then S is computable [10,14]. The question is: does this also hold if S is any circularly chainable continuum, i.e. is any semi-computable circularly chainable continuum computable? It is proved in [8,9] that the answer is positive under the assumptions that $(X, d, α)$ is locally computable and S is not chainable. The assumption that S is not chainable may seem strange, but there exist continua which are both circularly chainable and chainable [3,16]. However, such a situation can occur only for “unusual” spaces, namely, by [3], a chainable continuum K is circularly chainable if and only if K is indecomposable or 2-indecomposable. That a continuum K is 2-indecomposable means that it is decomposable and there exist no subcontinua $K_{1}$ , $K_{2}$ and $K_{3}$ of K whose union is K such that $K_{1} ⊈ K_{2} \cup K_{3}$ , $K_{2} ⊈ K_{1} \cup K_{3}$ and $K_{3} ⊈ K_{1} \cup K_{2}$ .

We are going to show that the assumption of local computability on $(X, d, α)$ can be removed. We are going to see that (9-2) also holds in any computable metric space (recall that a semi-computable chainable continuum need not be computable).
Theorem 6.12.
Let $(X, d, α)$ be a computable metric space and let $S \subseteq X$ be a semi-computable set.
Suppose S is chainable from a to b, where a and b are computable points. Then S is computable.

Suppose S is circularly chainable, but not chainable. Then S is computable.

Proof.
(i) Let Ω be the set of all $(k, l) \in N^{2}$ such that $H_{l}$ covers S, $H_{l}$ is a formal chain, $a \in J_{{(l)}_{0}}$ , $b \in J_{{(l)}_{\overline{l}}}$ and $fdiam (l) < 2^{- k}$ . By Proposition 5.3 in [10] and Propositions 4.6, 4.1, 2.2 and 2.1 Ω is c.e. Using Proposition 3.2, Proposition 4.10 and Lemma 4.11 we conclude that for each $k \in N$ there exists $l \in N$ such that $(k, l) \in Ω$ and therefore by the single-valuedness theorem there exists a computable function $f : N \to N$ such that $\begin{matrix} (41) & (k, f (k)) \in Ω \end{matrix}$ for each $k \in N$ . Let $k \in N$ . It follows from (41) that $H_{f (k)}$ is a chain which covers S and such that its first and last link intersects S. The connectedness of S now implies that each link of $H_{f (k)}$ intersects S. Furthermore, $fdiam (f (k)) < 2^{- k}$ . Altogether, this and Lemma 6.6 give that S is computable.

(ii) If $l \in N$ , we say that $H_{l}$ is a formal circular chain if for all $i, j \in {0, \dots, \overline{l}}$ $\begin{matrix} 1 < | i - j | < \overline{l} ⟹ J_{{(l)}_{i}} and J_{{(l)}_{j}} are formally disjoint . \end{matrix}$ Using Proposition 4.6 and Proposition 2.4 it is not hard to conclude that the set $\begin{matrix} {l \in N ∣ H_{l} is a formal circular chain} \end{matrix}$ is c.e. Moreover, using Proposition 6.11, Proposition 4.10 and Lemma 4.11 we easily conclude that for each $ε > 0$ there exists $l \in N$ such that $H_{l}$ is a formal circular chain which covers S and $fdiam (l) < ε$ .

Since S is not chainable, it follows from Proposition 3.3 that there exists $k_{0} \in N$ with the following property: there exists no open $2^{- k_{0}}$ -chain in S which covers S.

Let Ω be the set of all $(k, l) \in N$ such that $H_{l}$ covers S, $H_{l}$ is a formal circular chain and $fdiam (l) < 2^{- (k + k_{0})}$ . Then Ω is c.e. and for each $k \in N$ there exists $l \in N$ such that $(k, l) \in Ω$ . Therefore there exists a computable function $f : N \to N$ such that $(k, f (k)) \in Ω$ for each $k \in N$ . Let $k \in N$ . We have $S \subseteq ⋃ H_{f (k)}$ , $fdiam (f (k)) < 2^{- k}$ and, by Lemma 6.6, it will be enough to prove that each link of $H_{f (k)}$ intersects S. We have $\begin{matrix} H_{f (k)} = (C_{0}, \dots, C_{m}) . \end{matrix}$ Note that $C_{0}, \dots, C_{m}$ are open sets in $(X, d)$ whose diameters are less than $2^{- (k + k_{0})}$ , in particular less than $2^{- k_{0}}$ . Suppose that there exists $i \in {0, \dots, m}$ such that $S \cap C_{i} = \emptyset$ . Then $C_{i + 1}, \dots, C_{m}, C_{0}, \dots, C_{i - 1}$ is a chain which covers S. Let us consider the finite sequence of sets $\begin{matrix} C_{i + 1} \cap S, \dots, C_{m} \cap S, C_{0} \cap S, \dots, C_{i - 1} \cap S . \end{matrix}$ These sets are open in S and if we remove those of these sets which are empty we get an open $2^{- k_{0}}$ -chain in S which covers S. But this is impossible by the choice of the number $k_{0}$ .

Hence each link of $H_{f (k)}$ intersects S and this completes the proof of the theorem. □

Theorems 6.7 and 6.9 provide certain conditions under which a semi-computable chainable continuum contains a computable subcontinuum. The technique used in the proof of Theorem 6.7 can be used in the proof of the following result which also provides a sufficient condition for existence of a computable subcontinuum.
Theorem 6.13.
Let $(X, d, α)$ be a computable metric space and let $S \subseteq X$ be a semi-computable chainable continuum. Suppose $a, b \in S$ are computable points, $a \neq b$ . Then for each $ε > 0$ there exist computable points $a^{'}, b^{'} \in S$ such that $d (a, a^{'}) < ε$ , $d (b, b^{'}) < ε$ and a computable subcontinuum K of S chainable from $a^{'}$ to $b^{'}$ .
Proof.
Let $ε > 0$ . Let $Ω^{'}$ be the set of all $(p, l, q) \in N^{3}$ such that $\begin{matrix} S \subseteq J_{p} \cup (⋃ H_{l}) \cup J_{q}, (p, l, q) is a formal chain, a \in J_{p} and b \in J_{q} . \end{matrix}$ As in the proof of Theorem 6.7 we conclude that $Ω^{'}$ is c.e. Let Ω be the set of all $l \in N$ for which there exist $p, q \in N$ such that $(p, l, q) \in Ω^{'}$ . We claim that there exists $l_{0} \in Ω$ such that $fdiam (l_{0}) < min {1, \frac{ε}{2}}$ , $d (a, J_{{(l_{0})}_{0}}) < \frac{ε}{2}$ and $d (b, J_{{(l_{0})}_{\overline{l_{0}}}}) < \frac{ε}{2}$ .

Let $r = \frac{1}{2} min {d (a, b), 1, ε}$ . Let $D_{0}, \dots, D_{m}$ be a compact simple r-chain in S which covers S. There exist $i, j \in {0, \dots, m}$ such that $a \in D_{i}$ and $b \in D_{j}$ . We may assume $i ⩽ j$ (otherwise we take the chain $D_{m}, \dots, D_{0}$ ). Note that $i \neq j$ and $i + 1 \neq j$ (otherwise we get $d (a, b) < 2 r$ which contradicts the choice of r). Hence $i + 1 < j$ . Consider the compact chain $\begin{matrix} D_{0} \cup \dots \cup D_{i}, D_{i + 1}, \dots, D_{j - 1}, D_{j} \cup \dots \cup D_{m} . \end{matrix}$ As in the proof of Theorem 6.7 we get numbers $p, l_{0}, q \in N$ such that $(p, l_{0}, q)$ is a formal chain, $D_{0} \cup \dots \cup D_{i} \subseteq J_{p}$ , $D_{i + 1}, \dots, D_{j - 1}$ are contained respectively in $J_{{(l_{0})}_{0}}, \dots, J_{{(l_{0})}_{\overline{l_{0}}}}$ , $D_{j} \cup \dots \cup D_{m} \subseteq J_{q}$ and $fdiam (l_{0}) < 2 r$ . So $(p, l_{0}, q) \in Ω^{'}$ , hence $l_{0} \in Ω$ and $fdiam (l_{0}) < min {1, \frac{ε}{2}}$ . Since $D_{i} \cap D_{i + 1} \neq \emptyset$ , we have $d (a, D_{i + 1}) < r ⩽ \frac{ε}{2}$ , hence $d (a, J_{{(l_{0})}_{0}}) < \frac{ε}{2}$ . Also $d (b, J_{{(l_{0})}_{\overline{l_{0}}}}) < \frac{ε}{2}$ .

Let Γ be the set of all $(l, l^{'}) \in N^{2}$ such that $\begin{matrix} l, l^{'} \in Ω, H_{l^{'}} ⩽ H_{l}, fdiam (l^{'}) < \frac{1}{2} fdiam (l), J_{{(l^{'})}_{0}} \subset_{F} J_{{(l)}_{0}} and J_{{(l^{'})}_{\overline{l^{'}}}} \subset_{F} J_{{(l)}_{\overline{l}}} . \end{matrix}$ Let $l \in Ω$ . We claim that there exists $l^{'} \in Ω$ such that $(l, l^{'}) \in Γ$ .

Let $λ > 0$ be a Lebesgue number of the open cover ${J_{p}, J_{{(l)}_{0}}, \dots, J_{{(l)}_{\overline{l}}}, J_{q}}$ for S. There exist $r_{1}, r_{2} > 0$ such that $B (a, r_{1}) \subseteq J_{p}$ and $B (b, r_{2}) \subseteq J_{q}$ . Let $\begin{matrix} r = min {λ, \frac{fmesh (l)}{4}, \frac{d (a, b)}{2}, r_{1}, r_{2}} \end{matrix}$ and let us take a compact simple r-chain $D_{0}, \dots, D_{m}$ in S which covers S. Choose $i, j \in {0, \dots, m}$ so that $a \in D_{i}$ and $b \in D_{j}$ . We may assume $i + 1 < j$ . Since $diam D_{i} < r$ and $B (a, r) \subseteq J_{p}$ , we have $D_{i} \subseteq J_{p}$ . Similarly, $D_{j} \subseteq J_{q}$ . We proceed now as in the proof of Theorem 6.7. Using Lemma 3.8 we get $v, w \in {0, \dots, m}$ such that $\begin{matrix} i < v ⩽ w < j, D_{v} \subseteq J_{{(l)}_{0}}, D_{w} \subseteq J_{{(l)}_{\overline{l}}} and D_{v}, \dots, D_{w} refines H_{l} . \end{matrix}$ From this we conclude that there exists $l^{'} \in Ω$ such that $(l, l^{'}) \in Γ$ .

Therefore there exists a computable function $f : N \to N$ such that $f (0) = l_{0}$ and $(f (k), f (k + 1)) \in Γ$ for each $k \in N$ .

It is immediate from definition of $Ω^{'}$ that for each $l \in Ω$ $\begin{matrix} J_{{(l)}_{0}} \cap S, \dots, J_{{(l)}_{\overline{l}}} \cap S \end{matrix}$ is a simple chain. Now as in the proof of Theorem 6.7 we conclude that $\begin{matrix} K = ⋂_{k \in N} (Cl (J_{{(f (k))}_{0}} \cap S) \cup \dots \cup Cl (J_{{(f (k))}_{\overline{f (k)}}} \cap S)) \end{matrix}$ is a computable subcontinuum of S chainable from $a^{'}$ to $b^{'}$ , where $a^{'}$ and $b^{'}$ are computable points such that $a^{'} \in J_{{(l_{0})}_{0}}$ , $b^{'} \in J_{{(l_{0})}_{\overline{l_{0}}}}$ , from which it follows $d (a, a^{'}) < ε$ and $d (b, b^{'}) < ε$ . □

Using Theorem 6.13 and Corollary 6.8 we get more general statements than those of Theorem 5.3 and Theorem 5.4. Theorem 6.14.
Let $(X, d, α)$ be a computable metric space, let U and V be disjoint c.e. open sets in this space and let $S = X ∖ (U \cup V)$ .
Suppose $K \subseteq X$ is a semi-computable chainable continuum such that $K \cap S$ is totally disconnected and such that K intersects U and V in computable points. Then $K \cap S$ contains a computable point.

Suppose $K \subseteq X$ is a computable chainable continuum such that $K \cap S$ is totally disconnected and such that K intersects U and V. Then $K \cap S$ contains a computable point.

Suppose $A \subseteq X$ is a semi-computable arc such that A intersects U and V. Then $A \cap S$ contains a computable point.

Proof.

Let $a \in K \cap U$ and $b \in K \cap V$ be computable points. Using Theorem 6.13 we conclude that there exist $a^{'} \in U$ , $b^{'} \in V$ and a computable subcontinuum $K^{'}$ of K which is chainable from $a^{'}$ to $b^{'}$ . Since $K^{'} \cap S \subseteq K \cap S$ , we have that $K^{'} \cap S$ is also totally disconnected and by Theorem 5.3 it contains a computable point.

Since K is computable, computable points are dense in it and therefore K intersects U and V in computable points. The claim now follows from (i).

It follows from Corollary 6.8 that there exist $a \in U$ , $b \in V$ and a computable subarc $A^{'}$ of A whose endpoints are a and b. By Theorem 5.4 $A^{'} \cap S$ contains a computable point.
□

7. Conclusion

Motivated by a classical result of (computable) analysis, we started this paper with the question whether a computable arc K whose endpoints belong to disjoint c.e. open sets U and V (in some computable metric space) intersects the complement $S = X ∖ (U \cup V)$ in a computable point. Since chainable continua are natural generalization of arcs, we have focused throughout the paper on the general case when K is a chainable continuum and we have sought for conditions under which $K \cap S$ contains a computable point.

One of the main results of the paper is that $K \cap S$ contains a computable point if K intersects both U and V and $K \cap S$ is totally disconnected. If we return to the basic case when A is a computable arc and assume that $A \cap S \neq \emptyset$ , then $A \cap S$ need not contain a computable point (the first example in the introduction), however this situation can occur only if $A \cap S$ is totally disconnected. So the total disconnectedness is the only problem for a computable arc A to intersects S in a computable point (if A does not intersect both U and V). Interestingly, the total disconnectedness is exactly the assumption that we need to prove that a chainable continuum K which intersects U and V intersects S in a computable point and it is not clear what can we conclude without this assumption. If K is an arc, we easily get that the assumption of total disconnectedness of $K \cap S$ can be dropped, but what about general chainable continua? The open question is the following: do the statements of Theorem 5.3 and Theorem 6.14(i) and (ii) hold without the assumption that $K \cap S$ is totally disconnected?

The problem with a general chainable continuum K is that connected subsets of K which have more than one point may have empty interiors in K (which is not the case if K is an arc). Nevertheless, there are conditions under which we can conclude that a subcontinuum of K contains computable points. Since $K \cap S$ is semi-computable and since a subcontinuum of a chainable continuum is chainable, we come to the question what can be said about computable points in semi-computable chainable continua.

We proved that a semi-computable chainable continuum L can be approximated by a computable subcontinuum with an arbitrary given precision (which in particular means that L contains a computable point), however under assumption that L is decomposable. This gave that $K \cap S$ has a computable point if $K \cap S$ is connected and decomposable (and more generally, if $K \cap S$ has an isolated and decomposable component).

We have used here certain additional assumptions and the question is which of these assumptions are necessary. One of the main open questions is this: does the statement of Theorem 6.9 hold without the assumption that the chainable continuum is decomposable?

In fact, there is even a more elementary open question: if L is a semi-computable chainable continuum, does L contain a computable point? If L is decomposable, then computable points are dense in L, in fact L is “almost computable” (in the sense of Theorem 6.9), so it would be interesting if the answer to the previous question is negative, i.e. if there is an example of a semi-computable chainable continuum without a computable point. On the other hand, indecomposable continua are unusual by itself, so such an example would not be so surprising (related to this see [11]).

Since each indecomposable chainable continuum is circularly chainable [3], in view of Theorem 6.12(ii) it also makes sense to ask: does the semi-computability of an indecomposable chainable continuum imply its computability? A more direct open question which arises from this theorem is this: is any semi-computable circularly chainable continuum computable?

Similarly, if we think of a counterexample for the statement of Theorem 5.3 in which $K \cap S$ is connected, then $K \cap S$ has to be an indecomposable continuum. Note that a computable chainable continuum K in the plane which intersects the lower and the upper half-plane must intersect $S = R \times {0}$ in a computable point (without the assumption that $K \cap S$ is totally disconnected; this is an answer to the question from the introduction). Namely, this follows from Theorem 6.14(ii) and the fact that computable points are dense in S and nontrivial connected subsets of S have nonempty interiors in S.

Footnotes

Acknowledgements

The authors would like to thank the anonymous referees for their valuable suggestions and corrections.

References

Brattka, Plottable real number functions and the computable graph theorem, SIAM J. Comput. 38(1) (2008), 303–328. doi:10.1137/060658023.

Brattka and

Presser, Computability on subsets of metric spaces, Theoretical Computer Science 305 (2003), 43–76. doi:10.1016/S0304-3975(02)00693-X.

C.E.

Burgess, Chainable continua and indecomposability, Pac. J. Math. 9 (1959), 653–659. doi:10.2140/pjm.1959.9.653.

Burnik and

Iljazović, Computability of 1-manifolds, Logical Methods in Computer Science 10(2:8) (2014), 1–28.

C.O.

Christenson and

W.L.

Voxman, Aspects of Topology, Marcel Dekker, Inc., New York, 1977.

Daniel and

T.H.

McNicholl, Effective versions of local connectivity properties, Theory of Computing Systems 50(4) (2012), 621–640. doi:10.1007/s00224-011-9364-1.

Engelking, Dimension Theory, PWN – Polish Scientific Publishers, Warszawa, 1978.

Iljazović, Chainable and circularly chainable co-c.e. sets in computable metric spaces, Journal of Universal Computer Science 15(6) (2009), 1206–1235.

Iljazović, Local computability of computable metric spaces and computability of co-c.e. continua, Glasnik Matematički 47(67) (2012), 1–20.

10.

Iljazović, Compact manifolds with computable boundaries, Logical Methods in Computer Science 9(4:19) (2013), 1–22.

11.

Kihara, Incomputability of simply connected planar continua, Computability 1(2) (2012), 131–152.

12.

Le Roux and

Ziegler, Singular coverings and non-uniform notions of closed set computability, Math. Log. Q. 54 (2008), 545–560. doi:10.1002/malq.200610058.

13.

T.H.

McNicholl, The power of backtracking and the confinement of lenght, Proceedings of the American Mathematical Society 141(3) (2013), 1041–1053. doi:10.1090/S0002-9939-2012-11385-1.

14.

J.S.

Miller, Effectiveness for embedded spheres and balls, Electronic Notes in Theoretical Computer Science 66 (2002), 127–138. doi:10.1016/S1571-0661(04)80384-0.

15.

J.R.

Munkres, Topology, Pearson Education International, New York, 2000.

16.

S.B.

Nadler, Continuum Theory, Marcel Dekker, Inc., New York, 1992.

17.

M.B.

Pour-El and

Richards, Computability in Analysis and Physics, Springer-Verlag, Berlin–Heidelberg–New York, 1989.

18.

Specker, Der Satz vom Maximum in der rekursiven Analysis, in: Constructivity in Mathematics,

Heyting, ed., North Holland Publ. Comp., Amsterdam, 1959, pp. 254–265.

19.

Weihrauch, Computable Analysis, Springer, Berlin, 2000.