Proof By assumption, the set

$$\begin{align*}A := \{n\in\mathbb{N} \colon n \geq f(0) \text{ and }\alpha - a_n < 2^{-n}\} \end{align*}$$

is infinite. We define a function $g\colon A\to \mathbb {N}$ by

$$\begin{align*}g(n):=\min\{m\in\mathbb{N} \colon f(m+1)> n \} , \end{align*}$$

for $n\in A$ . The function g is well-defined because f is unbounded. For every $n\in A$ we have $f(g(n)) \leq n < f(g(n)+1)$ . The set

$$\begin{align*}g(A) := \{g(n) \colon n \in A\}\end{align*}$$

is infinite. Let $m\in g(A)$ be arbitrary and let $n\in A$ be such that $m=g(n)$ . Then

$$\begin{align*}\alpha - a_{f(m+1)} = \alpha - a_{f(g(n)+1)} \leq \alpha - a_n < 2^{-n} \leq 2^{-f(g(n))} = 2^{-f(m)}.\\[-34pt] \end{align*}$$

Proof $(2) \Rightarrow (1)$ : Trivial.

$(3) \Rightarrow (2)$ : Trivial.

$(1) \Rightarrow (3)$ : Let $\alpha $ be a regainingly approximable number. Let $(b_n)_n$ be a computable nondecreasing sequence of rational numbers converging to $\alpha $ with $\alpha - b_n < 2^{-n}$ for infinitely many $n \in \mathbb {N}$ . Let $f\colon \mathbb {N}\to \mathbb {N}$ be a computable, unbounded function. Then the function $g\colon \mathbb {N}\to \mathbb {N}$ defined by

$$\begin{align*}g(n) := 1+n+\max \{ f(m) \colon m \leq n \} \end{align*}$$

is computable, increasing, and satisfies $g(n)\geq f(n)+1$ , for all $n\in \mathbb {N}$ . In particular, g is unbounded. The sequence $(a_n)_n$ of rational numbers defined by

$$\begin{align*}a_n:=b_{g(n+1)} - 2^{-g(n)}\end{align*}$$

is computable and increasing and converges to $\alpha $ . By Lemma 3.1 there exist infinitely many n with $\alpha - b_{g(n+1)} < 2^{-g(n)}$ . For all such n we obtain

$$\begin{align*}\alpha - a_n = \alpha - b_{g(n+1)} + 2^{-g(n)} < 2^{-g(n)+1} \leq 2^{-f(n)}. \end{align*}$$

$(1) \Rightarrow (4)$ : Trivial.

$(4) \Rightarrow (1)$ : Assume that $f\colon \mathbb {N}\to \mathbb {N}$ is a computable, nondecreasing, and unbounded function and $(b_n)_n$ is a computable nondecreasing sequence of rational numbers converging to $\alpha $ such that, for infinitely many $n \in \mathbb {N}$ , $\alpha - b_n < 2^{-f(n)}$ . Define a function $g\colon \mathbb {N}\to \mathbb {N}$ via

$$\begin{align*}g(0):= \max\{m\in\mathbb{N} \colon f(m)=f(0)\} \end{align*}$$

and

$$\begin{align*}g(n+1) := \max\{m\in\mathbb{N} \colon f(m)=f(g(n)+1)\} , \end{align*}$$

for $n\in \mathbb {N}$ ; informally speaking, the graph of f is an infinite increasing sequence of plateaus of finite length and $g(n)$ gives the x-coordinate of the right-most point in the $(n+1)$ th plateau.

Clearly, g is computable and increasing and satisfies $f(g(n))\geq n$ for all $n\in \mathbb {N}$ . Furthermore, for every $k\in \mathbb {N}$ there exists exactly one $n\in \mathbb {N}$ with $f(k)=f(g(n))$ , and this n satisfies $k \leq g(n)$ . The sequence $(a_n)_n$ of rational numbers defined by $a_n := b_{g(n)}$ , for all $n\in \mathbb {N}$ , is computable and nondecreasing and converges to $\alpha $ . By assumption, the set

$$\begin{align*}B := \{k\in\mathbb{N} \colon \alpha - b_k < 2^{-f(k)} \} \end{align*}$$

is infinite. Hence, the set

$$\begin{align*}A := \{n \in \mathbb{N} \colon (\exists k \in B)\; f(k) = f(g(n)) \} \end{align*}$$

is infinite as well. Consider a number $n\in A$ , and let $k\in B$ be a number with $f(k)=f(g(n))$ . Then $k\leq g(n)$ and

$$\begin{align*}\alpha - a_n = \alpha - b_{g(n)} \leq \alpha - b_k < 2^{-f(k)} = 2^{-f(g(n))} \leq 2^{-n}.\\[-34pt] \end{align*}$$

Proof $(2) \Rightarrow (1)$ : Assume that there exists a computable, increasing function $r\colon \mathbb {N}\to \mathbb {N}$ such that we have ${\alpha - a_{r(n)} < 2^{-n}}$ for infinitely many n. Then the sequence $(b_n)_n$ of rational numbers defined by ${b_n:=a_{r(n)}}$ is computable, nondecreasing, converges to $\alpha $ , and satisfies, for infinitely many n, $\alpha - b_n < 2^{-n}$ . Hence, $\alpha $ is regainingly approximable.

$(1) \Rightarrow (2)$ : Assume that $\alpha $ is regainingly approximable. By Proposition 3.2 there exists a computable, increasing sequence $(b_n)_n$ of rational numbers converging to $\alpha $ such that there exist infinitely many n with $\alpha - b_n < 2^{-n}$ . We define a computable, increasing function ${r\colon \mathbb {N}\to \mathbb {N}}$ by $r(0):=\min \{m\in \mathbb {N} \colon a_m\geq b_0 \}$ , and

$$\begin{align*}r(n+1) := \min\{m\in\mathbb{N} \colon m> r(n) \text{ and } a_m\geq b_{n+1} \} , \end{align*}$$

for $n\in \mathbb {N}$ . For all $n\in \mathbb {N}$ we have $a_{r(n)} \geq b_n$ . Thus, for the infinitely many $n\in \mathbb {N}$ with $\alpha - b_n < 2^{-n}$ , we obtain

$$\begin{align*}\alpha - a_{r(n)} \leq \alpha - b_n < 2^{-n}.\\[-34pt] \end{align*}$$

Proof

1. (1) If $\alpha $ is rational or if $\mathbb {N}\setminus A$ is empty then A and $\mathbb {N}\setminus A$ are decidable; thus assume w.l.o.g. that $\alpha $ is irrational and that $\mathbb {N} \setminus A$ is non-empty. Then $\alpha - a_n\geq 2^{-n}$ if and only if $\alpha - a_n> 2^{-n}$ . Fix any ${e \in \mathbb {N} \setminus A}$ , and define a computable function $f \colon \mathbb {N} \to \mathbb {N}$ via

   $$ \begin{align*} f(\left\langle m,n\right\rangle ) := \begin{cases} n, &\text{if }a_m - a_n \geq 2^{-n}, \\ e, &\text{otherwise.} \end{cases} \end{align*} $$
   Clearly, f computably enumerates $\mathbb {N} \setminus A$ .

