Answer to Question #140816 in Discrete Mathematics for Mahesh Daulat Rayate

Question

Given set S = {1, 2, 3, 4, 5, 6} and a partition of S,
A1 = {1, 2, 3}
A2 = {4, 5}
A3 = {6}
Find the ordered pairs that make up the equivalence relation R produced by that
partition

Answer 1

Given set ,

$S=\{ 1,2,3,4,5,6\}$ and a partition of $S$ .

$A_1=\{ 1,2,3\}$ ,$A_2=\{ 4,5\}$ and

$A_3=\{6\}$ .

Let $P=\{ A_1,A_2,A_3\}$ be the given partition of $S$ .

Let a relation $R$ be defined in $S$ such that ,

$R=\{ (a,b):$ $a \ and \ b$ are the same number as of the partition $\}$

Then the relation $R$ can listed as

$R=\{ (1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),$

$(3,1),(2,3),(3,2),(4,4),(5,5),(4,5)$

$(5,4),(6,6)\}$

Claim: $R$ is an equivalence relation in $S$

Clearly, (1) $R$ is reflexive as $(x,x)\in R \ \forall \ x\in S$ .

(2) $R$ is symmetric as $(x,y)\in R \implies (y,x)\in R$

Because if $x \ and \ y$ are member of the same set of partition ,then $y \ and \ x$ are member of the same set .

(3) $R$ is transitive .

Let $(x,y)\in R$ and $(y,z)\in R$

$\implies$ $(x,y)$ belong to the some set $A_i$

in the partition and $(y,z)$ belong to the some set $A_j$ in the partition.

Since $y\in A_i$ and also $y\in A_j$ ,therefore we have $y\in A_i \cap A_j$

i,e $A_i \cap A_j \neq \phi$ .

But

$A_i ,A_j \in P \implies A_i \cap A_j=\phi$

Hence $A_i \cap A_j \neq \phi \implies A_i =A_j$

$\therefore x,y,z$ belong to same partition .

$\therefore (x,z)\in R$ .

Hence , $R$ is an equivalence relation.