# Thread: how to prove if a and b are recursively enumerable sets on N then so is

1. ## how to prove if a and b are recursively enumerable sets on N then so is

a intersection b ??

is it enough to state that since some thing is RE then its also Recursive ?

2. ## Re: how to prove if a and b are recursively enumerable sets on N then so is

A set $S \subseteq \mathbb{N}$ is r.e. iff there exists a turing machine ${M}_{S}$ such that $\forall x \in S$, ${M}_{S}(x)=1$ and that $\forall x \notin S$, ${M}_{S}(x)$ doesn't stop.

Let ${M}_{A}$ and ${M}_{B}$ be such turing machines for your r.e. sets A and B respectively. It is easy to construct turing machine ${M}_{C}$ such that ${M}_{C}(x)=1$ iff ${M}_{A}(x)={M}_{B}(x)=1$ and ${M}_{C}(x)$ doesn't stop otherwise ( ${M}_{C}$ just alternates between ${M}_{A}$ and ${M}_{B}$ and output 1 iff both of them output 1).

So by the above construction $C$ is r.e. and $C=A\cap B$.

---------------------------------------------------
A set $S$ is recursive iff both $S$ and $\mathbb{N}-S$ are r.e.. So in our previous argument you need the stronger condition: ${M}_{S}(x)=1$ $\forall x \in S$ and ${M}_{S}(x)=0$ $\forall x \notin S$.
Any recursive set is also r.e., but not vice versa.

3. ## Re: how to prove if a and b are recursively enumerable sets on N then so is

thanks.. much appreciated !!