Allegories of relations in regular categories

In a category C, a relation between objects X and Y is a span of morphisms ${\displaystyle X\gets R\to Y}$ that is jointly monic. Two such spans ${\displaystyle X\gets S\to Y}$ and ${\displaystyle X\gets T\to Y}$ are considered equivalent when there is an isomorphism between S and T that make everything commute; strictly speaking, relations are only defined up to equivalence (one may formalise this either by using equivalence classes or by using bicategories). If the category C has products, a relation between X and Y is the same thing as a monomorphism into X × Y (or an equivalence class of such). In the presence of pullbacks and a proper factorization system, one can define the composition of relations. The composition ${\displaystyle X\gets R\to Y\gets S\to Z}$ is found by first pulling back the cospan ${\displaystyle R\to Y\gets S}$ and then taking the jointly-monic image of the resulting span ${\displaystyle X\gets R\gets \bullet \to S\to Z.}$

Composition of relations will be associative if the factorization system is appropriately stable. In this case, one can consider a category Rel(C), with the same objects as C, but where morphisms are relations between the objects. The identity relations are the diagonals ${\displaystyle X\to X\times X.}$

A regular category (a category with finite limits and images in which covers are stable under pullback) has a stable regular epi/mono factorization system. The category of relations for a regular category is always an allegory. Anti-involution is defined by turning the source/target of the relation around, and intersections are intersections of subobjects, computed by pullback.

Maps in allegories, and tabulations

A morphism R in an allegory A is called a map if it is entire ${\displaystyle (1\subseteq R^{\circ }R)}$ and deterministic ${\displaystyle (RR^{\circ }\subseteq 1).}$ Another way of saying this is that a map is a morphism that has a right adjoint in A when A is considered, using the local order structure, as a 2-category. Maps in an allegory are closed under identity and composition. Thus, there is a subcategory Map(A) of A with the same objects but only the maps as morphisms. For a regular category C, there is an isomorphism of categories ${\displaystyle C\cong \operatorname {Map} (\operatorname {Rel} (C)).}$ In particular, a morphism in Map(Rel(Set)) is just an ordinary set function.

In an allegory, a morphism ${\displaystyle R\colon X\to Y}$ is tabulated by a pair of maps ${\displaystyle f\colon Z\to X}$ and ${\displaystyle g\colon Z\to Y}$ if ${\displaystyle gf^{\circ }=R}$ and ${\displaystyle f^{\circ }f\cap g^{\circ }g=1.}$ An allegory is called tabular if every morphism has a tabulation. For a regular category C, the allegory Rel(C) is always tabular. On the other hand, for any tabular allegory A, the category Map(A) of maps is a locally regular category: it has pullbacks, equalizers, and images that are stable under pullback. This is enough to study relations in Map(A), and in this setting, ${\displaystyle A\cong \operatorname {Rel} (\operatorname {Map} (A)).}$

Unital allegories and regular categories of maps

A unit in an allegory is an object U for which the identity is the largest morphism ${\displaystyle U\to U,}$ and such that from every other object, there is an entire relation to U. An allegory with a unit is called unital. Given a tabular allegory A, the category Map(A) is a regular category (it has a terminal object) if and only if A is unital.

More sophisticated kinds of allegory

Additional properties of allegories can be axiomatized. Distributive allegories have a union-like operation that is suitably well-behaved, and division allegories have a generalization of the division operation of relation algebra. Power allegories are distributive division allegories with additional powerset-like structure. The connection between allegories and regular categories can be developed into a connection between power allegories and toposes.