= Solution
Write $\Delta_A=\{(x,x):x\in A\}$ and regard each <binary relation> as a subset of $A\times A$. Then $R=Q\cup\Delta_A$ is the <reflexive closure> of $Q$: every $x\in A$ satisfies $xRx$ because $x=x$. The relation $S=R\cup R^{-1}$ is its <symmetric closure>. It is a <reflexive relation> since it contains $R$, and $xSy$ means either $xRy$ or $yRx$, either of which also gives $ySx$.
For $T$, a one-step chain $(x,x)$ is allowed because $xSx$, so $xTx$. If $(x_0,\ldots,x_n)$ witnesses $xTy$, the reversed chain $(x_n,\ldots,x_0)$ witnesses $yTx$, since $S$ is a <symmetric relation>. Finally, concatenate a chain from $x$ to $y$ with a chain from $y$ to $z$ to obtain a positive-length chain from $x$ to $z$. Hence $T$ is a <transitive relation> as well, and
$$
\boxed{R\text{ is reflexive},\quad S\text{ is reflexive and symmetric},\quad T\text{ is an equivalence relation}.}
$$
Thus $T$ is the <transitive closure of a relation> applied to $S$.
Now suppose $E$ is an <equivalence relation> containing $Q$. Its reflexivity implies $\Delta_A\subseteq E$, hence $R\subseteq E$. Its symmetry then implies $R^{-1}\subseteq E$, hence $S\subseteq E$. Along a chain witnessing $xTy$, every consecutive pair is $E$-related. Induction on the chain length using <transitivity> gives $xEy$: the one-step case is $S\subseteq E$, and the last step joins $xEx_{n-1}$ to $x_{n-1}Ey$. Therefore
$$
\boxed{T\subseteq E\text{ for every equivalence relation }E\supseteq Q.}
$$
Together with $Q\subseteq T$, this proves that $T$ is exactly the <equivalence closure> of $Q$. The reasoning also covers an empty $A$, where all assertions about elements are vacuous.
Back to article page
