information:extraction
Recursively enumerable Turing degrees

A degree is called recursively enumerable (r.e.) or computably enumerable (c.e.) if it contains a recursively enumerable set. Every r.e. degree is below 0 ′, but not every degree below 0 ′ is r.e.. However, a set A {\displaystyle A} is many-one reducible to 0 ′ iff A {\displaystyle A} is r.e..

Additionally, there is Shoenfield's limit lemma, a set A satisfies ≤ T ∅ ′ {\displaystyle \leq _{T}\emptyset '} iff there is a "recursive approximation" to its characteristic function: a function g such that for sufficiently large s, g (s) = χ A (s) {\displaystyle g(s)=\chi _{A}(s)}.

A set A is called n -r e. if there is a family of functions (A s) s ∈ N {\displaystyle (A_{s})_{s\in \mathbb {N} }} such that:

Properties of n -r.e. degrees: