classifying problems with reducibility

Question

How can we use a reduction to prove non membership of a class. Can we say if A is reducible to B they are in same class or if we can't reduce A to B. B is not same class as A.

Regards,

Answer 1

I'll talk about Turing reducibility. The answer translates to other reducibilities.

The answer to your first question is: It depends what you mean. Here's an example. Let $A = \emptyset$ and $B = \left\{ e \mid \Phi_e(n)\downarrow \right\}$ (the halting set). Clearly $A$ is Turing reducible to $B$, and $B$ is a recursively enumerable set. So $A$ is also r.e. and in this sense they are in the same class.

But while $A$ is also recursive, $B$ is not: its Turing degree is $\mathbf{0'}$ while the Turing degree of $A$ is $\mathbf{0}$. So showing that $A \leq_T B$ is not sufficient for $A$ and $B$ to have the same Turing degree; we would also need to have that $B \leq_T A$.

We can thus use the nonexistence of a reduction to show that a set does not have the same Turing degree as another. Since $B \not\leq_T A$, $A \not\in \mathbf{0'}$. (Note that we can be specific only because we know the degree of $B$: if we did not we'd just have that $A \not\in \mathrm{deg}(B)$.)

So in conclusion: $A \leq_T B$ does not imply they have the same degree. But $B \not\leq_T A$ does imply that they have different degrees. Hence, it depends what you mean by "in the same class".