$A\leq_m B$ and $B\in\Pi_n\implies A\in \Pi_n$

31 Views Asked by At

Suppose $A\leq_m B$ and $B$ is, say, $\Pi_2$. I don't understand this proof of the fact that $A$ is $\Pi_2$:

Assume $z\in B\iff \forall y_1\exists y_2 R(z,y_1,y_2)$ where $R$ is computable. If $A\leq_m B$ via $f$, then $$x\in A\iff f(x)\in B \iff \forall y_1\exists y_2 R(f(x),y_1,y_2).$$

Why does the above prove that $A$ is $\Pi_2$? $A$ being $\Pi_2$ amounts to saying that $$x\in A\iff \forall y_1\exists y_2 T(x,y_1,y_2)$$ for some computable $T$. But the above only shows that $$x\in A\iff \forall y_1\exists y_2 T(f(x),y_1,y_2)$$ for some computable $T$ and some computable total function $f$.

1

There are 1 best solutions below

4
On BEST ANSWER

The point is that we can "substitute $f$ in" since $f$ itself is total computable: given a computable relation $R$ and a total computable function $f$, the relation $$T(a,b,c):= R(f(a),b,c)$$ is again total computable.