91影视

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{鈭�}\mathit{S}\mathbf{脳}\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{鈭�}\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{鈭�}\mathit{R}$ for all $\mathit{X}\mathbf{鈭�}\mathit{S}$
• Symmetry: If $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{y}\mathbf{)}\mathbf{鈭�}\mathit{R}$ then $\mathbf{}\mathbf{(}\mathit{y}\mathbf{,}\mathit{x}\mathbf{)}\mathbf{鈭�}\mathit{R}$
• Transitivity: if $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{y}\mathbf{)}\mathbf{鈭�}\mathit{R}$ and $\mathbf{}\mathbf{(}\mathit{y}\mathbf{,}\mathit{z}\mathbf{)}\mathbf{鈭�}\mathit{R}$ then localid="1659006784500" $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{Z}\mathbf{)}\mathbf{鈭�}\mathit{R}$

For instance, the binary relation 鈥渉as the same birthday as鈥� is an equivalence relation, whereas 鈥渋s 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{鈥�}\mathbf{,}{\mathit{S}}_{\mathbf{k}}$ (in other words, $\mathit{S}\mathbf{=}{\mathit{S}}_{\mathbf{1}}\mathbf{鈭�}{\mathit{S}}_{\mathbf{2}}\mathbf{鈭�}\mathbf{鈥�}\mathbf{鈭�}{\mathit{S}}_{\mathbf{k}}\mathit{a}\mathit{n}\mathit{d}{\mathit{S}}_{\mathbf{i}}\mathbf{鈭�}{\mathit{S}}_{\mathbf{j}}\mathbf{=}\mathit{蠒}\mathit{f}\mathit{o}\mathit{r}\mathit{a}\mathit{l}\mathit{l}\mathbf{}\mathit{i}\mathbf{鈮�}\mathit{j}$ ) such that:

• Any two members of a group are related, that is, $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{y}\mathbf{)}\mathbf{鈭�}\mathit{R}$ for any localid="1659006702579" $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{y}\mathbf{)}\mathbf{鈭�}{\mathit{S}}_{\mathbf{i}}$, for any i .
• Members of different groups are not related, that is, for all $\mathbf{}\mathit{i}\mathbf{鈮�}\mathit{j}$, for all localid="1659006762355" $\mathit{x}\mathbf{鈭�}{\mathit{S}}_{\mathbf{i}}$ and$\mathit{y}\mathbf{鈭�}{\mathit{S}}_{\mathbf{i}}$, we have $\mathbf{}\mathbf{(}\mathit{x}\mathbf{,}\mathit{Z}\mathbf{)}\mathbf{鈭�}\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)鈭�R$for any$x,y鈭�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,鈥�,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.

Over 30 million students worldwide already upgrade their learning with 91影视!