3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You will have to tell us what STP is. Also, when you use the fact that $P$ is computable in this way, you probably want to use the index of a program computing it. $\endgroup$ – Yuval Filmus Sep 4 '13 at 14:37
  • $\begingroup$ @YuvalFilmus added what $\text{STP}$ is. I'm afraid I don't understand what you mean by "use the index of a program computing it", can you please be more clear? $\endgroup$ – haunted85 Sep 4 '13 at 14:47
2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am a bit confused when you say all programs $z$ isn't it true that if $P$ is a program then $z = \#(P)$ and therefore every program has a unique $z$ number? $\endgroup$ – haunted85 Sep 4 '13 at 16:15
  • $\begingroup$ Your set $B$ includes a program $z$ iff $z$ halts on some input. On the other hand, $P$ is a predicate, not a program. Since $P$ is computable, it is computed by some program. $\endgroup$ – Yuval Filmus Sep 4 '13 at 16:28
  • $\begingroup$ Perhaps you would like to review basic logic and basic set theory first, as well as mathematical English. $\endgroup$ – Yuval Filmus Sep 4 '13 at 16:29
  • $\begingroup$ Oops... I understand your remark and thank you for your explanation, but I did a poor letter choice, I didn't mean to refer to the predicate mentioned in my question, I was just considering a generic program $P$. $\endgroup$ – haunted85 Sep 4 '13 at 16:31
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.