Question

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

An equivalence relationis a binary relation which satisfies three properties:

• Reflexivity: localid="1659006645990" $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{y}\mathbf{)}\mathbf{\in }\mathit{R}$ for all $\mathit{X}\mathbf{\in }\mathit{S}$
• Symmetry: If $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{y}\mathbf{)}\mathbf{\in }\mathit{R}$ then $\mathbf{}\mathbf{(}\mathit{y}\mathbf{,}\mathit{x}\mathbf{)}\mathbf{\in }\mathit{R}$
• Transitivity: if $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{y}\mathbf{)}\mathbf{\in }\mathit{R}$ and $\mathbf{}\mathbf{(}\mathit{y}\mathbf{,}\mathit{z}\mathbf{)}\mathbf{\in }\mathit{R}$ then localid="1659006784500" $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{Z}\mathbf{)}\mathbf{\in }\mathit{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 partition set S into disjoint groups ${\mathit{S}}_{\mathbf{1}}\mathbf{,}{\mathit{S}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{S}}_{\mathbf{k}}$ (in other words, $\mathit{S}\mathbf{=}{\mathit{S}}_{\mathbf{1}}\mathbf{\cup }{\mathit{S}}_{\mathbf{2}}\mathbf{\cup }\mathbf{\dots }\mathbf{\cup }{\mathit{S}}_{\mathbf{k}}\mathit{a}\mathit{n}\mathit{d}{\mathit{S}}_{\mathbf{i}}\mathbf{\cap }{\mathit{S}}_{\mathbf{j}}\mathbf{=}\mathit{\varphi }\mathit{f}\mathit{o}\mathit{r}\mathit{a}\mathit{l}\mathit{l}\mathbf{}\mathit{i}\mathbf{\ne }\mathit{j}$ ) such that:

• Any two members of a group are related, that is, $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{y}\mathbf{)}\mathbf{\in }\mathit{R}$ for any localid="1659006702579" $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{y}\mathbf{)}\mathbf{\in }{\mathit{S}}_{\mathbf{i}}$, for any i .
• Members of different groups are not related, that is, for all $\mathbf{}\mathit{i}\mathbf{\ne }\mathit{j}$, for all localid="1659006762355" $\mathit{x}\mathbf{\in }{\mathit{S}}_{\mathbf{i}}$ and$\mathit{y}\mathbf{\in }{\mathit{S}}_{\mathbf{i}}$, we have $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{Z}\mathbf{)}\mathbf{\in }\mathit{R}$.

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

Short answer

It can be shown that equivalence relation partitions set $S$ into disjoint groups by the connected and disconnected branches.

Step-by-step solution

Explain the Equivalence relation

A relation is said to be in equivalence only if the relation satisfies reflexive, symmetry, and transitive properties.

Show that equivalence relation partitions set into disjoint groups.

Consider a set $S$ that has the partitions of an undirected graph. Consider any tow vertices x and y in the undirected graph.

In an undirected graph, the relation between the two vertices are equivalent to the binary equivalence$(x,y)\in R$for any$x,y\in S_i$, for any i .Each connected branch in the graph is the equivalence class.

Obviously, Each connected graph is disjoint and all vertices are connected and each connected branch is disconnected from each other.

Therefore, anequivalence relation can partition set $S$ into disjoint groups $S_1,S_2,\dots ,S_k.$.