Closed left-r.e. sets

Abstract

A set is called r-closed left-r.e. iff every set r-reducible to it is also a left-r.e. set. It is shown that some but not all left-r.e. cohesive sets are many–one closed left-r.e. sets. Ascending reductions are many–one reductions via an ascending function; left-r.e. cohesive sets are also ascending closed left-r.e. sets. Furthermore, it is shown that there is a weakly 1-generic many–one closed left-r.e. set. We also consider initial segment complexity of closed left-r.e. sets. We show that initial segment complexity of ascending closed left-r.e. sets is of sublinear order. Furthermore, this is near optimal as for any non-decreasing unbounded recursive function g, there are ascending closed left-r.e. sets A whose plain complexity satisfies $C (A (0) A (1) \dots A (n)) ⩾ n / g (n)$ for all but finitely many n. The initial segment complexity of a conjunctively (or disjunctively) closed left-r.e. set satisfies, for all $ε > 0$ , for all but finitely many n, $C (A (0) A (1) \dots A (n)) ⩽ (2 + ε) log (n)$ .

Keywords

Left-r.e. sets reducibilities Kolmogorov complexity cohesive sets weakly 1-generic sets

1. Introduction

When studying the limits of computation, one often looks at recursively enumerable (r.e.) and left-r.e. sets. Natural examples of the r.e. sets are Diophantine sets and the word problem of a finitely generated group [11,15,17]. The best-known left-r.e. set is Chaitin’s Ω [2,19]. The present work focuses on a special subclass of the left-r.e. sets, namely those which are closed downwards with respect to the many–one, ascending, disjunctive or conjunctive reducibilities. While all r.e. sets exhibit closure under various reducibilities – one–one, many–one, conjunctive, disjunctive, positive truth-table and enumeration [11,15,17] – some left-r.e. sets, such as Chaitin’s Ω, fail to do so.

We show that the classes of many–one closed left-r.e. sets and r.e. sets do not coincide: there exist both, cohesive and weakly 1-generic sets, which are many–one closed left-r.e. but not recursively enumerable, see Theorems 3.3, 4.1 and Remark 4.2. We also show that there are cohesive left-r.e. sets which are not many–one closed left-r.e., see Theorem 3.11. We introduce the more restrictive notion of ascending reducibility. We show that cohesive and even r-cohesive left-r.e. sets are already ascending closed left-r.e. sets, see Theorem 3.12.

Kolmogorov complexity measures the information content of strings; the applications of this notion range from quantifying the amount of algorithmic randomness [1,3,10] to establishing lower bounds on the average running time of an algorithm [7]. Here the idea is to fix a universal machine U and to measure the plain Kolmogorov complexity $C (x)$ as $log (y)$ for the least y such that $U (y) ↓ = x$ (we take $log (y)$ as the number of bits needed to represent y in binary). Given any acceptable numbering $φ_{0}, φ_{1}, \dots$ of the partial-recursive functions, one can define $U (2^{e} + 2^{e + 1} \cdot x - 1) = φ_{e} (x)$ in order to define a universal machine in an easy way. An important tool to measure the complexity of a set A is the initial segment complexity which maps each n to the Kolmogorov complexity of $A (0) A (1) \dots A (n)$ . We show that the initial segment complexity of ascending closed left-r.e. sets has to be sublinear, see Proposition 5.1. We also show that the initial segment complexity of an ascending closed left-r.e. sets can be at least $n / f (n)$ for all but finitely many n, for any unbounded non-decreasing recursive function f, which is close to optimal, see Theorem 5.2. Similarly Theorem 5.3 shows that the initial segment complexity of a many–one closed left-r.e. set can be at least $n / f (n)$ for infinitely many n, for any unbounded non-decreasing recursive function f. We also show that for conjunctively (or disjunctively) closed left-r.e. sets A, for all ε, for all but finitely many n, the initial segment complexity $C (A (0) A (1) \dots A (n))$ is bounded from above by $(2 + ε) log (n)$ (see Theorems 5.4 and 5.5).

2. Existence of closed left-r.e. sets

We formalise the notion of a “closed left-r.e.” set. Let $N$ denote the set of natural numbers ${0, 1, 2, \dots}$ . We identify a string σ of length n with the partial function $σ (0) σ (1) \dots σ (n - 1) = σ$ . $σ <_{lex} τ$ means that lexicographically σ is before τ. Let $φ_{0}, φ_{1}, \dots$ denote an acceptable numbering of partial recursive functions. Let $W_{0}, W_{1}, \dots$ denote an acceptable numbering of recursively enumerable (r.e.) sets. Let $W_{e, s}$ denote $W_{e}$ enumerated within s steps. We assume without loss of generality that $W_{e, s} \subseteq {0, 1, 2, \dots, s - 1}$ . Post [13] introduced many–one reducibility by defining that a set B many–one reduces to a set A, denoted $A ⩽_{m} B$ , if there exists a recursive function f such that $x \in A \Leftrightarrow f (x) \in B$ . Many–one reducibility can be generalised to so called strong reducibilities, that is, reducibilities which imply truth-table reducibility. Among those, the ones which preserve recursively enumerability are important for the present work, including conjunctive, disjunctive and positive reducibility [5,11]. For the following definition, fix a bijection between numbers and finite sets: the most common method is to use the index $e = \sum_{d \in D} 2^{d}$ for a finite set D. Then, for example, $D_{0} = \emptyset$ , $D_{2^{m}} = {m}$ and $D_{2^{m} + 2^{n}} = {m, n}$ for distinct m, n.

Definition 2.1.
We define following reducibilities.
$A ⩽_{asc} B$ (A is ascendingly reducible to B) iff there is a non-decreasing recursive function f such that $\forall x$ $[x \in A \Leftrightarrow f (x) \in B]$ .

$A ⩽_{m} B$ (A is many–one reducible to B) iff there is a recursive function f such that $\forall x$ $[x \in A \Leftrightarrow f (x) \in B]$ .

$A ⩽_{c} B$ (A is conjunctively reducible to B) iff there is a recursive function f such that $\forall x$ $[x \in A \Leftrightarrow D_{f (x)} \subseteq B]$ .

$A ⩽_{d} B$ (A is disjunctively reducible to B) iff there is a recursive function f such that $\forall x$ $[x \in A \Leftrightarrow B \cap D_{f (x)} \neq \emptyset]$ .

$A ⩽_{p} B$ (A is positively reducible to B) iff there is a set C with $A ⩽_{d} C \land C ⩽_{c} B$ .

Alternatively to the definition of positive reducibility above, one could also directly define that $A ⩽_{p} B$ iff there is an algorithm which computes for every x an expression consisting of conjunctions, disjunctions and atoms which are either the fixed truth values “false” or “true” or “ $y \in B$ ” for some y computed from x and then $x \in A$ iff this expression evaluated on B is true. Note that conjunctive and disjunctive reducibilities both generalise many–one reducibility; furthermore, positive reducibility is the least upper bound (among all transitive reducibilities) of conjunctive and disjunctive reducibilities.
Definition 2.2.
A set A is left-r.e. iff there is a uniformly recursive approximation $A_{0}, A_{1}, \dots$ to A such that $A_{s} ⩽_{lex} A_{s + 1}$ for all s. Here $A_{s} ⩽_{lex} A_{s + 1}$ means that either $A_{s} = A_{s + 1}$ or the least element x of the symmetric difference of $A_{s}$ and $A_{s + 1}$ satisfies $x \in A_{s + 1}$ .

If every set r-reducible to A is left-r.e. then we say that A is an r-closed left-r.e. set.

It is well-known that every set which is positively reducible to an r.e. set is also itself r.e. [15]; hence every r.e. set is a many–one closed left-r.e. set. Furthermore, a set is recursive iff it is a bounded truth-table (btt) closed left-r.e. set because the complement of any set btt-reduces to the set itself, see [11] for discussion of btt-reductions. The first result below shows that one can get positive closed left-r.e. sets in a non-trivial way.

Suppose $A ⩽_{p} B$ , and $f (x)$ is the corresponding expression for the reduction involving conjunctions, disjunctions and atoms which are of the form ‘true’ or ‘false’ or ‘ $y \in B$ ’. Then, one can construct a corresponding oracle Turing Machine $M^{B}$ which, on input x, only queries elements y such that ‘ $y \in B$ ’ is an atom in $f (x)$ , and then computes the value of $f (x)$ (which gives the value $A (x)$ ). We can consider the above M as witnessing the reduction $A ⩽_{p} B$ .

