• Advertisement
Sign in to follow this  

Transitivity Question

This topic is 3822 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

It may be that I am burnt from to much studying, but I fail to see how this is a proper counter example... Suppose P and Q are relations on A. If P and Q are transitive, must P U Q be transitive? I know the answer is no, but this counter example does not seem proper. Let A = {1, 2, 3} P = {(1,2)} and Q={(2,3)} I see that P U Q is not transitive, but in my mind I fail to see how P or Q is transitive. i.e. Vx,y,z in A(xPy and yPz -> xPz) Is all I have to do is show the consequent is false? If this is the case then it seems that I could also prove the same thing for symmetry, by constructing such a set.

Share this post


Link to post
Share on other sites
Advertisement
You're thinking clearly enough, P and Q are non-transitive, so that isn't a good example. And yes, when trying to prove something false, all it takes is one carefully constructed counter-example (which is why it's so much easier to prove things false than it is to prove things true).

[Edited by - Zipster on November 2, 2007 1:52:06 AM]

Share this post


Link to post
Share on other sites
I thought so. This is the counter example in the back of the book. Our professor gave a quiz on the last chapter (Relations) and this was one of the questions. For some reason I blanked. Tried to construct a formal proof, but got nowhere. Then proceeded to find a counter example. Ran out of time before I could find a proper one.

In my mind in order to construct a counter example you must maintain the truth value of the assumptions and show that the conclusion will always be false under at least one condition. For a second there I thought I had made a huge oversight on something very fundamental.

Thanks

Share this post


Link to post
Share on other sites
These sorts of proofs often become easier when you plug in concrete interpretations. Consider A to be the set of natural numbers, for instance, and make P and Q be arithmetically defined transitive relations. It's not hard to find a pair of them which disprove the statement.

Share this post


Link to post
Share on other sites
Actually, P and Q are transitive. With the definition of transitivity you gave, it is clearly impossible to prove that they are not transitive. In fact, it looks absolutely true that they are transitive to me.

If you can make a similiar proof that shows symmetric relations are not closed under unions, I'd like to see it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Vorpy
Actually, P and Q are transitive. With the definition of transitivity you gave, it is clearly impossible to prove that they are not transitive. In fact, it looks absolutely true that they are transitive to me.

If you can make a similiar proof that shows symmetric relations are not closed under unions, I'd like to see it.

You're right, it's a vacuous truth. Looks like I'm the one whose been awake for too long [rolleyes]

Share this post


Link to post
Share on other sites
Actually I did not post the exact question. Here it is from the book...

(R_sub_1 = R1 etc)

Suppose R1 and R2 are relations on A. If R1 and R2 are transitive, must R1 U R2 be transitive?

Counter Example: Let A = {1,2,3}. R1={(1,2)} R2={(2,3)}


Thanks Sneftel for the suggestion.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zipster
Quote:
Original post by Vorpy
Actually, P and Q are transitive. With the definition of transitivity you gave, it is clearly impossible to prove that they are not transitive. In fact, it looks absolutely true that they are transitive to me.

If you can make a similiar proof that shows symmetric relations are not closed under unions, I'd like to see it.

You're right, it's a vacuous truth. Looks like I'm the one whose been awake for too long [rolleyes]


Dam that vacuous truth. I see now.


Thanks.

Share this post


Link to post
Share on other sites
When faced with this type of problem, I usually find it easier to think of examples for which I have better intuitions than those tiny constructions.

For example, if A is the set of positions in a matrix with more than one row and more than one column, R1 means "being in the same column" and R2 means "being in the same row", then R1 U R2 means "being in the same column or row". Now it's clear that R1 and R2 are transitive but R1 U R2 isn't.

Share this post


Link to post
Share on other sites
Watch the schoolwork policy, folks...Forum FAQ. This is a site about game development, and not a general meeting place for discussing homework. At least the OP essentially disclosed that this was school related, gave some proof of their own analysis, and did not ask for an explicit answer. I do watch out and close posts that are blatant, and frankly the only reason I allowed this one to remain open is because the OP did have some discussion of their thought process indicating to me that they are indeed working to learn the material.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement