Question

Suppose \(R\) is a reflexive and symmetric relation on a finite set \(A .\) Define a relation \(S\) on \(A\) by declaring \(x S y\) if and only if for some \(n \in \mathbb{N}\) there are elements \(x_{1}, x_{2}, \ldots, x_{n} \in A\) satisfying \(x R x_{1}, x_{1} R x_{2}, x_{2} R x_{3}, x_{3} R x_{4}, \ldots, x_{n-1} R x_{n},\) and \(x_{n} R y .\) Show that \(S\) is an equivalence relation and \(R \subseteq S .\) Prove that \(S\) is the unique smallest equivalence relation on \(A\) containing \(R\).

Short answer

The relation \(S\) defined based on reflexive and symmetric relation \(R\) is an equivalence relation. Moreover, \(R\) is a subset of \(S\), and \(S\) is the unique smallest equivalence relation on the set \(A\) containing \(R\).

Step-by-step solution

Prove that \(S\) is reflexive

We need to show that for every \(x \in A\), \(x S x\) holds. According to the definition of \(S\), for \(x S x\) to hold, we need some \(n \in \mathbb{N}\) and elements \(x_{1}, x_{2}, \ldots, x_{n} \in A\) such that \(x R x_{1}, x_{1} R x_{2}, x_{2} R x_{3}, x_{3} R x_{4}, \ldots, x_{n-1} R x_{n}\), and \(x_{n} R x\). If we choose \(n = 1\) and \(x_{1} = x\), the definition is satisfied because \(x R x\) holds due to the reflexivity of \(R\). Therefore, \(S\) is reflexive.

Prove that \(S\) is symmetric

We need to show that for every \(x, y \in A\), if \(x S y\) then \(y S x\) holds. If \(x S y\), by the definition of \(S\), there are some \(n \in \mathbb{N}\) and elements \(x_{1}, x_{2}, \ldots, x_{n} \in A\) such that \(x R x_{1}, x_{1} R x_{2}, \ldots, x_{n-1} R x_{n}\), and \(x_{n} R y\). Since \(R\) is symmetric, we have \(y R x_{n}, x_{n} R x_{n-1}, \ldots, x_{2} R x_{1}\), and \(x_{1} R x\). Hence, by the definition of \(S\), \(y S x\) holds. Therefore, \(S\) is symmetric.

Prove that \(S\) is transitive

We need to show that for every \(x, y, z \in A\), if \(x S y\) and \(y S z\) then \(x S z\) holds. If \(x S y\) and \(y S z\), by the definition of \(S\), there exist sequences \((x_{1}, x_{2}, \ldots, x_{n})\) and \((y_{1}, y_{2}, \ldots, y_{m})\) such that \(x R x_{1}, x_{1} R x_{2}, \ldots, x_{n-1} R x_{n}\), \(x_{n} R y\), \(y R y_{1}, y_{1} R y_{2}, \ldots, y_{m-1} R y_{m}\), and \(y_{m} R z\). If we combine these two sequences to form a new sequence \((x_{1}, x_{2}, \ldots, x_{n}, y_{1}, y_{2}, \ldots, y_{m})\), then this new sequence satisfies the conditions in the definition of \(S\) for \(x S z\). Therefore, \(S\) is transitive.

Prove that \(R \subseteq S\)

To show \(R \subseteq S\), we need to prove that every pair \((x, y)\) that is in \(R\) is also in \(S\). If \((x, y) \in R\), we can choose \(n = 1\) and \(x_{1} = y\) in the definition of \(S\) and verify that \(x S y\) holds. Therefore, \(R \subseteq S\).

Prove that \(S\) is the smallest equivalence relation containing \(R\)

We need to show that for any equivalence relation \(T\) on \(A\) that contains \(R\), \(T\) must also contain \(S\). Note that since \(R \subseteq T\) and \(T\) is reflexive, symmetric, and transitive, for every \((x, y) \in S\), there exist some \(n \in \mathbb{N}\) and elements \(x_{1}, x_{2}, \ldots, x_{n} \in A\) such that \(x T x_{1}, x_{1} T x_{2}, \ldots, x_{n-1} T x_{n}\), and \(x_{n} T y\). Hence, \((x, y) \in T\). Therefore, \(S \subseteq T\), which means \(S\) is the smallest equivalence relation containing \(R\)