Let S be a finite set. A binary relation on S is simply a collection R of ordered pairs

QUESTION:

Let S be a finite set. A binary relation on S is simply a collection R of ordered pairs (x, y) \(\in S \times S\). For instance, S might be a set of people, and each such pair (x, y) \(\in R\) might mean “x knows y.”

An equivalence relation is a binary relation which satisfies three properties:

Reflexivity: (x, x) \(\in R\) for all \(x \in S\)

Symmetry: if (x, y) \(\in R\) then (y, x) \(\in R\)

Transitivity: if (x, y) \(\in R\) and (y, z) \(\in R\) then (x, z) \(\in R\)

For instance, the binary relation “has the same birthday as” is an equivalence relation, whereas “is the father of” is not, since it violates all three properties.

Show that an equivalence relation partitions set S into disjoint groups \(S_{1}, S_{2}, \ldots, S_{k}\) (in other words, \(S=S_{1} \cup S_{2} \cup \cdots \cup S_{k}\) and \(S_{i} \cap S_{j}=\emptyset\) for all \(i \neq j\)) such that:

Any two members of a group are related, that is, (x, y) \(\in R\) for any x, y \in S_{i} , for any i.

Members of different groups are not related, that is, for all \(i \neq j\), for all \(x \in S_{i}\) and \(y \in S_{j}\), we have (x, y) \(\in R\).

(Hint: Represent an equivalence relation by an undirected graph.)