left and right euclidean;
In category theory, an allegory is a category with properties meant to reflect properties that hold in a category Rel of relations. The notion was first introduced (as far as we know) and certainly first made famous in the book Categories, Allegories (Freyd-Scedrov).
Freyd and Scedrov argue that a categorical calculus of relations is an alternative and often more amenable framework for developing concepts traditionally couched in “functional” language (i.e., concepts which apply to sets and functions); for instance, a principal raison d’etre for regular categories is precisely that one can do relational calculus in them (as had been long known, e.g., Saunders MacLane showed how to calculate with relations to do diagram chases in abelian categories). Allegories, and correlative notions such as bicategories of relations, also offer a smooth approach to regular and exact completions, as used for example in the construction of realizability toposes.
A signal feature of allegories is emphasis on the modular law (see def. 1 below), which generalizes the modular law in lattices to more general relations, and which generalizes also so-called Frobenius reciprocity in categorical logic.
Any modular lattice can be regarded as a one-object allegory if we take composition to be union and the involution to be the identity.
A map in an allegory is a morphism that has a right adjoint. If , then (hint: use the modular law to show and ).
A tabulation of a morphism is a pair of maps such that and . An allegory is tabular if every morphism has a tabulation, and pretabular if every morphism is contained in one that has a tabulation.
Every regular category, and indeed every locally regular category, has a tabular allegory of internal binary relations. Conversely, by restricting to the morphisms with left adjoints (“maps”) in a tabular allegory, we obtain a locally regular category. These constructions are inverse, so tabular allegories are equivalent to locally regular categories.
A locally regular category has finite products if and only if its tabular allegory of relations has top elements in its hom-posets.
Finally, a unit in an allegory is an object such that is the greatest morphism , and every object admits a morphism such that . A locally regular category has a terminal object (hence is regular) if and only if its tabular allegory of relations has a unit.
A distributive allegory is an allegory whose hom-posets have finite joins that are preserved by composition. Thus a distributive allegory is locally a lattice. The category of maps in a unitary tabular distributive allegory is a pre-logos, and conversely the bicategory of relations in a pre-logos is a unitary tabular distributive allegory.
A division allegory is a distributive allegory in which composition on one (and therefore the other) side has a right adjoint (left or right division). That is: given and , there exists such that
(so that has right adjoint : an example of a right Kan extension). Composition on the other side, , has a right adjoint (an example of a right Kan lift) given by
In the bicategory of sets and relations, with notation as above, we have
where is shorthand for “ belongs to ”.
The category of maps (functional relations) of a unitary/unital tabular division allegory is a logos, and conversely the bicategory of relations in a logos is a unitary tabular division allegory. (Categories, Allegories, 2.32, page 227.)
A power allegory is, more or less, an allegory such that the inclusion functor has a right adjoint . The idea is that assigns to an object a power object , as in topos theory; if we summarize the notion of topos as a regular category for which the inclusion has a right adjoint , then it becomes apparent that the notion of power allegory is similar except that it takes the “relation side” as primary and derives the “function side” as , whereas in topos theory it’s just the other way around. But in either case the adjunction is fundamental.
Since the inclusion is the identity on objects, the counit of the adjunction at an object may be written
and we have a kind of comprehension scheme that to each there is a unique map , the characteristic map of , such that . (If and are related by a property , then for each there is a subobject of consisting of elements so related to .) In the case , the characteristic map is called the singleton map of , and more general may be defined as .
The exact definition of power allegory is a matter for consideration. One can get a certain distance just by adopting the naive definition suggested above, that a power allegory is nothing more than an allegory for which the inclusion has a right adjoint . (Below we introduce a similar notion that we call a -allegory.) But it seems hard to develop a theory from the naive notion that rises to a level comparable to topos theory.
Freyd and Scedrov start with a structure of division allegory (thus packing in a good amount of internal logic from the start) and introduce the fundamental adjunction in terms of that structure. For them, a power allegory is defined to be a division allegory which associates to each object a morphism such that for all
which expresses the truth of the formula , and
which internalizes an axiom of extensionality, which reads . Given those axioms, and given , one may define
which internalizes the formula-definition , and then show is a map. (See Categories, Allegories, pp. 235-236.)
The bicategory of relations in a topos is a power allegory; conversely, the category of maps in a unitary tabular power allegory is a topos.
Nevertheless, the spare elegance of the naive definition gives one something to shoot for. It appears that quite a decent theory can be developed just by adding the assumption of coproducts in an allegory: a reasonable and fairly mild assumption. (Most allegories don’t admit many colimits; for example having coequalizers is pretty rare. But the standard examples do have finite coproducts, coinciding with coproducts on the maps/functional side.)
A -allegory is an allegory with finite coproducts1 for which the inclusion has a right adjoint .
As before, the counit is denoted . It is perhaps surprising that the notion of -allegory is at least as strong as power allegory in the Freyd-Scedrov sense:
Any -allegory is a division allegory in which the Freyd-Scedrov conditions on are satisfied.
For now we content ourselves with a description of the division structure. Let and be morphisms; we construct a right Kan lift of through . This means that for all we have if and only if . We begin by constructing the right Kan lift for the case .
Define the internal union by , and define an internal order relation by . (Here .) Define .
We now show . That is, for , we show is equivalent to . The backward implication is easy; for the forward implication, one may prove it first for reflexive where we have an actual equation . It follows that , whence . A short calculation then yields . The case for general reduces to the reflexive case: form the reflexive completion as the composite
which is where coproducts come in; here is the codiagonal and we use the fact that in an allegory is a biproduct to form the pairing for the first arrow. It is easy to show that , and then we derive from before. Thus we have shown .
For general , we claim the right Kan lift is given by . For, we have , whence
thus proving the claim.
Further details may be found here.
Thus the notion of -category is just as strong as the Freyd-Scedrov notion of power allegory, and one can then piggy-back on their further developments.
Let be a regular theory. There is then an allegory given as follows:
the objects are finite strings of sorts of ;
a morphism is a predicate of sort (or rather a provable-equivalence class of such predicates);
the identity is (named by) ;
the composite of and is named by .
That is an allegory is B.311 in Freyd–Scedrov; that it is in fact unitary and pre-tabular is B.312.
Every pre-tabular allegory has a tabular completion, given by splitting its coreflexive morphisms (i.e. those endomorphisms such that ). The category of maps in the coreflexive splitting of is precisely the syntactic category of .
There are two possible ways to interpret a regular formula of the form in a unitary pre-tabular allegory, if and are interpreted as and respectively: as the composite , or more ‘literally’ by:
pulling and back to the same hom set and taking their intersection: ;
then forcing the two s to be equal by post-composing with , applying the existential quantifier by post-composing with the unique map to the unit, and post-composing with to get a morphism into ;
then forcing the in the domain to be equal to the in the codomain by taking the meet with ;
and finally pulling back along (precomposing with the right adjoint of) to get a morphism .
We would like to know that these morphisms are equal, so that an existential formula will have a unique interpretation:
We show inclusion in each direction.
Firstly, , because the product projections tabulate the top morphism. Notice also that the RHS above is equal to
where is the top morphism .
Now we can calculate:
In the other direction, we have
and we are back to where we started. In the fourth-last step we used the fact that if are the projections, then . But , and from lemma 1 here we have that .
Other attempted axiomatizations of the same idea “something that acts like the category of relations in a regular category” include:
Discussion of the relation between pretabular unitary allegories and bicategories of relations, and also between tabular unitary allegories and regular categories is in
The standard monograph is
The notion is discussed also in chapter A3 of
it is shown that any bicategory of relations is an allegory.