2

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?

St Vincent
  • 3,070
  • You have to show that if $T$ is an equivalence relation such that $R\subseteq T$, then $S\subseteq T$. – egreg Dec 05 '14 at 22:12
  • I am struggling with the same question, however I am stuck on the first part. How do I show S is an equivalence relation as well as R ⊆ S? – Sun Sep 05 '17 at 02:34
  • How did you prove the first part? That is, S is an equivalence relation and $R \subseteq S$ – Sun Sep 07 '17 at 19:10

1 Answers1

2

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

Community
  • 1
brick
  • 1,919