1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    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


    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

    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