Results 1 to 7 of 7

Math Help - Relations

  1. #1
    Newbie
    Joined
    May 2006
    Posts
    9

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,100
    Thanks
    379
    Awards
    1
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2006
    Posts
    9
    (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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    For (a), let 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 \{a,b,c\} and let R = \{(a,a), (a,b), (b,b), (c,c)\} and S = \{(a,a), (b,b), (b,c), (c,c) \}. Check that R and S are transitive but R \cup S is not: consider a(R)b and b(S)c.

    For (c), let the underlying set be \{a,b\} and R = \{(a,a),(a,b),(b,a),(b,b)\} and S=\{(a,a),(b,b)\}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by rgep
    For (a), let 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 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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relations and Functions - Inverse Relations Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2011, 12:20 PM
  2. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  3. [SOLVED] Relations on A
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: November 21st 2010, 11:25 AM
  4. Relations in a set
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 5th 2010, 10:03 PM
  5. relations help (3)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 18th 2010, 04:49 AM

Search Tags


/mathhelpforum @mathhelpforum