Re: Is P(x,y) Recursively Enumerable if P(N,x) is for every N?

David C. Ullrich wrote:
On Tue, 5 Feb 2008 09:46:55 -0800 (PST), Charlie-Boo
<shymathguy@xxxxxxxxx> wrote:

Is P(x,y) Recursively Enumerable if P(N,x) is for every N?

If for relation P over the natural numbers for all values of N the set
{x|P(N,x) holds} is r.e., then is {(x,y)|P(x,y)} necessarily r.e.?

I don't have a counterexample in my pocket but I doubt that
this is true.

The obvious approach to defining an algorithm to enumerate
P fails unless we have an algorithm that takes N as input
and outputs an algorithm to enumerate P(N,x); the hypothesis
that such an algorithm exists for every N does not imply this.

C-B

David C. Ullrich

Just fix any non-r.e. subset X of the natural numbers and let P(i,j)
hold if and only if both i = 0 and j is an element of X. For each j the
set {i: P(i,j)} is either {} or {0}, and so is recursive. But X is
Turing reducible to P (since j is in X iff P(0,j)) so P cannot be r.e.

Robert E. Beaudoin
.

Relevant Pages