Transitivity Question
Author
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.
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]
[Edited by - Zipster on November 2, 2007 1:52:06 AM]
Author
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
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
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.
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.
If you can make a similiar proof that shows symmetric relations are not closed under unions, I'd like to see it.
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]
Author
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.
(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.
Author
Quote:Original post by ZipsterQuote: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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
