Prove that $A≤_m A\cap B$ [Cutland 9-1.7-5]

Question

Suppose that $A$, $B$ are r.e. sets such that $A\cup B= \mathbb N$ and $A\cap B≠∅$ . Prove that $A≤_m A\cap B$.

The difficulty is that how to find a total computable function f such that for all x, $x\in A$ iff $f(x)\in A\cap B$.

Answer 1

The key observation is the following: if $A\cup B=\mathbb{N}$, then there is a computable function $f:\mathbb{N}\rightarrow \{0, 1\}$ such that if $h(x)=0$ then $x\in A$ and if $h(x)=1$ then $x\in B$. That's not an iff - the point is that $h$ picks out one of $A$ or $B$, but $x$ could in principle be in both. The reason this fact is true is that we can just run the machines enumerating $A$ and $B$ in parallel, waiting for one of them to enumerate $x$; one of them will, since $A\cup B=\mathbb{N}\ni x$, and when we see that happen we stop and output $0$ or $1$ accordingly. (Incidentally, you'll see a similar sort of thing to $h$ when you study DNR$_2$ functions, where for each $x$ you pick a "safe" option from two given options.)

So how will we build $f$? Well, to determine $f(x)$, we'll work in cases based on $h(x)$. I'll leave the actual construction to you, with the following hints:

• If $h(x)=1$ (we're guaranteed that $x\in B$), then $x\in A$ iff $x\in A\cap B$. This should look nice . . .

• If $h(x)=0$ (we're guaranteed that $x\in A$), then we know we want to map $x$ to something in $A\cap B$. So . . .