# Relations

• May 6th 2006, 07:09 AM
PhilipJ
Relations
"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
• May 6th 2006, 09:04 AM
topsquark
Quote:

Originally Posted by PhilipJ
"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.

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
• May 6th 2006, 10:09 AM
PhilipJ
(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?
• May 6th 2006, 01:45 PM
rgep
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)\}\$.
• May 6th 2006, 07:06 PM
ThePerfectHacker
Quote:

Originally Posted by rgep
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.

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.
• May 6th 2006, 11:03 PM
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.
• May 7th 2006, 08:35 AM
ThePerfectHacker
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.