2. (2) (a) $\Rightarrow $ (b): Suppose that $\alpha $ is computable. Then there exists a computable sequence $(b_m)_m$ of rational numbers with $\left |\alpha - b_m\right | < 2^{-m}$ for all $m \in \mathbb {N}$ . Due to (1) it suffices to show that A is computably enumerable. Fix some $d \in A$ and define a computable function $g \colon \mathbb {N} \to \mathbb {N}$ via

   $$ \begin{align*} g(\left\langle m,n\right\rangle ) := \begin{cases} n, &\text{if }b_m - a_n + 2^{-m} < 2^{-n}, \\ d, &\text{otherwise.} \end{cases} \end{align*} $$
   Then g computably enumerates A; indeed, if for some m it holds that ${b_m - a_n + 2^{-m} < 2^{-n}}$ then ${\alpha - a_n < 2^{-n}}$ ; and for the other direction, if ${\alpha - a_n < 2^{-n}}$ holds, then for all m satisfying ${\alpha - a_n + 2\cdot 2^{-m} < 2^{-n}}$ we have ${b_m - a_n + 2^{-m} < 2^{-n}}$ .

   (b) $\Rightarrow $ (c): Trivial.

   (c) $\Rightarrow $ (a): By assumption A is infinite. Define ${p_A \colon \mathbb {N} \to \mathbb {N}}$ as the uniquely determined increasing function with ${p_A(\mathbb {N}) = A}$ . Suppose that A is not hyperimmune. Then there exists a computable function $r \colon \mathbb {N} \to \mathbb {N}$ with $r(n) \geq p_A(n)$ for all $n \in \mathbb {N}$ (see, for instance, Soare [Reference Soare15, Theorem V.2.3]). Then we have

   $$ \begin{align*} \alpha - a_{r(n)} \leq \alpha - a_{p_A(n)} < 2^{-p_A(n)} \leq 2^{-n} \end{align*} $$
   for all $n \in \mathbb {N}$ . Hence, $\alpha $ is computable.

Proof $(3) \Rightarrow (2)$ : By Lemma 4.1 some uniformly computable approximation $(B_n)_n$ of A from the left exists. Then by assumption a function s as in (3) must exist as well. Thus, (2) follows immediately by letting $A_n:=B_{s(n)} \cap \{0,\ldots ,n-1\}$ for all $n\in \mathbb {N}$ .

$(2) \Rightarrow (1)$ : Let $(A_n)_n$ be a uniformly computable approximation of A from the left such that ${A\cap \{0,\ldots ,n-1\} = A_n}$ for infinitely many n. The sequence $(2^{-A_n})_n$ is a nondecreasing computable sequence of rational numbers converging to $2^{-A}$ . For the infinitely many n with ${A\cap \{0,\ldots ,n-1\} = A_n}$ we have

$$\begin{align*}2^{-A} - 2^{-A_n} \leq \sum\nolimits _{k=n+1}^\infty 2^{-k} = 2^{-n}.\end{align*}$$

Thus, $2^{-A}$ is regainingly approximable.

$(1) \Rightarrow (3)$ : If A is cofinite then it is easy to see that for any computable approximation of A from the left there is a function s as required by (3); thus w.l.o.g. let A be coinfinite.

Let $(B_n)_n$ be an arbitrary uniformly computable approximation of A from the left. Then $(2^{-B_n})_n$ is a computable, nondecreasing sequence of rational numbers converging to $2^{-A}$ . By Proposition 3.3 there exists a computable increasing function $r\colon \mathbb {N}\to \mathbb {N}$ such that, for infinitely many n, $2^{-A} - 2^{-B_{r(n)}} < 2^{-n}$ . If there are infinitely many n with

$$\begin{align*}A\cap\{0,\ldots,n-1\} = B_{r(n)}\cap\{0,\ldots,n-1\},\end{align*}$$

then (3) holds with $s:=r$ . Otherwise there is an $N>0$ such that for all $n\geq N$ we have $A\cap \{0,\ldots ,n-1\} \neq B_{r(n)}\cap \{0,\ldots ,n-1\}$ ; that is, one of:

1. (i) $2^{-A\cap \{0,\ldots ,n-1\}} + 2^{-n} \leq 2^{-B_{r(n)}\cap \{0,\ldots ,n-1\}}$

2. (ii) $2^{-B_{r(n)}\cap \{0,\ldots ,n-1\}} + 2^{-n} \leq 2^{-A\cap \{0,\ldots ,n-1\}}$

must hold. But (i), together with A’s coinfiniteness, would imply

$$\begin{align*}2^{-A} < 2^{-A\cap\{0,\ldots,n-1\}} + 2^{-n} \leq 2^{-B_{r(n)}\cap\{0,\ldots,n-1\}} \leq 2^{-B_{r(n)}} \leq 2^{-A}, \end{align*}$$

a contradiction. Thus, for $n\geq N$ , (ii) must hold. Define $s\colon \mathbb {N}\to \mathbb {N}$ via

and note that this is well-defined as $\lim _{n\to \infty } B_n(i)=A(i)$ for all $i\in \mathbb {N}$ . It is clear that s is increasing and computable. Fix any of the infinitely many $n\geq N$ with $2^{-A} - 2^{-B_{r(n)}} < 2^{-n}$ .

We claim that $A\cap \{0,\ldots ,n-1\} = B_{s(n)}\cap \{0,\ldots ,n-1\}$ . For the sake of a contradiction, assume otherwise; then one of

1. (iii) $2^{-A\cap \{0,\ldots ,n-1\}} + 2^{-n} \leq 2^{-B_{s(n)}\cap \{0,\ldots ,n-1\}}$

2. (iv) $2^{-B_{s(n)}\cap \{0,\ldots ,n-1\}} + 2^{-n} \leq 2^{-A\cap \{0,\ldots ,n-1\}}$

must hold. From (iii) we can deduce

$$\begin{align*}2^{-A} < 2^{-A\cap\{0,\ldots,n-1\}} + 2^{-n} \leq 2^{-B_{s(n)}\cap\{0,\ldots,n-1\}} \leq 2^{-B_{s(n)}} \leq 2^{-A}, \end{align*}$$

a contradiction; from (iv) we obtain

$$\begin{align*}\begin{array}{r@{\;}c@{\;}l} 2^{-A} &<& 2^{-B_{r(n)}} + 2^{-n} < 2^{-B_{r(n)}\cap\{0,\ldots,n-1\}} + 2^{-n} + 2^{-n} \\ &\leq & 2^{-B_{s(n)}\cap\{0,\ldots,n-1\}} + 2^{-n} \leq 2^{-A\cap\{0,\ldots,n-1\}} \leq 2^{-A} , \end{array}\end{align*}$$

another contradiction.

Proof of Theorem 4.7

$(3) \Rightarrow (1)$ : Let $r\colon \mathbb {N}\to \mathbb {N}$ be a computable, nondecreasing, unbounded function, and let $f\colon \mathbb {N}\to \mathbb {N}$ be a computable r-good enumeration of A. Then $(a_n)_n$ defined for all $n\in \mathbb {N}$ via

$$\begin{align*}a_n:= 2^{-\mathrm{Enum}(f)[r(n)]} \end{align*}$$

is a computable, nondecreasing sequence of rational numbers converging to $2^{-A}$ ; and since we have for infinitely many n that

$$\begin{align*}\{0,\ldots,n-1\} \cap A \subseteq \mathrm{Enum}(f)[r(n)] \end{align*}$$

it follows that $2^{-A} - a_n \leq \sum _{k=n}^\infty 2^{-k-1} = 2^{-n}$ . Thus $2^{-A}$ is regainingly approximable.

