Let A = {1,2,3,4,5} Let R = {(1,1), (1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4),(5,5)} and

S = {(1,1)(2,2),(3,3),(4,4),(4,5),(5,4)(5,5)} be the relation on A. Find the smallest equivalence relation containing the relation R and C.

Solution: Let A = {1,2,3,4,5}

R = {(1,1)(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4),(5,5)}

S = {(1,1)(2,2),(3,3),(4,4),(4,5),(5,4)(5,5)}

$\therefore$ $M_R = \begin{matrix} \Bigg [1 1 0 0 0 \\ 1 1 0 0 0 \\ 0 0 1 1 0 \\ 0 0 1 1 0 \\ 0 0 0 0 1 \Bigg] \end{matrix}$

$M_s = \begin{matrix} [1 0 0 0 0 \\ 0 1 0 0 0 \\ 0 0 1 0 0 \\ 0 0 0 1 1 \\ 0 0 0 1 1 ] \end{matrix}$

Step 1: Cal wo = MRus = MR.V.ms

$\therefore$ $w_o = M_{Rus} $ = MR \ VMs = $\begin{matrix} [ 1 1 0 0 0 \\ 1 1 0 0 0 \\ 0 0 1 1 0 \\ 0 0 1 1 1 \\ 0 0 0 1 1 ] \end{matrix}$

Using wars-halls find till $w_5$

Step 2: Cal $w_1$

$C_1$ - No. of 1's at c$w_1$ = 1,2

$R_1$ - No. of 1's at yow n = 1,2

$G \times R_1 $ = { (1,1), (1,2), (2,1), (2,2) }

$\therefore$ $w_2 = w_0$

Step 3: Cal $w_2$

$c_2$ = 1,2 $c_2 \times R_2$ = { (1,1), (1,2), (2,1), (2,2)}

$R_2$ = 1,2

$\therefore$ $w_2 = w_1$

Step 4: Cal $w_3$

$c_3$ = 3,4 $c_3 \ \times \ R_3 $ = { (3,3), (3,4), (4,5), (4,4)}

$R_3$ = 3,4

$\therefore$ $w_3 = w_2$

Step 5 : Cal $w_4$

$c_4$ = 3,4,5 $c_4 \ \times \ R_4$ = {(3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)}

$\therefore$ $w_4 = \begin{matrix} [ 1 1 0 0 0 \\ 1 1 0 0 0 \\ 0 0 1 1 1 \\ 0 0 1 1 1 \\ 0 0 1 1 1 ] \end{matrix}$

Step 6: Cal $w_5$

$c_5$ = 3,4,5 $\therefore$ $c_5 \times R_5 = c_4 \times R_4$

$R_5$ = 3,4,5

$\therefore$ $w_5 = w_4 = \begin{matrix} [ 1 1 0 0 0 \\ 1 1 0 0 0 \\ 0 0 1 1 1 \\ 0 0 1 1 1 \\ 0 0 1 1 1 ] \end{matrix}$

$\therefore$ Smallest equivalence relation containing R F S both is $( R U S)^\infty$

$\therefore$ $(RUS)^\infty$ = { (1,1) (1,2),(2,1),(2,2),(3,3),(3,4), (3,5) ,(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)}