Answer to Question #264916 in Discrete Mathematics for kalpana T

Question #264916

Let R ⊆ S × S be an equivalence relation on a set S. For an element x ∈ S, let

S(x) = {y ∈ S : (x, y) ∈ R}. Show that for every pair of elements x, y ∈ S, either

S(x) = S(y) or S(x) ∩ S(y) = ∅.



1
Expert's answer
2021-11-15T01:54:28-0500

Let RS×SR ⊆ S × S be an equivalence relation on a set S.S. For an element xS,x ∈ S, let S(x)={yS:(x,y)R}.S(x) = \{y ∈ S : (x, y) ∈ R\}. Let us show that for every pair of elements x,yS,x, y ∈ S, either S(x)=S(y)S(x) = S(y) or S(x)S(y)=.S(x) ∩ S(y) = ∅.

Let S(x)S(y).S(x) ∩ S(y) \ne ∅. Then there exists zS(x)S(y).z\in S(x) ∩ S(y). Let us show that in this case S(x)=S(y).S(x) = S(y).

Let aS(x).a\in S(x). Then (x,a)R.(x,a)\in R. Since zS(x),z\in S(x), we have that (x,z)R.(x,z)\in R. Taking into account that the relation RR is symmetric, we conclude that (z,x)R.(z,x)\in R. Then the transitivity of RR implies (z,a)R.(z,a)\in R. Since zS(y),z\in S(y), we get that (y,z)R,(y,z)\in R, and transitivity of RR implies (y,a)R.(y,a)\in R. Consequently, aS(y),a\in S(y), and hence S(x)S(y).S(x)\subseteq S(y).

Further, let aS(y).a\in S(y). Then (y,a)R.(y,a)\in R. Since zS(y),z\in S(y), we have that (y,z)R.(y,z)\in R. Taking into account that the relation is symmetric, we conclude that (z,y)R.(z,y)\in R. Then the transitivity of RR implies (z,a)R.(z,a)\in R. Since zS(x),z\in S(x), we get that (x,z)R,(x,z)\in R, and transitivity of RR implies (x,a)R.(x,a)\in R. Consequently, aS(x),a\in S(x), and hence S(y)S(x).S(y)\subseteq S(x).

Therefore, we get that if S(x)S(y),S(x) ∩ S(y) \ne ∅, then S(x)=S(y).S(x) = S(y).

We conclude that for every pair of elements x,yS,x, y ∈ S, either S(x)=S(y)S(x) = S(y) or S(x)S(y)=.S(x) ∩ S(y) = ∅.


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog