Allegory (category theory)
Encyclopedia
In mathematical category theory
, an allegory is a category
that has some of the structure of the category of sets and binary relation
s 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.
Precisely, 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".
In this article we adopt the convention that morphisms compose from right to left, so RS means "first do S, then do R".
A first example of an allegory is Rel(Set). 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.
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.
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→X×X.
Recall that a regular category
is a category with finite limits and images in which covers are stable under pullback. A regular category 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 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→Y is tabulated by a pair of maps f:Z→X, g:Z→Y if gf°=R and f°f∩g°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)).
-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.
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
, an allegory is a category
Category (mathematics)
In mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...
that has some of the structure of the category of sets and binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
s 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
Relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...
to relations between different sorts. Allegories are also useful in defining and investigating certain constructions in category theory, such as exact
Regular category
In category theory, a regular category is a category with finite limits and coequalizers of kernel pairs, satisfying certain exactness conditions. In that way, regular categories recapture many properties of abelian categories, like the existence of images, without requiring additivity...
completions.
Precisely, an allegory is a category
Category (mathematics)
In mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...
in which
- every morphism R:X→Y is associated with an anti-involution, i.e. a morphism R°:Y→X; and
- every pair of morphisms R,S:X→Y with common domain/codomain is associated with an intersection, i.e. a morphism R∩S:X→Y
all such that
- intersections are idempotent (R∩R=R), commutative (R∩S=S∩R), and associative (R∩S)∩T=R∩(S∩T);
- anti-involution distributes over composition ((RS)°=S°R°) and intersection ((R∩S)°=S°∩R°);
- composition is semi-distributive over intersection (R(S∩T)⊆RS∩RT, (R∩S)T⊆RT∩ST); and
- the modularity law is satisfied: (RS∩T⊆(R∩TS°)S).
Here, we are abbreviating using the order defined by the intersection: "R⊆S" means "R=R∩S".
In this article we adopt the convention that morphisms compose from right to left, so RS means "first do S, then do R".
A first example of an allegory is Rel(Set). 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
Composition of relations
In mathematics, the composition of binary relations is a concept of forming a new relation from two given relations R and S, having as its most well-known special case the composition of functions.- Definition :...
; intersection of morphisms is intersection
Intersection (set theory)
In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
of relations.
Allegories of relations in regular categories
In a category C, a relation between objects X, Y is a spanSpan (category theory)
A span, in category theory, is a generalization of the notion of relation between two objects of a category. When the category has all pullbacks , spans can be considered as morphisms in a category of fractions....
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
Monomorphism
In the context of abstract algebra or universal algebra, a monomorphism is an injective homomorphism. A monomorphism from X to Y is often denoted with the notation X \hookrightarrow Y....
into X×Y (or an equivalence class of such). In the presence of pullbacks and a proper factorization system
Factorization system
In mathematics, it can be shown that every function can be written as the composite of a surjective function followed by an injective function. Factorization systems are a generalization of this situation in category theory.-Definition:...
, 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.
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→X×X.
Recall that a regular category
Regular category
In category theory, a regular category is a category with finite limits and coequalizers of kernel pairs, satisfying certain exactness conditions. In that way, regular categories recapture many properties of abelian categories, like the existence of images, without requiring additivity...
is a category with finite limits and images in which covers are stable under pullback. A regular category 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⊆R°R) and deterministic (RR°⊆1). Another way of saying this: a map is a morphism that has a right adjoint in A, when A is considered, using the local order structure, as a 2-category2-category
In category theory, a 2-category is a category with "morphisms between morphisms"; that is, where each hom set itself carries the structure of a 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→Y is tabulated by a pair of maps f:Z→X, g:Z→Y if gf°=R and f°f∩g°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→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 unionUnion (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
-like operation that is suitably well-behaved, and division allegories have a generalization of the division operation of relation algebra
Relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...
. 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.