Languages that are not comparable in $R$

Question

I want to know if there are $2$ languages $A,B\in{R}$ such that there's no reduction between them. Namely, $2$ languages $A$ and $B$ $\in$ $R$ such that $A\not\le B$ and $B\not\le A$

Thanks a lot!

Answer 1

If $\leq$ is Turing reducibility (or truth-table reducibility, or weak truth table reducibility, etc., where the reducibility is based on computation from an oracle), the answer is no. All recursive sets are Turing-equivalent as they can be recognized without reference to any oracle.

If $\leq$ is many-one reducibility (or one-one reducibility, etc., where reduction is from one problem to another) then there is an example of such sets: $A$ is empty and $B$ contains all strings. Then there can be no reduction not because the problems are somehow different computationally (they are both completely trivial) but for the rather silly reason that there's nothing to reduce to: there are strings in $B$, so any reduction from $B$ to $A$ must take such a string to a string in $A$, but there are no strings in $A$; and there are strings not in $A$, so a reduction from $A$ to $B$ must take such a string to a string not in $B$, but there are no strings not in $B$.