Allegory (mathematics)

Last updated March 31, 2021

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.

Definition

An allegory is a category in which

every morphism $R\colon X\to Y$ is associated with an anti-involution, i.e. a morphism $R^{\circ }\colon Y\to X$ with $R^{\circ \circ }=R$ and $(RS)^{\circ }=S^{\circ }R^{\circ }{\text{;}}$ and
every pair of morphisms $R,S\colon X\to Y$ with common domain/codomain is associated with an intersection, i.e. a morphism $R\cap S\colon 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 }=S^{\circ }\cap R^{\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 TS^{\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 }$ : $yR^{\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 $C$ , a relation between objects $X$ and $Y$ is a span of morphisms $X\gets R\to Y$ that is jointly monic. Two such spans $X\gets S\to Y$ and $X\gets 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 \times 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\gets R\to Y\gets S\to Z$ is found by first pulling back the cospan $R\to Y\gets S$ and then taking the jointly-monic image of the resulting span $X\gets R\gets \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 $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 $(RR^{\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\cong \operatorname {Map} (\operatorname {Rel} (C)).$ In particular, a morphism in $Map(Rel(Set))$ is just an ordinary set function.

In an allegory, a morphism $R\colon X\to Y$ is tabulated by a pair of maps $f\colon Z\to X$ and $g\colon Z\to Y$ if $gf^{\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\cong \operatorname {Rel} (\operatorname {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.

Related Research Articles

In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects are associated to topological spaces, and maps between these algebraic objects are associated to continuous maps between spaces. Nowadays, functors are used throughout modern mathematics to relate various categories. Thus, functors are important in all areas within mathematics to which category theory is applied.

In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type. The word homomorphism comes from the Ancient Greek language: ὁμός meaning "same" and μορφή meaning "form" or "shape". However, the word was apparently introduced to mathematics due to a (mis)translation of German ähnlich meaning "similar" to ὁμός meaning "same". The term "homomorphism" appeared as early as 1892, when it was attributed to the German mathematician Felix Klein (1849–1925).

In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure of the categories involved. Hence, a natural transformation can be considered to be a "morphism of functors". Indeed, this intuition can be formalized to define so-called functor categories. Natural transformations are, after categories and functors, one of the most fundamental notions of category theory and consequently appear in the majority of its applications.

In mathematics, specifically abstract algebra, the isomorphism theorems are theorems that describe the relationship between quotients, homomorphisms, and subobjects. Versions of the theorems exist for groups, rings, vector spaces, modules, Lie algebras, and various other algebraic structures. In universal algebra, the isomorphism theorems can be generalized to the context of algebras and congruences.

In mathematics, specifically category theory, adjunction is a relationship that two functors may have. Two functors that stand in this relationship are known as adjoint functors, one being the left adjoint and the other the right adjoint. Pairs of adjoint functors are ubiquitous in mathematics and often arise from constructions of "optimal solutions" to certain problems, such as the construction of a free group on a set in algebra, or the construction of the Stone–Čech compactification of a topological space in topology.

In category theory, an epimorphism is a morphism f : X → Y that is right-cancellative in the sense that, for all objects Z and all morphisms g₁, g₂: Y → Z,

Homological algebra is the branch of mathematics that studies homology in a general algebraic setting. It is a relatively young discipline, whose origins can be traced to investigations in combinatorial topology and abstract algebra at the end of the 19th century, chiefly by Henri Poincaré and David Hilbert.

In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets. This functor makes it possible to think of the objects of the category as sets with additional structure, and of its morphisms as structure-preserving functions. Many important categories have obvious interpretations as concrete categories, for example the category of topological spaces and the category of groups, and trivially also the category of sets itself. On the other hand, the homotopy category of topological spaces is not concretizable, i.e. it does not admit a faithful functor to the category of sets.

In category theory, a branch of mathematics, a pushout is the colimit of a diagram consisting of two morphisms f : Z → X and g : Z → Y with a common domain. The pushout consists of an object P along with two morphisms X → P and Y → P that complete a commutative square with the two given morphisms f and g. In fact, the defining universal property of the pushout essentially says that the pushout is the "most general" way to complete this commutative square. Common notations for the pushout are $and .$

In category theory, a branch of mathematics, a pullback is the limit of a diagram consisting of two morphisms $f : X \to Z$ and $g : Y \to Z$ with a common codomain. The pullback is often written

In the branch of mathematics called homological algebra, a t-structure is a way to axiomatize the properties of an abelian subcategory of a derived category. A t-structure on $consists of two subcategories of a triangulated category or stable infinity category which abstract the idea of complexes whose cohomology vanishes in positive, respectively negative, degrees. There can be many distinct t -structures on the same category, and the interplay between these structures has implications for algebra and geometry. The notion of a t -structure arose in the work of Beilinson, Bernstein, Deligne, and Gabber on perverse sheaves.$

This is a glossary of properties and concepts in category theory in mathematics.

In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent of'. In formal terms, if $X$ and $Y$ are sets and $L \subseteq X \times Y$ is a relation from $X$ to $Y$ , then $L T$ is the relation defined so that $y L T x$ if and only if $x L y$ . In set-builder notation, $L T = {(y, x) \in Y \times X | \in L$ }.

In mathematics, the category Rel has the class of sets as objects and binary relations as morphisms.

In category theory, a branch of mathematics, a dagger category is a category equipped with a certain structure called dagger or involution. The name dagger category was coined by Peter Selinger.

In the mathematics of binary relations, the composition of relations is the forming of a new binary relation R ; S from two given binary relations R and S. In the calculus of relations, the composition of relations is called relative multiplication, and its result is called a relative product. Function composition is the special case of composition of relations where all relations involved are functions.

In category theory, a span, roof or correspondence 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.

In mathematics, a topos is a category that behaves like the category of sheaves of sets on a topological space. Topoi behave much like the category of sets and possess a notion of localization; they are a direct generalization of point-set topology. The Grothendieck topoi find applications in algebraic geometry; the more general elementary topoi are used in logic.

In algebraic geometry, a prestackF over a category C equipped with some Grothendieck topology is a category together with a functor p: F → C satisfying a certain lifting condition and such that locally isomorphic objects are isomorphic. A stack is a prestack with effective descents, meaning local objects may be patched together to become a global object.

In mathematics, a heterogeneous relation is a binary relation, a subset of a Cartesian product A × B, where A and B are distinct sets. The prefix hetero is from the Greek ἕτερος.

References

Peter Freyd, Andre Scedrov (1990). Categories, Allegories. Mathematical Library Vol 39. North-Holland. ISBN 978-0-444-70368-2.

Peter Johnstone (2003). Sketches of an Elephant: A Topos Theory Compendium. Oxford Science Publications. OUP. ISBN 0-19-852496-X.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.