Printable View
"Let R and S be two relations on a set A. For each statement below, if it's true, prove it; if it's false, give a counterexample. Remember that R and S are sets of ordered pairs.
a.) If R is transitive and S is transitive, then R intersects S is transitive.
b.) If R is transitive and S is transitive, then R U (union) S is transitive.
c.) If R is transitive and S is transitive, then R - S is transitive.
I am thinking a and c are true, and b is false.
Many thanks.
Phil
Hmmm...I am thinking that a) is not true. Obviously R and S will agree on any point (a,b) in the intersection of R and S, but to be transitive we need another point (b,?). I see no reason why this point needs to belong to the intersection. Specifically we may have: "a R b and b R c thus a R c", but have "a S b and b S d thus a S d" where (b,c) and (b,d) do not belong to the intersection.Quote:
Originally Posted by PhilipJ
Now if there are no points (b,?) in the intersection, then R and S may be transitive "vacuously" or something, so it may still work. Someone please check me on this! :)
-Dan
(a) is true (and very straightforward to prove) [or so I thought], but relooking at it, I think (b) and (c) are both false.
Take A to be Z, the integers; the relation 'not equals' on Z
is clearly not transitive. There are familiar transitive
relations R and S on Z whose union is 'not equals', and it's
also not hard to find transitive relations R and S on Z
whose difference is 'not equals'.
Hmmm.
Anyone got a take, and can perhaps prove it?
For (a), let $\displaystyle T = R \cap S$: that is, x(T)y is true iff both x(R)y and x(S)y. Suppose that R, S are transitive, that is, X(T)y and y(R)z implies x(R)z and similarly for S. Now suppose that x(T)y and y(T)z. Then x(R)y and y(R) z, and also x(S)y and y(S)z. From transitivity of R and S we deduce that x(R)z and x(S)z. So x(T)z.
For (b), let the underlying set be $\displaystyle \{a,b,c\}$ and let $\displaystyle R = \{(a,a), (a,b), (b,b), (c,c)\}$ and $\displaystyle S = \{(a,a), (b,b), (b,c), (c,c) \}$. Check that R and S are transitive but $\displaystyle R \cup S$ is not: consider a(R)b and b(S)c.
For (c), let the underlying set be $\displaystyle \{a,b\}$ and $\displaystyle R = \{(a,a),(a,b),(b,a),(b,b)\}$ and $\displaystyle S=\{(a,a),(b,b)\}$.
There is one flaw in your proof. You probably noticed this but. You assumed that $\displaystyle R\cap S\not = \{\}$, by taking elements from these sets. You should have considered two cases when their intersection is non-empty which you did and when their intersection is empty. When their intersection is empty the transitive property is never violated and thus the proof is complete.Quote:
Originally Posted by rgep
No, there's no flaw, except possibly for informal wording. If you replace the wwords "Suppose that x(T)y ..." by "For all x,y,z such that x(T)y ..." you see that the statement remains true even when the relation T is empty.
My fault sorry. I realized the proof is still good only on the next day. To late to delete my embarassing post.Quote:
Originally Posted by rgep
