Allegory (mathematics)

In the mathematical field of , an allegory is a 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 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 in which every morphism is associated with an anti-involution, i.e. a morphism with and and every pair of morphisms with common domain/codomain is associated with an intersection, i.e. a morphism all such that intersections are idempotent: commutative: and associative: anti-involution distributes over intersection: composition is semi-distributive over intersection: and and the modularity law is satisfied: Here, we are abbreviating using the order defined by the intersection: means A first example of an allegory is the . The of this allegory are sets, and a morphism is a binary relation between X and Y. Composition of morphisms is composition of relations, and the anti-involution of is the converse relation : if and only if . Intersection of morphisms is (set-theoretic) intersection of relations. In a category C, a relation between objects X and Y is a of morphisms that is jointly monic. Two such spans and 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 ). 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 and a proper factorization system, one can define the composition of relations.