Computable planar curves intersect in a computable point

Abstract

Consider two paths $f, g : [0; 1] \to {[0; 1]}^{2}$ in the unit square such that $f (0) = (0, 0)$ , $f (1) = (1, 1)$ , $g (0) = (0, 1)$ and $g (1) = (1, 0)$ . By continuity of f and g there is a point of intersection. We prove that there is a computable point of intersection if f and g are computable.

Keywords

Computable analysis planar curves

1. Introduction

A path in the Euclidean plane is a continuous function $f : [0; 1] \to R^{2}$ , a curve is the range of a path. The following is known about planar curves.

Theorem 1.1.
Let $f, g : [0; 1] \to {[0; 1]}^{2}$ be two paths in the unit square such that $\begin{array}{rcl} (1) & f (0) = (0, 0), f (1) = (1, 1), g (0) = (0, 1) and g (1) = (1, 0) . \end{array}$ Then the two curves $range (f)$ and $range (g)$ intersect.

Figure 1 visualizes the theorem. Manukyan [10] (in Russian) has proved the following surprising theorem, cited in [8, page 279] as follows:
Theorem 1.2 (Manukyan).

There are two constructive (and therefore continuous) planar curves $φ_{1}$ and $φ_{2}$ such that $\begin{array}{l} φ_{1} (0) = (0, 0), φ_{1} (1) = (1, 1), φ_{2} (0) = (0, 1), φ_{2} (1) = (1, 0), \\ for every 0 < t < 1 both φ_{1} (t) and φ_{2} (t) belong to the open unit square, \\ φ_{1} and φ_{2} do not intersect. \end{array}$

Since the paths in Theorem 1.1 are continuous, the two theorems seem to be contradictory. The contradiction vanishes by the observation that in Theorem 1.2, “constructive” means “Markov computable” or computable in the “Russian” way [1,7,12]. In the Russian approach only the countable set $R_{c}$ of computable real numbers is considered, hence $φ_{1}, φ_{2} : R_{c} \cap [0; 1] \to {(R_{c} \cap [0; 1])}^{2}$ .

Figure 1.

Intersecting curves.

In this article we use the definition of computable real functions f and g introduced by Grzegorczyk and Lacombe [4,5,9] and call them computable. We assume that the reader is familiar with the basic properties of this concept [3,12,13]. We will prove the following theorem.

Theorem 1.3.

Let $f, g : [0; 1] \to {[0; 1]}^{2}$ be two computable paths in the unit square such that $\begin{array}{rcl} (2) & f (0) = (0, 0), f (1) = (1, 1), g (0) = (0, 1) and g (1) = (1, 0) . \end{array}$ Then there is a computable point $x \in range (f) \cap range (g)$ .

The restrictions $φ_{f}$ and $φ_{g}$ of the computable functions f and g, respectively, to the computable points are Markov-computable [12]. This is no contradiction to Theorem 1.2 but merely means that the functions $φ_{1}$ and $φ_{2}$ from Theorem 1.2 have no extensions to computable functions $[0; 1] \to {[0; 1]}^{2}$ . The existence of computable intersection points in various other situations has been studied by Iljazović and Pažek in [6].

In the next sections we will prove the following formally weaker but equivalent version of Theorem 1.3.

Theorem 1.4.

Let $f, g : [0; 1] \to {[0; 1]}^{2}$ be two computable paths in the unit square such that $\begin{array}{l} (3) & f (0) = (0, 0), f (1) = (1, 1), g (0) = (0, 1), g (1) = (1, 0) and \\ (4) & for every 0 < t < 1 both f (t) and g (t) belong to the open unit square. \end{array}$ Then there is a computable point $x \in range (f) \cap range (g)$ .

Obviously Theorem 1.3 implies Theorem 1.4. The converse is also true: Suppose, Theorem 1.4 is true. Let $f, g : [0; 1] \to {[0; 1]}^{2}$ be computable functions such that (2) is true. We extend f and g to functions $f_{1}, g_{1} : [- 1; 2] \to {[- 1; 2]}^{2}$ by $f_{1} (t) : = (t, t)$ and $g_{1} (t) : = (t, 1 - t)$ for $- 1 ⩽ t < 0$ and $1 < t ⩽ 2$ . We transform the square ${[- 1; 2]}^{2}$ together with $f_{1}$ and $g_{1}$ to the unit square. For $0 ⩽ t ⩽ 1$ let $f_{2} (t) : = (f_{1} (3 t - 1) + (1, 1)) / 3$ and $g_{2} (t) : = (g_{1} (3 t - 1) + (1, 1)) / 3$ . Then $f_{2}$ and $g_{2}$ satisfy (3) and (4). By Theorem 1.4 there are (not necessarily computable) numbers $s, t \in [0; 1]$ such that $f_{2} (s) = x = g_{2} (t)$ and $x \in R^{2}$ is computable, hence $f_{1} (3 s - 1) = 3 x - (1, 1) = g_{1} (3 t - 1)$ . Since $f_{1}$ and $g_{1}$ cannot intersect outside the unit square $f (3 s - 1) = 3 x - (1, 1) = g (3 t - 1)$ where $0 ⩽ 3 s - 1 ⩽ 1$ and $0 ⩽ 3 t - 1 ⩽ 1$ . Therefore $3 x - (1, 1) \in range (f) \cap range (g)$ . The point $3 x - (1, 1)$ is computable.

A corollary of Theorem 1.4 is the computable intermediate value theorem [12].

Theorem 1.5 (Computable intermediate value).

Every computable function $h : [0; 1] \to [- 1; 1]$ with $h (0) = - 1$ and $h (1) = 1$ has a computable zero (that is, $h (t) = 0$ for some computable number t).

For a proof as a corollary of Theorem 1.4, define $f (t) : = (t, 0)$ and $g (t) : = (t, h (t))$ . By an easily provable corollary of Theorem 1.4, there are numbers s, t and a computable point $(x, y)$ such that $f (s) = (x, y) = g (t)$ , hence $(s, 0) = (x, y) = (t, h (t))$ . Therefore, $t = x$ is computable and $h (t) = 0$ .

The intermediate value theorem can be proved directly as follows:

Define a predicate $Q_{i v}$ by $\begin{array}{l} (5) & Q_{i v} ⟺ h (a; b) = {0} for some rational numbers a < b . \end{array}$

Suppose $Q_{i v}$ . Then $f (c) = 0$ for some rational (hence computable) number $c \in (a; b)$ .

Suppose $\neg Q_{i v}$ . Call an interval $I = (a; b)$ a crossing, if $a, b \in Q$ and $h (a) < 0 < h (b)$ . By continuity of h the following can be shown easily: $\begin{array}{rcl} (6) & For every crossing I there is a crossing J such that \overline{J} \subseteq I and length (J) < length (I) / 2 . \end{array}$

Since the set of crossings is c.e., beginning with $(0; 1)$ we can compute a nested sequence of crossings which converges to some real number t. Then $h (t) = 0$ .

We will prove Theorem 1.4 in similar steps.

Computable curves can be extremely complicated. Consider, for example, a space-filling curve or a curve with infinitely many spirals, each of which containing infinitely many sub-spirals etc. infinitely often or curves with chaotic behavior. Furthermore, there is a computable function $h : [0; 1] \to [- 1; 1]$ with $h (0) = - 1$ and $h (1) = 1$ such that $h^{- 1} {0}$ has measure $> 1 / 2$ but contains only a single computable number.1

¹
There is a computable open set $U \subseteq R$ with measure $< 1 / 2$ which contains the computable real numbers ([11], [12, Theorem 4.2.8]). Define a computable function $h_{0} : R \to R$ such that $(\forall t) h_{0} (t) ⩽ 0$ and $h_{0}^{- 1} (0) = R ∖ U$ . Construct h from $h_{0}$ .

Therefore at first glance there might be enough freedom to construct computable functions f and g which avoid to cross in a computable point.

In Sections 2 to 5 we prove Theorem 1.4 corresponding to Steps A, B, C, D above. In Section 2 we define a predicate Q which corresponds to the $Q_{i v}$ in Step A above. In Section 3 we prove that Q implies the existence of a computable point of intersection. In Section 4 assuming $\neg Q$ we define crossings and show that every crossing has a much smaller sub-crossing. In Section 5 we prove that every crossing has a proper sub-crossing and that the set of proper crossings is c.e. Then we compute a point of intersection of f and g as the limit of a decreasing sequence of proper crossings. In Section 6 we outline a proof for the special case that f is injective and add some further considerations.

Computability on the real numbers, on open and on compact subsets $R$ and of $R^{2}$ is defined via canonical representations2

A name of an open set U is a list $B_{1}, B_{2}, \dots$ of open rational balls such that $U = ⋂ B_{i}$ , a name of a compact set K is a list of all finite covers of K with rational balls.

