Let R and S be equivalence relations on a set X. (A) Prove that R intersect S is
ID: 2967073 • Letter: L
Question
Let R and S be equivalence relations on a set X. (A) Prove that R intersect S is an equivalence relation on X. (B) Prove that for each x element of X, (R intersect S)[X]=R[X] intersect S[X]. Let R and S be equivalence relations on a set X. (A) Prove that R intersect S is an equivalence relation on X. (B) Prove that for each x element of X, (R intersect S)[X]=R[X] intersect S[X]. (A) Prove that R intersect S is an equivalence relation on X. (B) Prove that for each x element of X, (R intersect S)[X]=R[X] intersect S[X].Explanation / Answer
I will use RS for R intersect S, R+S for R union S
to show eq rel, we must show reflexive, symmetric, transitive.
let x be in X. Then (x,x) is in R and in S, since they are eq rels, so (x,x) is in RS
let (x,y) be in RS. Then (y,x) is in R and in S since they are eq rels, so (y,x) is in RS.
let (x,y) and (y,z) be in RS. Then (x,z) is in R and in S since they are eq rels, so (x,z) is in RS.
Therefore RS is an eq rel.
let X be the integers. Let R be {(x,y) | y-x is even}
let S = {(x,y) | y-x is divisible by 3}
Now (2,0) and (0,3) are in R+S since (2,0) in R and (0,3) in S
But (2,3) is not in R+S, so transitivity fails. R+S not an eq rel.
(R+S)* is an eq rel. reflexiveness is trivial, and transitivity and symmetry follow from the definition of *.
Now if T is any eq rel where R+S is a subset of T, let (u,v) be in (R+S)*. Then there is x in X with (x,u) or (u,x) in R and (x, v) or (v,x) in S Since T contains these members, T also contains (u,v). So (R+S)* is a subset of T
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.