Results 1 to 4 of 4

Math Help - can't prove proposition about transitive trees.

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    6

    can't prove proposition about transitive trees.

    I need to prove: (T,S) is a transitive tree iff (T, S<) is a tree (where S< represents the immediate predecessor relation given by s S< t iff s S t and moreover s S v and v S t for holds for no v in T).

    I proved the ==> direction by its contrapositive, but I'm thinking the <== direction is false. What happens if S< simply equals S. We know S< isn't transitive from the definition - so (T,S) wouldn't be a transitive tree. If this isn't a counterexample, let me know what I'm missing here.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by jimbob11 View Post
    I need to prove: (T,S) is a transitive tree iff (T, S<) is a tree (where S< represents the immediate predecessor relation given by s S< t iff s S t and moreover s S v and v S t for holds for no v in T).

    I proved the ==> direction by its contrapositive, but I'm thinking the <== direction is false. What happens if S< simply equals S. We know S< isn't transitive from the definition - so (T,S) wouldn't be a transitive tree. If this isn't a counterexample, let me know what I'm missing here.
    I guess I am not the only one not familiar with the terminology.
    Obviously the OP uses book Modal logic By Patrick Blackburn, Maarten de Rijke, Yde Venema
    - it is exercise 1.1.4 from this book.

    I think your counterexample works, but if you change the claim to:
    "Let S be a SPO on T. (T,S) is a transitive tree if (T,S<) is a tree."
    then it should work.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2010
    Posts
    6
    Yes. I guess in this case the pf is trivial since a strict partial ordering is already transitive by defn. I'm extremely impressed that you found the reference. I should've included it, but didn't realize their terminology was idiosyncratic.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by jimbob11 View Post
    Yes. I guess in this case the pf is trivial since a strict partial ordering is already transitive by defn. I'm extremely impressed that you found the reference. I should've included it, but didn't realize their terminology was idiosyncratic.
    It wasn't that difficult to find - I've just searched for "transitive tree" in google books.

    BTW as far as this book is concerned, here's a part of a review by by Manuel Bremer SpringerLink - Minds and Machines, Volume 15, Number 1
    Further on, given the abstract approach, the book – although mostly clearly written – is not easy. The exercises are often far from trivial, and no solutions are provided. So this is not – as again the back cover has it – ‘‘both for novices and for more experienced readers’’ or ‘‘ideal for anyone wanting to learn modern modal logic’’. Novices will likely be frustrated if they try the book on their own. Crucial lemmas (like Lindenbaum’s Lemma) are left as an ‘‘exercise to the reader’’ and having not come up with the proof the overall picture may have gaps.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove transitive relations
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 21st 2010, 02:35 PM
  2. Prove or disprove that R^4 is a transitive relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 16th 2010, 04:52 PM
  3. Prove this proposition
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 22nd 2009, 07:41 AM
  4. prove the proposition
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: September 8th 2009, 12:48 PM
  5. Prove a Proposition
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 16th 2008, 03:30 PM

Search Tags


/mathhelpforum @mathhelpforum