Explain why these sets are recursive or r.e.

57 Views Asked by At

A set $A \subseteq \mathbb N$ is recursive. Working from an informal idea of "computability" explain why the set

$B = \big\{ x \in \mathbb N : \exists u,v \in A, u+v=x \big\}$

is recursive and the set

$C = \big\{ x \in \mathbb N : \exists u,v \in A, u-v=x \big\}$

is r.e.

I believe that I need to explain why both $B$ and $K*\setminus B$ are r.e, and why $K*\setminus C$ is not r.e., but I don't really know how to go about doing this. Hints are much appreciated.

1

There are 1 best solutions below

0
On

Regarding B, given an x, we only have to check the members u,v in A smaller than x (which are finite in number) and see if u+v=x. Once we check all such members in A we will be able to determine if x is in B or not. Hence, B is recursive.

Regarding C, given an x, we have to run through all members u in A and for all v< u in A we must see if if u-v=x. As long as A is infinite, this process will never terminate until we find such an u and v< u. We can never know if x is NOT in C, because there will always be more members in A to check, we can only know if x IS in C, which will be when the process stops. Hence, C is r.e.