$(1) \Rightarrow (4)$ : Let $A\subseteq \mathbb {N}$ be a c.e. set such that $2^{-A}$ is regainingly approximable, and let $f\colon \mathbb {N}\to \mathbb {N}$ be an arbitrary computable enumeration of A. Then $(a_n)_n$ defined by $a_n:=2^{-\mathrm {Enum}(f)[n]}$ , for all $n\in \mathbb {N}$ , is a computable nondecreasing sequence of rational numbers converging to $2^{-A}$ . By Proposition 3.3 there exists a computable, increasing function $r\colon \mathbb {N}\to \mathbb {N}$ such that, for infinitely many n, $2^{-A} - a_{r(n)} < 2^{-n}$ . We obtain $\{0,\ldots ,n-1\} \cap A \subseteq \mathrm {Enum}(f)[r(n)]$ for infinitely many n. Hence, f is r-good.

$(4) \Rightarrow (3)$ : Trivial, as every c.e. set has a computable enumeration.

$(2) \Rightarrow (3)$ : Trivial.

$(3) \Rightarrow (2)$ : Assume that ${r\colon \mathbb {N}\to \mathbb {N}}$ is a computable, nondecreasing, unbounded function and that $f\colon \mathbb {N}\to \mathbb {N}$ is a computable r-good enumeration of A. If A is finite, then f itself is trivially an $\mathrm {id}_{\mathbb {N}}$ -good enumeration of A; so assume that A is infinite. Let $L_0, M_0:=\emptyset $ and for $n \geq 1$ define $L_n := \{0,\ldots ,n-1\}\cap \mathrm {Enum}(f)[r(n)]$ as well as $M_n := L_n \setminus L_{n-1}$ ; that is, $M_1,\ldots ,M_n$ forms a disjoint partition of $L_n$ for every n.

We let $g\colon \mathbb {N}\to \mathbb {N}$ be the enumeration that first enumerates all elements of $M_1$ in increasing order, then those of $M_2$ in increasing order, and so on. More formally speaking, $g\colon \mathbb {N}\to \mathbb {N}$ is defined as follows: For every $n\in \mathbb {N}$ , let $m_n$ be the cardinality of $M_n$ , let $k_0^{(n)},\ldots ,k_{m_n-1}^{(n)}$ be its elements in increasing order and, for t with $0\leq t \leq m_n-1$ , define

$$\begin{align*}g\left( t + \sum_{j<n} m_j\right) := 1+k_t^{(n)}. \end{align*}$$

This is well-defined due to A’s infinity. Clearly, g is a computable enumeration (in fact, without repetitions) of A with $g(n)\neq 0$ for all n. We claim that it is in fact an $\mathrm {id}_{\mathbb {N}}$ -good enumeration of A. To see this, fix any of the, by assumption, infinitely many n with

$$\begin{align*}\{0,\ldots,n-1\} \cap A \subseteq \mathrm{Enum}(f)[r(n)]. \end{align*}$$

By construction, g enumerates exactly the elements of

$$\begin{align*}L_{n-1} = M_0\cup \dots \cup M_{n-1}\end{align*}$$

during the first $\sum _{j<n} m_j$ stages and, by choice of n, all elements of $\{0,\ldots ,n-1\}\cap A$ that are not enumerated during these stages must be in $M_n$ . In fact, they are exactly all elements of $M_n$ , and thus will be enumerated by g in the immediately following stages, starting with stage $\sum _{j<n} m_j$ . As there cannot be more than ${n-\sum _{j<n} m_j}$ such numbers, this process will be completed before stage n.

Proof By Sacks’ Splitting Theorem [Reference Sacks13] (see, for instance, Soare [Reference Soare15, Theorem VII.3.2]) there exist two disjoint, c.e., low subsets $A,B\subseteq \mathbb {N}$ with $C=A\cup B$ . Low sets are not high. Hence, by Example 1.2 and Theorem 4.7, A and B are regainingly approximable.

First proof

By Example 1.2, any c.e. set that is neither decidable nor high is regainingly approximable.

Second proof

Let $C\subseteq \mathbb {N}$ be an undecidable c.e. set. By Theorem 5.1 there are two disjoint regainingly approximable sets $A,B$ such that ${C=A\cup B}$ . At least one of A or B must be undecidable.

Proof Let $\varphi _0,\varphi _1,\varphi _2,\ldots $ be a standard enumeration of all possibly partial computable functions with domain and range in $\mathbb {N}$ . As usual, we write $\varphi _e(n)[t]{\downarrow }$ to express that the eth Turing machine (which computes $\varphi _e$ ) stops after at most t steps on input n.

We shall construct a computable enumeration $g\colon \mathbb {N}\to \mathbb {N}$ of a set $A \subseteq \mathbb {N}$ such that the following requirements $(\mathcal {R}_{e})$ will be satisfied for all $e\in \mathbb {N}$ :

$$\begin{align*}\begin{array}{r@{\;}l} (\mathcal{R}_{e})\colon & \text{if } \varphi_e \text{ is total and increasing then } \\ & (\exists n_e\in\mathbb{N}) (\forall n> n_e) (\{0,\ldots,n-1\} \cap A \not\subseteq \mathrm{Enum}(g)[\varphi_e(n)]). \end{array}\end{align*}$$

According to Theorem 4.7 this is sufficient.

We construct g in stages; in stage t we proceed as follows: Define $e:=\pi _1(\pi _1(t))$ and $k:=\pi _2(\pi _1(t))$ , hence, $\langle e,k \rangle = \pi _1(t)$ . Check whether the following conditions are satisfied:

$$ \begin{align*} & (\forall n\leq \langle e,k+1\rangle) \ \varphi_e(n)[t]{\downarrow} \\\text{and}\ &(\forall n < \langle e,k+1\rangle) \ \varphi_e(n) < \varphi_e(n+1) \\\text{and}\ &t \geq \varphi_e(\langle e,k+1\rangle ) \\\text{and}\ &\langle e,k \rangle \not\in \mathrm{Enum}(g)[t]. \end{align*} $$

If they are, set $g(t):=1+ \langle e,k \rangle $ , otherwise $g(t):=0$ .

This completes the construction; we proceed with the verification. It is clear that g is computable and an enumeration without repetitions of some c.e. set $A \subseteq \mathbb {N}$ . We wish to show that $\mathcal {R}_e$ is satisfied for all $e\in \mathbb {N}$ . Consider an $e\in \mathbb {N}$ such that $\varphi _e$ is total and increasing, as well as a number ${n> \langle e,0 \rangle }$ . There exists a unique $k\in \mathbb {N}$ with ${\langle e,k \rangle < n \leq \langle e,k+1\rangle }$ . The function g enumerates $\langle e,k\rangle $ into A at some uniquely determined stage t, that is, there exists exactly one $t \in \mathbb {N}$ with ${g(t)=1+\langle e,k\rangle }$ . Then

$$\begin{align*}\langle e,k \rangle \in \mathrm{Enum}(g)[t+1] \setminus \mathrm{Enum}(g)[t].\end{align*}$$

Since $n \leq \langle e,k+1\rangle $ , we have $\varphi _e(n) \leq \varphi _e( \langle e,k+1 \rangle ) \leq t$ , and therefore

$$\begin{align*}\langle e,k \rangle \not\in\mathrm{Enum}(g)[t] \supseteq \mathrm{Enum}(g)[\varphi_e(n)]. \end{align*}$$

Thus $\langle e,k \rangle \in \{0,\ldots ,n-1\}\cap A$ witnesses that $\mathcal {R}_e$ is satisfied with $n_e=\langle e,0\rangle $ .