[12 ,13]. In the following, f and g will be computable functions satisfying the conditions (3) and (4) from Theorem 1.4.

2. Two alternatives

In this section we define a predicate Q which corresponds to the predicate $Q_{i v}$ from Step A in Section 1. We consider Euclidean balls $B (f (a), r))$ such that $a, r \in Q$ and $\overline{B (f (a), r)} \subseteq {(0; 1)}^{2}$ . Since $\overline{B (f (a), r)} \subseteq {(0; 1)}^{2}$ iff $0 < a < 1$ , $r > 0$ and ${pr}_{i} \circ f (a) \in (r; 1 - r)$ (for $i = 1, 2$ ), $\begin{array}{rcl} (7) & {(a, r) \in Q^{2} ∣ \overline{B (f (a), r)} \subseteq {(0; 1)}^{2}} is c.e. \end{array}$ For $a, r \in Q$ such that $\overline{B (f (a), r)} \subseteq {(0; 1)}^{2}$ define $\begin{array}{l} (8) & (p_{a r}; q_{a r}) : = the longest open interval I such that a \in I and f (I) \subseteq B (f (a), r), \\ (9) & (p_{a r}^{'}; q_{a r}^{'}) : = the longest open interval I such that a \in I and f (\overline{I}) \subseteq \overline{B (f (a), r)}, \\ (10) & K_{a r} : = [p_{a r}^{'}; p_{a r}], \\ (11) & L_{a r} : = [q_{a r}; q_{a r}^{'}] . \end{array}$ The definitions are illustrated in Fig. 2. We can interpret the arguments of f and g as “time”. Starting at time a in positive direction f leaves the open ball at time $q_{a r}$ and leaves the closed ball at time $q_{a r}^{'}$ . Correspondingly, starting at time a in negative direction f leaves the open ball at time $p_{a r}$ and leaves the closed ball at time $p_{a r}^{'}$ . For radii r and s, Fig. 2 shows a time interval from $t < min K_{a s}$ to $t > max L_{a s}$ and its image. The function f can be much more complicated than shown in the figure. For example there is a computable function f such that $f (p_{a r}; q_{a r}) = B (f (a), r)$ and $f (K_{a r}) = f (L_{a r}) = \overline{B (f (a), r)}$ . Notice that f may cross the ball $B (f (a), r)$ additionally at times t with $t < p_{a r}^{'}$ or $t > q_{a r}^{'}$ .

Figure 2.

A segment of $graph (f)$ around time a crossing balls $B (f (a), r)$ and $B (f (a), s)$ .

Obviously, $f (p_{a r}), f (q_{a r}), f (p_{a r}^{'}), f (q_{a r}^{'}) \in \partial B (f (a), r)$ 3

Where $\partial V$ denotes the boundary of V.

and

\begin{array}{l} (12) & p_{a r} = inf {b \in (0; a) \cap Q ∣ f [b; a] \subseteq B (f (a), r)}, \\ (13) & q_{a r} = sup {b \in (a; 1) \cap Q ∣ f [a; b] \subseteq B (f (a), r)}, \\ (14) & p_{a r}^{'} = sup {b \in (0; a) \cap Q ∣ f (b) \notin \overline{B (f (a), r)}}, \\ (15) & q_{a r}^{'} = inf {b \in (a; 1) \cap Q ∣ f (b) \notin \overline{B (f (a), r)}} . \end{array}

The numbers

q_{a r}

