0

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.

Björn Friedrich
  • 3,747
AXN153
  • 1
  • Hello @AXN153. What is r.e.? What does the notation $K * \setminus B$ mean? – Björn Friedrich Dec 03 '15 at 09:01
  • @BjörnFriedrich From the context I'm guessing that r.e. = recursively enumerable (what some people nowdays call "computably enumerable), and that K*\B is somebody's weird notation for the complement of B. – bof Dec 03 '15 at 09:05
  • 1
    Hint for $B$: show directly that $x\in B$ is decidable. Namely, if $u+v=x$ (where $u,v\in\mathbb N$) then $u,v\le x$. Given a natural number $x,$ there are only finitely many natural numbers $\e x$; we can test each of those numbers for membership in $A,$ and from that we can tell whether $u+v=x$ has a solution with $u,b\in A.$ – bof Dec 03 '15 at 09:13
  • 1
    Hint for $C$: All you need here is that $A$ is r.e. Start enumerating the elements of $A$. Each time a new element of $A$ is produced, output all of the new differences $u-v$ which can be formed from the elements of $A$ that have been produced so far. If you prefer, enumerate $A$ in increasing order as $a_1\lt a_2\lt a_3\lt\dots$ and enumerate $C$ as $a_2-a_1,\ a_3-a_1,\ a_3-a_2,\ a_4-a_1,\ a_4-a_2,\dots.$ – bof Dec 03 '15 at 09:17
  • @bof Thank you for the hints, I understand how to explain it now. The notation K* indicated the set of strings over the alphabet K, so everything you assumed was correct. – AXN153 Dec 03 '15 at 10:22

1 Answers1

0

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.

Christopher Rose
  • 925