Proof W.l.o.g. we may assume that A is infinite. Thus fix some computable injective function $f \colon \mathbb {N} \to \mathbb {N}$ with $f(\mathbb {N}) = A$ .

We will build a c.e. B by defining a computable injective function ${g\colon \mathbb {N}\to \mathbb {N}}$ and letting $B:=g(\mathbb {N})$ . In parallel, we will define an increasing sequence $(S_i)_i$ such that:

1. (i) for all i we have $\{0,\ldots ,S_i-1\} \cap B\subseteq \{g(0),\ldots ,g(S_i-1)\}$ , which implies that B is regainingly approximable, and such that

2. (ii) $A \equiv _T (S_i)_i \equiv _T B$ .

To ensure these properties, we will define $(S_i)_i$ in such a way that, for all i and for all $t\geq S_i$ , we have on the one hand that $f(t)\geq i$ and on the other hand that $g(t)\geq S_i$ . This last property will imply (i); and concerning (ii), informally speaking, our choice of $(S_i)_i$ means that f and g can enumerate “small” numbers only for arguments smaller than $S_i$ . This will allow us to show $A \leq _T (S_i)_i$ and $B \leq _T (S_i)_i$ . Finally, the statements $(S_i)_i \leq _T A$ and $(S_i)_i \leq _T B$ will follow from the way we define $(S_i)_i$ alongside g.

After these informal remarks, we proceed with the full proof. The following algorithm works recursively in infinitely many stages to compute two functions $g \colon \mathbb {N} \to \mathbb {N}$ and ${s\colon \mathbb {N}^2\to \mathbb {N}}$ ; we write $s_i[t]$ for $s(i,t)$ . Since it will turn out below that $(s_i[t])_t$ is eventually constant for every i, allowing us to define $S_i:=\lim _{t\to \infty } s_i[t]$ , it is suggestive to think of $s_i[t]$ as our preliminary guess for $S_i$ at stage t.

At stage $0$ we let

$$ \begin{align*} s_i[0] := i \end{align*} $$

for all $i\in \mathbb {N}$ . And for every $t\in \mathbb {N}$ , at stage $t+1$ we define

$$ \begin{align*} g(t) := s_{f(t)}[t] \end{align*} $$

and set

$$ \begin{align*} s_i[t+1] := \begin{cases} s_i[t], &\text{if }i \leq f(t), \\ s_i[t] + \max\{t, g(0), \dots, g(t)\}+1, &\text{if }i> f(t), \\ \end{cases} \end{align*} $$

for all $i \in \mathbb {N}$ . Finally, we define $B := g(\mathbb {N})$ .

This ends the construction, and we proceed with the verification. First note that B is clearly computably enumerable.

Define the sequence $(S_i)_i$ by $S_i:=\lim _{t\to \infty } s_i[t]$ . By Claim 1, $(S_i)_i$ is increasing.

Proof Assume otherwise and choose $t\geq S_i$ with $s_i[t+1]\neq s_i[t]$ . Then

$$ \begin{align*} S_i\geq s_i[t+1]=s_i[t]+\max\{t, g(0), \dots, g(t)\}+1> t \geq S_i, \end{align*} $$

a contradiction.

Proof Consider any $i \in \mathbb {N}$ and some stage $t \geq S_i$ . If we had $f(t) < i$ , then we would obtain

$$ \begin{align*} s_i[t+1] = s_i[t]+\max\{t, g(0), \dots, g(t)\}+1> s_i[t]=S_i, \end{align*} $$

contradicting Claim 3.

Proof To determine $S_i$ for any $i \in \mathbb {N}$ it suffices to use oracle A to compute the smallest t such that

$$\begin{align*}A \cap \{0,\dots,i-1\} \subseteq \{f(0),\ldots,f(t-1)\} \end{align*}$$

and to output $S_i = s_i[t]$ .

This concludes the proof that for every c.e. set $A \subseteq \mathbb {N}$ there exists a regainingly approximable set $B \subseteq \mathbb {N}$ with $A \equiv _T B$ .

Proof Assume w.l.o.g. that $\alpha $ is not computable and $\alpha \in (0,1)$ . Let $(a_n)_n$ be an increasing, computable sequence of w.l.o.g. strictly positive rational numbers converging to $\alpha $ such that, for infinitely many n, $\alpha -a_n<2^{-n}$ .

For every $n\in \mathbb {N}$ , let $u_n$ be the binary string of length n with

$$\begin{align*}0.u_n \leq a_n < 0.u_n+2^{-n}.\end{align*}$$

If $u_n\neq 1^n$ let $v_n\in \Sigma ^n$ be such that $0.v_n = 0.u_n+2^{-n}$ ; otherwise let ${v_n:=u_n}$ . Clearly, $(u_n)_n$ and $(v_n)_n$ are computable.

Define a computable function $f\colon \mathrm {dom}(f)\to \Sigma ^*$ with prefix-free domain $\mathrm {dom}(f)\subseteq \Sigma ^*$ as follows: If $w\in \Sigma ^*$ satisfies $U(w)=0^n$ , for some $n\in \mathbb {N}$ , then let $f(w0) := u_n$ and $f(w1) := v_n$ . Otherwise we leave $f(wa)$ undefined for ${a\in \Sigma }$ . Note that the domain of f is prefix-free.

By construction, for infinitely many n, we have $\alpha - 0.u_n < 2 \cdot 2^{-n}$ . Then, for these n, we have $\alpha \restriction n \in \{u_n,v_n\}$ ; thus

$$\begin{align*}K(\alpha\restriction n) \leq^+ K_f(\alpha\restriction n) = K(0^n)+1,\end{align*}$$

and $\alpha $ is i.o. K-trivial.

Proof of Theorem 6.2

Fix a computable injective function $h\colon \mathbb {N}\to \Sigma ^*$ with ${h(\mathbb {N})=\mathrm {dom}(U)}$ . For $t\in \mathbb {N}$ and $v\in \Sigma ^*$ write

$$\begin{align*}U^{-1}\{v\}[t] &:= \{u \in\Sigma^* \colon U(u)=v \text{ and } (\exists s < t) (h(s)=u) \},\\K(v)[t] &:= \begin{cases} \infty, & \text{if } U^{-1}\{v\}[t]=\emptyset, \\ \min\{|u|\colon u \in U^{-1}\{v\}[t]\}, & \text{otherwise}. \end{cases} \end{align*}$$

Then, for every $v\in \Sigma ^*$ , the function $t\mapsto K(v)[t]$ is nonincreasing and eventually constant with limit $K(v)$ .

We sketch the underlying idea before giving the formal proof. In order to ensure that $\alpha $ has initial segments of high prefix-free Kolmogorov complexity, we want to mimic Chaitin’s $\Omega $ , that is, the sum $\sum _n 2^{-|h(n)|}$ . Of course, overdoing this would lead to a Martin-Löf random number in the limit, and such numbers cannot be regainingly approximable. Instead, $\alpha $ is obtained from the series $\sum _n 2^{-|h(n)|}$ by multiplying its elements by certain weights. More precisely, at any given time some weight is fixed, and we keep adding elements to the series scaled by this weight. As continuing to do this forever would lead to a scaled copy of $\Omega $ , that is, to some Martin-Löf random number, that process must eventually produce a rational number with an initial segment of high Kolmogorov complexity.

