Allegory (mathematics)

In the mathematical field of category theory, an allegory is a category that has some of the structure of the category Rel of sets and binary relations between them. Allegories can be used as an abstraction of categories of relations, and in this sense the theory of allegories is a generalization of relation algebra to relations between different sorts. Allegories are also useful in defining and investigating certain constructions in category theory, such as exact completions.

In this article we adopt the convention that morphisms compose from right to left, so Template:Math means "first do Template:Mvar, then do Template:Mvar".

Definition

An allegory is a category in which

• every morphism $R:X\to Y$ is associated with an anti-involution, i.e. a morphism $R^{\circ }:Y\to X$ with $R^{\circ \circ }=R$ and $(RS{)}^{\circ }=S^{\circ }{R}^{\circ }\text{;}$ and
• every pair of morphisms $R,S:X\to Y$ with common domain/codomain is associated with an intersection, i.e. a morphism $R\cap S:X\to Y$

all such that

• intersections are idempotent: $R\cap R=R,$ commutative: $R\cap S=S\cap R,$ and associative: $(R\cap S)\cap T=R\cap (S\cap T);$
• anti-involution distributes over intersection: $(R\cap S{)}^{\circ }=R^{\circ }\cap S^{\circ };$
• composition is semi-distributive over intersection: $R(S\cap T)\subseteq RS\cap RT$ and $(R\cap S)T\subseteq RT\cap ST;$ and
• the modularity law is satisfied: $RS\cap T\subseteq (R\cap T{S}^{\circ })S.$

Here, we are abbreviating using the order defined by the intersection: $R\subseteq S$ means $R=R\cap S.$

A first example of an allegory is the category of sets and relations. The objects of this allegory are sets, and a morphism $X\to Y$ is a binary relation between Template:Mvar and Template:Mvar. Composition of morphisms is composition of relations, and the anti-involution of $R$ is the converse relation $R^{\circ }$: $y{R}^{\circ }x$ if and only if $xRy$. Intersection of morphisms is (set-theoretic) intersection of relations.

Regular categories and allegories

Allegories of relations in regular categories

In a category Template:Mvar, a relation between objects Template:Mvar and Template:Mvar is a span of morphisms $X\leftarrow R\to Y$ that is jointly monic. Two such spans $X\leftarrow S\to Y$ and $X\leftarrow T\to Y$ are considered equivalent when there is an isomorphism between Template:Mvar and Template:Mvar 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 Template:Mvar has products, a relation between Template:Mvar and Template:Mvar is the same thing as a monomorphism into Template:Math (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\leftarrow R\to Y\leftarrow S\to Z$ is found by first pulling back the cospan $R\to Y\leftarrow S$ and then taking the jointly-monic image of the resulting span $X\leftarrow R\leftarrow \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 Template:Math, with the same objects as Template:Mvar, 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 Template:Mvar in an allegory Template:Mvar is called a map if it is entire $(1\subseteq R^{\circ }R)$ and deterministic $(R{R}^{\circ }\subseteq 1).$ Another way of saying this is that a map is a morphism that has a right adjoint in Template:Mvar when Template:Mvar 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 Template:Math of Template:Mvar with the same objects but only the maps as morphisms. For a regular category Template:Mvar, there is an isomorphism of categories $C\cong \mathrm{Map}(\mathrm{Rel}(C)).$ In particular, a morphism in Template:Math is just an ordinary set function.

In an allegory, a morphism $R:X\to Y$ is tabulated by a pair of maps $f:Z\to X$ and $g:Z\to Y$ if $g{f}^{\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 Template:Mvar, the allegory Template:Math is always tabular. On the other hand, for any tabular allegory Template:Mvar, the category Template:Math 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 Template:Math, and in this setting, $A\cong \mathrm{Rel}(\mathrm{Map}(A)).$

Unital allegories and regular categories of maps

A unit in an allegory is an object Template:Mvar for which the identity is the largest morphism $U\to U,$ and such that from every other object, there is an entire relation to Template:Mvar. An allegory with a unit is called unital. Given a tabular allegory Template:Mvar, the category Template:Math is a regular category (it has a terminal object) if and only if Template:Mvar 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

• Template:Cite book
• Template:Cite book