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

Step by step solution

01

Explain the Equivalence relation

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

02

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.$.

Unlock Step-by-Step Solutions & Ace Your Exams!

• Full Textbook Solutions

  Get detailed explanations and key concepts

• Unlimited Al creation

  Al flashcards, explanations, exams and more...

• Ads-free access

  To over 500 millions flashcards

• Money-back guarantee

  We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!