In Categories, Allegories, Freyd and Scedrov allude to a first attempt to define power allegory as an allegory satisfying a power object axiom: the inclusion has a right adjoint . The word βattemptβ probably signals that this is probably not an optimal definition: we probably need to assume more than just an allegory plus power objects in order to build an interesting theory. Indeed Freyd and Scedrov wind up assuming is a division allegory, embodying quite a lot of internal logic from the get-go, before they introduce power objects.
But the snappy immediacy of the power object axiom leads one to wonder what other assumptions on an allegory lead to a good theory of power allegories. In these notes we will see how far we get if we add one or both of the following assumptions:
The allegory admits finite coproducts (equivalently finite cartesian products, since allegories are self-dual).
The allegory is a bicategory of relations in the sense of Carboni-Walters (equivalently, a unitary pretabular allegory).
Our main focus is on the first assumption, where we show that an allegory with sums satisfying the power object axiom must be a division allegory, and indeed a positive power allegory in the terminology of Freyd-Scedrov, at which point we can piggy-back on their results. This is an interesting and perhaps surprising development, which in a loose sense is dual to the usual development of topos theory. In ordinary topos theory, having a subobject classifier, one may start with negative types (finite limits, exponentials, etc.), and derive positive types and formulas (finite colimits, internal unions, existential quantification, etc.). Whereas in allegory theory, the the initial emphasis is on positive formulas (relational composition is after all guarded existential quantification) and here we assume some positive types (namely finite coproducts); then when we add in the power object axiom, we can derive negative formulas in the form of division allegory structure involving guarded universal quantification. Under the finite coproduct axiom or bicategory of relations axiom, we can also construct some exponentials out of power objects.
Preliminaries
Lemma
If has a right adjoint in an allegory , then .
Proof
Given , we have and . Then
by the modular law. Clearly
as well, so . It follows that , or . By similar reasoning,
and , so or . Thus both and , as desired.
It is not known to me whether allegorical structure is property-like with respect to underlying -enriched categories, but we have the following partial result involving cartesian bicategories (which are property-like with respect to underlying 2-categories).
Theorem
Let be a (locally posetal) cartesian bicategory. Then carries at most one allegory structure. Indeed, a (locally posetal) cartesian bicategory is an allegory iff it is a bicategory of relations.
Proof
First we show that if carries an allegory structure, then it satisfies the Frobenius equations
(where , of course), making a bicategory of relations. Then we show that a bicategory of relations carries exactly one allegory structure.
Given such an allegory , we have for any map and morphisms , the equation
where the inequality comes for free, and the inequality is an instance of the modular law. Now put , , and . Then string diagrammatic calculations show
where is the symmetry isomorphism. The first Frobenius equation follows (and this is enough: if one Frobenius equation holds, then so does the other).
That a bicategory of relations is an allegory is shown in the nLab; here, letting , the opposite of a morphism is given by
The point is that any candidate for an allegorical structure must be equal to these expressions. We have for example
where the second line amounts to an instance of the modular law (taking and ), and the lines thereafter are valid in bicategories of relations. But now it follows that
where the first line follows from identities in bicategories of relations (that are most easily verified through string diagrams). Swapping the roles of and , this gives
The same line of argument shows
followed by
so we are done.
The following result is well-known and is proven in the nLab in the article βbicategory of relationsβ; it will not be reproven here.
Theorem
A bicategory of relations is a compact closed bicategory for which each object is dual to itself, with unit and counit .
In the sequel we will follow customary practice and denote the tensor product in by (which is an actual cartesian product when restricted to ).
First results for power objects
Now suppose our allegory is a power allegory: admits a right adjoint to the inclusion of 1-categories.
Notation:
We generally drop , and denote a component of the counit of by . It can be regarded as opposite to a membership relation (and thus we write , where is the βopposite relationβ involution on an allegory).
The unit is a map and can be regarded as a singleton relation. It is the unique map such that .
In general, given ,
denotes the unique map such that . It is also called the classifying map of .
Definition
Let and be arrows of . The right Kan lift of through , if it exists, is the unique arrow such that for all we have iff .
Existence of right Kan lifts implies that is a division allegory. For if and are arrows, we can form the right Kan extension by , since
Proposition
Suppose that for an object of the arrow exists. Then for every pair , , the arrow exists.
Proof
Since and , we have
where we have used and . Thus .
Define the internal union by , or in other words as the classifying map of the composite
Define the internal order by the composite
Its opposite is . We will show that under suitable conditions, .
Proposition
.
Proof
We have a diagram
Note in fact that the counit 2-cell is an equality because retracts (see the following proposition): we have where the inequality uses the counit .
Proposition
The internal relation is reflexive: .
Proof
By a triangular equation for the adjunction , we have . Thus , and it suffices to show . But this is equivalent to , which holds as an instance of the other triangular equation.
Proposition
If is reflexive, then if and only if .
Proof
If , then by Proposition . If and , then also , so . In that case, , which implies . We then have . This completes the proof.
Proposition
is transitive: .
Proof
By Proposition , is reflexive. So, by Proposition , it suffices to observe that , but this is immediate from Proposition .
Power allegories with sums
In addition to the power object axiom, we assume in this section that the allegory has coproducts . As we remarked earlier, also plays the role of cartesian product since allegories are dagger categories (or alternatively since allegories have local meets and are therefore -enriched). It follows, since right adjoints preserve products, that is a product in .
Let denote the initial object of .
Lemma
For any object , the unique arrow is a map (a left adjoint), and is also a map.
Proof
Of course there exists a map that classifies the arrow , and this map is the unique arrow . Then, we have , so we have a counit , which implies
giving a counit for a putative adjunction . On the other hand, we also have a unit , in fact an equality there is only one arrow in the first place.
Lemma
The coproduct functor preserves local meets (and in particular is -enriched).
Proof
This follows from a more general lemma that if the underlying category of a -enriched category has coproducts/biproducts, then the coproduct/biproduct functor is -enriched. This amounts to a claim of type
where the matrix entries on the right may be extracted by pre-composing and post-composing with coproduct injections and product injections, e.g., where is the matrix sum on the left, and we use the fact that such composition is -enriched.
Lemma
The coproduct inclusion arrows are maps.
Proof
Since is -enriched, it takes left adjoints to left adjoints. Hence is a map, and this may be identified with a map , the first coproduct inclusion. Similarly, is a map.
Lemma
The codiagonal is a map.
Proof
In fact we claim that the map must be . By the previous lemma, and are maps; they classify and . But is the unique classifying map of ; therefore and . At the same time, is the unique arrow in such that . We conclude .
Lemma
The codiagonal satisfies .
Proof
By the previous lemma, the composite is a map, being a composite of maps . Thus we have a counit
which leads to . On the other hand, retracts the map , and so
using the counit . Thus .
Lemma
The arrow is the bottom element of the poset .
Proof
Since is a map, we have a counit . Hence for any . But because is terminal. Hence .
Theorem
The poset admits binary joins: given , the composite
is the join of and .
Proof
For now we give a sketch. It is clear that is a poset morphism, as is . One checks that and , so we have and . Next, for any we have as may be seen from the diagram
where the commutativity of the triangle is Lemma . Thus if and , we have . This completes the proof.
Lemma
If is an arrow such that , then also satisfies .
Proof
We have a commutative diagram
which shows that , as desired.
Theorem
A power allegory with coproducts is a division allegory.
Proof
First we establish the residuation, i.e. the division operations and . According to Proposition , we need only exhibit , which we claim is . That is, we need only show that for , we have if and only if . The βifβ follows from Proposition . For the only if, use the fact that implies by Lemma , and since is reflexive, we have by Proposition , whence as desired.
We have seen that is a join semi-lattice; the residuation implies that composition on either side preserves joins as well.
The results 2.214-2.216 of Freyd-Scedrov assure us that is a distributive lattice, that and are maps, and finally that coproducts are biproducts.
At this point the connection between the Freyd-Scedrov notion of power allegory and the notion adopted here (allegory with coproducts and power objects) is practically an afterthought, but we may as well show that the Freyd-Scedrov axioms on are satisfied. (Hmmβ¦)
Bicategories of relations with power objects
Proposition
If the power allegory is a bicategory of relations, then is an exponential in for all objects . In particular, for all .
Proof
There are natural isomorphisms
whence satisfies the universal property that characterizes an exponential in .
Revised on December 1, 2019 at 19:06:59
by
Todd Trimble