q_{a r}^{'}

p_{a r}

and

p_{a r}^{'}

are not computable in general but semi-computable.

Lemma 2.1.

The sets $\begin{array}{l} (16) & {(a, r, c, d) \in Q^{4} ∣ \overline{B (f (a), r)} \subseteq {(0; 1)}^{2} and K_{a r} \subseteq (c; d)} and \\ (17) & {(a, r, c, d) \in Q^{4} ∣ \overline{B (f (a), r)} \subseteq {(0; 1)}^{2} and L_{a r} \subseteq (c; d)} \end{array}$ are c.e.

Proof.

From the compact set $[a; b]$ we can compute the compact set $f [a; b]$ . Since $K \subseteq O$ for compact K and open O is c.e. we can enumerate the set of all $b \in (a; 1) \cap Q$ such that $f [a; b] \subseteq B (f (a), r)$ . Since $f (b) \notin \overline{B (f (a), r)}$ is equivalent to $‖ f (a) - f (b) ‖ > r$ (in $R^{2}$ ), we can enumerate the set of all $b \in (a; 1) \cap Q$ such that $f (b) \notin \overline{B (f (a), r)}$ . (17) follows from (11), (13) and (15). Accordingly $K_{a r}$ . □

We define a predicate Q which in this proof corresponds to the predicate $Q_{i v}$ from the proof of the computable intermediate value theorem in Section 1. $\begin{array}{l} (18) & Q : \Leftrightarrow \{\begin{matrix} there are a, r, s \in Q with 0 < r < s and \overline{B (f (a), s)} \subseteq {(0; 1)}^{2}) such that \\ (\forall t \in Q \cap [r; s]) (f \circ max (K_{a t}) \in range (g) or f \circ min (L_{a t}) \in range (g)) \end{matrix}\} . \end{array}$ In Fig. 2, $f \circ max (K_{a r})$ and $f \circ min (L_{a r})$ are the marked points on the circle with radius r. By Q for every radius $r ⩽ t ⩽ s$ at least one of the corresponding marked points must be in $range (g)$ . We will prove that $range (f) \cap range (g)$ contains a computable point. In general neither Q nor $\neg Q$ are c.e.

3. The first alternative

We assume Q from (18). Therefore, there are $a, r, s \in Q$ with $0 < r < s$ and $\overline{B (f (a), s)} \subseteq {(0; 1)}^{2}$ such that $\begin{array}{rcl} (19) & (\forall t \in Q \cap [r; s]) (f \circ max (K_{a t}) \in range (g) or f \circ min (L_{a t}) \in range (g)) . \end{array}$

For an interval I let $lg (I)$ be its length. For closed real intervals K, L define $K < L$ iff $max (K) < min (L)$ . If $K < L$ let $lg (K \cup L) : = max (L) - min (K)$ .4

⁴
We consider $(K, L)$ as a generalized interval with lower bound K and upper bound L.

Then (see Fig. 2)

\begin{array}{rcl} (20) & K_{a s} & < & K_{a r} < L_{a r} < L_{a s} if r < s . \end{array}

Lemma 3.1.

From rational a, r, s, ε such that $0 < r < s$ , $\overline{B (f (a), s)} \subseteq {(0; 1)}^{2}$ and $ε > 0$ we can compute rational numbers $\overline{r}$ , $\overline{s}$ and rational intervals I, J such that $\begin{array}{rcl} (21) & r < \overline{r} < \overline{s} < s, K_{a \overline{s}} \cup K_{a \overline{r}} \subseteq I, L_{a \overline{r}} \cup L_{a \overline{s}} \subseteq J, lg (I) < ε and lg (J) < ε . \end{array}$

Proof.

First we prove that such numbers $\overline{r}$ , $\overline{s}$ exist. There is a sequence ${(r_{i})}_{i \in N}$ of rational numbers such that $r < r_{0} < r_{1} < r_{2} < \dots < s$ . Then by (20) $\begin{matrix} K_{a s} < \dots < K_{a r_{2}} < K_{a r_{1}} < K_{a r_{0}} < K_{a r} < L_{a r} < L_{a r_{0}} < L_{a r_{1}} < L_{a r_{2}} < \dots < L_{a s} . \end{matrix}$ Since all these intervals are pairwise disjoint, there are pairwise disjoint rational intervals $I_{i}$ and $J_{i}$ such that $K_{a r_{2 i + 1}} \cup K_{a r_{2 i}} \subseteq I_{i}$ and $L_{a r_{2 i}} \cup L_{a r_{2 i + 1}} \subseteq J_{i}$ . Since $\sum_{i} lg (I_{i}) + \sum_{i} lg (J_{i}) ⩽ max (L_{a s}) - min (K_{a s})$ there are only finitely many numbers i such that $lg (I_{i}) ⩾ ε$ and only finitely many numbers i such that $lg (J_{i}) ⩾ ε$ . Hence for some number i, $lg (I_{i}) < ε$ and $lg (J_{i}) < ε$ . Choose $\overline{r} : = r_{2 i}$ , $\overline{s} : = r_{2 i + 1}$ , $I : = I_{2 i}$ and $J : = J_{2 i}$ .

In general, for closed intervals $K < L$ , $K \cup L \subseteq I$ iff there are disjoint rational intervals $I_{1}$ , $I_{2}$ such that $K \subseteq I_{1}$ , $L \subseteq I_{2}$ and $I_{1} \cup I_{2} \subseteq I$ . Therefore by Lemma 2.1 we can compute appropriate radii $\overline{r}$ , $\overline{s}$ and intervals I and J. □

Theorem 3.2.

If Q then $f (α) \in range (g)$ for some computable number $α \in R$ .

Proof.

By Lemma 3.1 from a, r, s we can compute a sequence ${(r_{n}, s_{n})}_{n}$ of pairs of rational radii and sequences ${(I_{n})}_{n}$ and ${(J_{n})}_{n}$ of rational intervals such that $r < r_{0} < r_{1} < r_{2} < \dots < s_{2} < s_{1} < s_{0} < s$ and for all n, $\begin{array}{rcl} (22) & lg (I_{n}) < 2^{- n}, lg (J_{n}) < 2^{- n}, K_{a s_{n}} \cup K_{a r_{n}} \subseteq I_{n}, L_{a r_{n}} \cup L_{a s_{n}} \subseteq J_{n} . \end{array}$

Let $\begin{matrix} S_{n} : = ⋂_{m = 0}^{n} {\overline{I}}_{m} and T_{n} : = ⋂_{m = 0}^{n} {\overline{J}}_{m} . \end{matrix}$

Suppose $m < n$ . Then $r_{m} < r_{n} < s_{n} < s_{m}$ , hence $L_{a r_{m}} < L_{a r_{n}} < L_{a s_{n}} < L_{a s_{m}}$ , therefore, $L_{a r_{n}} \cup L_{a s_{n}} \subseteq J_{m}$ .

Therefore, ${(T_{n})}_{n}$ is a descending sequence of closed rational intervals such that $L_{a r_{n}} \cup L_{a s_{n}} \subseteq T_{n}$ and $lg (T_{n}) < 2^{- n}$ by (22). The sequence converges to a point $β \in R$ which is computable since the sequence ${(J_{n})}_{n}$ is computable. Correspondingly, $K_{a s_{n}} \cup K_{a r_{n}} \subseteq S_{n}$ , $lg (S_{n}) < 2^{- n}$ and the sequence ${(S_{n})}_{n}$ converges to a computable point α.

We apply assumption Q. By (19), $\begin{array}{rcl} (23) & (\forall n) (f \circ max (K_{a r_{n}}) \in range (g) or f \circ min (L_{a r_{n}}) \in range (g)) \end{array}$ (see the marked points in Fig. 2), hence $\begin{array}{rcl} (24) & f \circ max (K_{a r_{n}}) \in range (g) infinitely often or f \circ min (L_{a r_{n}}) \in range (g) infinitely often . \end{array}$

Suppose $f \circ max (K_{a r_{n}}) \in range (g)$ infinitely often. Then for some increasing sequence $n_{0}, n_{1}, n_{2}, \dots$ of indices, $f (α_{i}) \in range (g)$ where $α_{i} : = max (K_{a r_{n_{i}}})$ . By $i ⩽ n_{i}$ , $α_{i} \in K_{a r_{n_{i}}} \subseteq S_{n_{i}} \subseteq S_{i}$ , hence the sequence ${(α_{i})}_{i}$ converges to α. Since f is continuous, the sequence ${(f (α_{i}))}_{i}$ converges to $f (α)$ . Since $f (α_{i}) \in range (g)$ , ${(f (α_{i}))}_{i}$ is a sequence in $range (g)$ which converges to $f (α)$ . Since $range (g)$ is compact it is complete. Therefore, $f (α) \in range (g)$ . Correspondingly, if $f \circ min (L_{a r_{n}}) \in range (g)$ infinitely often then $f (β) \in range (g)$ .

Therefore, we have shown that Q implies $f (α) \in range (g)$ for some computable number $α \in R$ . □

Corollary 3.3.

If Q then $g (α) \in range (f)$ for some computable number $α \in R$ .

Proof.

By symmetry. □

4. Gates

In this section we generalize Step C of the proof of the computable intermediate value theorem in Section 1. We define gates and prove that every gate crossed by g contains a much smaller gate crossed by g. In Section 5 we compute an intersection point of f and g as the limit of a converging sequence of crossings. Let Q be the predicate defined in (18). In the following we assume $\neg Q$ , that is, for all $a, r, s \in Q$ such that $0 < r < s$ and $\overline{B (f (a), s)} \subseteq {(0; 1)}^{2}$ , $\begin{array}{rcl} (25) & (\exists t \in Q \cap (r; s)) (f \circ max (K_{a t}) \notin range (g) and f \circ min (L_{a t}) \notin range (g)) . \end{array}$

First we introduce gates and a concept of crossing. Gates generalize the intervals in our proof of the computable intermediate value theorem in Section 1.

Definition 4.1 (Passage, gate).

A passage is a pair $(V, c)$ such that V is the open unit square ${(0; 1)}^{2}$ or a ball $B (f (a), r)$ ( $a, r \in Q$ ) with $\overline{B (f (a), r)} \subseteq {(0; 1)}^{2}$ or the strict intersection5

⁵
Where we call the intersection of $B_{1}$ and $B_{2}$ strict if $B_{1} ⊈ B_{2}$ , $B_{2} ⊈ B_{1}$ and $B_{1} \cap B_{2} \neq \emptyset$ .

of two such balls, and

c \in Q \cap (0; 1)

with

f (c) \in V

Let $I_{V c}$ be the longest open interval I such that $c \in I$ and $f (I) \subseteq V$ and for $d \in Q$ with $g (d) \in V$ let $I_{V d}^{g}$ be the longest open interval I such that $d \in I$ and $g (I) \subseteq V$ (cf. (8) and (9)).

A gate is a passage such that $f \circ inf (I_{V c}) \notin range (g)$ and $f \circ sup (I_{V c}) \notin range (g)$ .

A gate $(V, c)$ is crossed by g via $d \in Q$ if $g (d) \in V$ and the straight line segments from $f \circ inf (I_{V c})$ to $f \circ sup (I_{V c})$ and from $f \circ inf (I_{V d}^{g})$ to $f \circ sup (I_{V d}^{g})$ intersect. We say that the gate $(V, c)$ is crossed by g if it is crossed via some d.

Notice that by (10) and (11), $\begin{array}{rcl} (26) & inf (I_{V a}) & = & max (K_{a r}) and sup (I_{V a}) = min (L_{a r}) if V = (B (f (a), r), a) . \end{array}$

Figure 3 shows a ball-shaped gate $(V, c)$ which is not crossed by g via d since the dotted line segments do not intersect (equivalently, surrounding the circle (boundary of V) the four endpoints of the curve segments do not alternate in f and g). Notice that nevertheless the curve segment $f (I_{V c})$ of f and the curve segment $g (I_{V d}^{g})$ of g intersect inside of V. Such intersection points will be irrelevant in our construction.

On the right Fig. 3 shows a lens-shaped gate (intersection of two balls) $(V, c)$ which is crossed by the path g via d (the dotted line segments intersect). As an example, $({(0; 1)}^{2}, 1 / 2)$ is a gate which is crossed by g via the point $d = 1 / 2$ (see Fig. 1). Here $I_{V c} = I_{V d}^{g} = (0; 1)$ .

Figure 3.

A ball-shaped gate not crossed by g via d and a lens-shaped gate crossed by g via d.

In the remainder of this section we prove the following central lemma which generalizes Step C of the proof of the computable intermediate value theorem in Section 1.

Lemma 4.2.

Suppose $\neg Q$ and let $(V, c)$ be a gate crossed by g. Then there is a gate $(V^{'}, c^{'})$ crossed by g such that $\overline{V^{'}} \subseteq V$ and $diameter (V^{'}) < diameter (V) / 2$ .

We define a sequence $(V_{i}, a_{i}) : = (B (f (a_{i}), r_{i}), a_{i})$ of overlapping ball-shaped gates covering $f ({\overline{I}}_{V c})$ such that also the intersections of consecutive balls (lenses) are gates and show that at least one of these gates must be crossed by g. Figure 4 shows a ball-shaped gate $(V, c)$ with such a sequence of balls. The picture is topologically correct but not metrically. In general the sequence of balls may have numerous loops. The exact details are given below.

Figure 4.

A ball-shaped gate $(V, c)$ with a chain of balls covering f in V.

First we define balls $V_{0}, V_{1}, \dots, V_{n}, V_{n + 1}$ and rational numbers $b_{1}, \dots, b_{n - 1}$ . Since the functions f and g are continuous on the compact interval $[0; 1]$ , they are uniformly continuous. Therefore, there is an non-decreasing modulus function $mod : Q \to Q$ such that for all $a, b \in [0, 1]$ , $\begin{array}{rcl} (27) & | f (a) - f (b) | & < & γ and | g (a) - g (b) | < γ if | a - b | < mod (γ) (for all γ > 0) . \end{array}$ Since $f \circ inf (I_{V c}), f \circ sup (I_{V c}) \notin range (g)$ (since $(V, c)$ is a gate) and $range (g)$ is compact, there is a rational number $\overline{r}$ such that $\begin{array}{rcl} (28) & B (f \circ inf (I_{V c}), 2 \overline{r}) \cap range (g) = \emptyset and B (f \circ sup (I_{V c}), 2 \overline{r}) \cap range (g) = \emptyset \end{array}$ (see the first ball and the last ball in Fig. 4). Since $(V, c)$ is crossed by g, $f \circ inf (I_{V c}) \neq f \circ sup (I_{V c})$ . Therefore for avoiding pathological cases, we may assume $\begin{array}{rcl} (29) & B (f \circ inf (I_{V c}), 2 \overline{r}) \cap B (f \circ sup (I_{V c}), 2 \overline{r}) = \emptyset . \end{array}$ Since f is continuous, there are rational numbers $a_{l}$ , $a_{r}$ such that $\begin{array}{l} (30) & \begin{matrix} inf (I_{V c}) < a_{l} < a_{r} < sup (I_{V c}), f [inf (I_{V c}); a_{l}] \subseteq B (f \circ inf (I_{V c}), \overline{r}) and \\ f [a_{r}; sup (I_{V c})] \subseteq B (f \circ sup (I_{V c}), \overline{r}) . \end{matrix} \end{array}$ Since $f [inf (I_{V c}); a_{l}]$ and $f [a_{r}; sup (I_{V c})]$ are compact and $f [a_{l}, a_{r}]$ is a compact subset of the open set V, there is a rational number $s > 0$ such that $\begin{array}{l} (31) & B (x, 3 s) \subseteq B (f \circ inf (I_{V c}), \overline{r}) for all x \in f [inf (I_{V c}); a_{l}], \\ (32) & B (x, 3 s) \subseteq B (f \circ sup (I_{V c}), \overline{r}) for all x \in f [a_{r}; sup (I_{V c})] and \\ (33) & B (x, 3 s) \subseteq V for all x \in f [a_{l}; a_{r}] . \end{array}$

For $i ⩾ 1$ let $ε_{i} : = 2^{- i - 1} \cdot s$ . Then $\sum_{i ⩾ 1} ε_{i} = s / 2$ . We choose $n \in N$ , rational numbers $a_{i}$ , $b_{i}$ , $r_{i}$ , $s_{i}$ and a real number $t_{i}$ inductively as follows.

$r_{0} : = s$ , $a_{1} : = a_{l}$ .

Suppose

r_{i - 1}

and

a_{i}

such that

r_{i - 1} ⩽ s

and

a_{i} ⩾ a_{l}

have been chosen.

If $a_{i} ⩾ a_{r}$ then define $n : = i - 1$ (End of construction.), else choose $t_{i}$ , $b_{i}$ , $s_{i}$ , $a_{i + 1}$ and $r_{i}$ such that $\begin{array}{l} (34) & t_{i} : = sup {b \in Q, a_{i} < b ∣ f [a_{i}; b] \subseteq B (f (a_{i}), r_{i - 1})}, \\ (35) & b_{i} \in Q, a_{i} < b_{i} and t_{i} - mod (ε_{i}) < b_{i} < t_{i}, \\ (36) & s_{i} < r_{i - 1} and f [a_{i}; b_{i}] \subseteq B (f (a_{i}), s_{i}), \\ (37) & t_{i} - mod ((r_{i - 1} - s_{i}) / 2) < a_{i + 1} < t_{i}, \\ (38) & s_{i} < r_{i} < (s_{i} + r_{i - 1}) / 2 and (B (f (a_{i}), r_{i}), a_{i}) is a gate . \end{array}$ Figure 5 illustrates the construction. Notice that in general $ε_{i}$ is much smaller than shown in the figure since it converges to 0 while $r_{i} > s / 2$ for all i (by (42)).

Figure 5.

The definition of $b_{i}$ , $a_{i + 1}$ and $r_{i}$ from $a_{i}$ and $r_{i - 1}$ .

We define $\begin{array}{rcl} (39) & V_{0} : = B (f \circ inf (I_{V c}), \overline{r}), V_{n + 1} : = B (f \circ sup (I_{V c}), \overline{r}), V_{i} : = B (f (a_{i}), r_{i}) (1 ⩽ i ⩽ n) . \end{array}$ These balls are shown in Fig. 4. We must show that the construction is sound, in particular that it ends after finitely many steps. First we show that numbers $t_{i}$ , $b_{i}$ , $s_{i}$ , $a_{i + 1}$ and $r_{i}$ exist provided $a_{i} < a_{r}$ .

$t_{i}$ : Since $a_{l} ⩽ a_{i} < a_{r}$ , $B (f (a_{i}), r_{i - 1}) \subseteq B (f (a_{i}), s) \subseteq V$ by (33). Therefore, $t_{i}$ exists.

$b_{i}$ exists.

$s_{i}$ exists since $b_{i} < t_{i}$ .

$a_{i + 1}$ exists since $s_{i} < r_{i - 1}$

$r_{i}$ : Since $s_{i} < r_{i - 1}$ , $s_{i} < (s_{i} + r_{i - 1}) / 2$ . By (25) $r_{i}$ exists such that $s_{i} < r_{i} < (s_{i} + r_{i - 1}) / 2$ , $f \circ max (K_{a_{i} r_{i}}) \notin range (g)$ and $f \circ \in (L_{a_{i} r_{i}}) \notin range (g)$ . By (26), $(B (f (a_{i}), r_{i}), a_{i})$ is a gate.

Notice that (38) is the place where the assumption $\neg Q$ is needed. Below we will use the following equality which follows from continuity of f: $\begin{array}{rcl} (40) & | f (a) - f (t) | & = & r if t = sup {b \in Q, a < b ∣ f [a; b] \subseteq B (f (a), r)} and B (f (a), r) \subseteq {(0; 1)}^{2} . \end{array}$

Lemma 4.3.

Suppose $i ⩾ 1$ , $a_{l} ⩽ a_{i} < a_{r}$ and $s - \sum_{k = 1}^{i - 1} ε_{k} ⩽ r_{i - 1} ⩽ s$ . Then: $\begin{array}{l} (41) & r_{i} < r_{i - 1}, \\ (42) & s - \sum_{k = 1}^{i} ε_{k} < s_{i} (< r_{i} < r_{i - 1} ⩽ s), \\ (43) & f [a_{i}; b_{i}] \subseteq B (f (a_{i}), r_{i}), \\ (44) & f [b_{i}; a_{i + 1}] \subseteq B (f (a_{i + 1}), s / 2), \\ (45) & r_{i} < | f (a_{i}) - f (a_{i + 1}) | < 3 s / 2, \\ (46) & a_{i + 1} ⩾ a_{i} + mod (s / 2) . \end{array}$

Proof.

( 41 ) This follows from (36) and (38).

( 42 ) By (35), $| f (t_{i}) - f (b_{i}) | < ε_{i}$ and by (36), $| f (a_{i}) - f (b_{i}) | < s_{i}$ . Therefore by (40) and (38), $r_{i - 1} = | f (a_{i}) - f (t_{i}) | ⩽ | f (a_{i}) - f (b_{i}) | + | f (b_{i}) - f (t_{i}) | < s_{i} + ε_{i}$ .

We obtain $s - \sum_{k = 1}^{i} ε_{k} = s - \sum_{k = 1}^{i - 1} ε_{k} - ε_{i} ⩽ r_{i - 1} - ε_{i} < s_{i} < r_{i} < r_{i - 1} < s$ (by (38) and (41)).

( 43 ) By (36) and (38), $f [a_{i}; b_{i}] \subseteq B (f (a_{i}), s_{i}) \subseteq B (f (a_{i}), r_{i})$ .

( 44 ) Let $b_{i} ⩽ b ⩽ a_{i + 1}$ .

By (35) and (37), $t_{i} - mod (ε_{i}) < b_{i} ⩽ b ⩽ a_{i + 1} < t_{i}$ , hence $| a_{i + 1} - b | < mod (ε_{i})$ , therefore by (42), $| f (b) - f (a_{i + 1}) | < ε_{i} < s / 2$ . (44) follows immediately.

( 45 ) By (42–44), $| f (a_{i}) - f (a_{i + 1}) | ⩽ | f (a_{i}) - f (b_{i}) | + | f (b_{i}) - f (a_{i + 1}) | < r_{i} + s / 2 ⩽ 3 s / 2$ .

By (37), $| f (a_{i + 1}) - f (t_{i}) | < (r_{i - 1} - s_{i}) / 2$ , hence by (40), $r_{i - 1} = | f (a_{i}) - f (t_{i}) | ⩽ | f (a_{i}) - f (a_{i + 1}) | + | f (a_{i + 1}) - f (t_{i}) | < | f (a_{i}) - f (a_{i + 1}) | + (r_{i - 1} - s_{i}) / 2$ . Therefore, $| f (a_{i}) - f (a_{i + 1}) | > r_{i - 1} - (r_{i - 1} - s_{i}) / 2 = (r_{i - 1} + s_{i}) / 2 > r_{i}$ by (38).

This proves (45).

( 46 ) Suppose $a_{i + 1} - a_{i} < mod (s / 2)$ . Then $| f (a_{i + 1}) - f (a_{i}) | < s / 2$ . But by (45) and (42), $| f (a_{i + 1}) - f (a_{i}) | > r_{i} ⩾ s - \sum_{k = 1}^{i} ε_{k} > s / 2$ . □

Since the assumptions of Lemma 4.3 are true for $i = 1$ ( $r_{i - 1} = s$ , $a_{1} = a_{l}$ ), the construction can be started with $i = 1$ . If it has been performed for $i - 1$ then (41)–(46) are true for $i - 1$ . By (42), $r_{i - 1} < s$ and $a_{i} ⩾ a_{l}$ . Then the construction can be continued with i, provided $a_{i} < a_{r}$ . By (46) there is a greatest number i such that $a_{i} < a_{r}$ . This number has been called n. Then $a_{n} < a_{r} ⩽ a_{n + 1}$ .

Lemma 4.4.

For the balls $V_{0}$ , $V_{n + 1}$ and $V_{i} = B (f (a_{i}), r_{i})$ ( $1 ⩽ i ⩽ n$ ) from ( 39 ) (see Fig. 4 ), $\begin{array}{l} (47) & {\overline{V}}_{1} \subseteq V_{0}, {\overline{V}}_{n} \subseteq V_{n + 1}, \\ (48) & {\overline{V}}_{i} \subseteq B (f (a_{i}), s) \subseteq B (f (a_{i}), 3 s) \subseteq V . \end{array}$

Proof.

${\overline{V}}_{1} = B (f (a_{1}), r_{1}) \subseteq V_{0}$ by (31) since $a_{1} = a_{l}$ and $r_{1} < s$ by (42). Since $B (f (a_{n + 1}), 3 s) \subseteq V_{n + 1}$ (by (32)), $| f (a_{n}) - f (a_{n + 1}) | < 3 s / 2$ (by (45)) and $r_{n} < s$ , ${\overline{V}}_{n} \subseteq B (f (a_{n}), s) \subseteq B (f (a_{n + 1}), 3 s) \subseteq V_{n + 1}$ . The third statement follows from (42) and (33). □

For $1 ⩽ i < n$ let $L_{i} : = V_{i} \cap V_{i + 1}$ . By (41)–(45) for $1 ⩽ i < n$ , $\begin{array}{rcl} (49) & f (a_{i}) \notin V_{i + 1}, f (a_{i + 1}) \notin V_{i}, f (b_{i}) \in V_{i} \cap V_{i + 1} = L_{i} . \end{array}$ Therefore the positions of $a_{i}$ , $a_{i + 1}$ and $b_{i}$ are drawn correctly in Fig. 6. By (49) $(L_{i}, b_{i})$ is a passage. Define $\begin{matrix} (p_{i}, q_{i}) : = I_{V_{i} a_{i}} and (p_{L i}, q_{L i}) : = I_{L_{i} b_{i}} . \end{matrix}$

The straight line segments in Fig. 6 correspond to the dotted lines in Fig. 3.

Figure 6.

The balls $V_{i}$ and $V_{i + 1}$ . The numbers $a_{i}$ , $b_{i}$ , $p_{i}$ , $q_{i}$ are “times” for f.

Lemma 4.5.

Suppose $1 ⩽ i < n$ . Then

$(V_{j}, a_{j})$ is a gate (for $1 ⩽ j ⩽ 1$ ),

$f (q_{i}) \in \partial V_{i} \cap V_{i + 1}$ and $f (p_{i + 1}) \in V_{i} \cap \partial V_{i + 1}$ ,

$q_{i} = q_{L i}$ and $p_{i + 1} = p_{L i}$ .

$(L_{i}, b_{i})$ is a gate.

Proof.

1: By (38).

2: This follows from (43) and (44)

3: By (43) and (44), $\begin{array}{l} \begin{matrix} q_{i} & = sup {b > a_{i} ∣ f [a_{i}; b] \in V_{i}} \\ = sup {b > b_{i} ∣ f [b_{i}; b] \in V_{i}} \\ = sup {b > b_{i} ∣ f [b_{i}; b] \in V_{i} \cap V_{i + 1}} = q_{L i}, \end{matrix} \\ \begin{matrix} p_{i + 1} & = inf {b < a_{i} ∣ f [b; a_{i}] \in V_{i + 1}} \\ = inf {b < a_{i} ∣ f [b; b_{i}] \in V_{i + 1}} \\ = inf {b < a_{i} ∣ f [b; b_{i}] \in V_{i} \cap V_{i + 1}} = p_{L i} . \end{matrix} \end{array}$

4: This follows from 3. and 1. □

By Lemma 4.5.2 in Fig. 6 the points $f (p_{i + 1})$ and $f (q_{i})$ are positioned correctly, in particular by Lemma 4.5.2 they are different and not in $\partial V_{i} \cap \partial V_{i + 1}$ (the peaks of $L_{i}$ ). Notice that $f (p_{i}) \in V_{i + 1}$ is not excluded, but always $f (p_{i}) \neq f (q_{i})$ by definition. The line segments in Fig. 6 correspond to the dotted line segments in Fig. 3.

Figure 7 (as a detail of Fig. 4) shows an example of the balls $V_{1} = B (f (a_{1}), r_{1}), \dots, V_{5} = B (f (a_{5}), r_{5})$ . The figure is topologically correct but not metrically, in particular since (31) and (33) are not satisfied.

For $1 ⩽ i ⩽ n$ let $γ_{i} : = \overline{f (p_{i}) f (q_{i})}$ be the straight line segment from $f (p_{i})$ to $f (q_{i})$ and for $1 ⩽ i < n$ let $δ_{i} : = \overline{f (q_{i}) f (p_{i + 1})}$ . These line segments correspond to the dotted lines in Fig. 3. The sequence $γ_{1}, δ_{1}, γ_{2}, \dots, δ_{n - 1}, γ_{n}$ forms a polygon path $Pf : = ⋃ γ_{i}$ running from $p_{1} \in V \cap V_{0}$ to $q_{n} \in V \cap V_{n + 1}$ (Fig. 7).6

⁶

We have $p_{i} < a_{i} < p_{i + 1} < b_{i} < q_{i} < a_{i + 1} < q_{i + 1}$ (where $p_{i + 1} < b_{i}$ by (44) and $f (p_{i + 1}) \in V_{i} ∖ V_{i + 1}$ ). However, running along the straight line segments in Fig. 6 the point $f (q_{i})$ is visited before the point $f (p_{i + 1})$ . This is no contradiction.

Figure 7.

The balls $V_{i} = B (f (a_{i}), r_{i})$ , $i = 1, \dots, 5$ inside of the set V and the path $Pf$ .

Now we complete the proof of Lemma 4.2. We have a gate $(V, c)$ crossed by g via some d as in Fig. 4 ( $f (c)$ and $g (d)$ are not marked in this figure) with more details in Fig. 7. Let $(t_{1}, t_{2}) : = I_{V d}^{g}$ . By (28), $\begin{matrix} g (t_{1}), g (t_{2}) \in V^{'} : = \overline{V} ∖ (V_{0} \cup V_{n + 1}) . \end{matrix}$ The polygon $Pf$ may have loops (not only loops inside a gate as shown in Fig. 7 but much longer ones). By cutting the loops we obtain a loop-free polygon ${Pf}^{'} \subseteq Pf$ running from $f (p_{1}) \in \partial V_{1}$ to $f (q_{n}) \in \partial V_{n}$ . Then $V^{'}$ is the disjoint union of ${Pf}^{'} \cap V^{'}$ and two connected sets $T_{1}$ , $T_{2}$ such that the set $T_{1} \cup T_{2}$ is not connected, $g (t_{1}) \in T_{1} \cap \partial V$ and $g (t_{2}) \in T_{2} \cap \partial V$ since $(V, c)$ is crossed by g. (The polygon ${Pf}^{'}$ cuts the set $V^{'}$ into disjoint parts $T_{l}$ and $T_{2}$ with $g (t_{1}) \in T_{1}$ and $g (t_{2}) \in T_{2}$ , see Fig. 4.)

Suppose $Pf \cap g [t_{1}; t_{2}] = \emptyset$ . Then ${Pf}^{'} \cap g [t_{1}; t_{2}] = \emptyset$ . Since $g (t_{1}) \in T_{1}$ , $g [t_{1}; t_{2}] \subseteq V^{'}$ and $g [t_{1}; t_{2}]$ is connected, $g [t_{1}; t_{2}] \subseteq T_{1}$ . Therefore, $\begin{matrix} g [t_{1}; t_{2}] \subseteq T_{1} \subseteq T_{1} \cup Pf \subseteq T_{1} \cup ⋃_{i = 1}^{n} {\overline{V}}_{i} . \end{matrix}$ We observe $g (t)$ for increasing $t ⩾ t_{1}$ . Whenever g enters a gate $(V_{i}, a_{i})$ or $(L_{i}, b_{i})$ it must leave it at the same side of the line $γ_{i}$ or $δ_{i}$ , respectively, without crossing it.

Now we replace the assumption $Pf \cap g [t_{1}; t_{2}] = \emptyset$ by the weaker assumption: none of the gates $(V_{i}, a_{i})$ and $(L_{i}, b_{i})$ is crossed by g. If g enters $V_{i}$ (by Definition 4.1 the endpoints of $γ_{i}$ are not in $range (g)$ ) then it may cross the line $γ_{i}$ but must stay in $V_{i}$ and finally leave $V_{i}$ in the same side. The line segment $γ_{i}$ can be crossed only locally. (correspondingly for $(L_{i}, b_{i})$ and $δ_{i}$ ), see the left example in Fig. 3. Therefore, also with this weaker assumption $\begin{array}{rcl} (50) & g (t_{2}) \in g [t_{1}; t_{2}] \subseteq T_{1} \cup ⋃_{i = 1}^{n} {\overline{V}}_{i} . \end{array}$ Since by the definition of $T_{1}$ and $T_{2}$ , $T_{1} \cap T_{2} = \emptyset$ and $g (t_{2}) \in T_{2}$ , $g (t_{2}) \in T_{1}$ is impossible. By (42) and (33), $\begin{matrix} d (⋃_{i = 1}^{n} {\overline{V}}_{i}, \partial V) ⩾ d (⋃_{i = 1}^{n} \overline{B} (f (a_{i}), s), \partial V) ⩾ 2 s . \end{matrix}$ Since $g (t_{2}) \in \partial V$ , $g (t_{2}) \in ⋃_{i = 1}^{n} {\overline{V}}_{i}$ is impossible. Therefore (50) is false. Contradiction.7

⁷

Consider the path $Pf$ as a fence with posts $p_{1}, q_{1}, p_{2}, q_{2}, \dots, p_{n}, q_{n}$ and planks between consecutive posts. Then it is not possible to walk from $g (t_{1})$ to $g (t_{2})$ without crossing one of the planks. If we replace each plank by a belt which allows to cross the plank only locally it is still impossible to walk from $g (t_{1})$ at time $g (t_{2})$ .

We conclude that one of the gates $(V_{i}, a_{i})$ and $(L_{i}, b_{i})$ must be crossed by g. This ends the proof of Lemma 4.2.

5. The second alternative

In this section we generalize Step D of the proof of the computable intermediate value theorem in Section 1. We generalize the sets K and L from (10), (11) and Fig. 2 to gates. If $(V, c)$ is a gate crossed by g via d we call $(V, c, d)$ a crossing.

Definition 5.1.

A meeting is a triple $(V, c_{f}, c_{g})$ , such that $c_{f}, c_{g} \in Q$ and $f (c_{f}), g (c_{g}) \in V$ where V is either a ball $B (f (a), r)$ (a ball-shaped meeting) such that $a, r \in Q$ and $\overline{B (f (a), r)} \subseteq {(0, 1)}^{2}$ or V is the strict intersection8
⁸
We call the intersection of $B_{1}$ and $B_{2}$ strict if $B_{1} ⊈ B_{2}$ , $B_{2} ⊈ B_{1}$ and $B_{1} \cap B_{2} \neq \emptyset$ .

of two such balls, $V = B_{1} \cap B_{2}$ where $B_{1} = B (f (a_{1}), r_{1})$ and $B_{2} = B (f (a_{2}), r_{2})$ (a lens-shaped meeting). For a lens-shaped meeting let ${z_{1}, z_{2}} : = \partial B_{1} \cap \partial B_{2}$ (the peaks of V).

For a meeting $(V, c_{f}, c_{g})$ define $\begin{array}{l} K^{f} : = [p_{f}^{'}, p_{f}] and \\ L^{f} : = [q_{f}, q_{f}^{'}] where \\ (p_{f}; q_{f}) : = the longest open interval I such that c_{f} \in I and f (I) \subseteq V, and \\ (p_{f}^{'}; q_{f}^{'}) : = the longest open interval I such that c_{f} \in I and f (\overline{I}) \subseteq \overline{V} . \end{array}$ The numbers and intervals $p_{g}$ , $q_{g}$ , $p_{g}^{'}$ , $q_{g}^{'}$ , $K^{g}$ and $L^{g}$ are defined accordingly.

A meeting $(V, c_{f}, c_{g})$ is a crossing if the four points $f (p_{f})$ , $f (q_{f})$ , $g (p_{g})$ and $g (q_{g})$ are pairwise different and alternate in f and g on the boundary of V (equivalently, if the straight line segments from $f (p_{f})$ to $f (q_{f})$ and from $g (p_{g})$ to $g (q_{g})$ intersect in V).

A meeting $(V, c_{f}, c_{g})$ is a proper crossing, if there are rational balls (i.e. balls $B (c, r)$ with rational c and r) $B_{K}^{f}$ , $B_{L}^{f}$ , $B_{K}^{g}$ , $B_{L}^{g}$ such that $\begin{array}{l} (51) & the four balls are pairwise disjoint, \\ (52) & the four balls alternate in f and g on the boundary of V, \\ (53) & f (K^{f}) \subseteq B_{K}^{f}, f (L^{f}) \subseteq B_{L}^{f}, f (K^{g}) \subseteq B_{K}^{g}, f (L^{g}) \subseteq B_{L}^{g} . \end{array}$ and if $V = B_{1} \cap B_{2}$ is lens-shaped then for each of the four balls B, $\begin{array}{rcl} (54) & \overline{B} \subseteq B_{1} or \overline{B} \subseteq B_{2}, or z_{1} \in B or z_{2} \in B . \end{array}$

Figure 8 shows a ball-shaped proper crossing. The right side shows a ball $B_{L}^{g}$ violating (54).

Figure 8.
A proper ball-shaped proper crossing and a ball $B_{L}^{g}$ violating (54).
Lemma 5.2.
Every proper crossing is a crossing.
Proof.
By the definitions $f (p_{f}) \in f (K^{f}) \cap \partial V$ , $f (q_{f}) \in f (L^{f}) \cap \partial V$ , $g (p_{g}) \in g (K^{g}) \cap \partial V$ and $g (q_{g}) \in g (L^{g}) \cap \partial V$ (see Fig. 2). Since the four sets are pairwise disjoint the four points are pairwise different. By (52) the four points $f (p_{f})$ , $f (q_{f})$ , $g (p_{g})$ and $g (q_{g})$ alternate in f and g on the boundary of V. □

In our new terminology Lemma 4.2 can be expressed as follows:
Lemma 5.3.
For every crossing $(V, c_{f}, c_{g})$ there is a crossing $(V^{'}, c_{f}^{'}, c_{g}^{'})$ such that $\overline{V^{'}} \subseteq V$ and $diameter (V^{'}) < diameter (V) / 2$ .

We will compute an intersection point of f and g as the limit of a nested decreasing sequence of crossings. Unfortunately the set of crossings is not c.e. since the endpoints of the sets K and L are not computable so that the condition from Definition 5.1.3 is not c.e.9
⁹
For example, for a crossing $(V, c_{f}, c_{g})$ possibly $f (K^{f}) = f (L^{f}) = f (K^{g}) = f (L^{g}) = \partial V$ .

We solve the problem by Lemma 5.4 and Lemma 5.5 below.
Lemma 5.4.
For every crossing $(V, c_{f}, c_{g})$ there is a proper crossing $(W, c_{f}, c_{g})$ such that $W \subseteq V$ .
Proof.
We consider the case of a lens-shaped crossing. The proof for ball-shaped crossings is similar but simpler. Consider a crossing $(V, c_{f}, c_{g})$ where $V = B_{1} \cap B_{2}$ . For $δ > 0$ let $V_{δ} : = B_{1 δ} \cap B_{2 δ}$ where $B_{1 δ} : = B (f (a_{1}), r_{1} - δ)$ and $B_{2 δ} : = B (f (a_{2}), r_{2} - δ)$ .

There is some $δ_{0} > 0$ such that ${f (c_{f}), g (c_{g})} \subseteq V_{δ}$ if $0 ⩽ δ < δ_{0}$ . Therefore, for $0 ⩽ δ < δ_{0}$ we have intervals and points $K_{δ}^{f}, \dots, q_{g δ}^{'}$ according to Definition 5.1.2 (see Fig. 2).

By Definition 5.1.3 the four points $f (p_{f})$ , $f (q_{f})$ , $g (p_{g})$ and $g (q_{g})$ are pairwise different. Therefore, there is some $e \in Q$ , $e > 0$ , such that the four balls $B (f (p_{f}), 2 e)$ , $B (f (q_{f}), 2 e)$ , $B (g (p_{g}), 2 e)$ and $B (g (q_{g}), 2 e)$ are pairwise disjoint and for each of these balls B with radius $2 e$ , $\begin{array}{rcl} (55) & \overline{B} \subseteq B_{1} or \overline{B} \subseteq B_{2} or z_{1} = center (B) or z_{1} = center (B) . \end{array}$ First we consider the point $q_{f}$ . Since f is continuous there is some $s \in Q$ , $c_{f} < s < q_{f}$ , such that $f [s; q_{f}] \subseteq B (f (q_{f}), e)$ . There is some $0 < δ_{1} < min (δ_{0}, e / 2)$ such that $f [c_{f}; s] \subseteq V_{δ_{1}}$ . For every $0 < β < δ_{1}$ we obtain $s < L_{β}^{f} < q_{f}$ (where $L_{β}^{f} : =$ the longest interval I such that $c_{f} \in I$ and $f (I) \subseteq V_{β}$ ), hence $\begin{matrix} (56) & f (L_{β}^{f}) \subseteq f [s; q_{f}] \subseteq B (f (q_{f}), e) if 0 < β < δ_{1} . \end{matrix}$ Correspondingly for the other numbers $p_{f}$ , $p_{g}$ , $q_{g}$ there are numbers $δ_{2}$ , $δ_{3}$ and $δ_{4}$ . Choose some $γ \in Q$ such that $\begin{array}{rcl} (57) & 0 < γ < min {δ_{1}, δ_{2}, δ_{3}, δ_{4}}, | z_{1 γ} - z_{1} | < e / 2, | z_{2 γ} - z_{2} | < e / 2 . \end{array}$

We show that $(V_{γ}, c_{f}, c_{g})$ is a proper crossing. Since $γ < δ_{1} < δ_{0}$ , ${f (c_{f}), g (c_{g})} \subseteq V_{γ}$ . Therefore, $(V_{γ}, c_{f}, c_{g})$ is a meeting. For $(V_{γ}, c_{f}, c_{g})$ let $z_{1 γ}, z_{2 γ}, p_{f γ}, \dots, K_{γ}^{f}, \dots$ be the numbers and intervals introduced in Definition 5.1. We must verify Definition 5.1.4 for $(V_{γ}, c_{f}, c_{g})$ . By (56), $\begin{array}{l} (58) & \begin{array}{l} f (K_{γ}^{f}) \subseteq B (f (p_{f}), e), f (L_{γ}^{f}) \subseteq B (f (q_{f}), e), \\ f (K_{γ}^{g}) \subseteq B (f (p_{g}), e), f (L_{γ}^{g}) \subseteq B (f (q_{g}), e), \end{array} \end{array}$ where the balls are not necessarily rational.

First we consider $L_{γ}^{f}$ . Since $f (L_{γ}^{f})$ is a compact subset of $B (f (q_{f}), e)$ there is some $c \in Q^{2}$ such that $\begin{array}{rcl} (59) & | f (q_{f}) - c | < e / 2 and f (L_{γ}^{f}) \subseteq B (c, e) \subseteq B (f (q_{f}), 3 e / 2) . \end{array}$ Define $B_{L γ}^{f} : = B (c, e)$ . Then $f (L_{γ}^{f}) \subseteq B_{L γ}^{f}$ . Therefore (53) is true for $L_{γ}^{f}$ . We apply (55).

Suppose $\overline{B (f (q_{f}), 2 e)} \subseteq B_{1}$ . Since $| f (q_{f}) - c | < e / 2$ and $γ < e / 2$ , $B_{L γ}^{f} = B (c, e) \subseteq B (f (q_{f}), 3 e / 2) \subseteq B_{1 γ}$ . Therefore (54) is true for the case $V_{γ}$ . If $\overline{B (f (q_{f}), 2 e)} \subseteq B_{2}$ then (54) is true for the case $V_{γ}$ accordingly.

Suppose in (55) $z_{1} = center (B (f (q_{f}), 2 e))$ , that is, $f (q_{f}) = z_{1}$ . By (57) and (59), $| z_{1 γ} - c | ⩽ | z_{1 γ} - z_{1} | + | z_{1} - c | < e / 2 + e / 2 = e$ , hence $z_{1 γ} \in B (c, e) = B_{L γ}^{f}$ . Therefore (54) is true for the case $V_{γ}$ . If $z_{2} = center (B (f (q_{f}), 2 e))$ then (54) is true for the case $V_{γ}$ accordingly.

All of this can be proved for $K_{γ}^{f}$ , $K_{γ}^{g}$ and $L_{γ}^{g}$ (see (58)) accordingly. Therefore (54) has been proved for $(V_{γ}, c_{f}, c_{g})$ .

Since $(V, c_{f}, c_{g})$ is a crossing the points $f (p_{f})$ , $f (q_{f})$ , $g (p_{g})$ and $g (q_{g})$ are pairwise different and alternate in f and g on the boundary of V. Let $u > 0$ be a lower bound of the mutual distances of these four points. We may choose $e < u / 100$ and $γ < u / 100$ . Then obviously the four balls $B_{K γ}^{f}$ , $B_{L γ}^{f}$ , $B_{K γ}^{g}$ and $B_{L γ}^{g}$ alternate in f and g on the boundary of $V_{γ}$ . We omit a detailed verification. This proves (52) for $V_{γ}$ .

Therefore, $(V_{γ}, c_{f}, c_{g})$ is a proper crossing. □
Lemma 5.5.
The set of ball-shaped proper crossings and the set of lens-shaped proper crossings are c.e.

More precisely, the set of tuples $(a, r, c_{f}, c_{g}) \in Q^{4}$ such that $(B (f (a), r), c_{f}, c_{g})$ is a proper crossing is c.e., and the set of tuples $(a_{1}, r_{1}, a_{2}, r_{2}, c_{f}, c_{g}) \in Q^{6}$ such that $(B (f (a_{1}), r_{1}) \cap B (f (a_{2}), r_{2}), c_{f}, c_{g})$ is a proper crossing is c.e.
Proof.
We consider the case of lens-shaped crossings. The proof for ball-shaped crossings is similar. We use Definition 5.1.

For a tuple $(a_{1}, r_{1}, a_{2}, r_{2}, c_{f}, c_{g}) \in Q^{6}$ , $(B (f (a_{1}), r_{1}) \cap B (f (a_{2}), r_{2}), c_{f}, c_{g})$ is a proper crossing if there are rational balls $B_{K}^{f}$ , $B_{L}^{f}$ , $B_{K}^{g}$ and $B_{L}^{g}$ such that $(V, c_{f}, c_{g})$ is a meeting and (51)–(54) are true.

The predicate ( $(V, c_{f}, c_{g})$ is a meeting) is c.e. The properties (51), (52) and (54) are decidable. Since $K^{f} \subseteq (d_{1}; d_{2})$ (for rational $d_{1}$ , $d_{2}$ ) is c.e. (c.f. Lemma 2.1), $K^{f}$ can computed (as a compact set). Since f is computable, $f (K^{f})$ can be computed (as a compact set). Therefore $f (K^{f}) \subseteq B_{K}^{f}$ is c.e. Since the other three predicates from (53) are c.e. accordingly, (53) is c.e.

Therefore, the set of tuples $(a_{1}, r_{1}, a_{2}, r_{2}, c_{f}, c_{g}) \in Q^{6}$ such that $(B (f (a_{1}), r_{1}) \cap B (f (a_{2}), r_{2}), c_{f}, c_{g})$ is a proper crossing is c.e. □

We can now prove the generalization of Step D of the proof of the computable intermediate value theorem in Section 1.
Theorem 5.6.
If $\neg Q$ then there is a computable point $x \in range (f) \cap range (g)$ .
Proof.
We assume $\neg Q$ (18). By Definition 4.1 the unit square, more precisely $({(0; 1)}^{2}, 1 / 2)$ is a gate which is crossed by g via $1 / 2$ . By Lemma 4.2 there is a gate $(V^{'}, c^{'})$ crossed by g via some d such that $diameter (V^{'}) < 1$ . According to Definition 5.1, $(V^{'}, c^{'}, d)$ is a crossing. which by Lemma 5.4 has a smaller proper subcrossing. By Lemma 5.3 and Lemma 5.4 every proper crossing has a has a proper subcrossing with much smaller diameter. By Lemma 5.5 we can compute a sequence ${((V_{i}, c_{f i}, c_{g i}))}_{i \in N}$ of proper crossings such that ${\overline{V}}_{i + 1} \subseteq V_{i}$ and $diameter (V_{i}) < 2^{- i}$ . The limit $x \in R^{2}$ such that ${x} = ⋂_{i} V_{i}$ is a computable point.

Every neighborhood of x contains $f (c_{f i}) \in range (f)$ for some $i \in N$ . Since $[0; 1]$ is compact, $range (f)$ is compact, hence complete. Therefore, $x \in range (f)$ . Accordingly, $x \in range (g)$ . □

The main theorem 1.4 follows from Theorems 3.2 and 5.6.
6. Final remarks

For Case Q we have shown that $f (α) \in range (g)$ for some computable number α (Theorem 3.2). But we have not shown that for this α there is a computable number β such that $f (α) = g (β)$ .

For Case $\neg Q$ in the proof of Theorem 5.6 we have shown that the $f (c_{f i})$ converge to x. (This does not mean that, for example, the sequence $c_{f 0}, c_{f 1}, c_{f 2}, \dots$ converges.) But we have not computed some $α \in (0; 1)$ such that $f (α) = x$ . Correspondingly, we have not computed some $β \in (0; 1)$ such that $f (β) = x$ . Therefore, possibly $f (α) = g (β) = x$ for no computable numbers α and β.

In general, from the fact that $x \in range (g)$ is computable we cannot conclude that $g (t) = x$ for some computable number t. In the following example $g (t) = x$ for many real numbers t but for no computable one.

Example 6.1.

Let $x : = (1 / 2, 1 / 2)$ . Let $h_{0}$ be the function from Footnote 1. From $h_{0}$ we can define a computable function $h_{1}$ such that $h_{1} (1 / 3) = - 1 / 2 = h_{1} (2 / 3)$ and $h_{0}$ and $h_{1}$ have the same zeroes. Define $\begin{matrix} g (t) : = \{\begin{matrix} (3 / 2 t, 0) & if 0 ⩽ t ⩽ 1 / 3, \\ (1 / 2, h_{1} (t) + 1 / 2) & if 1 / 3 ⩽ t ⩽ 2 / 3, \\ ((3 t - 1) / 2, 0) & if 2 / 3 ⩽ t ⩽ 1 . \end{matrix} \end{matrix}$ Then $g (t) = x$ for many non-computable numbers t but for no computable one.

If f and g are continuous but not necessarily computable our constructions are still computable in f and g (w.r.t. the canonical representation of the continuous functions $h : [0; 1] \to {[0; 1]}^{2}$ [12,13]). The predicate Q (31) however, is not continuous (hence not computable) in f, g and furthermore, in the proof of Theorem 3.2, the decision required in (24) is not continuous (hence not computable) in f, g. Possibly, the predicate Q is not optimal. Also for finding α and β such that $f (α) = g (β)$ possibly some other predicate must be used.

The degree of unsolvability of the operator finding a point of intersection in Theorem 1.1 has not yet been located in the Weihrauch lattice [2]. By [2, Theorem 7.34] ${CC}_{[0; 1]} \equiv_{s W} IVT$ . Presumably the following claim is true.

Claim 6.2.

The multi-valued operator H mapping each pair $(f, g)$ of continuous functions with the properties from Theorem 1.1 to a pair $(S_{f}, S_{g})$ of closed intervals such that $f (S_{f}) = g (S_{g})$ is computable.

From this claim Corollaries 6.3 and 6.4 can be proved

Corollary 6.3.

$IP \equiv_{s W} IVT$ .

Proof.

For a realization of $IP$ it suffices to find some real number α such that $f (α) \in range (g)$ . For finding such a number first apply H from Claim 6.2 and then apply ${CC}_{[0; 1]}$ to the set $S_{f}$ . This shows $IP ⩽_{s W} {CC}_{[0; 1]}$ . The statement follows from $IVT ⩽_{s W} IP ⩽_{s W} {CC}_{[0; 1]} ⩽_{s W} IVT$ . □

From Claim 6.2 we obtain a slight improvement of Theorem 1.3.

Corollary 6.4.

Under the assumptions of Theorem 1.3 there is a computable number α such that $f (α) \in range (g)$ .

Proof.

If $S_{f} = {α}$ (a singleton) then α is computable. Otherwise $α \in S_{f}$ for some rational number α which is computable. □

References

Aberth, Computable Analysis, McGraw-Hill, New York, 1980.

Brattka,

Gherardi and

Pauly, Weihrauch complexity in computable analysis, 2017, arXiv:1707.03202v1 [math.LO].

Brattka,

Hertling and

Weihrauch, A tutorial on computable analysis, in: New Computational Paradigms: Changing Conceptions of What Is Computable,

S.B.

Cooper,

Löwe and

Sorbi, eds, Springer, New York, 2008, pp. 425–491. doi:10.1007/978-0-387-68546-5_18.

Grzegorczyk, Computable functionals, Fundamenta Mathematicae42 (1955), 168–202. doi:10.4064/fm-42-1-168-202.

Grzegorczyk, On the definitions of computable real continuous functions, Fundamenta Mathematicae44 (1957), 61–71. doi:10.4064/fm-44-1-61-71.

Iljazović and

Pažek, Computable intersection points, Preprint, 2017.

B.A.

Kušner, Lectures on Constructive Mathematical Analysis, Izdat. Nauka, 1973(in Russian). Translated: by E. Mendelson and edited by L.J. Leifman, Transl. Math. Monographs, Vol. 60, 1984.

B.A.

Kušner, Markov’s constructive analysis; a participant’s view, Theoretical Computer Science219 (1999), 267–285. doi:10.1016/S0304-3975(98)00291-6.

Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles I, Comptes Rendus Académie des Sciences Paris240 (1955), 2478–2480, Théorie des fonctions.

10.

S.N.

Manukyan, O nekotorykh topologicheskikh osobennostyakh konstruktivnykh prostykh dug, in: Issledovaniya po Teorii Algorifmov i Matematicheskoy Logike, Vol. 2,

B.A.

Kushner and

A.A.

Markov, eds, Vychislitel’ny Tsentr AN SSSR, Moscow, 1976, pp. 122–129(in Russian).

11.

Specker, Der Satz vom Maximum in der rekursiven Analysis, in: Constructivity in Mathematics, Aug. 26–31, 1957, Amsterdam,

Heyting, ed., Studies in Logic and the Foundations of Mathematics, North-Holland. Proc. Colloq., Amsterdam, 1959, pp. 254–265.

12.

Weihrauch, Computable Analysis, Springer, Berlin, 2000.

13.

Weihrauch and

Grubba, Elementary computable topology, J. UCS15(6) (2009), 1381–1422.

Computable planar curves intersect in a computable point

Abstract

Keywords

1. Introduction

1 There is a computable open set U ⊆ R with measure < 1 / 2 which contains the computable real numbers ([11], [12, Theorem 4.2.8]). Define a computable function h 0 : R → R such that ( ∀ t ) h 0 ( t ) ⩽ 0 and h 0 − 1 ( 0 ) = R ∖ U . Construct h from h 0 .

4 We consider ( K , L ) as a generalized interval with lower bound K and upper bound L.

Definition 4.1 (Passage, gate).

5 Where we call the intersection of B 1 and B 2 strict if B 1 ⊈ B 2 , B 2 ⊈ B 1 and B 1 ∩ B 2 ≠ ∅ .

References

¹
There is a computable open set $U \subseteq R$ with measure $< 1 / 2$ which contains the computable real numbers ([11], [12, Theorem 4.2.8]). Define a computable function $h_{0} : R \to R$ such that $(\forall t) h_{0} (t) ⩽ 0$ and $h_{0}^{- 1} (0) = R ∖ U$ . Construct h from $h_{0}$ .

⁴
We consider $(K, L)$ as a generalized interval with lower bound K and upper bound L.

⁵
Where we call the intersection of $B_{1}$ and $B_{2}$ strict if $B_{1} ⊈ B_{2}$ , $B_{2} ⊈ B_{1}$ and $B_{1} \cap B_{2} \neq \emptyset$ .