Enumeration reducibility

In addition to his intuitive model, Rogers also provided a concise reformulation to create an informal definition. It reads:

For any ${\displaystyle A,B\subseteq \omega ,A}$ is enumeration reducible to ${\displaystyle B}$ if there is an effective procedure for getting an enumeration of ${\displaystyle A}$ from any enumeration of ${\displaystyle B}$. Thus we write:

${\displaystyle A\leq _{e}B}$

which is the standard notation of enumeration reducibility.

From Rogers' informal definition, a precise definition can be inferred.

For any ${\displaystyle A,B\subseteq \omega ,A\leq _{e}B}$ if there exists a computably enumerable set ${\displaystyle W}$ such that, for all ${\displaystyle x\in \omega ,}$

${\displaystyle x\in A}$ ${\displaystyle \Leftrightarrow }$ ${\displaystyle \exists D[\langle x,D\rangle \in W}$ ${\displaystyle \And }$ ${\displaystyle D\subseteq B].}$

In this case, we write that

${\displaystyle A\leq _{e}B}$ via ${\displaystyle W}$

or that ${\displaystyle W}$ (the enumeration operator) witnesses ${\displaystyle A\leq _{e}B}$.

• If ${\displaystyle A\leq _{e}B}$ and ${\displaystyle B\leq _{e}A,}$ ${\displaystyle A}$ is considered to be equivalent through enumeration to ${\displaystyle B}$. Thus we write

${\displaystyle A\equiv _{e}B.}$

• Conversely, if ${\displaystyle A\leq _{e}B}$ but ${\displaystyle B\nleq _{e}A,}$ we write

${\displaystyle A<_{e}B.}$

• Inversely, if ${\displaystyle A\nleq _{e}B}$ and ${\displaystyle B\nleq _{e}A,}$ we write

${\displaystyle A}$ ${\displaystyle |_{e}}$ ${\displaystyle B.}$

• The supremum (least upper bound) of sets ${\displaystyle A}$ and ${\displaystyle B}$ with respect to ${\displaystyle \leq _{e}}$ can be modeled by a symmetric difference equation. This equation accounts for the lack of information with an abstract variable ${\displaystyle n}$, which is squared due to the intersection (expressed as the ${\displaystyle \cup }$ symbol; a union.) It is written as

${\displaystyle A\Delta B=(2n}$ ${\displaystyle$ :} ${\displaystyle n\in A)\cup (2n+1}$ ${\displaystyle$ :} ${\displaystyle n\in B).}$

• A relationship between Turing reducibility, e-reducibility, and the relation "computably enumerable in" can be shown if a set ${\displaystyle A^{+}}$ is given different properties by ${\displaystyle A^{+}=A\Delta {\overline {A}}}$. This codes it in a positive way regardless if positive or negative information is supplied. It is formally expressed as follows:[5]

1. ${\displaystyle A\leq _{T}B}$ ${\displaystyle \Leftrightarrow }$ ${\displaystyle A^{+}\leq _{e}B^{+}}$
2. ${\displaystyle A}$ is computably enumerable if and only if ${\displaystyle A\leq _{e}B^{+}.}$

In addition to e-reducibility, there exist strong versions, the most important one being s-reducibility (named after Robert M. Solovay). S-reducibility states that a computably enumerable real set ${\displaystyle A}$ is s-reducible to another computably enumerable real set ${\displaystyle B}$ if ${\displaystyle B}$ is at least as difficult to be approximated as ${\displaystyle A}$.[7] This method shows similarity to e-reducibility in that it compares the elements of multiple sets. In addition, the structure of s-degrees have natural analogs in the enumeration degrees.[5]

The reasoning for using s-reducibility is summarized by Omandaze and Sorbi as a result of positive reducibility models being unable to answer certain oracle questions (e.g. an answer to "Is ${\displaystyle x\in A}$?" is only given if ${\displaystyle x\in A}$, and is not true for the inverse.) because they inherently model computational situations where incomplete oracle information is available.[8] This is in contrast from the well-studied Turing reducibility, in which information is captured in both negative and positive values. In addition, T-reducibility uses information that is provided immediately and without delay. A strong reducibility is utilized in order to prevent problems occurring when incomplete information is supplied.

E-reducibility can be defined for partial functions as well. Writing graph${\displaystyle (f)=\{\langle x,y\rangle }$ ${\displaystyle |}$ ${\displaystyle f(x)=y\}}$ , etc., we can define for partial functions ${\displaystyle f,g}$:[9]

${\displaystyle f\leq _{e}g\Leftrightarrow }$ graph${\displaystyle (f)\leq _{e}}$ graph${\displaystyle (g).}$

Kleene's recursion theorem introduces the notion of relative partial recursiveness, which, by means of systems of equations, can demonstrate equivalence through ${\displaystyle \leq _{e}}$ between graphs of partial functions.[10] E-reducibility relates to relative partial recursiveness in the same way that T-reducibility relates to μ-recursiveness.[5]