Suppose $R$ is a reflexive and symmetric relation on a finite set $A$. Define a relation $S$ on $A$ by declaring $xSy$ if and only if for some $n \in \mathbb{N}$ there are elements $x_1,x_2,\ldots,x_n \in A$ satisfying $xRx_1, x_1Rx_2, x_2Rx_3, x_3Rx_4, x_{n-1}Rx_n$ and $x_nRy$. Prove that $S$ is the unique smallest equivalance relation on $A$ containing $R$.
I have shown that $S$ is an equivalance relation and $R \subseteq S$, how do I show that $S$ is the "unique smallest equivalance relation" on A?
You need to show that $S$ is contained in every other equivalence relation containing $R$. So let $T$ is equivalence relation in A and $R \subseteq T$. If $xSy$, then $xRa_1, a_1Ra_2, \dots, a_nRy$, for some $a_1, \dots a_n \in A$. Since $R \subseteq T$, then $xTa_1, a_1Ta_2, \dots, a_nTy$ it follows that $xTy$, applying the transitivity property of $T$ several times. So $S \subseteq T$.