Turing computability between subsets

51 Views Asked by At

Is it true that, given two infinite subsets $A,B\subset \mathbb{N}$, either there is a (infinite) subset $C$ of $A$ s.t. $C \le_T B$ or there is a (infinite) subset $D$ of $B$ s.t. $D \le_T A$?

I suspect this is not the case, but I don't whether it should follow from some well-known result or whether it should be proved by a careful priority argument.

1

There are 1 best solutions below

0
On BEST ANSWER

At a glance, I think a pair of mutually (sufficiently) Cohen generics give a counterexample since given a pair of finite binary strings $\sigma,\tau$ and an $e\in\omega$, we can always do one of the following:

  • find some extensions $\hat{\sigma}\succ\sigma,\hat{\tau}\succ\tau$ and some $n\in\omega$ such that $\Phi_e^{\hat{\sigma}}(n)\downarrow=1$ but $\hat{\tau}(n)=0$, in which case if $f\succ\hat{\sigma}$ and $g\succ\hat{\tau}$ are reals we can't have $\Phi_e^f\subseteq g$; or

  • find some extension $\hat{\sigma}\succ \sigma$ and some $n\in\omega$ such that no further extension $\overline{\sigma}\succ\hat{\sigma}$ has $\Phi_e^{\overline{\sigma}}(k)\downarrow=1$ for any $k>n$, in which case if $f\succ\hat{\sigma}$ we can't have $\Phi_e^f$ be infinite.