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?

  • $\begingroup$ I think the author is saying that it IS true that a composition of equivalence relations is an equivalence relation. It's only "wrong" in the sense that "it induced the reader to think that the conjunction of the 3 properties plays a role in proving the conclusion." I am not sure what he is getting at. $\endgroup$ – Jair Taylor Dec 18 '12 at 19:33
  • 2
    $\begingroup$ 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. $\endgroup$ – Andreas Blass Dec 18 '12 at 19:42

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.