Exercise 10, § 6

(a) If $R\{x, y\}$ is any relation, then "$R\{x, y\}$ and $R\{y, x\}$" is a symmetric relation. Under what condition is it reflexive on a set $E$?

*(b) Let $R\{x, y\}$ be a reflexive and symmetric relation on a set $E$. Let $S\{x, y\}$ be the relation "there exists an integer $n > 0$ and a sequence $(x_i)_{0 \leqslant i \leqslant n}$ of elements of $E$ such that $x_0 = x$, $x_n = y$, and for each index $i$ such that $0 \leqslant i < n$, $R\{x_i, x_{i+1}\}$". Show that $S\{x, y\}$ is an equivalence relation on $E$ and that its graph is the smallest of all graphs of equivalences on $E$ which contain the graph of $R$. The equivalence classes with respect to $S$ are called the connected components of $E$ with respect to the relation $R$.

(c) Let $\mathfrak{F}$ be the set of subsets $A$ of $E$ such that, for each pair of elements $(y, z)$ such that $y \in A$ and $z \in E - A$, we have "not $R\{y, z\}$".

For each $x \in \mathrm{E}$, show that the intersection of the sets $\mathrm{A} \in \mathfrak{F}$ such that $x \in \mathrm{A}$ is the connected component of $x$ with respect to the relation R.\*