# Computability: Proving a predicate is not recursively enumerable

Let P(p) <=> for each x, comp(p,x) is defined.

Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?

• What is "comp(p,x)"? – dkaeae May 15 '19 at 7:31
• Presumably, "comp(p,x) is defined" is the same as program $p$ halting on input $x$. Your predicate then states that $p$ is total, and is known to be $\Pi_2$-complete. – Yuval Filmus May 15 '19 at 8:04

Show that your predicate is coRE-hard, that is, every coRE predicate reduces to it. If your predicate were RE, then it would follow that RE=coRE, which is known to be false.

The rest of the answer assumes that "comp(p,x) is defined" is the same as "program $$p$$ halts on input $$x$$".

In order to show that your predicate is coRE-hard, you need to show that for every coRE predicate $$Q$$ there is a computable function $$f$$ such that $$Q(z)$$ iff $$P(f(z))$$. A predicate $$Q$$ is coRE if there is a computable function $$q$$ such that $$Q(z)$$ iff for all $$x$$, $$q(z,x)$$. Hence we need

for all $$x$$, $$q(z,x)$$ iff for all $$x$$, $$f(z)$$ halts on $$x$$.

You take it from here.

(In fact, your predicate is $$\Pi_2$$-complete.)

• Thanks. I was thinking about defining f(q,y) that returns the code of g. With g being g(x) = 0 if not T(q,y,x) and undefined otherwise. (T Kleene predicate). Then use that f – A. Othmane May 15 '19 at 8:29
• Nobody here can be assumed to know your notations, neither "comp" nor "T". Try to use "program $p$ halts on $x$", "program $p$ accepts $x$", and the like. – Yuval Filmus May 15 '19 at 8:30
• Duly noted. This is my second post as my first one was this exact question but in the wrong section – A. Othmane May 15 '19 at 8:34
• Alternatively, you can keep your notations, but first define them. – Yuval Filmus May 15 '19 at 8:35