Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Jair Taylor Dec 18 '12 at 19:33
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. – Andreas Blass Dec 18 '12 at 19:42
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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