Allegory (category theory)

In the mathematical field of category theory, an allegory is a category that has some of the structure of the category 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 RS means "first do S, then do R".

An allegory is a category in which

all such that

Here, we are abbreviating using the order defined by the intersection: "R⊆S" means "R=R∩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→Y is a binary relation between X and Y. Composition of morphisms is composition of relations; intersection of morphisms is intersection of relations.

In a category C, a relation between objects X, Y is a span of morphisms X←R→Y that is jointly-monic. Two such spans X←S→Y and X←T→Y are considered equivalent when there is an isomorphism between S and T that make everything commute, and strictly speaking relations are only defined up to equivalence (one may formalise this either using equivalence classes or 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 of X←R→Y←S→Z is found by first pulling back the cospan R→Y←S and then taking the jointly-monic image of the resulting span X←R←·→S→Z.

...
Wikipedia