Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In universal algebra there is the notion of congruence relation: Consider a (1-sorted) algebraic structure, i.e. a set $A$ with a bunch of finitary operations $f_i$ satisfying equations.

A congruence relation is an equivalence relation $\sim$ on $A$ such that the operations on $A$ produce well-defined operations on the set $A/\sim$ of equivalence classes by applying them to representatives. I.e. for any operation $f$ on $A$ the operation $\bar{f}$ on $A/\sim$ given by $\bar{f}([x_1],...,[x_n]):=[f(x_1,...x_n)]$ is well-defined, i.e. if $x_1 \sim y_1, ... , x_n \sim y_n$ then $f(x_1,...,x_n) \sim f(y_1,...,y_n)$ for all operations $f$ of the given structure. Thus these relations are the right ones to form quotients inside the given category of algebraic structures.

An essentially algebraic structure is a (if 1-sorted) or several (if many-sorted) sets with partially defined operations satisfying equational laws, where the domain of any given operation is a subset defined by equations between previously defined operations (equivalenty: it is a $Set$-model of a finite limit sketch). The standard example are categories, where one has three global operations, identity, source and target, and a partial operation, composition, defined only for certain pairs of morphisms.

My question is: Is there a notion of congruence relation for these more general algebraic structures? E.g. one equivalence relation on each set satisfying the analogous properties to the above? If so have these "congruence relations" been studied, do they e.g. form lattices?

Motivation: Just curiosity really. I asked myself this question, after reading this MO-question of Colin Tan, which might be a special case. He asks whether there is a way to collapse two objects in a category. If there was a lattice of congruence relations on a category, there might be the congruence relation generated by the relation which identifies just the two objects (this would of course mean to treat categories in an "evil", non-two-categorical way, but that was what the question sounded like to me). Googling did reveal nothing, so I ask you people...

share|improve this question
    
Graetzer's classic book Universal Algebra deals with partial operations on universal algebras. (I think Burmeister has an updated book on partial algebras.) Congruences apply there, and one can interpret your construct as a partial algebra over the disjoint union of the sorts, although that may mean using a different language. I defer to others for the details, as it has been over a decade since I looked at either book. Gerhard "Ask Me About System Design" Paseman, 2010.08.12 –  Gerhard Paseman Aug 13 '10 at 0:22
add comment

2 Answers 2

up vote 3 down vote accepted

As Finn says, lfp categories have all coequalizers. However, there is a fly in the ointment. In set-models of algebraic theories, the underlying functor preserves the congruences and the quotients of the congruences. This means that a congruence is an equivalence relation on the underlying set and the quotient alegbraic structure has underlying set the set-quotient of the congruence. This is true even in many sorted algebraic theories.

But in models of finite limit sketches the quotient can blow up. The quotient need not be a structure whose underlying set is the quotient of the equivalence relation on the underlying set. An example of this happens in the category of small categories when you merge nonisomorphic objects. All of a sudden arrows may compose that didn't meet each other before, creating new arrows. (So the underlying set of arrows in the quotient is not the quotient of the congruence on the underlying set.)

This is spelled out and proved in Toposes, Triples and Theories, by Michael Barr and Charles Wells, in Theorem 4.1 of Chapter 8. In that theorem, "LE" means "Finite Limits" and "EE" means "effective equivalence relations whose quotients are preserved by the underlying set functor". This book is available for free on the internet -- just google it. Exercises EEPO and ORTHODOX give specific examples of that behavior. I think there is a specific example for small categories somewhere but at the moment I can't find it.

ADDED: The specific example is in section 1.8, exercise CBB. Section 1.8 talks about effective equivalence relations in general and calls them congruences.

share|improve this answer
    
Congruences on categories work very nicely when restricted to bijections on objects. This has attracted a lot of interest. Extension Theories for Categories, by Charles Wells. cwru.edu/artsci/math/wells/pub/pdf/catext.pdf For the following references I thank Peter Webb: An Introduction to the Representations and Cohomology of Categories, by Peter Webb. math.umn.edu/~webb/Publications/CategoryAlgebras.pdf G. Hoff, Cohomologies et extensions de categories, Math. Scand. 74 (1994), 191--207. H.-J. Baues and G. Wirsching, Cohomology of small categories, JPAA 38 –  SixWingedSeraph Aug 13 '10 at 2:11
    
Some colimits blow up even with algebraic theories. For example, the underlying set of the coproduct of two groups in the category of groups is not the coproduct (disjoint sum) of the underlying sets. –  SixWingedSeraph Aug 14 '10 at 18:54
    
Thanks for the explanation and all the references! (I have been offline for a week, hence the late reply) –  Peter Arndt Aug 21 '10 at 9:04
add comment

There is an internal definition of congruence (q.v.) that works for any category. The categories of (Set-)models of finite limit sketches are exactly the locally finitely presentable categories, which are cocomplete, so any congruence therein has a coequalizer (= quotient). I don't know off the top of my head whether congruences in lfp categories in particular have been studied, though.

share|improve this answer
add comment

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.