Lattices of congruences of categories

Every algebraic structure in universal algebra is associated with two types of lattices: lattices of subalgebras and lattices of categories. Categories in this sense are no different then any other structure we have encountered in universal algebra. Let $C$ be a category, then its lattice of subcategories is $Sub(C)$ and its lattice of congruences is $Con(C)$ which we will now construct.

Categorical partitions:
Let $C$ be a category. Then its underlying set consists of both its objects and morphisms. Therefore, a partition of the domain of a category is a set partition with its set of objects and morphisms as a ground set. A noticeable property of categories is the separation of objects and morphisms. This separation holds for categorical partitions.

• Object partition: a set partition of $Ob(C)$
• Morphism partition: a set partition of $Arrows(C)$

There are therefore two ways to represent a categorical partition: either as a partition of the underlying set of objects and morphisms or as an ordered pair of partitions $(O,M)$ of the object and morphism sets.

Compositional congruences:
The composition function of a category $\circ : M_2^* \to M$ only effects the morphism system of the category. Compositional congruences therefore can be phrased entirely in terms of morphism partitions. A morphism partition $M$ is a compositional congruence provided that: \[ \forall a_1,a_2,b_1,b_2 : a_1 =_M a_2 \wedge b_2 =_M b_2 \Rightarrow a_1 \circ b_1 =_M a_2 \circ b_2 \] It follows from the definition of functors that for any functor $F$ we have $F(fg) = F(f)F(g)$ for all morphisms $f$ and $g$ in $C$. This clearly implies that the morphism partition induced by any functor must at least be a compositional congruence.

Congruence closure:
Let $(O,M)$ be a partition of the object and morphism sets of a category. Then in order for a partition of this form to be a congruence it must satisfy a number of preservation conditions defined by logical implications:

• Composition : $a_1 =_M a_2 \wedge b_2 =_M b_2 \Rightarrow a_1 \circ b_1 =_M a_2 \circ b_2$
• Identities: $1_X =_M 1_Y \Leftrightarrow X =_O Y$
• Inputs: $f =_M g \Rightarrow Source(f) =_O Source(g)$
• Outputs: $f =_M g \Rightarrow Target(f) =_O Target(g)$

Let $(O,M)$ be a partition of a category $C$. Then the congruence closure of $(O,M)$ is determined by running through all logical implications until a closed set is produced. A partition that satisfies all four identities is a categorical congruence.

Definition. a categorical congruence is a partition that separates objects from morphisms that preserves composition, identities, inputs, and outpust.

The four conditions correspond to the four conditions placed on any functor, so the equivalence relation induced by any functor is a categorical congruence.

Lattice of congruences of a category
The set of congruences of a category forms a closure system with an upper bound equal to the maximal congruence, which makes all objects and morphisms equal. The closed sets of this closure operation therefore form a lattice.

Definition. let $C$ be a category then $Con(C)$ is the set of all categorical congruences on $C$ ordered by inclusion.

A well known special case consists of all object-injective congruences. These form an interval in the lattice of congruences of a category from the minimal congruence to the hom congruence, which equates all morphisms in each hom class.

Quotients:
Let $C$ be a category and let $P = (O,M)$ be a congruence of $C$. Then we can define a partial magmoid $\frac{C}{P}$ with $O$ classes as its objects and $M$ classes as its morphisms. The axioms of source preservation and target preservation mean that $\frac{C}{P}$ is a valid quiver, so it only remains to construct a valid composition operation for $\frac{C}{P}$ in order for it to be a partial magmoid.

Let the composition operation of the quiver $\circ$ be presented as a ternary relation $R \subseteq Arrows(C)^3$. Then we can construct a composition operation for $\frac{C}{P}$ by a map from $R$ to $M^3$ that maps each ordered triple in $R$ to an ordered triple in $M^3$ by the projection $\pi : Arrows(C) \to M$ applied to each component of the triple. \[ \pi^3 : R \to M^3 \] We are interested in the image $S$ of this projection map. By the fact that $M$ is a compositional congruence, this image is a single valued ternary relation, and so it can also be cast to a binary operation. Consider any triple $T$ in $S$. Then by the fact that $\frac{C}{P}$ is a valid quiver, each morphism class is associated to a hom class $(O_1,O_2)$ consisting of a pair of object classes.

The fact that any triple $T$ is the image of $R$ means that there is a triple of morphisms $(f : A \to B, g : B \to C, g \circ f : A \to C)$ whose image under $\pi^3$ is equal to $T$. This image has hom classes $((\pi(A),\pi(B))$, $(\pi(B),\pi(C))$ and $(\pi(A),\pi(C))$. It follows that the object classes of any triple take the form $((O_1,O_2),(O_2,O_3),(O_1,O_3))$ which means that this composition respects quotient hom classes.

If we have a triple of morphisms $(f,g,h)$ then the two types of composition $f \circ (g \circ h)$ and $(f \circ g) \circ h$ are equal, so they belong in the same $M$ class. It follows that quotient composition respects associtaivity. The partition preserves identities, so there is a quotient identity morphism for each object. This is clearly an identity for quotient composition. Therefore, $\frac{C}{P}$ is a partial magmoid.