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

• Jun 29th 2011, 08:36 PM
ikurwae89
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 ?
• Jun 29th 2011, 10:31 PM
godelproof
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.
• Jun 30th 2011, 03:25 AM
ikurwae89
Re: how to prove if a and b are recursively enumerable sets on N then so is
thanks.. much appreciated !! :)