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

• Jun 29th 2011, 07: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, 09:31 PM
godelproof
Re: how to prove if a and b are recursively enumerable sets on N then so is
A set $\displaystyle S \subseteq \mathbb{N}$ is r.e. iff there exists a turing machine $\displaystyle {M}_{S}$ such that $\displaystyle \forall x \in S$, $\displaystyle {M}_{S}(x)=1$ and that $\displaystyle \forall x \notin S$, $\displaystyle {M}_{S}(x)$ doesn't stop.

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

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

---------------------------------------------------
A set $\displaystyle S$ is recursive iff both $\displaystyle S$ and $\displaystyle \mathbb{N}-S$ are r.e.. So in our previous argument you need the stronger condition: $\displaystyle {M}_{S}(x)=1$ $\displaystyle \forall x \in S$ and $\displaystyle {M}_{S}(x)=0$ $\displaystyle \forall x \notin S$.
Any recursive set is also r.e., but not vice versa.
• Jun 30th 2011, 02:25 AM
ikurwae89
Re: how to prove if a and b are recursively enumerable sets on N then so is
thanks.. much appreciated !! :)