An example given for a relation R where its negation and itself are not semi-decidable was:$R(x,y)$ holds iff $y = 0$ then $R_{HALT}(x)$ holds, otherwise $y = 1$ and $R_{HALT}(x)$ does not hold.It's stated with the assumption that the proof is trivial (which for most it probably is), but I am struggling to see why it is the case. Can anyone run me through why it is true?
Why is it true that the relation R and its negation are not semi decidable?
computability;undecidability;halting problem;semi decidability
If the relation $R$ was semi-decidable, then the halting problem would be decidable: if you want to know whether program $x$ terminates, just enumerate the elements of $R$ until you find either $(x,0)$ or $(x,1)$. In the first case, output $x$ halts; in the second, $x$ does not halt. One of these is guaranteed to happen, so you have a decider for the halting problem, contradicting the undecidability of that problem.The argument for the complement of $R$ is nearly identical: observe that $\overline{R} = \{(x,1-y)\mid (x,y)\in R\}$.