3
$\begingroup$

I looked for material relating to compositions of equivalence relations, and was surprised to find the claim (here) that the composition of equivalence relations is not necessarily again an equivalence relation. Upon reading more closely, I saw that the author of that post was using the term "composition", in the context of equivalence relations, rather differently to the interpretation that seemed natural to me. That author uses "composition" to mean a certain binary operation on the set of binary relations on a given set.

My assumed notion of "composition" of equivalence relations is this: let $S$ be a set, let $\sim$ be an equivalence relation on $S$, and let $\bowtie$ be an equivalence relation on $S / \sim$. Given an $s \in S$, write $[s]_{\sim}$ for the equivalence class of $s$ under $\sim$. Now define an equivalence relation $\bowtie \circ \sim$ on $S$ as follows: given any $s \in S$, $s \bowtie \circ \sim t$ if and only if $[s]_{\sim} \bowtie [t]_{\sim}$.

The reason why this makes sense as a notion of "composition" is that the quotient map associated to the composition of equivalence relations is the composition of the quotient maps of the individual equivalence relations, after a "flattening" step in which each equivalence class is replaced by the union of its elements (those elements themselves being the equivalence classes under the first equivalence relation). Why is the term "composition" used to mean something else for equivalence relations?

  • 2
    In the passage linked in the question, the author is misusing "composition" to mean the conjunction (i.e., "and") or intersection of equivalence relations. That produces an equivalence relation, because each of "reflexive", "symmetric", and "transitive" is preserved by conjunction. But the standard meaning of "composition" of relations is as in Henning Makholm's answer, and this, when applied to equivalence relations, may fail to produce an equivalence relation.2012-12-18

1 Answers 1

4

I would understand "composition" of relations to mean that operation $\circ$ that takes $R\subseteq A\times B$ and $S\subseteq B\times C$ to $ R\circ S = \{ \langle a,c\rangle \mid \exists b\in B: (aRb \land bSc) \} \subseteq A\times C$ This directly generalizes composition of functions -- that is, it makes $f\circ g$ have the usual meaning when the functions $f$ and $g$ are viewed as binary relations.