Answer to Question #264586 in Discrete Mathematics for Abhijeet Kaur

Question

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) = ∅.

Answer 1

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\}.$ Let us show that for every pair of elements $x, y ∈ S,$ either $S(x) = S(y)$ or $S(x) ∩ S(y) = ∅.$

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

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

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

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

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