Union, intersection, set theoretic difference of recursively enumerable sets

Question

Forgive me for asking though some of this has been asked/answered elsewhere and there are many examples on the internet; I ask again because I am doing a Maths course (not computer science) and we don't learn about Turing machines or decidability etc and thus I can't understand many of these explanations.

For my course, a recursively enumerable set R is defined as:

• A set that is the range of some partial recursive function $f: \Bbb{N} \rightarrow \Bbb{N}$
• A set that is either empty or the range of a (primitive) recursive function $g: \Bbb{N} \rightarrow \Bbb{N}$
• A set that is the domain of a partial recursive function $h: \Bbb{N} \rightarrow \Bbb{N}$

Question: If A,B are recursively enumerable, then decide (with proof or counterexample) whether or not the following are recursively enumerable:

$C=A\cap B$; $D=A\cup B$ and $E=A\setminus B$ where $A\setminus B$ is the set theoretic difference.

My thoughts:

$D$ is clearly recursively enumerable as if $A,B$ are empty then the result is trivial. So we assume that each are nonempty and the range of recursive functions and $f$ and $g$ and define: $$h(0)=f(0), h(1)=g(0), h(2)=f(1), h(3)=f(1), h(4)=f(2),\ldots$$ and so on. Thus, $h$ consists of alternate values of $f$ and $g$. Then clearly $D$ is the range of $h$ - a recursive function - and so is recursively enumerable.

Similarly, $C$ is recursively enumerable because A and B are the domains of partial recursive functions and if we denote them $k,l$ respectively, then $C$ is just the domain of $k+l$

I am not so sure about the last part. I suspect that $E$ is not recursively enumerable because I know that a set $A$ is recursive if and only if both $A$ and its complement are recursively enumerable. Since not all sets are recursive, there must be cases where $A$ is recursively enumerable but is complement is not. In this case, $\Bbb{N}\setminus A$ would provide a counterexample. I can't, however, think of an actual example. Any help would be greatly appreciated :)

Answer 1

In my opinion, the most useful characterization is that a set $\def\nn{\mathbb{N}}$$S \subseteq \nn$ is RE (recursively enumerable) if and only if it is the set accepted by some program $P$ ($P$ on input $x$ outputs "yes" if and only if $x \in S$). Note that since programs may not halt, simply negating the output of $P$ would not in general give a program that accepts the complement of an RE set, since there may be inputs on which $P$ does not output anything at all.

A set is said to be coRE if and only if its complement is RE. The easiest way to show the existence of an RE set that is not coRE is via the halting problem or similar. Let $H$ be the set of pairs $(P,x)$ such that that $P$ halts on $x$. $H$ is clearly RE because we just simulate $P$ on $x$ and accept if it halts. But $H$ is not coRE, otherwise let $D$ be a decider for $H$ and consider the program $Q$ that takes input $P$ and halts if and only if $\neg D(P,P)$, which means that $Q(Q)$ halts if and only if $\neg D(Q,Q)$, which is a contradiction.