Closed Left-r.e. Sets

What is it about?

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)...A(n)) \geq 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 epsilon>0, for all but finitely many n, C(A(0)A(1) ... A(n)) \leq (2+epsilon) log(n).

Featured Image

Why is it important?

Studies several properties of left-r.e. sets and reductions, and initial segment complexity