4.II.5E

Explain what is meant by an equivalence relation on a set $A$.

If $R$ and $S$ are two equivalence relations on the same set $A$, we define

$R \circ S=\{(x, z) \in A \times A:$ there exists $y \in A$ such that $(x, y) \in R$ and $(y, z) \in S\} .$

Show that the following conditions are equivalent:

(i) $R \circ S$ is a symmetric relation on $A$;

(ii) $R \circ S$ is a transitive relation on $A$;

(iii) $S \circ R \subseteq R \circ S$;

(iv) $R \circ S$ is the unique smallest equivalence relation on $A$ containing both $R$ and $S$.

Show also that these conditions hold if $A=\mathbb{Z}$ and $R$ and $S$ are the relations of congruence modulo $m$ and modulo $n$, for some positive integers $m$ and $n$.

*Typos? Please submit corrections to this page on GitHub.*