Show $B= \{z \mid (\exists x)\; P(x,z)\}$ is a recursive enumerable set

Question

Let $B = \{z \mid (\exists x)\; P(x,z)\}$ and $P$ be a computable predicate. Show $B$ is a recursive enumerable set.

My attempt

As $P$ is a computable predicate then there is a program that computes it, therefore $B= \{z \mid (\exists x)(\exists t)\;\text{STP}^{(1)}(x,z,t)\} \Rightarrow B= \{z \mid \Phi(x)\downarrow\} = W_z$ and so $B$ is a recursive enumerable set.

Further info

$\text{STP}^{(n)} (x_1, \ldots, x_n, y,t)$ is a predicate that is true if the program number $y$ halts after $t$ or fewer steps on inputs $x_1, \ldots, x_n$.

Note: please note this is the first time I ever try to solve this kind of exercises, so even if I got everything wrong and nothing makes sense, every nudge in the right direction is really welcome.

Answer 1

Hint, do you know the argument for the countability of the rational numbers?

Just enumerate every pair $a,b$ of natural numbers and output the $b$ if $P(a,b)$ is true.

Other way, can you construct a machine that given a $b$, answers YES if there is an $a$ such that $P(a,b)$ is true?

Answer 2

Your set $B$ includes all programs $z$ that halt on some input. This has no connection to $P$. Your proof should start like so: Suppose that $P$ is computed by program number $y$, and should invoke $\mathrm{STP}^{(2)}$, since $P$ has two inputs.

Answer 3

In fact being able to express $B$ in that form and saying that $B$ is recursively enumerable are equivalent.

Here's a proof using Kleene Normal Form when $P$ is any partial recursive relation. First I'll show that if $B\subseteq\mathbb{N}^n$ is r.e., then there is a recursive relation $P\subseteq\mathbb{N}^{n+1}$ such that $$B(x_1,\ldots, x_n)\iff\exists y P(x_1,\ldots, x_n,y).$$

If $B=\emptyset$ the result is clear. Else let $f:\mathbb{N}\to\mathbb{N}^n$ be a total recursive function such that $B=\operatorname{range}(f)$. Then we have \begin{align*}B(x_1,\ldots, x_n) &\iff\exists y (f(y) = x_1,\ldots, x_n) \\ &\iff\exists y\forall i\le n (f_i(y) = x_i)\end{align*} which is in the desired form.

Now we show that there is a partial recursive function $f:\mathbb{N}^n\to\mathbb{N}$ such that $B=\operatorname{dom}(f)$. We can write $B(x_1,\ldots, x_n)\iff\exists y P(x_1,\ldots, x_n,y)$ where $P$ is a recursive relation. Then we simply take $$f(x_1,\ldots, x_n)=\mu y P(x_1,\ldots, x_n, y).$$ $f$ is recursive and $f(x_1,\ldots, x_n)\downarrow\iff B(x_1,\ldots, x_n)$.

Finally, we'll use the Kleene Normal form theorem get a primitive recursive function $f:\mathbb{N}\to\mathbb{N}^n$ such that $B=\operatorname{range}(f)$ or $B=\emptyset$. Indeed, write $B=\operatorname{dom}(f)$ for partial recursive $f$. Then, there are primitive recursive functions $U$ and $T$ and some $e\in\mathbb{N}$ such that $$f(x_1,\ldots, x_n)=U(\mu c T(e, \langle x_1,\ldots, x_n\rangle, c)).$$ Then $$B(x_1,\ldots, x_n)\iff f(x_1,\ldots, x_n)\downarrow\iff\exists c T(e,\langle x_1,\ldots, x_n\rangle, c),$$ which is in the form we wanted.

It is easy to see that the last condition implies the usual definition for r.e. sets, so we are done.