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)=∅. Then there exists z∈S(x)∩S(y). Let us show that in this case S(x)=S(y).
Let a∈S(x). Then (x,a)∈R. Since z∈S(x), we have that (x,z)∈R. Taking into account that the relation R is symmetric, we conclude that (z,x)∈R. Then the transitivity of R implies (z,a)∈R. Since z∈S(y), we get that (y,z)∈R, and transitivity of R implies (y,a)∈R. Consequently, a∈S(y), and hence S(x)⊆S(y).
Further, let a∈S(y). Then (y,a)∈R. Since z∈S(y), we have that (y,z)∈R. Taking into account that the relation is symmetric, we conclude that (z,y)∈R. Then the transitivity of R implies (z,a)∈R. Since z∈S(x), we get that (x,z)∈R, and transitivity of R implies (x,a)∈R. Consequently, a∈S(x), and hence S(y)⊆S(x).
Therefore, we get that if S(x)∩S(y)=∅, 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)=∅.
Comments
Leave a comment