3

Let $X =$ {$d$ : $\psi_d(0)=0\}$ and $Y$ = { $d$ : $\psi_d(0) = 1$ }. Show that if $S\subseteq \mathbb{N}$ has the property $X \subseteq S$ and $Y \cap S = \emptyset$ then $S$ is not recursive.

So I was thinking if I could find some function $f$ such that $\psi_{f(d)}(x) = \psi_d(d)$ for all $d$ and $x$. And then we were to consider the characteristic function of $\{t: f(t) \in S\}$ which we could call $\psi_a$ and see that computing $\psi_a(a)$ can be paradoxical. But how do we show we can find such a function $f$ and does my thinking sound right?

Carl Mummert
  • 81,604
Rex
  • 167
  • :What is $Th(\mathbb N)$? – Styles Jun 12 '18 at 15:27
  • 1
    @PKStyles I think he means the theory of the natural numbers – Raton Jun 12 '18 at 17:23
  • 2
    If $X$ and $Y$ are any disjoint sets, a set $S$ with $X \subseteq S$ and $S \cap Y = \emptyset$ is called a "separating set" for $X$ and $Y$. The fact in this question is a standard fact in computability theory. You can prove it by a diagonalization argument. – Carl Mummert Jun 12 '18 at 18:34
  • 2
    The existence of the function $f$ follows from the s-m-n theorem. – Carl Mummert Jun 12 '18 at 18:39
  • 1
    @CarlMummert I've looked at Soare's book as you recommended in this post https://math.stackexchange.com/questions/717815/show-that-a-recursively-inseparable-pair-of-recursively-enumerable-sets-exists and could not find this example--I am confused about how s-m-n applies in this example – Rex Jun 12 '18 at 19:48
  • 1
    @Carl Mummert s-m-n would tell us as far as I can tell that there is some function $f$ such that $\psi_d(x,y) = \psi_{f(d,x)}(y)$ – Rex Jun 12 '18 at 19:51
  • 1
    @Carl Mummert I understand the canonical example of $A = {e|\psi_e(e) = 0}$, $B = {e | \psi_e(e) = 1}$ and how this works but am unsure how to adapt it to this case. – Rex Jun 12 '18 at 19:53
  • 1
    @Carl Mummert also, where does diagonalization come into play? Are we trying to find some $t$ that will never be in $S$? – Rex Jun 12 '18 at 19:55
  • 2
    For the s-m-n theorem, you have it: $\psi_{f(d,d)}(y) = \psi_d(d,y)$, and if $\psi_d$ never looks at the second input this is $\psi_d(d)$. Maybe I am excessively flexible about the number of inputs, compared to some statements of the theorem. – Carl Mummert Jun 12 '18 at 20:35
  • 2
    For Soare's book, this is exercise 4.22 on p. 23, with the variation $A = { x : \phi_x(x) = 0}$ and $B = {x : \phi_x(x) = 1}$. – Carl Mummert Jun 12 '18 at 20:53

1 Answers1

3

I think that the ideas in the post are completely on track. However, when I tried to write up the answer as a hint, I kept making mistakes. In the end, it seemed that the recursion theorem was useful to solve the problem. Otherwise, I was trying to re-prove it in my solution.

For the diagonalization, we want a $d$ so that $d \in X$ if and only if $d \not \in S$. Expanding that, we want $\psi_d(0) = 0$ if and only if $\chi_S(d) = 0$. Thinking intuitively, we want $\psi_d(0)$ to simply compute $\chi_S(d)$, which we can achieve with the recursion theorem.

Assuming $S$ is computable, we have $\chi_S = \psi_e$ for some $e$. Consider the function $g$ so that $\psi_{g(z)}(0) = \psi_e(z) = \chi_S(z)$. We know $g$ is total computable from the s-m-n theorem. Therefore, by the recursion theorem, $g$ has a fixed point $d$ so that $\psi_d(0) = \psi_{g(d)}(0)$.

Then we have $$d \in X \leftrightarrow \psi_d(0) = 0 \leftrightarrow \psi_{g(d)}(0) = 0 \leftrightarrow \chi_S(d) = 0 \leftrightarrow d \not \in S.$$

Carl Mummert
  • 81,604