Thread: 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.

Originally Posted by jimbob11

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.

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.

Originally Posted by jimbob11

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.