# Transitivity of quasi-reducibility

A set $A$ is quasi-reducible to $B$ ($A \leq_Q B$) if there is a recursive function $f$ such that $$x \in A \iff W_{f(x)} \subseteq B$$ Or equivalently $$x \in \overline{A} \iff W_{f(x)} \cap \overline{B} \neq \emptyset$$ Where $W_{e}$ is the domain of the recursive function of index $e$, i.e. $W_{e} = \{y : \varphi_{e}(y) \downarrow\}$.

Everywhere I look it says the transitivity of the relation is easy to see, but for some reason it doesn't click for me.

Ok I think I have found it.

Let $A$, $B$ and $C$ such that $A \leq_Q B$ and $B \leq_Q C$, respectively by the recursive functions $f$ and $g$. Let \begin{align*} h : x,y \mapsto & \text{ find } b \in W_{f(x)} \text{ and } c \in W_{g(b)} \text{ such that } y = c \\ & \text{ return } 0 \end{align*} By $s$-$m$-$n$ we have a recursive function $s$ such that $\varphi_{s(x)}(y) = h(x,y)$.

Assume $x \in A$. If $y \in W_{s(x)}$, then $\exists b \in W_{f(x)}$ and $\exists c \in W_{g(b)}$ such that $y = c$ so $b \in B$ and $c \in C$ by the assumed reductions, so $y \in C$ and $W_{s(x)} \subseteq C$.

Now if $x \in \overline{A}$, then $\exists b \in W_{f(x)} \cap \overline{B}$ and $\exists c \in W_{g(b)} \cap \overline{C}$, so $h(x,c)\downarrow$ and $c \in W_{s(x)} \cap \overline{C}$.

So we can conclude $A \leq_Q C$.

Let me know if you think there's a problem with this.

• It looks OK to me. Nice.
– chi
May 14 '18 at 15:36