For the following theorem, let $⟨ \cdot, \cdot ⟩$ be a one–one recursive pairing function such that if $max {d, e} < max {d^{'}, e^{'}}$ then $⟨ d, e ⟩ < ⟨ d^{'}, e^{'} ⟩$ . For example, the pairing function $\begin{matrix} ⟨ d, e ⟩ = \{\begin{matrix} {(max {d, e})}^{2} + 2 d, & if d ⩽ e; \\ {(max {d, e})}^{2} + 2 e + 1, & otherwise. \end{matrix} \end{matrix}$ satisfies the above requirements. Theorem 2.3.
There exists a non-r.e. positive closed left-r.e. set.
Proof.
If for some $B ⩽_{p} A$ , B is not left-r.e., then, without loss of generality, one can assume that for some non-left-r.e. set C there exists an e such that $φ_{e}$ witnesses $C ⩽_{p} A$ and $φ_{e}^{A} (x)$ is computed by querying only to values $y ⩽ x$ and the computation needs at most $x^{2}$ time to be computed. This can be shown as follows. Suppose $B (x) = b_{x}$ . Suppose that $q (x)$ is the maximum of the largest question asked in the reduction $B ⩽_{p} A$ for input x and the time to compute a truth-table. Then let the characteristic function of C be given by the string $1^{q (0) + 1} b_{0} 1^{q (1) + 1} b_{1} 1^{q (2) + 1} b_{2} \dots$ ; clearly, C is not a left-r.e. set and C can be computed using oracle for A via a positive reduction, where the largest questions asked on any input y is bounded by y. For the following let $ψ_{0}, ψ_{1}, \dots$ be a recursive sequence of all reductions which are quadratic time bounded and do not use any query greater than x on input x.

We will construct finite sets $X_{i}$ , with approximation ${lim}_{s \to \infty} X_{i, s} = X_{i}$ . It will be the case that $max X_{i, s} < min X_{i + 1, s}$ .

Let $A_{s} = N - ⋃_{i} X_{2 i + 1, s}$ and $A = N - ⋃_{i} X_{2 i + 1}$ . Initially, $X_{i, 0} = {i}$ . We will have requirements $R_{2 d + 1}$ and $R_{2 ⟨ d, e ⟩}$ with $d < e$ ; the goals of the requirements are the following: $\begin{array}{l} R_{2 d + 1} : if W_{d} intersects infinitely many X_{i} then there exists an odd e such that W_{d} \cap X_{e} \neq \emptyset; \\ R_{2 ⟨ d, e ⟩} (where d ⩽ e) : ψ_{d}^{A \cup X_{2 e + 1}} (y) > ψ_{d}^{A} (y), for some y ⩽ max X_{2 e + 1} . \end{array}$ Note that we do not use $R_{2 ⟨ d, e ⟩}$ , $d > e$ . For ease of notation, we assume them to be null requirements which are always satisfied. It will be a priority construction and requirements earlier satisfied may be injured by higher priority requirements (if $i < j$ , then $R_{i}$ has higher priority than $R_{j}$ ). Additionally, in trying to satisfy the requirements, we may block certain $X_{e}$ from changing. Intuitively, ${Blk}_{2 d + 1} = 2 e + 1$ at the beginning of stage s means that $W_{d} \cap ⋃_{i ⩽ e} X_{2 i + 1, s} \neq \emptyset$ and thus $R_{2 d + 1}$ is satisfied; hence to preserve this, $X_{i}$ , for $i ⩽ 2 e + 1$ should not be changed when satisfying any requirement $R_{2 d^{'} + 1}$ with $d^{'} > d$ . ${Blk}_{2 d + 1} = 0$ correspondingly means that $R_{2 d + 1}$ is not satisfied. Intuitively, ${Blk}_{2 d} = 2 e + 1$ means that we are looking to satisfy $R_{2 ⟨ d, e ⟩}$ (and the higher priority requirements $R_{2 ⟨ d, e^{'} ⟩}$ , $d ⩽ e^{'} < e$ , are currently satisfied and not injured). Initially, ${Blk}_{2 d + 1} = 0$ and ${Blk}_{2 d} = 2 d + 1$ . The construction in stages $s = 0, 1, 2, \dots$ , is as follows.
Stage s: Satisfy the highest priority (that is least index) requirement $R_{i}$ , $i ⩽ s$ , which can be satisfied and which is currently not satisfied. The requirements, whether they can be satisfied and the mechanism to satisfy them is listed as follows:

$R_{2 d + 1}$ can be satisfied if:
there exists an e, with $2 d + 1 ⩽ 2 e + 2 ⩽ s$ , such that $W_{d, s} \cap X_{2 e + 2, s} \neq \emptyset$ ,

$W_{d, s} \cap ⋃_{e^{'} < e} X_{2 e^{'} + 1, s} = \emptyset$ ,

${Blk}_{2 d^{'} + 1} < 2 e + 1$ , for $d^{'} < d$ , and

${Blk}_{2 d^{'}} \neq 2 e + 1$ , for $d^{'} < d$ .
In this case, pick the least such e. The requirement can be satisfied by setting ${Blk}_{2 d + 1} = 2 e + 1$ , $X_{j, s} = X_{j, s}$ , for $j < 2 e + 1$ , $X_{2 e + 1, s + 1} = X_{2 e + 2, s}$ , and $X_{2 e + 2 + j, s + 1} = X_{2 e + 2 + j + 1, s}$ , for $j ⩾ 0$ . Furthermore, we injure all requirements $R_{2 d^{'} + 1}$ , $d^{'} > d$ , and set ${Blk}_{2 d^{'} + 1} = 0$ . Furthermore, for all $d^{'}$ , with ${Blk}_{2 d^{'}} > 2 e + 1$ , we set ${Blk}_{2 d^{'}} = max {2 e + 1, 2 d^{'} + 1}$ .

$R_{2 ⟨ d, e ⟩}$ can be satisfied if:
${Blk}_{2 d} = 2 e + 1$ ,

$max X_{2 e + 1, s} ⩽ s$ and

$(\exists y ⩽ s) [ψ_{d}^{A_{s} \cup {x : min X_{2 e + 1, s} ⩽ x ⩽ s}} (y) ↓ > ψ_{d}^{A_{s}} (y) ↓]$ .
$R_{2 ⟨ d, e ⟩}$ can be satisfied by first choosing an $e^{'}$ such that $s < max X_{2 e^{'} + 1, s}$ . Then, setting $X_{j, s + 1} = X_{j, s}$ , for $j < 2 e + 1$ , $X_{2 e + 1, s + 1} = ⋃_{{i : 2 e + 1 ⩽ 2 i + 1 ⩽ 2 e^{'} + 1}} X_{2 i + 1, s}$ , $X_{j, s + 1} = X_{j - 2 e + 2 e^{'}, s}$ , for $j > 2 e + 1$ . Furthermore, set ${Blk}_{2 d} = 2 e + 3$ , and for all $d^{'}$ , with ${Blk}_{2 d^{'}} > 2 e + 1$ , set ${Blk}_{2 d^{'}} = max {2 e + 3, 2 d^{'} + 1}$ . For all $d^{'}$ , $e^{″}$ with ${Blk}_{2 d^{'} + 1} = 2 e^{″} + 1$ , ${Blk}_{2 d^{'} + 1}$ is updated to the value $2 e^{‴} + 1$ with $X_{2 e^{″} + 1, s} \subseteq X_{2 e^{‴} + 1, s + 1}$ .

Note that $A_{s + 1} = A_{s}$ . Using this, and the above updates it is easy to verify that satisfying $R_{2 ⟨ d, e ⟩}$ did not injure any $R_{2 d^{'} + 1}$ , $d^{'} \in N$ , and any $R_{2 ⟨ d^{'}, e^{'} ⟩}$ , with $d^{'} ⩽ e^{'} ⩽ e$ which were earlier satisfied.

End Stage s.
By induction, ${lim}_{s \to \infty} X_{e, s}$ converges. To see this suppose ${lim}_{s \to \infty} X_{e^{'}, s}$ converges for all $e^{'} < e$ . Let $s_{0}$ be large enough so that $X_{e^{'}, s}$ , $e^{'} < e$ , have converged to their final values by stage $s_{0}$ . Then, for $s > s_{0}$ , $X_{e, s}$ can change its value due to satisfying of $R_{1}$ at most once, and after this happens (if ever) for the last time, at most once due to satisfying of $R_{3}$ , and so on for satisfying $R_{2 e^{'} + 1}$ , up to the largest $e^{'}$ such that $2 e^{'} + 1 ⩽ e$ . After all of the above modifications are done, satisfying $R_{2 ⟨ d, e^{'} ⟩}$ , for $2 d ⩽ 2 e^{'} ⩽ e$ , can update $X_{e, s}$ , at most once each. Thus, ${lim}_{s \to \infty} X_{e, s}$ converges to say $X_{e}$ . Thus, we also have that $R_{2 d + 1}$ is satisfied for all d, and thus A is not an r.e. set.

Now suppose $B ⩽_{p} A$ as witnessed by $ψ_{d}$ . Then, consider a stage $s_{0}$ such that all $X_{e}$ have attained their final value for $e ⩽ 2 d + 1$ .
In case $R_{2 ⟨ d, e ⟩}$ is satisfied for all $e ⩾ d$ (that is ${Blk}_{2 d}$ converges to ∞), then we can compute $ψ_{d}^{A}$ in left-r.e. fashion as follows. For $s ⩾ s_{0}$ , define $k_{s}$ to be value of ${Blk}_{2 d}$ at the beginning of stage s. Then, for $s ⩾ s_{0}$ , let $B_{s} (x) = ψ_{d}^{A_{s}} (x)$ , for $x ⩽ max X_{k_{s}}$ and let $B_{s} (x) = 0$ , for $x > max X_{k_{s}}$ . Now, $B_{s}$ , $s ⩾ s_{0}$ , approximate B in a left-r.e. fashion. To see this, suppose $s ⩾ s_{0}$ . If $A_{s} \cap {x : x ⩽ max X_{k_{s}, s}} ⊈ A_{s + 1}$ , then for the least r such that $X_{2 r, s} ⊈ A_{s + 1}$ , we have that $X_{2 r - 1, s} \subseteq A_{s + 1} - A_{s}$ . Furthermore, $R_{2 ⟨ d, r - 1 ⟩}$ was satisfied at the beginning of stage s, and thus some $y ⩽ max X_{2 r - 1, s}$ satisfies $ψ_{d}^{A_{s + 1}} (y) > ψ_{d}^{A_{s}} (y)$ (that is, $ψ_{d}^{A_{s + 1}} (y) = 1$ and $ψ_{d}^{A_{s}} (y) = 0$ ). Also, by constraints on queries used by ψ, for all $y ⩽ max X_{2 r - 1, s}$ , $ψ_{d}^{A_{s + 1}} (y) ⩾ ψ_{d}^{A_{s}} (y)$ . Thus, ${(B_{s})}_{s \in N}$ witness that B is left-r.e.

In case $R_{2 ⟨ d, e ⟩}$ is not satisfied in the limit, for some least $e ⩾ d$ (that is ${Blk}_{2 d}$ converges to $2 e + 1$ ), then for sufficiently large x and all $s > x$ , $ψ_{d}^{N - ⋃_{j < e} X_{2 j + 1}} (x)$ is same as $ψ_{d}^{A_{s}} (x)$ . Thus, B is recursive and, for all but finitely many x, $B (x) = ψ_{d}^{A_{x + 1}} (x)$ .
Hence A is a positive closed left-r.e. set. □

3. Cohesive and maximal sets

When trying to construct r.e. sets which are neither recursive nor Turing complete, Post [13] introduced various notions of immune, hyperimmune and hyperhyperimmune sets which formalise that one cannot pick out infinitely many elements of these sets in certain more and more powerful ways. Furthermore, Post considered r.e. sets with immune, hyperimmune and hyperhyperimmune complement which he correspondingly called simple, hypersimple and hyperhypersimple, respectively. In the search for the existence of hyperhypersimple sets (which was left open by Post [13]), these notions have been strengthened and led to the following definition.

Definition 3.1 (Friedberg [4], Lachlan [6], Myhill [8] and Robinson [14]).

An infinite set A is cohesive iff for every r.e. set B either $B \cap A$ or $\overline{B} \cap A$ is finite. An infinite set A is r-cohesive iff for every recursive set B either $A \cap B$ or $A \cap \overline{B}$ is finite. If a set is r.e. and has a cohesive/r-cohesive complement then it is called maximal/r-maximal, respectively.

Theorem 3.3 below provides an example of a cohesive many–one closed left-r.e. set. We remark that Soare [16] already discovered a cohesive left-r.e. set. The following notational conventions will be useful. Let $\begin{matrix} φ_{e, s} (x) = \{\begin{matrix} φ_{e} (x), & if x ⩽ s and φ_{e} halts on input y within s steps for all y ⩽ x, \\ ↑, & otherwise . \end{matrix} \end{matrix}$ Note that if $φ_{e}$ is total, then $⋃_{s} φ_{e, s} = φ_{e}$ . Otherwise, the domain of $⋃_{s} φ_{e, s}$ is some initial segment of $N$ . Let $φ_{e, s}^{- 1} (x) = min {y : φ_{e, s} (y) = x}$ and let $φ_{e}^{- 1} = {lim}_{s} φ_{e, s}^{- 1}$ . (Here we assume that $min \emptyset$ is undefined.)

Lemma 3.2.
Suppose $φ_{e_{1}}, φ_{e_{2}}, \dots, φ_{e_{k}}$ are total. Furthermore, suppose that the set $S = range (φ_{e_{1}}) \cap range (φ_{e_{2}}) \cap \dots \cap range (φ_{e_{k}})$ is infinite. Then, for all a, r, there exist $a_{1}, a_{2}, \dots, a_{r} \in S$ such that $a < a_{1} < a_{2} < \dots < a_{r}$ and, for n, m with $1 ⩽ n < r$ and $1 ⩽ m ⩽ k$ it holds that $φ_{e_{m}}^{- 1} (a_{n}) < φ_{e_{m}}^{- 1} (a_{n + 1})$ .
Proof.
Let $a_{1}$ be any member of S which is greater than a. For i with $2 ⩽ i ⩽ r$ , let $a_{i} \in S$ be chosen such that $a_{i} > a_{i - 1}$ and for m with $1 ⩽ m ⩽ k$ , $φ_{e_{m}}^{- 1} (a_{i - 1}) < φ_{e_{m}}^{- 1} (a_{i})$ . Note that there exist such $a_{i} \in S$ , as S is infinite and only finitely many elements x can have $φ_{e_{m}}^{- 1} (x) ⩽ φ_{e_{m}}^{- 1} (a_{i - 1})$ . □
Theorem 3.3.
There is a cohesive many–one closed left-r.e. set A.
Proof.
The following is a modification of the construction of cohesive/maximal set, say A (see for example [17]), where instead of using moving markers individually, we use intervals of moving markers. Then, using a concept similar to e-state in the construction of cohesive/maximal sets, we ensure that the chosen set A is cohesive (where, for members of A, we choose one element from each interval). Furthermore, instead of e-state bits having values 0 or 1, we consider them having values 0, 1 and 2, where the values 1 and 2 are used to ensure some monotonicity in the reductions to A. This will allow us to show that A is many–one closed left-r.e. set. We now proceed formally.

We will use moving markers, $a_{0}, a_{1}, \dots$ ; let $a_{m, s}$ denote the value of marker $a_{m}$ as at the beginning of stage s. Inductively for $d \in N$ and $s \in N$ , we define $l_{0} = 0$ , $r_{d} = l_{d} + 3^{d + 2} + 1$ , $l_{d + 1} = r_{d} + 1$ and $I_{d, s} = {a_{m, s} : l_{d} ⩽ m ⩽ r_{d}}$ . For all m, s, we will have the following property: $\begin{matrix} (R 1) : a_{m, s} < a_{m + 1, s} . \end{matrix}$ Define the predicate $P_{e, s} (d)$ as $\begin{matrix} P_{e, s} (d) : (\exists a_{m, s}, a_{n, s} \in I_{d, s}) [a_{m, s} < a_{n, s} and φ_{e, s}^{- 1} (a_{m, s}) > φ_{e, s}^{- 1} (a_{n, s})] . \end{matrix}$ For $e ⩽ d$ , let $\begin{matrix} i_{e, s} (d) = \{\begin{matrix} 0, & if I_{d, s} ⊈ range (φ_{e, s}), \\ 1, & if I_{d, s} \subseteq range (φ_{e, s}) and P_{e, s} (d), \\ 2, & if I_{d, s} \subseteq range (φ_{e, s}) and not P_{e, s} (d) \end{matrix} \end{matrix}$ and $Q_{e, s} (d) = (i_{0, s} (d), i_{1, s} (d), \dots, i_{e, s} (d))$ . Note that one can consider $Q_{e, s} (d)$ as a number (base 3), with $i_{0, s} (d)$ as being the most significant bit. So one can talk about $Q_{e, s} (d) > Q_{e^{'}, s^{'}} (d^{'})$ etc. We let $a_{m} = {lim}_{s \to \infty} a_{m, s}$ , $I_{d} = {lim}_{s \to \infty} I_{d, s}$ , $i_{e} (d) = {lim}_{s \to \infty} i_{e, s} (d)$ , and $\begin{matrix} Q_{e} (d) = lim_{s \to \infty} Q_{e, s} (d) = (i_{0} (d), i_{1} (d), \dots, i_{e} (d)) . \end{matrix}$ We will show later that these limits exist. Intuitively, the aim of the construction of the moving markers $a_{m}$ is to maximise the values of $Q_{e} (e)$ with higher priority given for lower values of e. The required set A will be defined later by choosing one element from each $I_{e}$ . We define $a_{m, s}$ via the staging construction below. Stage s defines $a_{m, s + 1}$ .

Initially, let $a_{m, 0} = m$ . Execute stages $s = 0, 1, 2, \dots$ as follows.
Stage s: Check whether there exists $e ⩽ s$ such that, by using $a_{m, s + 1} = a_{m, s}$ for $m < l_{e}$ , some values of $a_{m, s + 1} ⩽ s$ for $l_{e} ⩽ m ⩽ r_{e}$ , and any values for $a_{m, s + 1}$ for $m > r_{e}$ such that (R1) is satisfied, we have $Q_{e, s + 1} (e) > Q_{e, s} (e)$ .

If so, then update the values of $a_{m, s + 1}$ to the values witnessing above for the least such e. If no such e exists, then $a_{m, s + 1} = a_{m, s}$ , for all m.

End Stage s.
Claim 3.4.
For all e,
for all m with $l_{e} ⩽ m ⩽ r_{e}$ , ${lim}_{e \to \infty} Q_{e, s} (e)$ and ${lim}_{s \to \infty} a_{m, s}$ converge;

${lim}_{s \to \infty} I_{e, s}$ converges;

for all $d ⩾ e$ , ${lim}_{s \to \infty} i_{e, s} (d)$ converges.

Statement (a) follows by induction on e and the fact that $Q_{e, s} (e)$ is bounded. Now (b) and (c) follow by definitions. We let $a_{m}$ , $I_{e}$ , $i_{e} (d)$ and $Q_{e} (d)$ respectively denote ${lim}_{s \to \infty} a_{m, s}$ , ${lim}_{s \to \infty} I_{e, s}$ , ${lim}_{s \to \infty} i_{e, s} (d)$ and ${lim}_{s \to \infty} Q_{e, s} (d)$ . Claim 3.5.
For all d and all $e ⩽ d$ , $Q_{e} (d + 1) ⩽ Q_{e} (d)$ .

To prove the claim, suppose by way of contradiction that some least d and a corresponding least $e ⩽ d$ does not satisfy the claim. Let s be large enough such that for all $d^{'} ⩽ d + 1$ , $s^{'} > s$ , $I_{d^{'}, s^{'}} = I_{d^{'}, s}$ and $Q_{d^{'}, s^{'}} (d^{'}) = Q_{d^{'}, s} (d^{'})$ . Then, in stage s, one could choose $a_{l_{d}, s + 1}, \dots, a_{r_{d}, s + 1}$ to be $a_{l_{d + 1}}, \dots, a_{r_{d} + l_{d + 1} - l_{d}}$ , which makes $Q_{e, s + 1} (d) > Q_{e, s} (d)$ , and thus $Q_{d, s + 1} (d) > Q_{d, s} (d)$ , in contradiction to the choice of s.

It follows from Claim 3.5 that, for all e, for all but finitely many $d ⩾ e$ , $Q_{e} (d) = Q_{e} (d + 1)$ . Thus we get the following: Claim 3.6.
For all e, for all but finitely many $d > e$ , $i_{e} (d + 1) = i_{e} (d)$ . We let $j_{e} = {lim}_{d \to \infty} i_{e} (d)$ .
Claim 3.7.
For all e, $j_{e} \in {0, 2}$ .

To prove the claim, suppose by way of contradiction that $j_{e} = 1$ , for some least e. Choose d large enough such that, for all $e^{'} ⩽ e$ , for all $d^{'} ⩾ d$ , $i_{e^{'}} (d^{'}) = j_{e^{'}}$ . Consider a large enough stage s such that, for all $d^{'} ⩽ d$ , for all $s^{'} ⩾ s$ , $I_{d^{'}, s^{'}} = I_{d^{'}, s}$ and $Q_{d^{'}, s^{'}} (d^{'}) = Q_{d^{'}, s} (d^{'})$ . Then we could make $Q_{e, s^{'}} (d) > Q_{e, s} (d)$ , for large enough $s^{'} > s$ by choosing $a_{l_{d}, s^{'}}, \dots, a_{r_{d}, s^{'}}$ (with $a_{l_{d}, s^{'}} > a_{l_{d}}$ ) appropriately such that for all $e^{'} ⩽ e$ , if $I_{d} \subseteq range (φ_{e^{'}})$ , then $φ_{e^{'}}^{- 1} (a_{m, s^{'}}) < φ_{e^{'}}^{- 1} (a_{n, s^{'}})$ for $l_{d} ⩽ m < n ⩽ r_{d}$ . (It is possible to choose such values as, for $e^{'} ⩽ e$ , if $I_{d} \subseteq range (φ_{e^{'}})$ , then $I_{d^{'}} \subseteq range (φ_{e^{'}})$ for all $d^{'} > d$ , and then we can use Lemma 3.2.) But this contradicts the choice of s. Claim 3.8.
For all e with $φ_{e}$ being total, for all but finitely many $d ⩾ e$ , $i_{e} (d) = 0$ implies, for all but finitely many d, $range (φ_{e}) \cap I_{d} = \emptyset$ .

To prove the claim, suppose by way of contradiction that e is such that for all but finitely many $d ⩾ e$ , $i_{e} (d) = 0$ , but for infinitely many d, $range (φ_{e}) \cap I_{d} \neq \emptyset$ . Fix least such e, and let d be such that
for all $e^{'} ⩽ e$ , for all $d^{'} ⩾ d$ , $Q_{e} (d^{'}) = Q_{e} (d)$ and

for all $e^{'} < e$ , if $i_{e^{'}} (d) = 0$ , then for all $d^{'} ⩾ d$ , $range (φ_{e^{'}}) \cap I_{d^{'}} = \emptyset$ .
Let s be such that for all $d^{'} ⩽ d$ , for all $s^{'} ⩾ s$ , $I_{d^{'}, s^{'}} = I_{d^{'}, s}$ and $Q_{d^{'}, s^{'}} (d^{'}) = Q_{d^{'}, s} (d^{'})$ . Let $E = {e^{'} : e^{'} < e, i_{e^{'}} (d) = 2} \cup {e}$ . Then, clearly, $⋂_{e^{'} \in E} range (φ_{e^{'}})$ is infinite, and thus using Lemma 3.2, for large enough $s^{'} > s$ , we can find, $a_{l_{d}, s^{'}}, \dots, a_{r_{d}, s^{'}}$ such that $i_{e^{'}, s^{'}} (d) = 2$ for $e^{'} \in E$ , which makes $Q_{d, s^{'}} (d) > Q_{d, s} (d)$ , contradicting the choice of s. The claim follows.

Note above that $r_{e} - l_{e} ⩾ Q_{e + 1} (e + 1)$ for all possible values of $Q_{e + 1} (e + 1)$ and thus $a_{r_{e} - Q_{e + 1} (e + 1)} \in I_{e}$ . Claim 3.9.
The set $A = {a_{r_{e} - Q_{e + 1} (e + 1)} : e \in N}$ is cohesive.

To prove the claim, consider any total $φ_{e}$ . If for all but finitely many $d > e$ , $i_{e} (d) = 0$ , then by Claim 3.8 $range (φ_{e})$ contains elements from only finitely many $I_{e^{'}}$ , and thus only finitely many elements of A. On the other hand, if, for all but finitely many $d > e$ , $i_{e} (d) = 2$ , then $range (φ_{e})$ contains all but finitely many $I_{e^{'}}$ , and thus all but finitely many elements of A. The claim follows. Claim 3.10.
Suppose $B ⩽_{m} A$ as witnessed by $φ_{e}$ . Then, B is a left-r.e. set.

To prove the claim, first suppose that $range (φ_{e}) \cap A$ is finite. In this case $B = {y : φ_{e} (y) \in S}$ for some finite set S. Thus, B is recursive and a left-r.e. set.

Now suppose that $range (φ_{e}) \cap A$ is infinite. It follows that, for all but finitely many $d > e$ , $i_{e} (d)$ has value 2 (by Claims 3.7 and 3.8). Let d be large enough such that $Q_{e} (d) = Q_{e} (d^{'})$ , for all $d^{'} ⩾ d$ . Consider a stage $s_{0}$ such that for all $d^{'} ⩽ d$ , for all $s ⩾ s_{0}$ , $I_{d^{'}, s} = I_{d^{'}, s_{0}}$ and $Q_{d^{'}, s} (d^{'}) = Q_{d^{'}, s_{0}} (d^{'})$ . Define $s_{k + 1} > s_{k}$ such that, for $d ⩽ d^{'} ⩽ d + k + 1$ , $Q_{e, s_{k + 1}} (d^{'}) = (j_{0}, j_{1}, \dots, j_{e})$ . Let $\begin{matrix} α (m, k) = a_{r_{m} - Q_{m + 1, s_{k}} (m + 1), s_{k}}, \end{matrix}$ and define $B_{k}$ as the characteristic function of ${y : φ_{e} (y) \in A_{s_{k}} \cap ⋃_{r < d + k} I_{r, s_{k}}}$ where $A_{s_{k}} = {α (m, k) : m < d + k}$ .

The characteristic value of $B_{k}$ as above converges to characteristic function of B. To show that B is left-r.e., we need to show that $B_{k} ⩽_{lex} B_{k + 1}$ . For this consider least $d^{'}$ such that for $m ⩽ d^{'}$ , $I_{m, s_{k + 1}} = I_{m, s_{k}}$ and $Q_{m, s_{k + 1}} (m) = Q_{m, s_{k}} (m)$ , but $\begin{matrix} [I_{d^{'} + 1, s_{k + 1}} \neq I_{d^{'} + 1, s_{k}} or Q_{d^{'} + 1, s_{k + 1}} (d^{'} + 1) \neq Q_{d^{'} + 1, s_{k}} (d^{'} + 1) or d^{'} = d + k + 1] . \end{matrix}$ Note that $d^{'} ⩾ d$ . If $d^{'} ⩾ d + k$ , then clearly $B_{k} ⩽_{lex} B_{k + 1}$ . Otherwise, for $m < d^{'}$ , we have that $α (m, k) = α (m, k + 1)$ . Also, $Q_{d^{'} + 1, s_{k}} (d^{'} + 1) < Q_{d^{'} + 1, s_{k + 1}} (d^{'} + 1)$ and $α (d^{'}, k + 1) < α (d^{'}, k)$ , which implies that $φ_{e}^{- 1} (α (d^{'}, k + 1)) < φ_{e}^{- 1} (α (d^{'}, k))$ (as $φ_{e}^{- 1}$ is monotonic on $I_{d^{'}, s_{k}}$ , due to $Q_{e, s_{k}} (d^{'}) = Q_{e, s_{k + 1}} (d^{'}) = (j_{0}, j_{1}, \dots, j_{e})$ , where $j_{e} = 2$ ). Thus, $B_{k} ⩽_{lex} B_{k + 1}$ . It follows that B is a left-r.e. set. □

Not every left-r.e. set is many–one closed left-r.e.: Besides Ω, a quite easy example can be found by taking an r.e. and non-recursive set A and considering the set $\begin{matrix} B = {2 x : x \in A} \cup {2 x + 1 : x \notin A} . \end{matrix}$ Then the complement of A is many–one reducible to B but not a left-r.e. set. In contrast to Theorem 3.3, one can also find cohesive sets with this property.
Theorem 3.11.
There is a left-r.e. cohesive set A which is not a many–one closed left-r.e. set.
Proof.
The following is a modification of the construction of cohesive/maximal set, say A, where we fix intervals, and consider the intervals to which the moving markers belong and have a high enough e-state. Then, we choose a specific marker in each of these intervals to ensure cohesiveness. The mechanism of this construction also ensures that A is left-r.e. To ensure that A is not left-r.e. closed, we consider the reduction which maps ith least element of an interval to the ith highest element of the same interval. This ensures that if the set B formed using the above reduction is left-r.e., then A would be recursive, contradicting the cohesiveness of A. We now proceed formally.

Partition $N$ into intervals $I_{i}$ of length $2^{i}$ : $I_{i} = {2^{i} - 1, 2^{i}, 2^{i} + 1, \dots, 2^{i + 1} - 2}$ . Furthermore, assign to every x the e-state given as $\begin{matrix} (3.1) & q_{e, s} (x) = \sum_{d < e} 2^{e - 1 - d} \cdot W_{d, s} (x) . \end{matrix}$ We say that $\begin{matrix} (3.2) & \begin{matrix} q_{e, s} (I_{i}) = c iff c < 2^{e} is the largest number satisfying \\ q_{e, s} (x) ⩾ c for at least 2^{i} - 2^{i - e - 1} \cdot (c + 1) elements x of I_{i} . \end{matrix} \end{matrix}$ Here we let $J_{e, i, s}$ be a witness for the above fact in the way such that $J_{e, i, s} \subseteq I_{i}$ , $| J_{e, i, s} | = 2^{i} - 2^{i - e - 1} \cdot (c + 1)$ and $q_{e, s} (x) ⩾ c$ for all $x \in J_{e, i, s}$ . We also assume that $J_{e, i, s + 1} \neq J_{e, i, s}$ implies $q_{e, s + 1} (I_{i}) > q_{e, s} (I_{i})$ . It is easy to verify that ${lim}_{s \to \infty} q_{e, s} (I_{i})$ converges for each e, i and thus, ${lim}_{s \to \infty} J_{e, i, s}$ converges for each e, i.

Define $i_{0, s}, i_{1, s}, \dots$ such that the following properties are satisfied:
for all e, s: $i_{e, s} < i_{e + 1, s}$ and $i_{e, s + 1} ⩾ i_{e, s} > 2 e + 2$ ;

for all e, s, j with $i_{e, s} ⩽ j ⩽ s$ it holds that $q_{e, s} (I_{i_{e, s}}) ⩾ q_{e, s} (I_{j})$ ;

for all s, for the least e (if any) with $i_{e, s} \neq i_{e, s + 1}$ or $J_{e, i_{e, s}, s} \neq J_{e, i_{e, s + 1}, s + 1}$ : $q_{e, s + 1} (I_{i_{e, s + 1}}) > q_{e, s} (I_{i_{e, s}})$ .
Note that such $i_{j, s}$ can be recursively defined. It is easy to verify by induction that $i_{e} = {lim}_{s \to \infty} i_{e, s}$ converges. Furthermore, note that $q_{0, s} (I_{i_{0, s}}) = 0$ for all s and $J_{0, i_{0, s}, s} = I_{i_{0, s}}$ for all s. Hence, $i_{0, s} = i_{0, 0}$ for all s. Now we are ready to define A.
Definition of $A_{s}$ :

Let $H_{e, s} = {x \in J_{e, i_{e, s}, s} : q_{e, s} (x) = q_{e, s} (I_{i_{e, s}})}$ for all e.

Let $x_{e, s}$ be the $(q_{e + 1, s} (I_{i_{e + 1, s}}) + 1) th$ element from above of $H_{e, s}$ for all e.

Let $A_{s} = {x_{0, s}, x_{1, s}, \dots}$ .

End Definition of $A_{s}$ .
Let $A (x) = {lim}_{s \to \infty} A_{s} (x)$ . One can verify that ${lim}_{s \to \infty} i_{e, s}$ , ${lim}_{s \to \infty} q_{e, s} (I_{i_{e, s}})$ and ${lim}_{s \to \infty} J_{e, i_{e, s}, s}$ converge. Thus it is easy to verify that A is well defined. We also let $i_{e}$ , $J_{e, i_{e}}$ , $H_{e}$ , $q_{e} (x)$ , $q_{e} (I_{j})$ denote the limiting values of $i_{e, s}$ , $J_{e, i_{e, s}, s}$ , $H_{e, s}$ , $q_{e, s} (x)$ , $q_{e, s} (I_{j})$ , respectively.

Here, it should be noted that $H_{e, s}$ has at least $2^{i_{e, s} - e - 1}$ elements. To see this, let $c = q_{e, s} (I_{i_{e, s}})$ and note that $J_{e, i_{e, s}, s}$ has at least $2^{i_{e, s}} - 2^{i_{e, s} - e - 1} \cdot (c + 1)$ elements of which less than $2^{i_{e, s}} - 2^{i_{e, s} - e - 1} \cdot (c + 2)$ many x satisfy $q_{e, s} (x) > c$ while all x satisfy $q_{e, s} (x) ⩾ c$ . So at least $2^{i_{e, s} - e - 1}$ elements x of $J_{e, i_{e, s}, s}$ satisfy $q_{e, s} (x) = c$ and these are in $H_{e, s}$ . As $i_{e, s} ⩾ 2 e + 2$ , it follows that $| H_{e, s} | ⩾ 2^{e + 1}$ and so there is, for each possible value $c^{'}$ of $q_{e + 1, s} (I_{i_{e + 1, s}}) < 2^{e + 1}$ , a $(c^{'} + 1) th$ largest element of $H_{e, s}$ . Thus every $x_{e, s}$ as defined above really exists. For each e, the sequence of the $x_{e, s}$ converges to some value $x_{e}$ .

To show that ${(A_{s})}_{s \in N}$ forms a left r.e. approximation, we need to show that $A_{s} ⩽_{lex} A_{s + 1}$ . So consider the least e (if any) such that $x_{e, s + 1} \neq x_{e, s}$ . Note that $i_{e, s + 1} = i_{e, s}$ and $J_{e, i_{e, s + 1}, s + 1} = J_{e, i_{e, s}, s}$ , as otherwise $e > 0$ and $x_{e - 1, s + 1} \neq x_{e - 1, s}$ . Hence $H_{e, s + 1} \subseteq H_{e, s}$ and, for $s^{'} = s, s + 1$ , $x_{e, s^{'}}$ is the $(q_{e + 1, s^{'}} (I_{i_{e + 1, s^{'}}}) + 1) th$ element of $H_{e, s^{'}}$ from above. As $i_{d, s + 1} = i_{d, s}$ and $J_{d, i_{d, s + 1}, s + 1} = J_{d, i_{d, s}, s}$ for all $d ⩽ e$ , it follows by rule (c) that $\begin{matrix} q_{e + 1, s + 1} (I_{e + 1, i_{e + 1, s + 1}, s + 1}) ⩾ q_{e + 1, s} (I_{e + 1, i_{e + 1, s}, s}) . \end{matrix}$ Hence $x_{e, s + 1} < x_{e, s}$ and that implies that $A_{s + 1} >_{lex} A_{s}$ . So A is a left-r.e. set.

Now we show that A is cohesive. So consider any d, e, k such that $d < e$ and $k ⩾ 0$ . Then, we claim that $q_{d + 1} (x_{e}) ⩾ q_{d + 1} (x_{e + k})$ . To see this, write $q_{e + k}$ using $e + k$ bits (including potentially some leading zeros), and let c be the leading e bits of this representation so that $2^{k} c ⩽ q_{e + k} (I_{i_{e + k}}) ⩽ 2^{k} c + 2^{k} - 1$ . Then by (3.2) at least $\begin{matrix} 2^{i_{e + k}} - 2^{i_{e + k} - e - k - 1} \cdot (2^{k} \cdot c + 2^{k}) = 2^{i_{e + k}} - 2^{i_{e + k} - e - 1} (c + 1) \end{matrix}$ many x in $I_{i_{e + k}}$ have $q_{e + k} (x) ⩾ 2^{k} c$ . It follows from (3.1) that at least this same number of $x \in I_{i_{e + k}}$ satisfy $q_{e} (x) ⩾ c$ , and thus $q_{e} (I_{i_{e}}) ⩾ q_{e} (I_{i_{e + k}}) ⩾ c$ . Now, for $x_{e + k} \in H_{e + k}$ and $x_{e} \in H_{e}$ , $\begin{matrix} q_{d + 1} (x_{e + k}) = ⌊ \frac{q_{e + k} (I_{i_{e + k}})}{2^{k + e - d - 1}} ⌋ < \frac{(c + 1) 2^{k}}{2^{k + e - d - 1}}, \end{matrix}$ and since c is an integer, it follows from the strict inequality above that $q_{d + 1} (x_{e + k}) ⩽ c / 2^{e - d - 1}$ . On the other hand, $q_{d + 1} (x_{e}) = ⌊ q_{e} (I_{i_{e}}) / 2^{e - d - 1} ⌋ ⩾ ⌊ c / 2^{e - d - 1} ⌋$ . Thus, $q_{d + 1} (x_{e + k}) ⩽ q_{d + 1} (x_{e})$ . As $A = {x_{0}, x_{1}, \dots}$ , for all d, $q_{d + 1} (x_{e})$ is same for all but finitely many e. For each d it follows that $W_{d} (x_{e})$ is the same value for all but finitely many e. Thus A is cohesive.

Now consider $B ⩽_{m} A$ via f where, for all i and $x \in I_{i}$ , $f (x) = max (I_{i}) + min (I_{i}) - x$ . Note that $f (x) = f^{- 1} (x)$ . Thus, f also witnesses $A ⩽_{m} B$ . Let ${(A_{s})}_{s \in N}$ be the left-r.e. approximation of A as given above and ${(B_{s})}_{s \in N}$ be a left-r.e. approximation of B. Then, the following holds for all e, s:
If the least $e + 1$ elements $x_{0, s}, x_{1, s}, \dots, x_{e, s}$ of $A_{s}$ satisfy that $f (x_{0, s}), f (x_{1, s}), \dots, f (x_{e, s})$ are the unique elements of $B_{s}$ below $max (I_{i_{e, s}})$ then $x_{0} = x_{0, s}, x_{1} = x_{1, s}, \dots, x_{e} = x_{e, s}$ .
For a proof, assume that the above would be false for some e, s and let d be the least index such that $x_{d} \neq x_{d, s}$ ; as the approximation is a left-r.e. one, $x_{d} < x_{d, s}$ . Furthermore, by (c), $i_{d, s} = i_{d}$ as otherwise $d > 0$ and $x_{d - 1} \neq x_{d - 1, s}$ . So $f (x_{d, s}) < f (x_{d})$ and $\begin{matrix} B \cap {0, 1, \dots, max (I_{i_{d}})} = {f (x_{0}), f (x_{1}), \dots, f (x_{d})} <_{lex} {f (x_{0, s}), f (x_{1, s}), \dots, f (x_{d, s})} \end{matrix}$ and hence $B <_{lex} B_{s}$ , a contradiction to ${(B_{s})}_{s \in N}$ being a left-r.e. approximation of B. So $()$ is true. Now one can determine $x_{e}$ by searching for the first stage s where $f (x_{0, s}), f (x_{1, s}), \dots, f (x_{e, s})$ are the unique elements of B below $max (I_{i_{e, s}})$ and then one knows that $x_{e} = x_{e, s}$ . Therefore, we get that A is recursive, in contradiction to A being cohesive. □

Recall from Definition 2.1 that an ascending reduction is a recursive function f which satisfies $f (x) ⩽ f (x + 1)$ for all x; $B ⩽_{asc} A$ iff there is an ascending reduction f with $B (x) = A (f (x))$ for all x. Furthermore, recall from Definition 2.2 that A is called ascending closed left-r.e. iff every $B ⩽_{asc} A$ is a left-r.e. set.

The next result shows that every r-cohesive left-r.e. set is an ascending closed left-r.e. set. Thus, r-cohesive left-r.e. sets form a subclass of ascending closed left-r.e. sets. Recall that every cohesive set is r-cohesive.
Theorem 3.12.
Every left-r.e. r-cohesive set is an ascending closed left-r.e. set.*
Proof.
Suppose A is a left-r.e. r-cohesive set. Suppose $B ⩽_{asc} A$ . Let ${(A_{s})}_{s \in N}$ be the left-r.e. approximation of A, and let f be a non-decreasing recursive function which witnesses that $B ⩽_{asc} A$ . If $range (f) \cap A$ is finite, then clearly B is recursive. So assume $range (f) \cap A$ is infinite. But then, for some x and for all $y ⩾ x$ , $y \in A$ implies $y \in range (f)$ because A is r-cohesive. Fix this x.

Let $s_{0}$ be such that for all $s ⩾ s_{0}$ , for all $y ⩽ x$ , $A_{s} (y) = A (y)$ ; let $s_{n + 1} > s_{n}$ be such that the least $n + 1$ members of $A_{s_{n + 1}} - {y : y ⩽ x}$ exist and are in $range (f)$ ; note that one can effectively find such $s_{n + 1}$ from $s_{n}$ . Let $\begin{matrix} B_{n} (y) = \{\begin{matrix} A (f (y)), & if f (y) ⩽ x, \\ 1, & if f (y) is among the least n members of A_{s_{n}} which are greater than x, \\ 0, & otherwise . \end{matrix} \end{matrix}$ It is easy to verify that $B_{n}$ is an approximation of B. To see that ${(B_{n})}_{n \in N}$ forms a left-r.e. approximation, we need to show that $B_{n} ⩽_{lex} B_{n + 1}$ for all n. So consider any n. If $B_{n} ⊈ B_{n + 1}$ , then there exists least y such that $y \in B_{n} - B_{n + 1}$ . Then $f (y)$ is among the first n members of $A_{s_{n}}$ which are greater than x and not among the first $n + 1$ members of $A_{s_{n + 1}}$ which are greater than x. As ${(A_{s})}_{s \in N}$ is a left-r.e. approximation, we have that $A_{s_{n + 1}}$ must contain an $f (y^{'})$ , $x < f (y^{'}) < f (y)$ , such that $f (y^{'}) \notin A_{s_{n}}$ . But then $y^{″} \in B_{n + 1} - B_{n}$ for some $y^{″} ⩽ y^{'}$ . Thus, ${(B_{n})}_{n \in N}$ is a left-r.e. approximation of B. □

The next result provides a natural way to construct many–one closed left-r.e. sets via maximal sets. Recall that a set is maximal iff it is r.e. and its complement is cohesive. This construction generalises a method of Stephan and Teutsch [18, Theorem 6.5].
Theorem 3.13.
Assume A is a maximal set with complement in ascending order $a_{0}, a_{1}, \dots$ and that B is a left-r.e. set. Let $\begin{matrix} E (x) = \{\begin{matrix} 1, & if x \in A, \\ B (n), & if x = a_{n} . \end{matrix} \end{matrix}$ Then, E is many–one closed left-r.e. set.
Proof.
Suppose that a recursive function f many–one reduces some set F to E and assume for a contradiction that F is not a left-r.e. set. If $\overline{A} \cap range (f)$ is finite, then clearly F is recursive. So assume $\overline{A} \cap range (f)$ is infinite. Then, all but finitely many elements of $\overline{A}$ are in $range (f)$ because $\overline{A}$ is cohesive. Without loss of generality we assume $\overline{A} \subseteq range (f)$ and that f is one–one.

The condition $\overline{A} \subseteq range (f)$ can be assumed because one can make a finite modification of F and f in order to satisfy this and when the modified F is left-r.e. so is the original one. To see that f can be taken to be one–one, define g inductively by $g (x) = f (y)$ for the minimal y with $f (y) \notin {g (z) : z < x}$ and note that g is recursive. Now let $\begin{matrix} G = {x : g (x) \in A} \cup {x : g (x) = a_{n} and n \in B} . \end{matrix}$ It is easy to see that G and F are many–one equivalent and that a left-r.e. enumeration ${(G_{s})}_{s \in N}$ of G can be translated into a left-r.e. enumeration of F by letting $F_{s} = {x : \exists y \in G_{s} [f (x) = g (y)]}$ . Thus if F is not left-r.e. then also G cannot be a left-r.e. set. Hence, we could just replace F by G in the proof and consider the one–one reduction g in place of f.

Now, for all but finitely many n, $f^{- 1} (a_{n}) < f^{- 1} (a_{n + 1})$ . This holds as otherwise the r.e. set ${x : x \in A or \forall n < f^{- 1} (x) [f (n) < x or f (n) \in A]}$ will both contain infinitely many elements of $\overline{A}$ and miss out infinitely many elements of $\overline{A}$ , contradicting cohesiveness of $\overline{A}$ . As left-r.e. sets are closed under finite variants and shifts by constantly many positions (with the elements in the front being skipped or inserted), one can without loss of generality assume that f is taken such that $\forall n$ $[f^{- 1} (a_{n}) < f^{- 1} (a_{n + 1})]$ .

Let ${(B_{s})}_{s \in N}$ be a left-r.e. approximation of B. Let ${(A_{s})}_{s \in N}$ be a recursive approximation of A such that $A_{s} \subseteq A_{s + 1}$ . Now, let ${\hat{E}}_{s} = A_{t_{s}} \cup {a_{n, t_{s}} : n ⩽ s and B_{t_{s}} (n) = 1}$ , where $a_{n, r}$ is the nth non-element of $A_{r}$ and $t_{s}$ is the least number strictly above s such that $f^{- 1} (a_{0, t_{s}}) < f^{- 1} (a_{1, t_{s}}) < \dots < f^{- 1} (a_{s, t_{s}})$ and $f (x) \in A_{t_{s}} \cup {a_{0, t_{s}}, a_{1, t_{s}}, \dots, a_{s, t_{s}}}$ for all $x ⩽ f^{- 1} (a_{s, t_{s}})$ . Let $F_{s} = {x ⩽ f^{- 1} (a_{s, t_{s}}) : f (x) \in {\hat{E}}_{s}}$ . It follows from the construction that for all m, n with $m ⩽ n ⩽ s$ that $f^{- 1} (a_{m, t_{s}}) ⩽ f^{- 1} (a_{n, t_{s + 1}})$ . By the assumption on B, $\begin{array}{l} (F (f^{- 1} (a_{0, t_{s}})), F (f^{- 1} (a_{1, t_{s}})), \dots, F (f^{- 1} (a_{s, t_{s}}))) \\ = (B_{t_{s}} (0), B_{t_{s}} (1), \dots, B_{t_{s}} (s)) \\ ⩽_{lex} (B_{t_{s + 1}} (0), B_{t_{s + 1}} (1), \dots, B_{t_{s + 1}} (s), B_{t_{s + 1}} (s + 1)) \\ = (F (f^{- 1} (a_{0, t_{s + 1}})), F (f^{- 1} (a_{1, t_{s + 1}})), \dots, F (f^{- 1} (a_{s, t_{s + 1}})), F (f^{- 1} (a_{s + 1, t_{s + 1}}))) . \end{array}$ Now the characteristic functions of $F_{s}$ is $\begin{matrix} 1^{f^{- 1} (a_{0, t_{s}})} B_{t_{s}} (0) 1^{f^{- 1} (a_{1, t_{s}}) - f^{- 1} (a_{0, t_{s}}) - 1} B_{t_{s}} (1) 1^{f^{- 1} (a_{2, t_{s}}) - f^{- 1} (a_{1, t_{s}}) - 1} B_{t_{s}} (2) \dots B_{t_{s}} (s) 0^{\infty} \end{matrix}$ and for $F_{s + 1}$ accordingly. One can see that, for each m, s with $m ⩽ s$ , the position of $B_{t_{s}} (m)$ in the characteristic function of $F_{s}$ is at $f^{- 1} (a_{m, t_{s}})$ and this position moves only upwards or stays the same when going from stage s to $s + 1$ ; together with the fact that $B_{s}$ is a left-r.e. enumeration of B, this also implies (in contradiction to the assumption above), F is a left-r.e. set as witnessed by the approximations $F_{s}$ . □

Similarly, one can construct ascending closed left-r.e. supersets of r-maximal sets. Theorem 3.14.
Assume A is an r-maximal set with complement $a_{0}, a_{1}, \dots$ and that B is a left-r.e. set. Let $\begin{matrix} E (x) = \{\begin{matrix} 1, & if x \in A, \\ B (n), & if x = a_{n} . \end{matrix} \end{matrix}$ Then, E is an ascending closed left-r.e. set; furthermore, for certain choices of A and B, E is not a many–one closed left-r.e. set.
Proof.
The proof that the set E is ascending closed is similar to the proof in Theorem 3.13. Now it is shown that there exist an r-maximal set A and a left-r.e. set B, such that the corresponding set E is not a many–one closed left-r.e. set. First one splits the natural numbers into intervals $I_{0}, I_{1}, \dots$ with each $I_{e}$ having length $2^{min (I_{e}) + 5 e + 5}$ and one defines an r.e. set $\tilde{A}$ , with approximation ${\tilde{A}}_{s}$ from below, such that whenever a function $φ_{d}$ with $d ⩽ e$ gets defined on all $x \in I_{e} - {\tilde{A}}_{s}$ , then at most half of these x are enumerated into ${\tilde{A}}_{s + 1}$ – in a way so that either all members $x \in I_{e} - {\tilde{A}}_{s + 1}$ satisfy $φ_{d} (x) > 0$ or all satisfy $φ_{d} (x) = 0$ . The e-state of $I_{e}$ is the sum of all $3^{- d - 1}$ over all $d ⩽ e + 1$ where $φ_{d}$ is 0 on $I_{e} - \tilde{A}$ plus the sum of all $2 \cdot 3^{- d - 1}$ over all $d ⩽ e + 1$ where $φ_{d}$ is positive on $I_{e} - \tilde{A}$ .

Furthermore, let $\hat{A}$ be a maximal set and now let A be the union of $\tilde{A}$ and all $I_{e}$ with $e \in \hat{A}$ . The set A is r-maximal: For each rational q, either all but finitely many $e \notin \hat{A}$ satisfy that the e-state of $I_{e}$ is above q or all but finitely many $e \notin \hat{A}$ satisfy that the e-state of $I_{e}$ is below q. Therefore, one can conclude for all recursive sets R that either $I_{e} - \tilde{A} \subseteq R$ for all but finitely many $e \notin \hat{A}$ or $I_{e} - \tilde{A} \subseteq N - R$ for all but finitely many $e \notin \hat{A}$ .

For each e, let $g (e)$ be the minimum number $x ⩾ min (I_{e})$ such that $C (x) ⩾ min (I_{e}) + 2 e$ and let B contain all natural numbers except those $g (e)$ where $e \notin \hat{A}$ . One can approximate the values of each $g (e)$ from below starting with $min (I_{e})$ , and $g (e) = {lim}_{s} g_{s} (e)$ is at most $2^{min (I_{e}) + 2 e} + min (I_{e})$ . Note when the approximation of $g (e)$ increases then its old position is enumerated into B while the new one is removed from B; furthermore, when e is enumerated into $\hat{A}$ then the current position of $g (e)$ is enumerated into B without taking anything out. Hence B is a left-r.e. set and E is therefore also a left-r.e. set.

Now let $\tilde{E}$ be obtained from E by inverting the order on all intervals $I_{e}$ , that is, for each e and each x with $min (I_{e}) + x \in I_{e}$ , it holds that $\tilde{E} (min (I_{e}) + x) = E (max (I_{e}) - x)$ . Furthermore, $I_{e} \subseteq E$ iff $I_{e} \subseteq \tilde{E}$ iff $e \in \hat{A}$ ; for $e \notin \hat{A}$ , it holds that at least $| I_{e} | / 2^{e + 1}$ many elements of $I_{e}$ are not enumerated into A and therefore all n with $n ⩾ min (I_{e})$ and $n ⩽ | I_{e} | / 2^{e + 1}$ satisfy $a_{n} \in I_{e}$ . All of these $a_{n}$ except $a_{g (e)}$ will be members of E; for this note that $2^{min (I_{e})} ⩽ g (e) ⩽ 2^{min (I_{e}) + 2 e} ⩽ | I_{e} | / 2^{e + 1}$ and thus $a_{g (e)} \in I_{e}$ .

Assume now by way of contradiction that not only E but also $\tilde{E}$ are left-r.e. sets. If one knows for some bound b, at how many stages t an element below $e ⩽ b$ is enumerated into $\hat{A}$ or a e-state of an interval $I_{e}$ with $e ⩽ b$ changes then one can compute the non-elements $a_{0}, a_{1}, \dots, a_{n}$ of A up to the largest $a_{n} ⩽ max (I_{b})$ , hence one knows for all $m ⩽ n$ the corresponding $a_{m}$ and that $B (m) = E (a_{m})$ . Note that $t ⩽ b$ and the number of times e-state of an interval $I_{e}$ with $e ⩽ b$ changes is bounded by $b^{2}$ . Thus, the needed information (number of such stages t and b) can be described with roughly $4 \cdot log (b)$ bits. Furthermore, knowing E below $min (I_{b})$ (what can be described by $min (I_{b})$ bits), one can then wait for a stage s such that $A_{s}$ equals A below $max (I_{b})$ , that $E_{s}$ and ${\tilde{E}}_{s}$ are equal to E and $\tilde{E}$ , respectively, below $min (I_{b})$ and that there is a unique value $min (I_{e}) + x \in I_{e}$ not in $E_{s}$ such that $max (I_{e}) - x$ is the unique value of $I_{e}$ not in ${\tilde{E}}_{s}$ . This value must be $a_{g (b)}$ and hence one could compute $g (b)$ from $4 \cdot log (b) + min (I_{b})$ bits of information (up to some additive constant) though $C (g (b)) ⩾ min (I_{b}) + 2 b$ , a contradiction for sufficiently large $b \notin \hat{A}$ . Hence the assumption of $\tilde{E}$ being left-r.e. is false and E is not a many–one closed left-r.e. set. □

4. Weakly 1-generic sets

Another important type of sets are the 1-generic and weakly 1-generic sets [11,12]. As one cannot have left-r.e. 1-generic sets [12, p. 662], one might ask for which reducibilities r there are r-closed left-r.e. weakly 1-generic sets. The next result shows that one can make such sets for the notion of ascending closed left-r.e. sets.

Recall that a set is weakly 1-generic iff for every recursive function f from numbers to strings there exist n and m with $f (n) = A (n + 1) A (n + 2) \dots A (n + m)$ . The difference between weakly 1-generic and 1-generic is that here one requires the f to be total and independent of the values of A below n.

Theorem 4.1.
There is an ascending closed left-r.e. weakly 1-generic set A.
Proof.
Let str be a one–one recursive bijection from $N$ to strings over ${0, 1}$ . We will be defining moving markers $a_{e}$ , $b_{e}$ and $c_{e}$ , where $a_{e} ⩽ b_{e} ⩽ c_{e}$ , $a_{0} = 0$ and $a_{e + 1} = c_{e} + 1$ . Intuitively, we want to use the part $A (b_{e}), A (b_{e} + 1), \dots, A (c_{e})$ to ensure weak 1-genericity (by making $A (b_{e}) A (b_{e} + 1) \dots A (b_{e} + | str (φ_{e} (b_{e})) | - 1) = str (φ_{e} (b_{e}))$ , if $φ_{e} (b_{e})$ is defined). The part $A (a_{e}), \dots, A (b_{e} - 1)$ is used to ensure that A is an ascending closed left-r.e. set.

At the beginning of stage s, the markers have values $a_{e, s}$ , $b_{e, s}$ and $c_{e, s}$ respectively. We will have that $a_{e} = {lim}_{s \to \infty} a_{e, s}$ , $b_{e} = {lim}_{s \to \infty} b_{e, s}$ , $c_{e} = {lim}_{s \to \infty} c_{e, s}$ . Let $a_{0, s} = 0$ for all s. Let $a_{e + 1, s} = c_{e, s} + 1$ , for all e, s. Initially $a_{e, 0} = b_{e, 0} = c_{e, 0} = e$ , and $A_{0} (x) = 0$ , for all x. We will also use sets $J_{e^{'}, e, s}$ , for $e^{'} < e$ . These sets are useful for defining A in such a way that, if $φ_{e^{'}}$ witnesses an ascending reduction from B to A, then B is a left-r.e. set. Initially, for all e, for $e^{'} < e$ , $J_{e^{'}, e, 0} = \emptyset$ . Below, for ease of presentation, we will only describe the changes from stage s to stage $s + 1$ ; all variables which are not explicitly updated will retain the corresponding values from stage s. Go to stage 0.
Stage s:

If there exists an $e ⩽ s$ such that either Cond $e .1$ or Cond $e .2$ below hold, then choose least such e and go to step (2). Otherwise go to stage $s + 1$ . $\begin{array}{l} Cond e .1 : There exists e^{'} < e such that, J_{e^{'}, e, s} = \emptyset and range (φ_{e^{'}}) \cap {x : x > c_{e, s}} \\ contains at least 2 e + 2 elements as can be verified within s steps . \\ Cond e .2 : c_{e, s} = b_{e, s} and φ_{e} (b_{e, s}) ↓ within s steps . \end{array}$

Fix the least e such that Cond $e .1$ or Cond $e .2$ holds. If Cond $e .1$ holds, then go to step (3). Otherwise go to step (4).

Fix one $e^{'}$ such that Cond $e .1$ holds for $e^{'}$ .

Let $J_{e^{'}, e, s + 1}$ be $2 e + 2$ elements from $range (φ_{e^{'}}) \cap {x : x > c_{e, s}}$ .

Update $b_{e, s + 1} = max (J_{e^{'}, e, s + 1}) + 1$ , $c_{e, s + 1} = b_{e, s + 1}$ .

For $m > e$ , let $a_{m, s + 1} = b_{m, s + 1} = c_{m, s + 1} = c_{m - 1, s + 1} + 1$ .

For $m > e$ , and $m^{'} < m$ , let $J_{m^{'}, m, s + 1} = \emptyset$ .

Let $A_{s + 1}$ be obtained from $A_{s}$ by doing the following:
deleting all elements $⩾ b_{e, s}$ and

inserting, for each $m < e$ such that $J_{m, e, s} \neq \emptyset$ , one new element (which was not earlier in $A_{s}$ ) from $J_{m, e, s}$ .
Go to Stage $s + 1$ .

Suppose $str (φ_{e} (b_{e, s})) = y$ .

Let $c_{e, s + 1} = b_{e, s} + | y | + 1$ .

For $m > e$ , let $a_{m, s + 1} = b_{m, s + 1} = c_{m, s + 1} = c_{m - 1, s + 1} + 1$ .

For $m > e$ , and $m^{'} < m$ , let $J_{m^{'}, m, s + 1} = \emptyset$ .

Let $A_{s + 1}$ be obtained from $A_{s}$ by doing the following:
deleting all elements $⩾ b_{e, s} + | y | + 1$ and

inserting, for each $m < e$ such that $J_{m, e, s} \neq \emptyset$ , one new element (which was not earlier in $A_{s}$ ) from $J_{m, e, s}$ and

setting $A_{s + 1} (b_{e, s}) \dots A_{s + 1} (b_{e, s} + | y | - 1) = y$ .
Go to Stage $s + 1$ .

End Stage s.
It can be shown by induction on e that ${lim}_{s \to \infty} a_{e, s}$ , ${lim}_{s \to \infty} b_{e, s}$ , ${lim}_{s \to \infty} c_{e, s}$ indeed exist. For this, for $e^{'} < e$ , after $a_{e^{'}}$ , $b_{e^{'}}$ and $c_{e^{'}}$ have reached their final value, $a_{e}$ does not get modified any further ( $a_{e}$ is set to $c_{e - 1} + 1$ , in the last stage in which $c_{e - 1}$ gets modified). Furthermore, once $a_{e}$ reaches its final value, $b_{e}$ can change at most e times due to Cond $e .1$ holding for some $e^{'} < e$ (and thus execution of step (3)). Once $b_{e}$ reaches its final value, $c_{e}$ gets modified at most once due to success of Cond $e .2$ (and thus execution of step (4)). The “ $2 e + 2$ ” in the algorithm description suffices since each index e has e indices below it, and, after all variables $a_{e^{'}}$ , $b_{e^{'}}$ , $c_{e^{'}}$ , with $e^{'} < e$ have stabilised, we encounter Cond $e .1$ at most once for each $e^{'} < e$ , and correspondingly Cond $e .2$ once in the beginning, and at most once after each modification of $b_{e}$ via Cond $e .1$ . Also, note that, for $m < e$ , $J_{m, e, s} \subseteq {x : a_{e, s} ⩽ x < b_{e, s}}$ .

Let $A (x) = {lim}_{s \to \infty} A_{s} (x)$ . Now we show that A is weakly 1-generic. Suppose s is least such that $a_{e^{'}}$ , $b_{e^{'}}$ , $c_{e^{'}}$ , for $e^{'} < e$ , and $a_{e}$ , $b_{e}$ reach their final values by stage s. If $φ_{e} (b_{e})$ is defined then Cond $e .2$ succeeds in some stage $s^{'} ⩾ s$ , and step (4) defines $A_{s^{'} + 1} (b_{e}) \dots A_{s^{'} + 1} (b_{e} + | y | - 1) = y$ , where $str (φ_{e} (b_{e})) = y$ . Furthermore, A never gets modified on inputs between $b_{e} = b_{e, s} = b_{e, s^{'} + 1}$ and $c_{e, s^{'} + 1} = c_{e}$ after stage $s^{'}$ .

Now suppose $B ⩽_{asc} A$ as witnessed by $φ_{r}$ . If $range (φ_{r})$ is finite, then clearly B is recursive. So assume $range (φ_{r})$ is infinite. Thus, for each $e > r$ , Cond $e .1$ will succeed (eventually) for $e^{'} = r$ , after $a_{e}$ has achieved its final value. Define $s_{0}$ such that $a_{m}$ , $b_{m}$ , $c_{m}$ (for $m ⩽ r$ ) as well as $A (0), A (1), \dots, A (c_{r})$ have reached their final values before stage $s_{0}$ . Let $s_{k + 1} > s_{k}$ such that $J_{r, r + j, s_{k + 1}} \neq \emptyset$ , for all $j ⩽ k + 1$ . Let $B_{k} = {x : φ_{r} (x) \in A_{s_{k}} and φ_{r} (x) ⩽ c_{r + k, s_{k}}}$ . Clearly $B (x) = {lim}_{k \to \infty} B_{k} (x)$ . Thus, to show that B is left-r.e. it suffices to show that $B_{k} ⩽_{lex} B_{k + 1}$ . So consider the least $x ⩽ c_{r + k, s_{k}}$ , if any, such that in some least stage $s^{'}$ , $s_{k} ⩽ s^{'} < s_{k + 1}$ , Cond $e .1$ or Cond $e .2$ succeeds, and $x ⩾ b_{e, s^{'}}$ (if there is no such x, then we are done). Clearly, $e > r$ by hypothesis on $s_{0}$ . Note that for $j ⩽ k$ , $J_{r, r + j, s_{k}} \neq \emptyset$ . Thus, $J_{r, e, s^{'}} \neq \emptyset$ . Thus, in stage $s^{'}$ , $A_{s^{'} + 1} (x^{'})$ is set to 1, for some $x^{'} \in J_{r, e, s^{'}}$ such that $A_{s_{k}} (x^{'}) = 0$ . Note that $x^{'} < b_{e, s^{'}} ⩽ x$ . Let $y^{'}$ be least such that $φ_{r} (y^{'}) = x^{'}$ . Thus, $\begin{matrix} B_{k} ⩽_{lex} A_{s^{'} + 1} (φ_{r} (0)) A_{s^{'} + 1} (φ_{r} (1)) \dots A_{s^{'} + 1} (φ_{r} (y^{'})) ⩽_{lex} B_{k + 1} \end{matrix}$ as desired. □
Remark 4.2.
One can adjust the proof of Theorem 4.1 to show that there is a many–one closed left-r.e. and weakly 1-generic set. To build this set, we modify Cond $e .1$ in the construction in the proof of Theorem 4.1 above as follows: $\begin{array}{l} Cond e .1 : There exists e^{'} < e such that J_{e^{'}, e, s} = \emptyset, and for some z, z^{'}, for all x ⩽ z, φ_{e^{'}} (x) ↓ ⩽ z^{'} \\ within s steps, and {φ_{e^{'}} (x) : x ⩽ z} \cap {x : c_{e, s} < x ⩽ z^{'}} contains at least 2 e + 2 elements . \end{array}$ Then setting $J_{e^{'}, e, s + 1}$ as in step (3) and making $b_{e}$ to be $> z^{'}$ , we achieve the goal as any element in A which is larger than $z^{'}$ would be able to influence membership in $B = {x^{'} : φ (x^{'}) \in A}$ , only for $x > z$ . We omit the details.

5. Initial segment complexity

Let $A [n]$ denote the string $A (0) A (1) \dots A (n)$ . Recall that $C (x)$ denotes the plain Kolmogorov complexity for x. That is, $C (x) = min {log (y) : U (y) = x}$ , where U is a fixed universal Turing machine. The function mapping n to $C (A [n])$ is called the initial segment complexity of A and the next result shows that the initial segment complexity of ascending closed left-r.e. sets is sublinear.

Proposition 5.1.
If A is an ascending closed left-r.e. set then the initial segment complexity $n \mapsto C (A [n])$ is a function of sublinear order.
Proof.
Let c be any constant, and let $G_{n}$ denote the interval ${x : x ⩽ ⌈ n / c ⌉}$ . For $d < c$ , define $B^{d}$ by $B^{d} (x) = A (c x + d)$ . Thus $B^{d} ⩽_{asc} A$ . Let ${(B_{s}^{d})}_{s \in N}$ be left-r.e. approximations of $B^{d}$ . For each n, let $d_{n} < c$ be the index for which ${(B_{s}^{d_{n}} \cap G_{n})}_{s \in N}$ converges slowest. Then given $d_{n}$ and $B^{d_{n}} \cap G_{n}$ , we can determine $B^{d} \cap G_{n}$ for each $d < c$ and therefore $A [n]$ as well. Hence, for some constant $b_{c}$ and for all n, $C (A [n]) ⩽ n / c + b_{c}$ . This shows that the complexity function $n \mapsto C (A [n])$ has sublinear order. □
Theorem 5.2.
Let g be a recursive and unbounded non-decreasing function with $g (0) = 1$ . Then there is an ascending closed left-r.e. set A such that $n \mapsto C (A [n])$ takes at least the value $n / g (n)$ , for all but finitely many n.
Proof.
Note that it suffices to show that $C (A [n]) ⩾ c \cdot n / g (n)$ , for all but finitely many n, for some constant $c > 0$ , as one could replace $g (n)$ by $\sqrt{g (n)}$ in the proof to get the result claimed in the theorem (since, for all constant $c^{'} > 0$ , for all but finitely many n, $g (n) ⩾ \sqrt{g (n)} / c^{'}$ ).

Without loss of generality assume $1 ⩽ g (i) ⩽ i$ , for $i ⩾ 1$ . Partition $N$ into intervals $I_{i}$ of length $2^{i}$ : $I_{i} = {2^{i} - 1, 2^{i}, 2^{i} + 1, \dots, 2^{i + 1} - 2}$ . For each $I_{i}$ , we will construct a subset $J_{i} = {lim}_{s \to \infty} J_{i, s}$ . Let $J_{i, 0} = I_{i}$ . At stage s, if there is an $e < log (g (i)) - 1$ (which has not been handled earlier) and an x such that $\begin{matrix} φ_{e} (0) ↓ ⩽ φ_{e} (1) ↓ ⩽ φ_{e} (2) ↓ ⩽ \dots ⩽ φ_{e} (x) ↓ and φ_{e} (x) > max (I_{i}) . \end{matrix}$ Then, choose one such e and the corresponding x. Determine the two subsets $J_{i, s} \cap {φ_{e} (y) : y ⩽ x}$ and $J_{i, s} - {φ_{e} (y) : y ⩽ x}$ , and let $J_{i, s + 1}$ be that one of these two subsets which has the higher cardinality (in case of tie, choose arbitrarily). Note that during the approximation process $J_{i, s}$ gets halved at most $log (g (i)) - 1$ times and therefore the limit $J_{i}$ has at least $2^{i} / g (i)$ many elements.

Define A so that the characteristic function of A on the set $J_{i}$ , in ascending order, is the binary representation of the least number $a_{i}$ with $C (a_{i}) ⩾ 2^{i} / g (i) - 2$ (where as many leading zeros are added as needed to use up all bits of $J_{i}$ ); A has no elements outside the sets $J_{i}$ . Note that there is a recursive approximation $a_{i, s}$ to $a_{i}$ from below.

The set A is left-r.e. as we can have an approximation $A_{s}$ which takes on each $J_{i, s}$ the characteristic function of the binary representation of $a_{i, s}$ (with sufficiently many leading zeros added in); $A_{s}$ is 0 on $I_{i} - J_{i, s}$ . If the interval $J_{i, s}$ shrinks to $J_{i, s + 1}$ , then the bits of $a_{i, s}$ move to the left and some leading zeros are skipped; if $a_{i, s + 1} > a_{i, s}$ then the bits are also ascending in lexicographic manner. Hence the resulting approximation is a left-r.e. approximation which runs independently on each interval $I_{i}$ .

Now suppose $B ⩽_{asc} A$ via a recursive non-decreasing function $φ_{e}$ . If the range of $φ_{e}$ is finite, then B is clearly recursive. Now suppose that range of $φ_{e}$ is infinite. Let r be the greatest index satisfying $log (g (r)) - 1 ⩽ e$ . Let $s_{0} = s_{1} = s_{2} = \dots = s_{r}$ be so large that $A_{s_{0}} (x) = A (x)$ for all $x ⩽ max (I_{r})$ . For $k ⩾ r$ , let $s_{k + 1} > s_{k}$ be such that for all $s ⩾ s_{k + 1}$ either $J_{k + 1, s} \subseteq range (φ_{e})$ or $J_{k + 1, s} \cap range (φ_{e}) = \emptyset$ . Note that $s_{k + 1}$ can be computed effectively from k.

We define the approximation ${(B_{k})}_{k \in N}$ of B as $\begin{matrix} B_{k} (x) = \{\begin{matrix} A_{s_{k}} (φ_{e} (x)), & if φ_{e} (x) ⩽ max (I_{k}), \\ 0, & if φ_{e} (x) > max (I_{k}) . \end{matrix} \end{matrix}$ This approximation is a left-r.e. approximation to B as it starts to consider the interval $I_{k}$ , for $k > r$ , only after stage $s_{k}$ such that for all $s ⩾ s_{k}$ , $J_{k, s} \subseteq range (φ_{e})$ or $J_{k, s} \cap range (φ_{e}) = \emptyset$ . In the first case all the bits of $J_{k, s_{k}}$ are copied order-preservingly into $B_{k}$ and the left-r.e. approximation to A on $I_{k}$ is turned into a left-r.e. approximation to B on the preimage of $I_{k}$ under $φ_{e}$ ; in the second case all x with $φ_{e} (x) \in I_{k}$ satisfy $φ_{e} (x) \notin J_{k, s_{k}}$ and therefore $B_{s} (x) = 0$ for these x and all stages s. So A is an ascending closed left-r.e. set.

Furthermore, $C (a_{i}) ⩾ 2^{i} / g (i) - 2$ . Also, we can compute $a_{i}$ from the number i, the string $A [max (I_{i})]$ and the number of stages s at which $J_{i, s + 1} \neq J_{i, s}$ . Hence, for some b and all but finitely many i we have $\begin{matrix} C (A [max (I_{i})]) ⩾ C (a_{i}) - 2 log i - 2 log g (i) - b ⩾ \frac{2^{i}}{2 g (i)} . \end{matrix}$ Now for all sufficiently large n with $min (I_{i + 1}) ⩽ n ⩽ max (I_{i + 1}) = 2^{i + 2} - 2$ , we have $2^{i} ⩾ n / 4$ and $C (A [max (I_{i})]) ⩽ C (A [n]) + 2 log i + O (1)$ . Thus we obtain from the calculation above that $C (A [n]) ⩾ n / (9 g (log n))$ for all but finitely many n. Since g is non-decreasing, this proves the postulated bound. □

Theorem 5.3 below considers $C (A [n])$ for many–one closed left-r.e. sets. On one hand it generalizes Theorem 5.2 to consider many–one reductions rather than just ascending reductions. On the other hand, it is weaker in the sense that the bound holds only for infinitely many n. It is an open question whether “infinitely many” in Theorem 5.3 can be replaced with “all but finitely many”.
Theorem 5.3.
Let $g^{'}$ be a recursive and unbounded non-decreasing function with $g^{'} (0) = 1$ . Then there is a many–one closed left-r.e. set A such that $n \mapsto C (A [n])$ takes at least the value $n / g^{'} (n)$ for infinitely many n.
Proof.
We will construct intervals $I_{e} = {r_{e}, r_{e} + 1, \dots, 2 \cdot r_{e}}$ , where $2 \cdot r_{e} < r_{e + 1}$ . Along with these intervals we will define disjoint subsets $E_{e, i}$ , $i < h_{e}$ , of $I_{e}$ , and a string $V_{e}$ of length $h_{e}$ (where $h_{e}$ will depend on e). These constructions will be limiting constructions using moving markers. That is, $r_{e} = {lim}_{s \to \infty} r_{e, s}$ , where $r_{e, s}$ are defined effectively in e and s; $r_{e, s}$ can be considered as the value/approximation of $r_{e}$ at sth stage. Similar convention applies for $I_{e}$ , $h_{e}$ , $E_{e, i}$ , $V_{e}$ and the defined below numbers $c_{e}$ , $c_{e}^{'}$ and sets $J_{e}$ and their corresponding approximations. The set A will be formed by taking the union of $E_{e, i}$ , such that $V_{e} (i) = 1$ .

The string $V_{e} (i)$ will have “high” Kolmogorov complexity which will allow us to show that $C (A [2 \cdot r_{e}]) ⩾ 2 \cdot r_{e} / g^{'} (2 \cdot r_{e})$ , for all but finitely many e. Additionally, we will have that, for each possible many–one reduction $φ_{d}$ , either:
for all but finitely many e, $range (φ_{d})$ intersects only a “small” number of $E_{e, i}$ among $E_{e, 0}, E_{e, 1}, \dots, E_{e, h_{e} - 1}$ , and none of these small number of $E_{e, i}$ ’s intersect with A, or

$range (φ_{d})$ intersects with all but finitely many $E_{e, i}$ ’s, and for $(e, i) < (e^{'}, j)$ (in lexicographic ordering), the minimal x such that $φ_{d} (x) \in E_{e, i}$ is smaller than the minimal x such that $φ_{d} (x) \in E_{e^{'}, j}$ (in case both these minimal numbers exist). We will ensure this latter property by appropriately choosing $E_{e, i}$ using e-states of $I_{e}$ (defined later below) and corresponding definition of $V_{e}$ .
In case (a), ${x : φ_{d} (x) \in A}$ will be recursive. In case (b), because of the way $V_{e, s}$ , $I_{e, s}$ , and $E_{e, i, s}$ will be defined, we will be able to show that ${x : φ_{d} (x) \in A}$ is left-r.e. We now proceed formally.

Given the non-decreasing unbounded recursive function $g^{'}$ , let g be defined as $g (0) = 1$ and $g (n) = max {m : m^{2 m} ⩽ min {n, g^{'} (n)}}$ for all $n ⩾ 1$ . Intuitively, $g {(n)}^{g (n)} ⩽ g^{'} (n)$ , and we will be proving the theorem by using $g {(n)}^{g (n)}$ instead of $g^{'} (n)$ . Let $φ_{d, s}$ be as defined in Section 3 just before Lemma 3.2. Let $x_{d, s}$ be the minimal value such that $φ_{d, s}$ is undefined; thus $dom (φ_{d, s}) = {y : y < x_{d, s}}$ . For ease of notation, for all e, s let $J_{e, s}$ denote $⋃_{i < h_{e, s}} E_{e, i, s}$ . For all e, s, let $c_{e, s} = g (2 \cdot r_{e, s})$ and $c_{e, s}^{'} = ⌊ r_{e, s} / {(c_{e, s})}^{c_{e, s}} ⌋$ . Note that $r_{e, s} ⩾ c_{e, s}^{'} \cdot {(c_{e, s})}^{c_{e, s}}$ . Below we define $I_{e, s}$ , $r_{e, s}$ , $h_{e, s}$ , $E_{e, i, s}$ for $i < h_{e, s}$ , after having defined $I_{d, t}$ , $r_{d, t}$ , $h_{d, t}$ , $E_{d, i, t}$ for $i < h_{d, t}$ , for all d, e satisfying $[(d < e and t ⩽ s) or (d ⩽ e and t < s)]$ . $V_{e, s}$ is defined after having defined $V_{e, t}$ for $t < s$ and $r_{e^{'}, s}$ , $I_{e^{'}, s}$ for each $e^{'} ⩽ e + 1$ .

Definition of e-state. For all e, s, define the e-state (at stage s) of interval I as the lexicographically largest string $σ \in {0, 1}^{e + 1}$ such that for all $d ⩽ e$ with $σ (d) = 1$ , $\begin{matrix} | range (φ_{d, s}) \cap I | ⩾ c_{e, s}^{'} \cdot {(c_{e, s})}^{2 p (σ) + 1}, \end{matrix}$ where $p (σ)$ is the cardinality of the set ${τ \in {0, 1}^{} : | τ | = | σ | \land σ ⩽_{lex} τ}$ . For example, $p (000) = 8, p (001) = 7, p (010) = 6, \dots, p (111) = 1$ .

Definition of* $r_{e, s}$ and $I_{e, s}$ . Parameter $r_{e, s}$ , and thus $I_{e, s}$ , are chosen such that the following constraints are met. Intuitively, (P1) to (P4) and (P5.3) below just make sure that the $r_{e, s}$ are large enough and monotonic in e, s. The constraints (P5) and (P6) ensure that e-states are as high as possible (P5.1, P6) and that some monotonicity constraints on the reductions are maintained (P5.2, P6).
$20 + 4 \cdot {(e + 2)}^{2} + 2^{e + 2} ⩽ c_{e, s}$ ;

If $e > 0$ , then $4 \cdot r_{e - 1, s} + 4 ⩽ c_{e, s} ⩽ r_{e, s}$ ;

$\forall c^{″} ⩾ c_{e, s}^{'} [2^{c^{″} / 4} ⩾ c_{e, s} \cdot c^{″} \cdot 2^{e + 2}]$ ;

If $s > 0$ , then $r_{e, s - 1} ⩽ r_{e, s}$ ;

If $s > 0$ and $r_{e, s} > r_{e, s - 1}$ then at least one of the following conditions holds:

$I_{e, s}$ has a higher e-state (at stage s) than $I_{e, s - 1}$ ;

There are d, $e^{'}$ with $e^{'} < e$ , $d ⩽ e$ such that $min {x : φ_{d, s} (x) \in J_{e, s - 1}} < min {x : φ_{d, s} (x) \in J_{e^{'}, s - 1}}$ (where both the minimal numbers exist). In this case we also require that $r_{e, s} > φ_{d} (y)$ for all $y < x_{d, s}$ ;

$I_{d, s - 1} \neq I_{d, s}$ for some $d < e$ ;

For $s > 0$ , $r_{e, s - 1} < r_{e, s}$ whenever (P5.2) or (P5.3) above hold or some interval ${r_{e, s - 1} + c^{″}, r_{e, s - 1} + c^{″} + 1, \dots, 2 \cdot (r_{e, s - 1} + c^{″})}$ with $c^{″} \in {1, 2, \dots, s}$ has a higher e-state (at stage s) than $I_{e, s - 1}$ .

Definitions of $h_{e, s}$ and $E_{e, j, s}$ , for $j < h_{e, s}$ . If $s > 0$ and $I_{e, s} = I_{e, s - 1}$ and the e-state of $I_{e, s}$ (at stage s) is same as the e-state of $I_{e, s - 1}$ (at stage $s - 1$ ), then let $h_{e, s} = h_{e, s - 1}$ and $E_{e, j, s} = E_{e, j, s - 1}$ for $j < h_{e, s - 1}$ . Otherwise (that is, if $s = 0$ or $I_{e, s} \neq I_{e, s - 1}$ or the e-state (at stage s) of $I_{e, s}$ is larger than that of $I_{e, s - 1}$ (at stage $s - 1$ )), then define $h_{e, s}$ and $E_{e, j, s}$ , for $j < h_{e, s}$ , as follows. Let σ be the e-state of $I_{e, s}$ at stage s, let $h_{e, s} = c_{e, s}^{'} \cdot {(c_{e, s})}^{2 p (σ)}$ , and let $\begin{matrix} E_{e, i, s} = {φ_{d} (x) : d ⩽ e, σ (d) = 1, and x = min {z : φ_{d} (z) \in I_{e} - ⋃_{j < i} E_{e, j, s}}} . \end{matrix}$ Note that by (P1), $| E_{e, i, s} | ⩽ e + 1 ⩽ c_{e, s}$ and thus the corresponding minimal x in the definition of $E_{e, i, s}$ exists as $range (φ_{d, s}) \cap I_{e, s}$ has at least $h_{e, s} \cdot c_{e, s}$ elements by the definition of e-state.

Definitions of $V_{e, s}$ and $A_{s}$ . Let σ denote the e-state of $I_{e, s}$ at stage s. Let $V_{e, s} = b_{0} b_{1} \dots b_{h_{e, s} - 1}$ be the lexicographically least binary string of length $h_{e, s}$ satisfying the following conditions:
The string $b_{0} b_{1} \dots b_{h_{e, s} - 1}$ is in ${0, 1}^{h_{e, s}} - {0}^{h_{e, s}}$ and there is no $u < 2^{c_{e, s}^{'} \cdot c_{e, s}}$ such that the universal Turing machine U computes on input u the value $U (u) = b_{0} b_{1} \dots b_{h_{e, s} - 1}$ within s steps;

There are no $d ⩽ e$ and no $i < h_{e, s}$ such that $σ (d) = 0$ and $b_{i} = 1$ and $range (φ_{d, s}) \cap E_{e, i, s} \neq \emptyset$ ;

$V_{e, t} \neq b_{0} b_{1} \dots b_{h_{e, s} - 1}$ for any $t < s$ which satisfies

$I_{e, t} = I_{e, s}$ and e-state of $I_{e, t}$ are same at stages t and s, and

either $I_{e + 1, t + 1} \neq I_{e + 1, t}$ or the $(e + 1)$ -state of $I_{e + 1, t}$ is different at stages t and $t + 1$ .
Let $A_{s} = ⋃ {E_{e, i, s} : e \in N, i < h_{e, s}, and V_{e, s} (i) = 1}$ .

We now argue that $V_{e, s}$ as above is always defined. Condition (I) rules out at most $2^{c_{e, s}^{'} \cdot c_{e, s}}$ many possibilities of the string $b_{0} b_{1} \dots b_{h_{e, s} - 1}$ . Now $\begin{matrix} h_{e, s} = c_{e, s}^{'} \cdot {(c_{e, s})}^{2 p (σ)} ⩾ c_{e, s}^{'} \cdot c_{e, s}^{2} \end{matrix}$ and by (P1) $c_{e, s} ⩾ 4$ , so condition (I) blocks less than $2^{h_{e, s} / 4}$ possibilities for $b_{0} b_{1} \dots b_{h_{e, s} - 1}$ . For condition (II) note that for any d with $σ (d) = 0$ , there are at most $c_{e, s}^{'} \cdot {(c_{e, s})}^{2 (p (σ) - 1) + 1} = h_{e, s} / c_{e, s}$ many $i < h_{e, s}$ such that $E_{e, i, s}$ intersects with $range (φ_{d, s})$ (otherwise, one could increase the e-state of $I_{e, s}$ by making $σ (d) = 1$ ). Hence in total at most $(e + 1) \cdot h_{e, s} / c_{e, s} ⩽ h_{e, s} / 4$ many $b_{i}$ ’s are forced to be 0 by condition (II) (as (P1) implies $c_{e, s} ⩾ 4 (e + 1)$ ). Condition (III) states that old values of $b_{0} b_{1} \dots b_{h_{e, s} - 1}$ which are abandoned due to $I_{e + 1}$ moving or improving its $(e + 1)$ -state should not be reused while $I_{e}$ itself neither moved nor improved its e-state. Let $s^{'} ⩽ s$ be minimal such that $I_{e, s^{'}} = I_{e, s}$ and e-state of $I_{e, s^{'}}$ is same at stages s and $s^{'}$ . Condition (III) thus holds due to one of the following cases:
For some $d ⩽ e + 1$ , $e^{'} < e + 1$ , and $s^{'} < t < s$ , $\begin{matrix} min {x : φ_{d, t} (x) \in J_{e + 1, t}} < min {x : φ_{d, t} (x) \in J_{e^{'}, t}}, \end{matrix}$ where both the minimal numbers exist. By the choice of $r_{e, s}$ in (P5.3), each element in $J_{e^{'}, s}$ , $e^{'} < e + 1$ , can cause the above at most once. Thus, the total number of such cases is bounded by $\begin{matrix} (e + 2) \cdot (\sum_{e^{'} ⩽ e, i < h_{e^{'}, s}} | E_{e^{'}, i} |) ⩽ (e + 2) \cdot [2 \cdot r_{e - 1, s} + h_{e, s} \cdot (e + 1)] ⩽ 2 \cdot {(e + 2)}^{2} \cdot h_{e, s}, \end{matrix}$ as $2 \cdot r_{e - 1, s} ⩽ c_{e, s} ⩽ h_{e, s}$ by (P2) and the definition of $h_{e, s}$ .

After each of the events in (i), the $(e + 1)$ -state of $I_{e + 1}$ can increase up to $2^{e + 2} - 1$ times.
Thus the number of possibilities of the string $b_{0} b_{1} \dots b_{h_{e, s} - 1}$ ruled out due to condition (III) is bounded by $\begin{matrix} 2 \cdot {(e + 2)}^{2} \cdot h_{e, s} \cdot 2^{e + 2} ⩽ c_{e, s} \cdot h_{e, s} \cdot 2^{e + 2} ⩽ 2^{h_{e, s} / 4}, \end{matrix}$ where the leftmost inequality is due to (P1) and the rightmost inequality follows from (P3) and the fact that $h_{e, s} ⩾ c_{e, s}^{'}$ . By the above analysis, there will still be some possibilities for $b_{0} b_{1} \dots b_{h_{e, s} - 1}$ after ruling out the values as dictated by the conditions (I), (II) and (III).

The above arguments also show that once all $I_{d}$ , $d < e$ , have stabilised and reached their final d-state, $I_{e}$ will also move finitely often and reach its final e-state. If σ is the final e-state of $I_{e}$ and there is $d > e$ such that the final d-state of $I_{d}$ is $τ η$ with $| τ | = | σ |$ and $σ <_{lex} τ$ , then $I_{e}$ could increase its e-state to τ by moving to the position of $I_{d}$ . As such a move does not happen, by the assumption on the values being final, one can conclude that, for each d, there is a $τ \in {0, 1}^{d + 1}$ such that all but finitely many e satisfy that the final e-state σ of $I_{e}$ has the prefix τ.

Now assume that $B ⩽_{m} A$ via $φ_{d}$ . Let $τ \in {0, 1}^{d + 1}$ be such that all but finitely many e satisfy that the final e-state σ of $I_{e}$ has the prefix τ. If $τ (d) = 0$ then B is recursive, as the intersection of A and the range of $φ_{d}$ is a finite set (by definition of A and the condition (II) in the definition of $V_{e, s}$ ). If $τ (d) = 1$ then, for all but finitely many e, the range of $φ_{d}$ intersects all the $E_{e, i}$ , $i < h_{e}$ . Now it is shown that this condition can be used to show that B is a left-r.e. set. So let $e^{'}$ be a number such that $e^{'} ⩾ | τ |$ and all intervals $I_{e}$ with $e ⩾ e^{'}$ satisfy that the final e-state of $I_{e}$ extends τ. Let $t_{0}$ be the least stage such that for all $s ⩾ t_{0}$ , for all $e ⩽ e^{'}$ , $I_{e} = I_{e, s}$ and e-state of $I_{e, s}$ at stage s is the final e-state of $I_{e}$ , and similarly, other variables $V_{e}$ , $h_{e}$ , $r_{e}$ , $E_{e, i}$ for $i < h_{e}$ have reached their final values by stage $t_{0}$ . For $s = 0, 1, \dots$ , let $t_{s + 1}$ be the least stage satisfying the following conditions:
$t_{s + 1} > t_{s} + s$ ;

For $e \in {e^{'}, e^{'} + 1, \dots, e^{'} + s}$ , the e-state of $I_{e, t_{s + 1}}$ at stage $t_{s + 1}$ has the prefix τ;

For each $e \in {e^{'}, e^{'} + 1, \dots, e^{'} + s}$ and each $E_{e, i, t_{s + 1}}$ for $i < h_{e, t_{s + 1}}$ , the value $\begin{matrix} y_{e, i, t_{s + 1}} = min {x : φ_{d, t_{s + 1}} (x) \in E_{e, i, t_{s + 1}}} \end{matrix}$ is defined;

For each $e^{″}$ , $e^{‴} \in {e^{'}, e^{'} + 1, \dots, e^{'} + s}$ , $i < h_{e^{″}, t_{s + 1}}$ , and $j < h_{e^{‴}, t_{s + 1}}$ , $\begin{matrix} y_{e^{″}, i, t_{s + 1}} < y_{e^{‴}, j, t_{s + 1}} ⟺ e^{″} < e^{‴} \lor (e^{″} = e^{‴} \land i < j) . \end{matrix}$
Now let $\begin{matrix} B_{s} (z) = \{\begin{matrix} A_{t_{s}} (φ_{d} (z)), & if z < x_{d, t_{s}} \land φ_{d} (z) \in J_{0, t_{s}} \cup J_{1, t_{s}} \cup \dots \cup J_{e^{'} + s, t_{s}}, \\ 0, & otherwise . \end{matrix} \end{matrix}$ We claim that the sequence of these $B_{s}$ witnesses that B is a left-r.e. set. To see this, compare $B_{s}$ and $B_{s + 1}$ for arbitrary s. There is a least e such that the interval $I_{e + 1, t_{s}} \neq I_{e + 1, t_{s + 1}}$ or $(e + 1)$ -state of $I_{e + 1, t_{s}}$ is different at stages $t_{s}$ and $t_{s + 1}$ (if there is none, then clearly, $B_{s} \subseteq B_{s + 1}$ ; here note that by definition of $t_{0}$ , $I_{0}$ has reached its final value and 0-state by stage $t_{0}$ ). Then, by construction $V_{e, t_{s}}$ is different from $V_{e, t_{s + 1}}$ , and $V_{e, t_{s + 1}}$ is lexicographically greater than $V_{e, t_{s}}$ . Let i be least such that $0 = V_{e, t_{s}} (i) \neq V_{e, t_{s + 1}} (i) = 1$ . Note that $y_{e, i, t_{s}} = y_{e, i, t_{s + 1}}$ , and both are defined.
First consider the case where $e ⩽ e^{'} + s$ . Now it holds that
$y_{e, i, t_{s}} = y_{e, i, t_{s + 1}} < x_{d, t_{s}}$ ,

$A_{t_{s}} (φ_{d} (y_{e, i, t_{s}})) = 0$ , and

$A_{t_{s + 1}} (φ_{d} (y_{e, i, t_{s}})) = 1$ .
Furthermore, for all $z < y_{e, i, t_{s}}$ , either
$φ_{d} (z) \in J_{e^{″}, t_{s}}$ for some $e^{″} < e$ , or

$φ_{d} (z) \in I_{e, s} \cap E_{e, j, s}$ for some $j < i$ , or

$φ_{d} (z) \notin J_{0, t_{s}} \cup J_{1, t_{s}} \cup \dots \cup J_{e^{'} + s, t_{s}}$ (by the fourth condition in the definition of $t_{s + 1}$ ).
In each of these subcases we have $A_{t_{s}} (φ_{d} (z)) ⩽ A_{t_{s + 1}} (φ_{d} (z))$ , hence $B_{s} ⩽_{lex} B_{s + 1}$ .

Second consider the case that $e > e^{'} + s$ . In this case, all z which are in $B_{s}$ satisfy that $φ_{d} (z) \in J_{e^{″}, t_{s}}$ for some $e^{″} ⩽ e^{'} + s$ and therefore $φ_{d} (z)$ is also in $J_{e^{″}, t_{s + 1}}$ and $A_{t_{s}} (φ_{d} (z)) = A_{t_{s + 1}} (φ_{d} (z))$ . It follows that $B_{s} \subseteq B_{s + 1}$ which, in turn, implies $B_{s} ⩽_{lex} B_{s + 1}$ . This case-distinction completes the proof that the $B_{s}$ form a left-r.e. approximation for B.
To complete the proof, the condition on the Kolmogorov complexity needs to be verified. For a fixed e, consider the limiting values of $V_{e}$ (corresponding to the interval $I_{e}$ ). Using condition (I) from above, the Kolmogorov complexity of $V_{e}$ is at least $c_{e}^{'} \cdot c_{e}$ . If one could describe $C (A [2 \cdot r_{e}])$ with a code of length $2 \cdot c_{e}^{'} + 1 ⩾ 2 \cdot r_{e} / g^{'} (2 \cdot r_{e})$ , then one could modify this to a short description of $V_{e}$ as follows. One adds a prefix $1^{e} 0 σ$ before the description of $A [2 \cdot r_{e}]$ in order to code e and the limiting e-state σ of $I_{e}$ ; the resulting description has at most $c_{e} / 2 + 2 \cdot c_{e}^{'}$ bits (using (P1)). Note that ${(c_{e})}^{2 c_{e}} ⩽ 2 \cdot r_{e}$ , by definition of g. Thus $c_{e} ⩾ 20$ (by (P1)) and $c_{e}^{'} = ⌊ 2 \cdot r_{e} / ({(c_{e})}^{c_{e}}) ⌋ ⩾ c_{e}$ . Hence, $c_{e} / 2 + 2 \cdot c_{e}^{'} ⩽ c_{e} \cdot c_{e}^{'} / 2$ . Furthermore, one can retrieve the length $2 \cdot r_{e} + 1$ of $A [2 \cdot r_{e}]$ and can then find the interval $I_{e}$ . Hence from all these items of information, one can compute the final values of $h_{e}$ and $E_{e, 0}, E_{e, 1}, \dots, E_{e, h_{e} - 1}$ and $V_{e}$ . This permits to deduce that $C (V_{e}) ⩽ c_{e} \cdot c_{e}^{'} / 2$ plus a constant in contradiction to the choice of $V_{e}$ for large enough e. Therefore the Kolmogorov complexity of $C (A [2 \cdot r_{e}])$ is, for all but finitely many e, at least $2 \cdot c_{e}^{'} + 1$ . Thus, for all but finitely many e, $C (A [2 \cdot r_{e}]) ⩾ 2 \cdot r_{e} / g^{'} (2 \cdot r_{e})$ . □
Theorem 5.4.
If A is a conjunctively closed left-r.e. set then, for every $ε > 0$ and for all but finitely many n, $C (A [n]) ⩽ (2 + ε) \cdot log (n)$ .
Proof.
Let ε with $0 < ε < 1$ be given. First one chooses r, k such that $\sum_{h \in {1, 2, 3, \dots}} r^{- h} < ε / 6$ and $r^{1 / k} < 1 + ε / 6$ . For each $ℓ \in {0, 1, \dots, k - 1}$ , one constructs a set $B_{ℓ}$ using the following intervals (where the length of each $I_{m}$ also depends on ℓ and so do the intervals $J_{m, h}$ ). Partition $N$ into intervals $I_{0}, I_{1}, \dots$ with size of $I_{m}$ being $⌊ 2^{r^{m + ℓ / k}} ⌋$ and $min I_{m + 1} = 1 + max I_{m}$ for all m, and partition $N$ into intervals $J_{m, h}$ where $m \in N$ and $h \in {0, 1, \dots, | I_{m} |}$ such that $min J_{m, h + 1} = 1 + max J_{m, h}$ and $min J_{m + 1, 0} = 1 + max J_{m, | I_{m} |}$ for all $m \in N$ and all $h < | I_{m} |$ . Furthermore, $J_{m, h}$ has $(\binom{| I_{m} |}{h})$ many elements and now $\begin{array}{l} let the u th element of J_{m, h} be in B_{ℓ} iff the u -last | I_{m} | - h element subset of I_{m} according to lexicographic \\ order is a subset of A . \end{array}$ Clearly, each $B_{ℓ}$ is conjunctively reducible to A (let us say the reduction is via recursive function f). So fix an ℓ for the further investigation. Now, as A is conjunctively closed left-r.e., $B_{ℓ}$ is a left-r.e. set. Let $B_{ℓ, t}$ and $A_{t}$ be left-r.e. approximations of $B_{ℓ}$ and A, respectively.

Now, we can compute $A \cap (⋃_{u ⩽ m} I_{u})$ by knowing the cardinality $c_{u} = | A \cap I_{u} |$ for all $u ⩽ m$ and then enumerating $A_{t}$ and $B_{ℓ, t}$ (in left-r.e. fashion) until a t is found such that
$A_{t} \cap I_{u}$ has exactly $c_{u}$ elements, for $u ⩽ m$ , and

f gives the correct reduction from $B_{t}$ to $A_{t}$ for all intervals $J_{u, h}$ , with $u ⩽ m$ and $h ⩽ | I_{u} |$ .
Note that one can prove by induction that for all $u ⩽ m$ there is exactly one possible choice of values for $A_{t}$ on $I_{u}$ such that $A_{t} \cap I_{u}$ has $c_{u}$ elements and the unique element in $B_{ℓ, t} \cap J_{u, c_{u}}$ corresponds to the unique $c_{u}$ -element set $A_{t} \cap I_{u}$ as given by reduction f. It then follows that when the values of $c_{0}, c_{1}, \dots, c_{m}$ are chosen correctly, the corresponding set $A_{t}$ coincides with A on $I_{0} \cup I_{1} \cup \dots \cup I_{m}$ . The description of $c_{0}, c_{1}, \dots, c_{m}$ needs $log (I_{0}) + log (I_{1}) + \dots + log (I_{m})$ bits and this can be bounded by $log (| I_{m} |) \cdot (1 + r^{- 1} + r^{- 2} + \dots) ⩽ log (| I_{m} |) \cdot (1 + ε / 6)$ bits. Furthermore, for computing $A (0) A (1) \dots A (n)$ with $n ⩽ max I_{m}$ , one needs a constant amount of bits to code ℓ plus $log (n)$ bits to code n, so the overall amount of bits needed is at most $2 \cdot log (| I_{m} |) \cdot (1 + ε / 6)$ .

Note that the reduction might know the programs to left-enumerate all the sets $B_{0}, B_{1}, \dots, B_{k - 1}$ ; hence one can choose in dependence of n which $B_{ℓ}$ to use. Thus m, ℓ can both be chosen suitably such that $m + ℓ / k$ is the least value with $r^{m + ℓ / k} ⩾ log (n)$ . Then $log (| I_{m} |) ⩽ log (n) \cdot r^{1 / k}$ which means that one needs at most $\begin{matrix} 2 \cdot log (n) \cdot r^{1 / k} \cdot (1 + ε / 6) ⩽ 2 \cdot log (n) \cdot (1 + 2 ε / 6 + ε^{2} / 36) ⩽ (2 + ε) \cdot log (n) \end{matrix}$ bits to describe $A (0) A (1) \dots A (n)$ . □

One can modify the above construction as follows to cover the case of disjunctive reducibility by changing the following items in the proof:
the uth member of $J_{m, h}$ is in B iff the u-last $| I_{m} | - h$ element subset of $I_{h}$ in lexicographic order intersects A;

the interval $J_{m, c_{m}}$ is then the first interval among $J_{m, 0}, J_{m, 1}, \dots, J_{m, | I_{m} |}$ which is not a subset of $B_{ℓ}$ and this has exactly one non-element, namely the element which corresponds to the $| I_{m} | - c_{m}$ element set $I_{m} - A$ .
The remaining parts of the proof are the same and one obtains the following parallel result.
Theorem 5.5.
If A is a disjunctively closed left-r.e. set then, for every $ε > 0$ and for all but finitely many n, $C (A [n]) ⩽ (2 + ε) \cdot log (n)$ .

Note that these results state that the conjunctively, disjunctively and positively closed left-r.e. sets are, in terms of their initial segment Kolmogorov complexity, quite similar to the r.e. sets whose plain initial segment complexity is bounded by $2 log (n)$ (plus a constant) for all n.
6. Conclusion

Left-r.e. sets are a natural generalisation of r.e. sets. However, they fail to have many closure properties of the r.e. sets: The unions and intersections of left-r.e. sets may fail to be left-r.e.; furthermore they are not closed under easy ascending reducibilities like taking the half of a set. For example, it is known that the set ${x : 2 x \in Ω}$ is not left-r.e. and this extends to all Martin-Löf random left-r.e. sets; similarly, the intersection of Ω with the set of even numbers is not left-r.e. and the same holds for the union of these two sets. Therefore the present work studies left-r.e. sets which are strongly left-r.e. in the sense that every set r-reducible to them is again left-r.e., where the reducibility r can either be ascending, many–one, conjunctive, disjunctive or positive reducibility. It is shown that even for the very general positive reducibility, there are closed left-r.e. sets which are not recursively enumerable; thus the positive closed left-r.e. sets are a proper generalisation of the r.e. sets. One of the main questions studied was which additional properties of such sets can be achieved. While many–one closed left-r.e. sets can be taken to be cohesive or weakly 1-generic, they cannot be taken to be Martin-Löf random. For ascending reducibility, the initial segment complexity of such sets can be $n / f (n)$ for all but finitely many n, for any recursive unbounded and monotone function f. In the case of many–one reducibility, the initial segment complexity can be infinitely often above a bound $n / f (n)$ , for any recursive unbounded and monotone function f. However, for every $ϵ > 0$ , the initial segment complexity of a disjunctive or conjunctive closed left-r.e. sets is bounded almost everywhere by $(2 + ε) \cdot log (n)$ . This shows that conjunctive, disjunctive and positive closed left-r.e. sets are very near to r.e. sets which obey a similar bound, although they do not coincide with them.

In previous versions of this paper we mentioned the open question whether there is a non-r.e. set such that all the sets enumeration-reducible to it are left-r.e.; recently, Keng Meng Ng proved that such sets do not exist [9]. Furthermore, one might study the many–one degrees of many–one closed left-r.e. sets. This degree structure can easily be shown to be an upper semilattice. However, fundamental properties are not yet known: for example does this upper semilattice have a greatest element (as in the case of the r.e. many–one degrees).

Footnotes

Acknowledgements

S. Jain has been supported in part by NUS grants C252-000-087-001, R146-000-181-112, R146-000-184-112 and R252-000-420-112; F. Stephan has been supported in part by NUS grants R146-000-181-112, R146-000-184-112 and R252-000-420-112; J. Teutsch has been supported by the Deutsche Forschungsgemeinschaft grant ME 1806/3-1. We also like to thank the anonymous referees for helpful comments and Keng Meng Ng for discussions on closed left-r.e. sets.

References

C.S.

Calude, Information and Randomness: An Algorithmic Perspective, 2nd edn, Springer, Berlin, 2002.

G.J.

Chaitin, Incompleteness theorems for random reals, Advances in Applied Mathematics 8(2) (1987), 119–146.

R.G.

Downey and

Hirschfeldt, Algorithmic Randomness and Complexity, Springer, New York, 2010.

R.M.

Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, The Journal of Symbolic Logic 23 (1958), 309–316.

C.G.

Jockusch, Semirecursive sets and positive reducibility, Transactions of the American Mathematical Society 131 (1968), 420–436.

A.H.

Lachlan, On the lattice of recursively enumerable sets, Transactions of the American Mathematical Society 130 (1968), 1–37.

Li and

Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn, Graduate Texts in Computer Science, Springer, New York, 2008.

Myhill, Solution of a problem of Tarski, The Journal of Symbolic Logic 21(1) (1956), 49–51.

K.M.

Ng, Enumeration closed left-r.e. sets are recursively enumerable, Private Communication (2015).

10.

Nies, Computability and Randomness, Oxford Univ. Press, New York, 2009.

11.

Odifreddi, Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, Vol. 125, North-Holland, Amsterdam, 1989.

12.

Odifreddi, Classical Recursion Theory, Volume II, Studies in Logic and the Foundations of Mathematics, Vol. 143, Elsevier, Amsterdam, 1999.

13.

E.L.

Post, Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society 50 (1944), 284–316.

14.

R.W.

Robinson, Simplicity of recursively enumerable sets, The Journal of Symbolic Logic 32 (1967), 162–172.

15.

RogersJr., Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge, 1987.

16.

R.I.

Soare, Cohesive sets and recursively enumerable Dedekind cuts, Pacific Journal of Mathematics 31(1) (1969), 215–231.

17.

R.I.

Soare, Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer, Berlin, 1987.

18.

Stephan and

Teutsch, Things that can be made into themselves, Information and Computation 237 (2014), 174–186.

19.

A.K.

Zvonkin and

L.A.

Levin, The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Mathematical Surveys 25(6) (1970), 83–124.