If at a stage t it looks as if that has happened, we change the weight to a new, smaller value that is at most $2^{-t}$ . As all new terms that are added to the series after t will now be scaled by this new weight, their total sum cannot exceed $2^{-t}$ . Doing this for infinitely many t then ensures regaining approximability of $\alpha $ .

One issue with this approach is that we can never be sure about the stages when we change weights. This is because prefix-free Kolmogorov complexity is uncomputable, and we have to work with its approximations. Thus, it may turn out that what looked like an initial segment of high complexity at stage t really has much lower complexity, and as a result we may have dropped the weight too early. However, since $\alpha $ only needs to be left-computable, it is easy to deal with this: we simply retroactively scale up the weights of all terms that had been given too small a weight.

We now come to the formal construction, which will proceed in stages to define computable functions ${\ell ,r\colon \mathbb {N}^2\to \mathbb {N}}$ and $w\colon \mathbb {N}^2\to \mathbb {N}\cup \{\infty \}$ as well as a computable sequence $(a_t)_t$ of dyadic rational numbers in the interval $[0,1)$ . We shall write $\ell (n)[t]$ for $\ell (n,t)$ , $r(n)[t]$ for $r(n,t)$ , and $w(n)[t]$ for $w(n,t)$ .

At stage $0$ define

$$\begin{align*}\ell(n)[0]:=0 \text{ and } r(n)[0]:=n \text{ and } w(n)[0]:=\infty, \end{align*}$$

for all $n\in \mathbb {N}$ , as well as $a_0:=0$ .

At a stage t with $t>0$ first define $\ell (0)[t]:=0$ and, for $n>0$ ,

$$\begin{align*}\ell(n)[t] := \min\{m \in \mathbb{N} \colon m> \ell(n-1)[t] \text{ and } K(a_{t-1} \restriction m)[t]>m\}. \end{align*}$$

Note that this is well-defined because for a fixed t we have $K(v)[t]=\infty $ for almost all $v\in \Sigma ^*$ . Intuitively speaking, $\ell (n)[t]$ is our guess at stage t about the length of what we hope will be the nth witness for the existence of infinitely many initial segments of $\alpha $ that have high complexity.

If there is no $i<t$ with $\ell (i)[t]\neq \ell (i)[t-1]$ , then define

$$\begin{align*}r(n)[t] := r(n)[t-1] \text{ and } w(n)[t]:=w(n)[t-1], \end{align*}$$

for every $n\in \mathbb {N}$ . Otherwise let $i_t$ denote the minimal such i and define

$$\begin{align*}r(n)[t] &:= \begin{cases} r(n)[t-1], & \text{if } n \leq i_t, \\ r(n)[t-1]+t, & \text{if } i_t < n, \end{cases} \\w(n)[t] &:= \begin{cases} \min(w(n)[t-1],r(i_t)[t]), & \text{if } n < t,\\ \infty, & \text{otherwise,} \end{cases}\end{align*}$$

for every $n\in \mathbb {N}$ . In either case, using the convention $2^{-\infty }:=0$ , define

$$\begin{align*}a_t := \sum_{n=0}^{t-1} 2^{-w(n)[t]} \cdot 2^{-|h(n)|}. \end{align*}$$

Using the terminology from the informal proof sketch above, r is employed to reduce weights when we believe that we discovered an initial segment of high complexity, with the intent of ensuring regaining approximability of $\alpha $ . This is then used to define the function w determining the scaling factors that will be applied to the elements of the series $\sum _n 2^{-|h(n)|}$ ; note how the appearance of $i_t$ in the definition of w enables retroactively increasing these factors later if required.

This ends the description of the construction; we proceed with the verification. It is easy to see that $\ell ,r, w$ , and $(a_t)_t$ are computable; we need to argue that $\alpha :=\lim _{t\to \infty } a_t$ exists with the desired properties. The following claims are immediate.

Due to Claim 3, using the convention $2^{-\infty }=0$ , we can write

$$\begin{align*}a_t = \sum_{n=0}^\infty 2^{-w(n)[t]} \cdot 2^{-|h(n)|} , \end{align*}$$

for all $t\in \mathbb {N}$ . By Claim 4, $(a_t)_t$ is nondecreasing, and since

$$\begin{align*}a_t \leq \sum_{n=0}^{t-1} 2^{-|h(n)|} < 1 , \end{align*}$$

for all $t\in \mathbb {N}$ , its limit $\alpha $ exists and is a left-computable number in $(0,1]$ .

Proof Fix any $n<t_0$ and $t>t_0$ ; in order to show ${w(n)[t]=w(n)[t_0]}$ we may inductively assume that the statement has already been proven for $t-1$ , that is, that ${w(n)[t-1]=w(n)[t_0]}$ holds; thus it suffices to prove $w(n)[t]=w(n)[t-1]$ .

This is clear by construction if there is no $i<t$ with ${\ell (i)[t]\neq \ell (i)[t-1]}$ ; thus let us assume that such an i does exist. In this case, by construction,

$$\begin{align*}w(n)[t]=\min (w(n)[t-1],r(i_t)[t])\end{align*}$$

and hence it is enough to show that $w(n)[t-1] \leq r(i_t)[t]$ .

By definition we have $\ell (i_t)[t]\neq \ell (i_t)[t-1]$ ; thus (iii) implies $i_t\geq n_0$ . Similarly, (ii) and (iii) imply $i_{t_0}=n_0$ . Then using Claims 1 and 2 as well as the induction hypothesis we obtain

$$ \begin{align*} w(n)[t-1] &= w(n)[t_0] = \min(w(n)[t_0-1],r(i_{t_0}[t_0])) \\ &\leq r(i_{t_0})[t_0] = r(n_0)[t_0] \leq r(i_t)[t_0] \leq r(i_t)[t], \end{align*} $$

which concludes the proof.

Proof For the sake of a contradiction, assume that there is a smallest $n_0\in \mathbb {N}$ such that $t\mapsto \ell (n_0)[t]$ is not eventually constant. By the definitions above we must have $n_0>0$ . Define

$$\begin{align*}t_0 := \min\left\{t> n_0 \colon \begin{array}{c} \ell(n_0)[t]\neq \ell(n_0)[t-1] \text{ and } \\ (\forall i< n_0) (\forall s \geq t) ( \ell(i)[s]=\ell(i)[s-1] ) \end{array} \right\} \end{align*}$$

and, for $j>0$ ,

$$\begin{align*}t_j := \min\{t> t_{j-1} \colon \ell(n_0)[t]\neq \ell(n_0)[t-1] \}. \end{align*}$$

The sequence $(t_j)_j$ is trivially increasing and $w(n)[t_j]=w(n)[t_0]$ for all $n<t_0$ and all $j\in \mathbb {N}$ , by Claim 5.

We show by induction that $w(n)[t]\geq r(n_0)[t_0]$ for all $n\geq t_0$ and $t\geq t_0$ :

• • For $t=t_0$ this is clear by Claim 3.

• • For $t>t_0$ and if there is no $i<t$ with $\ell (i)[t]\neq \ell (i)[t-1]$ then the assertion is clear inductively by definition of w.

• • If $t>t_0$ and there is an $i<t$ with $\ell (i)[t]\neq \ell (i)[t-1]$ then,

  1. – if $n\geq t$ we have $w(n)[t]=\infty> r(n_0)[t_0]$ , and

  2. – if $n<t$ then $w(n)[t] = \min (w(n)[t-1],r(i_t)[t]) \geq r(n_0)[t_0]$ .This is because, on the one hand, $w(n)[t-1] \geq r(n_0)[t_0]$ can be assumed to hold inductively and, on the other hand, $r(i_t)[t] \geq r(n_0)[t] \geq r(n_0)[t_0]$ by Claims 1 and 2 together with the fact that $i_t\geq n_0$ by choice of $t_0$ .

