Results 1 to 5 of 5

Math Help - logic proof

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    73

    logic proof

    Show that the ancestral R* of a relation R has the following properties:

    1)for every a R*aa
    2)for all a and b if Rab then R*ab
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765
    What is the definition of R*? Sometimes the properties you mention hold by definition.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2009
    Posts
    73
    definition of an ancestor is that
    R*xy holds when there is a finite
    chain of objects a1,...,an, where x=a1 and y=an, such that
    R(a1,a2),...,R(an-1,an)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765
    Then your claims hold by definition: 1) when n = 0 and 2) when n = 1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by scubasteve123 View Post
    definition of an ancestor is that
    R*xy holds when there is a finite
    chain of objects a1,...,an, where x=a1 and y=an, such that
    R(a1,a2),...,R(an-1,an)
    Usually we say 'sequence' rather than 'chain', as usually 'chain' is a different notion.

    Also, I take it that n greater than 0.

    Anyway, as far as I can tell, what you are being asked to show is not true:

    Counterxample:

    Let R = {<a b>} with a not equal to b.
    Then R* = {<a b>} and neither <a a> nor <b a> are in R*.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logic and Proof help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 26th 2011, 08:57 AM
  2. p and q logic proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 24th 2010, 03:59 AM
  3. Is my logic for this proof okay?
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: February 3rd 2010, 03:18 PM
  4. Logic Proof
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 26th 2008, 02:24 PM
  5. logic and proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 23rd 2007, 12:30 PM

Search Tags


/mathhelpforum @mathhelpforum