Prove that two sets recursively inseparable.

164 Views Asked by At

Let φ be the standard indexing of the partial computable functions. Prove that the sets $$A = \left\{e : φ_e(0) = 0\right\}$$ and $$B = \left\{e : φ_e(0) = 1\right\}$$ are recursively inseparable

In books like "Handbook of recursive mathematics, Vol. 2" I found different example: $$A = \left\{x : φ_x(x) = 0\right\}$$ and $$B = \left\{x : φ_x(x) = 1\right\}$$ which can be proven very easy, what I can't say about this.

1

There are 1 best solutions below

0
On BEST ANSWER

I think it's most illuminating to observe that we can whip up a reduction of the new problem to the old problem.

Specifically, we can translate from one context to the other as follows:

  • There is a total computable $c$ such that for all $x$ we have $\varphi_x(x)\simeq\varphi_{c(x)}(0)$.

  • There is a total computable $d$ such that for all $x$ we have $\varphi_x(0)\simeq\varphi_{d(x)}(d(x))$.

Here "$\alpha\simeq\beta$" means "Either both $\alpha$ and $\beta$ are undefined or both $\alpha$ and $\beta$ are both defined and are equal."

With such $c$ and $d$, we can show that the recursive inseparability of either pair implies the recursive inseparability of the other. Let $A,B$ be the first pair in your post and $\hat{A},\hat{B}$ be the second pair; pulling back along $c$ or $d$ as appropriate lets us produce a recursive separator for one from a recursive separator for the other. (Basically, we're thinking about many-one reductions between pairs of r.e. sets.)