By choice of $t_0$ we have for every $j\in \mathbb {N}$ that $i_{t_j}=n_0$ and thus

$$\begin{align*}r(i_{t_j})[t_j]=r(n_0)[t_j]=r(n_0)[t_0]. \end{align*}$$

Combining this with the previous results and using the definition of w, for $j>0$ we see that

$$\begin{align*}w(n)[t_j]= r(n_0)[t_0] \text{ for } t_0 \leq n < t_j. \end{align*}$$

Hence, for all $j>0$ we obtain

$$ \begin{align*} a_{t_j} &= \sum_{n=0}^{t_j-1} 2^{-w(n)[t_j]} \cdot 2^{-|h(n)|} \\ &= \sum_{n=0}^{t_0-1} 2^{-w(n)[t_0]} \cdot 2^{-|h(n)|} + \sum_{n=t_0}^{t_j-1} 2^{-r(n_0)[t_0]} \cdot 2^{-|h(n)|} \\ &= b_0 + 2^{-r(n_0)[t_0]} \cdot \sum_{n=0}^{t_j-1} 2^{-|h(n)|} , \end{align*} $$

where $b_0$ is the rational number given by

$$\begin{align*}b_0 := \sum_{n=0}^{t_0-1} \left( 2^{-w(n)[t_0]} - 2^{-r(n_0)[t_0]} \right) \cdot 2^{-|h(n)|}. \end{align*}$$

Writing $\Omega :=\sum _{u\in \mathrm {dom}(U)} 2^{-|u|}=\sum _{n=0}^\infty 2^{-|h(n)|}$ we conclude that

$$\begin{align*}\alpha = b_0 + 2^{-r(n_0)[t_0]} \cdot \Omega .\end{align*}$$

Thus we see that $\alpha $ is Martin-Löf random, and by a result of Chaitin [Reference Chaitin3] (see, for instance, Downey and Hirschfeldt [Reference Downey and Hirschfeldt4, Corollary 6.6.2]) we have for all sufficiently large m that $K(\alpha \restriction m)> m$ . Fix an $m_0>\ell (n_0-1)[t_0]$ with $K(\alpha \restriction m_0)> m_0$ , and a $j_0$ such that, for all $t\geq t_{j_0}$ , we have $a_{t-1} \restriction m_0 = \alpha \restriction m_0$ . Then, for $t\geq t_{j_0}$ we obtain

$$\begin{align*}K(a_{t-1} \restriction m_0)[t] = K(\alpha \restriction m_0)[t] \geq K(\alpha \restriction m_0)> m_0, \end{align*}$$

hence, by definition, $\ell (n_0)[t]\leq m_0$ for any such t. Combining this with the fact that the map $t \mapsto \ell (n_0)[t]$ is by definition nondecreasing for $t\geq t_{j_0}$ shows that it must be eventually constant after all, a contradiction.

Define $L_n:=\lim _{t\to \infty } \ell (n)[t]$ , for $n\in \mathbb {N}$ . By the definition of $\ell $ we have that $(L_n)_n$ is increasing and that

(*) $$ \begin{align} K(\alpha\restriction L_n)> L_n \text{ for all } n\in\mathbb{N}. \end{align} $$

It remains to show that $\alpha $ is regainingly approximable. To that end, define a sequence $(s_m)_m$ by

$$\begin{align*}s_m := \max\left(\{0\}\cup \{s \in\mathbb{N} \colon (\exists i<m)\; (i<s \text{ and } \ell(i)[s]\neq \ell(i)[s-1]) \}\right), \end{align*}$$

for all $m\in \mathbb {N}$ . Clearly, $(s_m)_m$ is nondecreasing.

Consider an $m\in \mathbb {N}$ with $s_m>0$ . We claim that

$$\begin{align*}\alpha - a_{s_m} < 2^{-s_m}. \end{align*}$$

By Claim 4, for every $n\in \mathbb {N}$ , the function $t\mapsto w(n)[t]$ is eventually constant. Thus we can define $W_n:=\lim _{t\to \infty } w(n)[t]$ for every $n\in \mathbb {N}$ and write

$$\begin{align*}\alpha = \sum_{n=0}^\infty 2^{-W(n)} \cdot 2^{-|h(n)|}. \end{align*}$$

Proof It suffices to prove that $w(n)[t]\geq s_m$ for all $t\geq s_m$ and $n\geq s_m$ . We proceed by induction over t. By Claim 3 the assertion is clear for $t=s_m$ . Thus consider an arbitrary $t>s_m$ . If there is no $i<t$ with $\ell (i)[t]\neq \ell (i)[t-1]$ , then the assertion is clear inductively by definition of $w$ .

So let us assume that there exists such an i. In case that $n\geq t$ we obtain $w(n)[t]=\infty>s_m$ , and we are done. Otherwise, if $n<t$ , then by definition $w(n)[t]=\min (w(n)[t-1],r(i_t)[t])$ . Assuming inductively that the assertion is already proven for $t-1$ , it is thus enough to show $r(i_t)[t]\geq s_m$ . By the definition of $s_m$ we have $i_t>i_{s_m}$ , thus by Claim 2,

$$\begin{align*}r(i_t)[t] \geq r(i_t)[s_m] = r(i_t)[s_m-1]+s_m \geq s_m, \end{align*}$$

completing the proof of Claim 9.

Using Claim 8 it follows that

$$\begin{align*}a_{s_m} = \sum_{n=0}^{s_m-1} 2^{-w(n)[s_m]} \cdot 2^{-|h(n)|} = \sum_{n=0}^{s_m-1} 2^{-W(n)} \cdot 2^{-|h(n)|},\end{align*}$$

and thus, using Claim 9, we can conclude that

$$ \begin{align*} \alpha - a_{s_m} &= \sum_{n=s_m}^\infty 2^{-W(n)} \cdot 2^{-|h(n)|}\\ &\leq \sum_{n=s_m}^\infty 2^{-s_m} \cdot 2^{-|h(n)|}\\ &< 2^{-s_m} \cdot \Omega \\ &< 2^{-s_m}.\\[-34pt] \end{align*} $$

Proof of Lemma 7.2

Let $f_X\colon \mathbb {N}\to \mathbb {N}$ and $f_Y\colon \mathbb {N}\to \mathbb {N}$ be computable enumerations (in the sense defined in Section 4) of X and Y, respectively. Then $f_Z\colon \mathbb {N}\to \mathbb {N}$ defined by

$$\begin{align*}f_Z(n):=\begin{cases} f_X(n/2), & \text{if } n \text{ is even}, \\ f_Y((n-1)/2), & \text{if } n \text{ is odd}, \end{cases} \end{align*}$$

is a computable enumeration of $Z:=X\cup Y$ . Define a computable function $g\colon \mathrm {dom}(g)\to \Sigma ^*$ with $\mathrm {dom}(g)\subseteq \Sigma ^*$ as follows for every $v\in \Sigma ^*$ :

• • If $U(v)$ is defined and if there is a $t\in \mathbb {N}$ such that

  $$\begin{align*}U(v) = \mathrm{Enum}(f_X)[t] \restriction |U(v)|, \end{align*}$$
  then let t be the smallest such number and set
  $$\begin{align*}g(v0):= \mathrm{Enum}(f_Z)[2t] \restriction |U(v)|.\end{align*}$$
  Otherwise we leave $g(v0)$ undefined.

