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 ?

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

A set is r.e. iff there exists a turing machine such that , and that , doesn't stop.

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

So by the above construction is r.e. and .

---------------------------------------------------

A set is recursive iff both and are r.e.. So in our previous argument you need the stronger condition: and .

Any recursive set is also r.e., but not vice versa.

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

thanks.. much appreciated !! :)