# Transitivity Question

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

## 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 on other sites
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 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 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 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 on other sites
Quote:
 Original post by VorpyActually, 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 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 on other sites
Quote:
Original post by Zipster
Quote:
 Original post by VorpyActually, 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 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 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.

1. 1
Rutin
32
2. 2
3. 3
4. 4
5. 5

• 13
• 70
• 11
• 10
• 14
• ### Forum Statistics

• Total Topics
632967
• Total Posts
3009571
• ### Who's Online (See full list)

There are no registered users currently online

×