• • If $U(v)$ is defined and if there is a $t\in \mathbb {N}$ such that

  $$\begin{align*}U(v) = \mathrm{Enum}(f_Y)[t] \restriction |U(v)|,\end{align*}$$
  then let t be the smallest such number and set
  $$\begin{align*}g(v1):= \mathrm{Enum}(f_Z)[2t] \restriction |U(v)|.\end{align*}$$
  Otherwise we leave $g(v1)$ undefined.

For the verification, consider any $n \in \mathbb {N}$ . Let $s_X\in \mathbb {N}$ be the smallest number with $\mathrm {Enum}(f_X)[s_X]\restriction n = X\restriction n$ , and let $s_Y\in \mathbb {N}$ be the smallest number with $\mathrm {Enum}(f_Y)[s_Y]\restriction n = Y\restriction n$ . Then $s:=\max \{s_X,s_Y\}$ satisfies $\mathrm {Enum}(f_Z)[2s]\restriction n = Z\restriction n$ .

If $s=s_X$ , then for every $v\in \Sigma ^*$ with $U(v)=X\restriction n$ we obtain $g(v0)=Z\restriction n$ . Similarly, if $s=s_Y$ , then for every $v\in \Sigma ^*$ with $U(v)=Y\restriction n$ we obtain $g(v1)=Z\restriction n$ . Thus,

$$\begin{align*}C(Z\restriction n) \leq^+ C_g(Z\restriction n) \leq \max\{C(X\restriction n), C(Y\restriction n)\} + 1 .\\[-34pt] \end{align*}$$

Proof of Theorem 7.1

Let $Z \subseteq \mathbb {N}$ be a c.e. Kummer complex set. By Theorem 5.1 there exist regainingly approximable sets ${X, Y \subseteq Z}$ with $X \cup Y = Z$ . Fix a constant $d \in \mathbb {N}$ that is large enough to witness the Kummer complexity (†) of Z and such that (‡) is true for all n. If we let $c:=2d$ , then we have, for the infinitely many n satisfying (†), that

$$\begin{align*}2\log(n) - d \leq C(Z \restriction n) \leq \max\{C(X \restriction n), C(Y \restriction n) \} + d, \end{align*}$$

hence,

$$\begin{align*}\max\{C(X \restriction n), C(Y \restriction n) \} \geq 2\log(n) - c, \end{align*}$$

and at least one of X and Y has to be Kummer complex.

Proof Let $A\subseteq \mathbb {N}$ be a regainingly approximable set. By Theorem 4.7 there exists a computable $\mathrm {id}_{\mathbb {N}}$ -good enumeration $g\colon \mathbb {N}\to \mathbb {N}$ of A. For the first assertion, let $B\subseteq \mathbb {N}$ be a decidable set. Then the function $h\colon \mathbb {N}\to \mathbb {N}$ defined by $h(2n):=g(n)$ and $h(2n+1):=n+1$ if $n\in B$ , $h(2n+1):=0$ if $n\not \in B$ , is a computable and $2n$ -good enumeration of ${A\cup B}$ .

For the second assertion, let $f\colon \mathbb {N}\to \mathbb {N}$ be a computable, nondecreasing function. Then the function $h\colon \mathbb {N}\to \mathbb {N}$ defined by

$$\begin{align*}h(n):=\begin{cases} 0, & \text{if } g(n)=0, \\ f(g(n)-1)+1, & \text{if } g(n)>0, \end{cases} \end{align*}$$

for $n\in \mathbb {N}$ , is a computable enumeration of $f(A)$ . If f is bounded then $f(A)$ is finite and h is trivially an $\mathrm {id}_{\mathbb {N}}$ -good enumeration of $f(A)$ . Thus assume that f is unbounded. Then the function $r\colon \mathbb {N}\to \mathbb {N}$ defined by

$$\begin{align*}r(n) := \max\{m\in\mathbb{N} \colon f(m)\leq n\} , \end{align*}$$

for $n\in \mathbb {N}$ , is computable, nondecreasing, and unbounded. We claim that h is an r-good enumeration of $f(A)$ . By assumption, the set

$$\begin{align*}B := \{m\in\mathbb{N} \colon \{0,\ldots,m-1\}\cap A \subseteq \mathrm{Enum}(g)[m]\} \end{align*}$$

is infinite. So is the set $C:=f(B)$ . Consider numbers $n\in C$ and $m\in B$ with $f(m)=n$ . Then $m \leq r(n)$ and we obtain

$$ \begin{align*} \{0,\ldots,n-1\}\cap f(A) &= \{0,\ldots,f(m)-1\}\cap f(A) \\ &\subseteq f(\{0,\ldots,m-1\}\cap A) \\ &\subseteq f(\mathrm{Enum}(g)[m]) \\ &= \mathrm{Enum}(h)[m] \\ &\subseteq \mathrm{Enum}(h)[r(n)].\\[-34pt] \end{align*} $$

Proof For natural numbers $a,b$ and a set $D\subseteq \mathbb {N}$ we write $(a\cdot D + b)$ for the set

$$\begin{align*}(a\cdot D + b) :=\{ n\in\mathbb{N} \colon (\exists d\in D)\; n=a\cdot d + b \} \end{align*}$$

and $(a\cdot D)$ for the set $(a\cdot D + 0)$ . By Theorem 5.3 there exists a c.e. set $\widetilde {C}\subseteq \mathbb {N}$ that is not regainingly approximable. By Theorem 5.1 there exist two disjoint, regainingly approximable sets $\widetilde {A},\widetilde {B}\subseteq \mathbb {N}$ with $\widetilde {A} \cup \widetilde {B} = \widetilde {C}$ . By Lemma 8.1 the sets

$$\begin{align*}A:=(2\cdot \widetilde{A}) \cup (2\cdot\mathbb{N}+1) \ \text{ and } \ B:=(2\cdot\widetilde{B}+1) \cup (2\cdot \mathbb{N}) \end{align*}$$

are regainingly approximable. We claim that their intersection

$$\begin{align*}A\cap B = (2\cdot \widetilde{A}) \cup (2\cdot \widetilde{B}+1)\end{align*}$$

is not regainingly approximable. To see this, let $g\colon \mathbb {N}\to \mathbb {N}$ be defined by $g(n)= \lfloor n/2 \rfloor $ for all $n\in \mathbb {N}$ . We observe ${\widetilde {C}=g(A\cap B)}$ . Thus, if $A\cap B$ were a regainingly approximable set, then so would be $\widetilde {C}$ according to Lemma 8.1(2), a contradiction.

Proof The first assertion follows from Theorems 4.7 and 5.3. The second assertion follows from Corollary 5.2 and Theorem 4.7 and from the well-known fact that, for any $A\subseteq \mathbb {N}$ , the number $2^{-A}$ is computable if and only if A is decidable.

Proof Let $f\colon \{q\in \mathbb {Q} \colon q < \beta \}\to \mathbb {Q}$ be a computable function and ${c\in \mathbb {N}}$ be a number such that, for all $q\in \{q\in \mathbb {Q} \colon q < \beta \}$ , we have $f(q)<\alpha $ and ${\alpha - f(q) < 2^c \cdot (\beta - q)}$ . By Proposition 3.2 there exists a computable and increasing sequence $(b_n)_n$ of rational numbers converging to $\beta $ such that $\beta - b_n < 2^{-n-c}$ for infinitely many ${n\in \mathbb {N}}$ . The sequence $(a_n)_n$ defined by

