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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.