Congruence lattices of categories

Congruences are the most fundamental concept there is. For example, in ring theory we study congruences indirectly through ideals. Its unthinkable that such important structures as categories shouldn't have congruences define over them. Fortunately, we can solve this problem by embedding categories in an appropriate topos.

Background
A categorical congruence of a category $C$ is a unital-quiver congruence $(=_M,=_O)$ that satisfies the equivalent of a semigroup congruence on the composition operation of a category: \[ \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 \] In other words, $((=_M)^2|_{D(C)},=_M)$ is a composition congruence where $(=_M)^2|_{D(C)}$ is the partition of the composition domain of $C$ induced by $=_M$. Then every such congruence induces a congruence $(=_M)^2|_{D(C)},=_M,=_O)$ of $C$ in the topos of compositional quivers.

Congruences of the two arrow category:
Consider the index category $T_2^*$ of the topos of quivers: Then it has a congruence lattice that looks like this: As a quiver is a functor on this category $T_2^*$, and every functor induces a categorical congruence, each of these congruences determine different types of quivers.

• The congruence that equates no objects and morphisms determines a generic quiver.
• The congruence that equates the source and arrow morphisms determines a coreflexive quiver. These are precisely the quivers whose underlying relations are coreflexive.
• The congruence that equates the object and morphism sets describes a quiver whose vertex and edge sets are the same.
• The congruence that equates the source and arrow morphisms and both objects determines a coreflexive quiver on a common set of edges and morphisms.
• The congruence that equates the source and identity morphisms makes it so that the source of each morphism is the morphism itself.
• The congruence that equates the target and identity morphisms makes it so that the target of each morphism is the morphism itself.
• The congruence that equates everything is a coreflexive quiver on a single set, where the source and target objects of a morphism are the morphism itself.

So the congruence lattice $Con(T_2^*)$ does tell us something interesting about this category, and the functors that can be formed on it. In the same way that the ideals lattice determines what morphisms can be sourced from a given ring. So for example, a homomorphism starting from a field must always be either trivial or injective because a field has only two ideals. This simple example fails to demonstrate the fact that the congruences of a category don't always coincide with the congruences of that category as a unital quiver.

Congruences of a total order on three elements:
Consider the three element total order $T_3$: Then its lattice of congruences as a unital quiver $Con(T_3)$ looks like this: On the other hand, its lattice of congruences as a category $Con(T_3)$ looks like this. Then its clearly smaller then its counterpart. In fact, the former has seven coatoms while the later has only four. So while it is note the case that the congruence lattice of $T_2^*$ is smaller for it as a category then as a unital quiver, in the general case the categorical congruence lattice is smaller because it has the extra condition of being a congruence of composition. It can clearly be seen:

Proposition. let $C$ with $Q$ its underlying quiver then $Con(C) \subseteq Con(Q)$ and $Con(C)$ is a meet subsemilattice of $Con(Q)$.

So categorical congruences are just defined from unital quiver congruences by the condition that compositions must be unique with respect the morphism partition. This makes them a subsemilattice of the unital quiver congruence lattice.

Congruences of the two pair category:
Consider a category with two different ordered pairs: Then its congruence lattice looks like this: Consider now the congruence that equates the objects one and two but no morphisms. Then this is certainly a valid congruence, for example we can define a monotone map from this thin category to $T_3$ that takes 0 to 0, 1 and 2 to 1, and 2 to 2 and as a monotone map that is a functor, and its underlying partition is a categorical congruence. However, consider the resulting quotient. Clearly it is not a category, because the composition of two arrows that have an intermediate object is not always defined.

Proposition. the quotient of a category by a congruence is not necessarily a category

Instead, the quotient of a category by a congruence is always a partial magmoid. Partial magmoids have no axioms that would prevent them from being closed under quotients, because any quotient of their binary operation is again a partial magma. So the category of partial magmoids is nicer then the category of categories $Cat$ in at least one way, but it is still not enough. The nicest categories are topoi.

The topos of composition quivers:
So we define the topos of composition quivers from a presheaf on the index category that looks like this: The relevant fact is that a category is essentially described by the data of three sets and six functions: the first, second, composition, identity, source, and target functions. This topos includes not only categories but all their generalisations like partial magmoids and beyond. Topos theory is the most advanced branch of mathematical logic we have available. Applying it to understanding categories can be very rewarding.

See also:
Congruence lattices of quivers