Allegories of relations in regular categories In a category , a
relation between objects and is a
span of morphisms X\gets R\to Y that is jointly
monic. Two such spans X\gets S\to Y and X\gets T\to Y are considered equivalent when there is an isomorphism between and 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 has products, a relation between and is the same thing as a
monomorphism into (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 X\gets R\to Y\gets S\to Z is found by first pulling back the cospan R\to Y\gets S and then taking the jointly-monic image of the resulting span 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 , with the same objects as , but where morphisms are relations between the objects. The identity relations are the diagonals 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 in an allegory is called a
map if it is entire (1\subseteq R^\circ R) and deterministic (RR^\circ \subseteq 1). Another way of saying this is that a map is a morphism that has a
right adjoint in when 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 of with the same objects but only the maps as morphisms. For a regular category , there is an isomorphism of categories C \cong \operatorname{Map}(\operatorname{Rel}(C)). In particular, a morphism in is just an ordinary
set function. In an allegory, a morphism R\colon X\to Y is
tabulated by a pair of maps f\colon Z\to X and g\colon Z\to Y if gf^\circ = R and f^\circ f \cap g^\circ g = 1. An allegory is called
tabular if every morphism has a tabulation. For a regular category , the allegory is always tabular. On the other hand, for any tabular allegory , the category 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 , and in this setting, A\cong \operatorname{Rel}(\operatorname{Map}(A)).
Unital allegories and regular categories of maps A
unit in an allegory is an object for which the identity is the largest morphism U\to U, and such that from every other object, there is an entire relation to . An allegory with a unit is called
unital. Given a tabular allegory , the category is a regular category (it has a
terminal object) if and only if 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. ==References==