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

[Servo888]

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 R \cup S 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 R \cup S 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 explanation; and I don't even know if it's right. If anybody could help me out, that would be great.

2) If R \cap S 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.

 

[HallsofIvy]

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 R \cup S 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 R \cup S 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 explanation; and I don't even know if it's right. If anybody could help me out, that would be great.

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 R \cup S is?

2) If R \cap S 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.

Yes, a pair (x,x) is in R \cap S then it must be in both R and S.

 

[Servo888]

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 R \cup S is?

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 R \cup S is", is where I draw a blank.

[EDIT] What would a reflexive relation of R \cup S be? aRa?

 

[honestrosewater]

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 X². 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?

 

[Servo888]

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.