Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: [Discrete Math] Relations, (R subset S) / (R Intersects S)

  1. Feb 19, 2006 #1
    Ok; this is another thread that covers two questions. I didn't want to mix them with my previous post; it's from the same 'section' but the questions are different. If any mods have issues with this, please say so.

    1) If [tex]R \cup S[/tex] is reflexive, then either R is reflexive or S is reflexive.

    * I see this as false; If there's some (x,x) such that xRx in R, then since R is in [tex]R \cup S[/tex] that relation must also be in S. So they would both have to be reflexive. My question, I don't think this is enough of an explaination; and I don't even know if it's right. If anybody could help me out, that would be great.

    2) If [tex]R \cap S[/tex] is reflexive, then both R is reflexive and S is reflexive.

    * True, since your talking about the intersection of R and S. If x is related to x in R, then this must also hold true for S since x would also be an element in S, and therefore related to x. I think I'm hitting something close to the answer... But I'm not sure.
     
  2. jcsd
  3. Feb 19, 2006 #2

    HallsofIvy

    User Avatar
    Science Advisor

    You might consider giving a counter-example: Suppose X= {a, b, c}. Can you think of relations R and S on X that are not reflexive but such that [tex]R \cup S[/tex] is?

    Yes, a pair (x,x) is in [tex]R \cap S[/tex] then it must be in both R and S.
     
    Last edited by a moderator: Feb 19, 2006
  4. Feb 19, 2006 #3
    No real clue to what you mean... (hehe sorry, mathematics is not my strong side). I understand your looking for a relation R and S, from the set X with the elements a,b,c that are NOT reflexive, "but such that [tex]R \cup S[/tex] is", is where I draw a blank.

    [EDIT] What would a reflexive relation of [tex]R \cup S[/tex] be? aRa?
     
  5. Feb 19, 2006 #4

    honestrosewater

    User Avatar
    Gold Member

    A binary relation R on a set X is just a set of ordered pairs whose terms are members of X, i.e., R is a subset of X2. If R and S are sets of ordered pairs, their union (and nonempty intersection) is also a set of ordered pairs a.k.a. a binary relation. If you write xRx, you would also write xRuSx.

    1) To construct your counterexample, you can assume that RuS is reflexive and try to make both R and S fail to be reflexive -- while still keeping RuS reflexive. For R to fail to be reflexive, there must exist some x in X such that (x, x) is not in R, right? Same for S. Say there does exist some x in X such that (x, x) is not in R. Can't (x, x) still be in RuS as long as (x, x) is in S?
     
    Last edited: Feb 19, 2006
  6. Feb 21, 2006 #5
    Solution

    R = {(2,2),(3,3)}, S = {(1,1)}, X = {1,2,3}
    R = not reflexive, S = not reflexive
    R U S is reflexive =-).

    That was tricky.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook