Results 1 to 3 of 3

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

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    54

    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 ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2009
    Posts
    146

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2010
    Posts
    54

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

    thanks.. much appreciated !!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. sets prove
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2009, 01:58 PM
  2. sets prove
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 29th 2009, 07:03 AM
  3. Replies: 0
    Last Post: April 10th 2009, 09:29 AM
  4. sets prove
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 15th 2008, 07:55 AM
  5. Another sets prove
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 12th 2008, 06:28 AM

Search Tags


/mathhelpforum @mathhelpforum