Allegory (mathematics)

In this article we adopt the convention that morphisms compose from right to left, so RS means "first do S, then do R".

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 $(R S)^{\circ} = S^{\circ} R^{\circ};$ 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 R S \cap R T$ and $(R \cap S) T \subseteq R T \cap S T;$ and
the modularity law is satisfied: $R S \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 X and Y. 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 $x R y$ . Intersection of morphisms is (set-theoretic) intersection of relations.

One more chapter is free with a Lably account.

Regular categories and allegories

Allegories of relations in regular categories

In a category C, a relation between objects X and Y 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 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 $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 ∙ \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 $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 $(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 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 $C ≅ Map (Rel (C)) .$ In particular, a morphism in Map(Rel(Set)) 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 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, $A ≅ Rel (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 $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.