Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can we always find the smallest equivalence relation satisfying some conditions in an algebraic category? If so, do we always know how?

I'm currently dealing with $\bf Mon$ so I have very few operations at my disposal. What I understand is that it is unique, since it's determined by its equivalence classes. It exists since we always have the trivial eq-rel $M\times M$ which equates all elements with each other.

I'm dealing with coequalizers and it feels rather vague to just call upon this, although I did the same with $\bf Set$.

Further here we have various constraints, because it must respect multiplication and all equivalence classes must commute with the identity class. But maybe this is ensured by the monoid morphisms.

Anyway, I know I'm only half coherent right now and I apologise for that. Hope somebody can make sense of my question and put me at ease. Thanks either way for taking the time to read this far.

share|improve this question

1 Answer 1

See any textbook on universal algebra. The lattice of equivalence relations on a given set $X$ is complete: If $D$ is a set of equivalence relations on $X$, then $\cap D$ is the smallest equivalence relation on $X$ which is contained in every member of $D$. If $X$ carries algebraic structure, one looks at congruence relations on $X$: These are equivalence relations compatible with the algebraic structure: If $a_i,b_i$ are equivalent $(1 \leq i \leq n)$, then $t(a_1,\dotsc,a_n)=t(b_1,\dotsc,b_n)$ for every $n$-ary term $t$ in the given signature. [These are significant because we can immediately write down the corresponding quotient structure] Congruence relations form a complete sublattice of the lattice of equivalence relations, since it is trivial to verify that they are closed under intersections. In particular, for every relation $\sim$ on $X$ there is a smallest congruence relation $\sim_c$ which satisfies $\sim \subseteq \sim_c$. In order to do computations, it is useful to have a specific description of $\sim_c$. First construct the smallest equivalence relation containing $\sim$ by taking zig zag paths of relations in $\sim$. Then close off under the term rule above; formally define inductively equivalence relations and $\sim_c$ is their union. Of course, this might get quite complicated. But since monoids have so few operations, in that case it is often rather easy.

For example, when $M$ is a monoid, and $\sim$ is the relation which contains all $(nm,mn)$, where $m,n \in M$, then the generated equivalence relation $\sim_e$ is the set of all $(m_1 \dotsc m_n,m_{\sigma(1)} \dotsc m_{\sigma(n)})$, where $n \in \mathbb{N}$, $m_i \in M$ and $\sigma \in \Sigma_n$. It is already a congruence relation. I have used this in your question about making monoids commutative.

share|improve this answer

Your Answer

 
discard

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.