$$\begin{align*}a_n := \max\{f(b_i) \colon 0 \leq i \leq n\} \end{align*}$$

is a nondecreasing, computable sequence of rational numbers converging to $\alpha $ . For the infinitely many n with $\beta - b_n < 2^{-n-c}$ we obtain

$$\begin{align*}\alpha - a_n \leq \alpha - f(b_n) < 2^c \cdot(\beta - b_n) < 2^{-n}.\\[-34pt] \end{align*}$$

Proof The first assertion follows from Proposition 8.4 and from the fact that for any two left-computable numbers $\alpha $ , $\beta $ one has $\alpha \leq _{\mathrm {S}} \alpha +\beta $ and $\beta \leq _{\mathrm {S}} \alpha +\beta $ .

Since adding a computable number to a left-computable number does not change its Solovay degree, the second assertion follows from Proposition 8.4 as well.

Proof This follows from Theorem 5.1 together with Theorem 4.7.

Proof According to Corollary 8.3(1), there exists a strongly left-computable number $\gamma $ that is not regainingly approximable. Then, according to Corollary 8.6, there exist two strongly left-computable and regainingly approximable numbers $\alpha $ , $\beta $ with ${\alpha +\beta =\gamma }$ that witness the truth of the assertion.

Proof Let a function f as in the statement be given. We will describe an algorithm that works in stages to define the desired functions g and h, as well as a function $s\colon \mathbb {N}\times \mathbb {N}\to \mathbb {N}$ . We write $s_i[t]$ for $s(i,t)$ to express the intuition that $s_i[t]$ is our current guess for $S_i$ at stage t.

We begin with a high-level overview of the proof strategy: Whenever f enumerates a number n at stage t, we need to let either g or h enumerate it. To decide between the two, we follow a greedy strategy in the following sense: for every t the sequence $(s_i[t])_i$ will be increasing; if at stage t the largest number i with $s_i[t]\leq n$ is even then we let g enumerate n, otherwise h. As we will show this is sufficient to prove the statement of the lemma; in particular, for every i, $(s_i[t])_t$ will turn out to be nondecreasing and eventually constant, allowing us to define ${S_i:=\lim _{t\to \infty } s_i[t]}$ .

With this we are ready to give the formal proof.

At stage $0$ we define $s_i[0]:=i$ for all $i\in \mathbb {N}$ .

At a stage $t+1$ with $t\in \mathbb {N}$ we proceed as follows:

• • If $f(t)=0$ then we set $g(t):=0$ and $h(t):=0$ . Intuitively speaking this means that f does not enumerate any new element at stage t, and that we therefore do not let g and h enumerate any new elements either. We also set $s_i[t+1]:=s_i[t]$ for all $i\in \mathbb {N}$ .

• • If $f(t)>0$ then this means $n:=f(t)-1$ is enumerated by f at stage t. We want to let n be enumerated by either g or by h, as follows: If

  $$\begin{align*}k_t := \min\{j\in\mathbb{N} \colon s_j[t]> n\} \end{align*}$$
  is even then we set $g(t):=0$ and $h(t):=n+1$ (which means that n is enumerated by h); otherwise, if $k_t$ is odd, then we set $g(t):=n+1$ and $h(t):=0$ (which means that n is enumerated by g). Furthermore, we define $s_i[t+1]$ for all $i\in \mathbb {N}$ by
  $$\begin{align*}s_i[t+1] := \begin{cases} s_i[t], & \text{if } i \leq k_t, \\ s_i[t] + t + 1, & \text{if } k_t < i. \end{cases} \end{align*}$$

This ends the description of stage t and of the algorithm; we proceed with the verification.

By Claim 1, for every $t\in \mathbb {N}$ with $f(t)>0$ , the number $k_t$ is well defined; thus it is clear that g and h as defined by the algorithm satisfy ( $\ast $ ) for every $n\in \mathbb {N}$ . It remains to prove the second condition in the statement of the lemma.

Proof That $(s_i[t])_t$ is nondecreasing for every i is clear by definition. We show by induction over i that it is eventually constant as well.

It is easy to see that $s_0[t]=0$ for all t. Thus consider an arbitrary number $i>0$ . By the induction hypothesis there exists a number $t_1$ such that, for all $t\geq t_1$ , $s_{i-1}[t]=s_{i-1}[t_1]$ . Let $t_2$ be large enough so that $t_2> t_1$ and

$$\begin{align*}f^{-1}\{1,\ldots, s_{i-1}[t_1]\} \subseteq \{0,\ldots,t_2-1\} \end{align*}$$

(meaning that numbers smaller than $s_{i-1}[t_1]$ are enumerated by f only in stages before $t_2$ ). Then, for every $t\geq t_2$ with $f(t)>0$ and for every $j<i$ we have

$$\begin{align*}s_j[t] \leq s_{i-1}[t] = s_{i-1}[t_1] \leq f(t)-1 , \end{align*}$$

hence, $k_t\geq i$ and consequently $s_i[t+1]=s_i[t]$ . By induction we obtain $s_i[t]=s_i[t_2]$ , for all $t\geq t_2$ . Thus, $(s_i[t])_t$ is eventually constant, and Claim 2 is proven.

Let the sequence $(S_i)_i$ be defined by $S_i:=\lim _{t\to \infty } s_i[t]$ . Due to Claim 1, $(S_i)_i$ is increasing.

Proof Consider an even number i as well as some $t\geq S_i$ with $g(t)>0$ ; we need to show that $g(t)>S_i$ . To see this, first observe that the assumption that $g(t)>0$ implies that we must have $f(t)=g(t)$ and that $k_t$ must be odd. Hence $k_t\neq i$ . If $k_t$ were smaller than i then we would obtain $s_i[t+1] = s_i[t]+t+1> s_i[t]=S_i$ in contradiction to Claim 3. We conclude $i<k_t$ . This implies $s_i[t]\leq f(t)-1$ by the definition of $k_t$ . As $t\geq S_i$ , using Claim 3 again, we obtain

$$\begin{align*}S_i=s_i[t] \leq f(t)-1 <f(t) = g(t),\end{align*}$$

which proves Claim 4.

Proof First transform $f_C$ into an enumeration without repetitions $\widetilde {f_C}$ as in Remark 4.5; then apply the algorithm described in the proof of Lemma 9.1 to $\widetilde {f_C}$ .

Proof Applying the algorithm in the proof of Lemma 9.1 to $f_\gamma $ proves the first assertion. For the second assertion, use the first assertion and the following claim.

Proof As above, define

$$\begin{align*}a_k := \begin{cases} 2^{-f(k)}, & \text{if } f(k)>0, \\ 0, & \text{if } f(k)=0, \end{cases} \end{align*}$$

and $A_t:=\sum _{k<t} a_k$ . Then the sequence $(A_t)_t$ is a computable nondecreasing sequence converging to $\alpha = \sum _{k=0}^\infty a_k$ . For any of the infinitely many t with $f^{-1}\{1,\ldots ,t\}\subseteq \{0,\ldots ,t-1\}$ we obtain

$$\begin{align*}\alpha - A_t = \sum_{k=t}^\infty a_k \leq n \cdot \sum_{j=t+1}^\infty 2^{-j} = n \cdot 2^{-t}. \end{align*}$$

By Proposition 3.2 this implies that $\alpha $ is regainingly approximable.

The third follows immediately from the second assertion.