# proof that specific disjoint sets are recursively enumerable, but don't lie in a decidable set and its complement

let's call a set $$A \subseteq \mathbb{N}$$ recursively enumerable if it's "partial characteristic function" $$\tilde{\chi}_A$$ is computable, whereby $$\tilde{\chi}_A$$ is defined as: $$\tilde{\chi}_A$$:= 1, if $$x \in A$$ and $$\tilde{\chi}_A$$ is undefined otherwise.

Now for $$i = 0,1$$ let $$P_i$$ be the set of all programmes p that terminate for input p and have output i. It's clear that $$P_0 \cap P_1 = \emptyset$$.
I'd be glad if you could help me with showing that the sets $$P_0$$ and $$P_1$$ are recursively enumerable, but that there's no decidable set E with $$P_0 \subseteq E$$, $$P_1 \subseteq \mathbb{N}\backslash E$$.

Looking forward to your suggestions!

The partial characteristic function of $$P_0$$ is computable by the algorithm: "On input $$p$$, run program $$p$$ with input $$p$$; if and when it terminates with output $$0$$, print $$1$$." $$P_1$$ is recursively enumerable similarly.
If they were separated by a decidable set $$E$$ as in the question, let $$p$$ be a program that outputs $$1$$ when $$p\in E$$ and outputs $$0$$ when $$p\notin E$$, i.e., $$p$$ computes the characteristic function of $$E$$. What would $$p$$ do when fed input $$p$$? It must eventually halt and output $$0$$ or $$1$$, since that's all $$p$$ ever does on any input. If it outputs $$0$$, then that means $$p\in P_0\subseteq E$$, so, by our choice of $$p$$, it should, on input $$p$$, compute $$1$$. Similarly, if $$p$$ on input $$p$$ outputs $$1$$, then $$p\in P_1$$, so $$p\notin E$$, and $$p$$ on input $$p$$ should output $$0$$. So we have a contradiction in either case. Therefore, no such program $$p$$ can exist.
• @Studentu No, I meant what I wrote. If and when the computation of program $p$ on input $p$ terminates with output $0$, this shows that $p\in P_0$, and therefore the partial characteristic function of $P_0$ (as in the first paragraph of the question)is defined at $p$ and has value $1$ (not $0$) there. – Andreas Blass Jan 6 at 16:15
• Yeah, this part I understood. This is the contradiction we want. But for simply considering a program $P_0$ in the beginning, you wrote The partial characteristic function of $P_0$ is computable by the algorithm: "On input p, run program p with input p; if and when it terminates with output 0, print 1." So why "print 1"? Did you just write this to emphasize that the partial characteristic function has output 1 and therefore $P_0$ is recursively enumerable? – Studentu Jan 6 at 16:42
• @Studentu To prove that $P_0$ is recursively enumerable, using the definition in the first paragraph of the question, I must give a program that computes the partial characteristic function of $P_0$. That partial characteristic function has (still quoting the definition) value $1$, not $0$, wherever it is defined. So a program that computes it had better print $1$'s not $0$'s. – Andreas Blass Jan 6 at 16:48