Todd Trimble
Note on power allegories

Contents

In Categories, Allegories, Freyd and Scedrov allude to a first attempt to define power allegory as an allegory π’œ\mathcal{A} satisfying a power object axiom: the inclusion i:Map(π’œ)β†’π’œi: Map(\mathcal{A}) \to \mathcal{A} has a right adjoint PP. 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 π’œ\mathcal{A} 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:

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 r:Aβ†’Br: A \to B has a right adjoint s:Bβ†’As: B \to A in an allegory π’œ\mathcal{A}, then s=r ops = r^{op}.

Proof

Given r⊣sr \dashv s, we have 1 A≀sr1_A \leq s r and rs≀1 Br s \leq 1_B. Then

1 A=sr∧1 A≀(s∧1 Ar op)r=(s∧r op)r1_A = s r \wedge 1_A \leq (s \wedge 1_A r^{op})r = (s \wedge r^{op})r

by the modular law. Clearly

r(s∧r op)≀rs≀1 Br(s \wedge r^{op}) \leq r s \leq 1_B

as well, so r⊣s∧r opr \dashv s \wedge r^{op}. It follows that s=s∧r ops = s \wedge r^{op}, or s≀r ops \leq r^{op}. By similar reasoning,

1 A=sr∧1 A≀s(r∧s op1 A)=s(r∧s op)1_A = s r \wedge 1_A \leq s(r \wedge s^{op} 1_A) = s(r \wedge s^{op})

and r∧s op⊣sr \wedge s^{op} \dashv s, so r∧s op=rr \wedge s^{op} = r or r≀s opr \leq s^{op}. Thus both r op≀sr^{op} \leq s and s≀r ops \leq r^{op}, as desired.

It is not known to me whether allegorical structure is property-like with respect to underlying PosPos-enriched categories, but we have the following partial result involving cartesian bicategories (which are property-like with respect to underlying 2-categories).

Theorem

Let B\mathbf{B} be a (locally posetal) cartesian bicategory. Then B\mathbf{B} 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 B\mathbf{B} carries an allegory structure, then it satisfies the Frobenius equations

δδ op=(Ξ΄ opβŠ—1)(1βŠ—Ξ΄)=(1βŠ—Ξ΄ op)(Ξ΄βŠ—1)\delta \delta^{op} = (\delta^{op} \otimes 1)(1 \otimes \delta) = (1 \otimes \delta^{op})(\delta \otimes 1)

(where δ⊣δ op\delta \dashv \delta^{op}, of course), making B\mathbf{B} a bicategory of relations. Then we show that a bicategory of relations carries exactly one allegory structure.

Given such an allegory B\mathbf{B}, we have for any map f:A→Bf: A \to B and morphisms r:B→Cr: B \to C, s:A→Cs: A \to C the equation

(s∧rf)f op=sf op∧r(s \wedge r f)f^{op} = s f^{op} \wedge r

where the inequality ≀\leq comes for free, and the inequality β‰₯\geq is an instance of the modular law. Now put f=Ξ΄ Af = \delta_A, r=Ο΅ A opβŠ—1 Ar = \epsilon_A^{op} \otimes 1_A, and s=Ο΅ AβŠ—1 AβŠ—Ο΅ A ops = \epsilon_A \otimes 1_A \otimes \epsilon_A^{op}. Then string diagrammatic calculations show

(s∧rf)f op=Οƒ AΞ΄ AΞ΄ A op(s \wedge r f)f^{op} = \sigma_A \delta_A \delta_A^{op}
sf op∧r=Οƒ A(Ξ΄ A opβŠ—1 A)(1 AβŠ—Ξ΄ A)s f^{op} \wedge r = \sigma_A (\delta_A^{op} \otimes 1_A)(1_A \otimes \delta_A)

where Οƒ A:AβŠ—Aβ†’AβŠ—A\sigma_A: A \otimes A \to A \otimes A 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 B\mathbf{B} is an allegory is shown in the nLab; here, letting Ξ· A=Ξ΄ AΟ΅ A op:1β†’AβŠ—A\eta_A = \delta_A \epsilon_A^{op}: 1 \to A \otimes A, the opposite of a morphism r:Aβ†’Br: A \to B is given by

r op≔(Ξ· B opβŠ—1 A)(1 BβŠ—rβŠ—1 A)(1 BβŠ—Ξ· A)=(1 AβŠ—Ξ· B op)(1 AβŠ—rβŠ—1 B)(Ξ· AβŠ—1 B).r^{op} \coloneqq (\eta_B^{op} \otimes 1_A)(1_B \otimes r \otimes 1_A)(1_B \otimes \eta_A) = (1_A \otimes \eta_B^{op})(1_A \otimes r \otimes 1_B)(\eta_A \otimes 1_B).

The point is that any candidate r opr^{op} for an allegorical structure must be equal to these expressions. We have for example

(Ξ· B opβŠ—1 A)(1 BβŠ—rβŠ—1 A)(1 BβŠ—Ξ· A) = (Ο΅ BβŠ—1 A)(Ξ΄ B opβŠ—1 A)(1 BβŠ—rβŠ—1 A)(1 BβŠ—Ξ· A) ≀ (Ο΅ BβŠ—1 A)(rβŠ—1 A)(Ξ΄ B opβŠ—1 A)(r opβŠ—1 AβŠ—1 A)(1 BβŠ—Ξ· A) ≀ (Ο΅ BβŠ—1 A)(Ξ΄ B opβŠ—1 A)(r opβŠ—1 AβŠ—1 A)(1 BβŠ—Ξ· A) = r op(Ξ· A opβŠ—1 A)(1 AβŠ—Ξ· A) = r op\array{ (\eta_B^{op} \otimes 1_A)(1_B \otimes r \otimes 1_A)(1_B \otimes \eta_A) & = & (\epsilon_B \otimes 1_A)(\delta_B^{op} \otimes 1_A)(1_B \otimes r \otimes 1_A)(1_B \otimes \eta_A) \\ & \leq & (\epsilon_B \otimes 1_A)(r \otimes 1_A)(\delta_B^{op} \otimes 1_A)(r^{op} \otimes 1_A \otimes 1_A)(1_B \otimes \eta_A) \\ & \leq & (\epsilon_B \otimes 1_A)(\delta_B^{op} \otimes 1_A)(r^{op} \otimes 1_A \otimes 1_A)(1_B \otimes \eta_A) \\ & = & r^{op}(\eta_A^{op} \otimes 1_A)(1_A \otimes \eta_A) \\ & = & r^{op} }

where the second line amounts to an instance of the modular law t∧rs≀r(r opt∧s)t \wedge r s \leq r(r^{op} t \wedge s) (taking t=Ο€ 1:BβŠ—Aβ†’Bt = \pi_1: B \otimes A \to B and s=Ο€ 2:BβŠ—Aβ†’As = \pi_2: B \otimes A \to A), and the lines thereafter are valid in bicategories of relations. But now it follows that

r = (1 BβŠ—Ξ· A op)(1 BβŠ—Ξ· B opβŠ—1 AβŠ—A)(1 BβŠ—BβŠ—rβŠ—1 AβŠ—A)(1 BβŠ—BβŠ—Ξ· AβŠ—1 A)(Ξ· BβŠ—1 A) ≀ (1 BβŠ—Ξ· A op)(1 BβŠ—r opβŠ—1 A)(Ξ· BβŠ—1 A)\array{ r & = & (1_B \otimes \eta_A^{op})(1_B \otimes \eta_B^{op} \otimes 1_{A \otimes A})(1_{B \otimes B} \otimes r \otimes 1_{A \otimes A})(1_{B \otimes B} \otimes \eta_A \otimes 1_A)(\eta_B \otimes 1_A) \\ & \leq & (1_B \otimes \eta_A^{op})(1_B \otimes r^{op} \otimes 1_A)(\eta_B \otimes 1_A) }

where the first line follows from identities in bicategories of relations (that are most easily verified through string diagrams). Swapping the roles of rr and r opr^{op}, this gives

r op≀(1 AβŠ—Ξ· B op)(1 AβŠ—rβŠ—1 B)(Ξ· AβŠ—1 B).r^{op} \leq (1_A \otimes \eta_B^{op})(1_A \otimes r \otimes 1_B)(\eta_A \otimes 1_B).

The same line of argument shows

(1 AβŠ—Ξ· B op)(1 AβŠ—rβŠ—1 B)(Ξ· AβŠ—1 B)≀r op(1_A \otimes \eta_B^{op})(1_A \otimes r \otimes 1_B)(\eta_A \otimes 1_B) \leq r^{op}

followed by

r op≀(Ξ· B opβŠ—1 A)(1 BβŠ—rβŠ—1 A)(1 BβŠ—Ξ· A),r^{op} \leq (\eta_B^{op} \otimes 1_A)(1_B \otimes r \otimes 1_A)(1_B \otimes \eta_A),

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 B\mathbf{B} is a compact closed bicategory for which each object BB is dual to itself, with unit Ξ· B:1β†’BβŠ—B\eta_B: 1 \to B \otimes B and counit Ξ· B op:BβŠ—Bβ†’1\eta_B^{op}: B \otimes B \to 1.

In the sequel we will follow customary practice and denote the tensor product in B\mathbf{B} by Γ—\times (which is an actual cartesian product when restricted to Map(B)Map(\mathbf{B})).

First results for power objects

Now suppose our allegory B\mathbf{B} is a power allegory: admits a right adjoint PP to the inclusion i:Map(B)β†’Bi: Map(\mathbf{B}) \to \mathbf{B} of 1-categories.

Notation:

  1. We generally drop ii, and denote a component of the counit of i⊣Pi \dashv P by βˆ‹ A:P(A)β†’A\ni_A \colon P(A) \to A. It can be regarded as opposite to a membership relation (and thus we write ∈ A=βˆ‹ A o\in_A = \ni_A^o, where (βˆ’) o(-)^o is the β€œopposite relation” involution on an allegory).

  2. The unit Οƒ:Aβ†’P(A)\sigma \colon A \to P(A) is a map and can be regarded as a singleton relation. It is the unique map f:Aβ†’P(A)f \colon A \to P(A) such that βˆ‹ Cf=1 A\ni_C f = 1_A.

  3. In general, given r:A→Br \colon A \to B,

    χ r:A→P(B)\chi_r \colon A \to P(B)

    denotes the unique map such that βˆ‹ BΟ‡ r=r\ni_B \chi_r = r. It is also called the classifying map of rr.

Definition

Let r:Aβ†’Cr: A \to C and s:Bβ†’Cs: B \to C be arrows of B\mathbf{B}. The right Kan lift s\rs \backslash r of rr through ss, if it exists, is the unique arrow Aβ†’BA \to B such that for all t:Aβ†’Bt: A \to B we have t≀s\rt \leq s \backslash r iff st≀rs t \leq r.

Existence of right Kan lifts implies that B\mathbf{B} is a division allegory. For if r:A→Br: A \to B and s:A→Cs: A \to C are arrows, we can form the right Kan extension r/s:B→Cr/s: B \to C by r/s=(s o\r o) or/s = (s^o\backslash r^o)^o, since

t≀r/s⇔t≀(s o\r o) o⇔t o≀s o\r o⇔s ot o=(ts) o≀r o⇔ts≀r.t \leq r/s \Longleftrightarrow t \leq (s^o\backslash r^o)^o \Longleftrightarrow t^o \leq s^o\backslash r^o \Longleftrightarrow s^o t^o = (t s)^o \leq r^o \Longleftrightarrow t s \leq r.
Proposition

Suppose that for an object CC of B\mathbf{B} the arrow βˆ‹ C\βˆ‹ C\ni_C\backslash \ni_C exists. Then for every pair r:Aβ†’Cr: A \to C, s:Bβ†’Cs: B \to C, the arrow s\r:Aβ†’Bs \backslash r: A \to B exists.

Proof

Since r=βˆ‹ CΟ‡ rr = \ni_C \chi_r and s=βˆ‹ CΟ‡ ss = \ni_C \chi_s, we have

st≀r iff βˆ‹ CΟ‡ stβ‰€βˆ‹ CΟ‡ r iff βˆ‹ CΟ‡ stΟ‡ r oβ‰€βˆ‹ C iff Ο‡ stΟ‡ r oβ‰€βˆ‹ C\βˆ‹ C iff t≀χ s o(βˆ‹ C\βˆ‹ C)Ο‡ r\array{ s t \leq r & iff & \ni_C \chi_s t \leq \ni_C \chi_r \\ & iff & \ni_C \chi_s t \chi_r^o \leq \ni_C \\ & iff & \chi_s t \chi_r^o \leq \ni_C \backslash \ni_C \\ & iff & t \leq \chi_s^o (\ni_C \backslash \ni_C) \chi_r }

where we have used Ο‡ rβŠ£Ο‡ r o\chi_r \dashv \chi_r^o and Ο‡ sβŠ£Ο‡ s o\chi_s \dashv \chi_s^o. Thus s\r=Ο‡ s o(βˆ‹ C\βˆ‹ C)Ο‡ rs \backslash r = \chi_s^o (\ni_C \backslash \ni_C) \chi_r.

Define the internal union by ⋃ C=P(βˆ‹ C):PP(C)β†’P(C)\bigcup_C = P(\ni_C): P P(C) \to P(C), or in other words as the classifying map of the composite

PP(C)β†’βˆ‹ P(C)P(C)β†’βˆ‹ CC.P P(C) \stackrel{\ni_{P(C)}}{\to} P(C) \stackrel{\ni_C}{\to} C.

Define the internal order [β‡’]:P(C)β†’P(C)[\Rightarrow] \colon P(C) \to P(C) by the composite

P(C)β†’βˆˆ P(C)PP(C)→⋃ CP(C).P(C) \stackrel{\in_{P(C)}}{\to} P P(C) \stackrel{\bigcup_C}{\to} P(C).

Its opposite is [⇐]β‰”βˆ‹ P(C)⋃ C o[\Leftarrow] \coloneqq \ni_{P(C)} \bigcup_C^o. We will show that under suitable conditions, [⇐]=βˆ‹ C\βˆ‹ C[\Leftarrow] = \ni_C \backslash \ni_C.

Proposition

βˆ‹ C[⇐]β‰€βˆ‹ C\ni_C [\Leftarrow] \leq \ni_C.

Proof

We have a diagram

PC →⋃ C o PPC β†’βˆ‹ PC PC 1β†˜β‰₯ ↓⋃ C β†“βˆ‹ C PC β†’βˆ‹ C C\array{ P C & \stackrel{\bigcup_C^o}{\to} & P P C & \stackrel{\ni_{P C}}{\to} & P C \\ & \mathllap{1} \searrow \geq & \downarrow \mathrlap{\bigcup_C} & & \downarrow \mathrlap{\ni_C} \\ & & P C & \underset{\ni_C}{\to} & C }

Note in fact that the counit 2-cell β‰₯\geq is an equality because ⋃ C\bigcup_C retracts Οƒ PC\sigma_{P C} (see the following proposition): we have 1=⋃ CΟƒ PCΟƒ PC o⋃ C o≀⋃ C⋃ C o1 = \bigcup_C \sigma_{P C} \sigma_{P C}^o \bigcup_C^o \leq \bigcup_C \bigcup_C^o where the inequality uses the counit σσ o≀1\sigma \sigma^o \leq 1.

Proposition

The internal relation [⇐]:PCβ†’PC[\Leftarrow]: P C \to P C is reflexive: 1 PC≀[⇐]1_{P C} \leq [\Leftarrow].

Proof

By a triangular equation for the adjunction i⊣P:Bβ†’Map(B)i \dashv P: \mathbf{B} \to Map(\mathbf{B}), we have 1 PC=P(βˆ‹ C)Οƒ PC=⋃ CΟƒ PC1_{P C} = P(\ni_C) \sigma_{P C} = \bigcup_C \sigma_{P C}. Thus 1 PC=Οƒ PC o⋃ C o1_{P C} = \sigma_{P C}^o \bigcup_C^o, and it suffices to show Οƒ PC oβ‰€βˆ‹ PC:PPCβ†’PC\sigma_{P C}^o \leq \ni_{P C}: P P C \to P C. But this is equivalent to 1 PCβ‰€βˆ‹ PCΟƒ PC1_{P C} \leq \ni_{P C} \sigma_{P C}, which holds as an instance of the other triangular equation.

Proposition

If R:PCβ†’PCR: P C \to P C is reflexive, then βˆ‹ CRβ‰€βˆ‹ C\ni_C R \leq \ni_C if and only if R≀[⇐]R \leq {[\Leftarrow]}.

Proof

If R≀[⇐]R \leq [\Leftarrow], then βˆ‹ CRβ‰€βˆ‹ C[⇐]β‰€βˆ‹ C\ni_C R \leq \ni_C [\Leftarrow] \leq \ni_C by Proposition 2. If βˆ‹ CRβ‰€βˆ‹ C\ni_C R \leq \ni_C and 1≀R1 \leq R, then also βˆ‹ Cβ‰€βˆ‹ CR\ni_C \leq \ni_C R, so βˆ‹ CR=βˆ‹ C\ni_C R = \ni_C. In that case, P(βˆ‹ C)P(R)=P(βˆ‹ C)P(\ni_C) P(R) = P(\ni_C), which implies P(R)≀P(βˆ‹ C) oP(βˆ‹ C)=⋃ C oP(βˆ‹ C)P(R) \leq P(\ni_C)^o P(\ni_C) = \bigcup_C^o P(\ni_C). We then have R=βˆ‹ PCP(R)Οƒ PCβ‰€βˆ‹ PC⋃ C oP(βˆ‹ C)Οƒ PC=βˆ‹ PC⋃ C o=[⇐]R = \ni_{P C} P(R) \sigma_{P C} \leq \ni_{P C} \bigcup _C^o P(\ni_C) \sigma_{P C} = \ni_{P C} \bigcup_C^o = [\Leftarrow]. This completes the proof.

Proposition

[⇐][\Leftarrow] is transitive: [⇐]∘[⇐]≀[⇐][\Leftarrow] \circ [\Leftarrow] \leq [\Leftarrow].

Proof

By Proposition 3, [⇐][⇐][\Leftarrow] [\Leftarrow] is reflexive. So, by Proposition 4, it suffices to observe that βˆ‹ C[⇐][⇐]β‰€βˆ‹ C\ni_C [\Leftarrow] [\Leftarrow] \leq \ni_C, but this is immediate from Proposition 2.

Power allegories with sums

In addition to the power object axiom, we assume in this section that the allegory B\mathbf{B} has coproducts A+BA + B. As we remarked earlier, A+BA + B also plays the role of cartesian product since allegories are dagger categories. It follows, since right adjoints preserve products, that P(A+B)P(A + B) is a product P(A)Γ—P(B)P(A) \times P(B) in Map(B)Map(\mathbf{B}).

Let 00 denote the initial object of B\mathbf{B}.

Lemma

For any object CC, the unique arrow ! PC:0β†’PC!_{P C}: 0 \to P C is a map (a left adjoint), and ! C:0β†’C!_C: 0 \to C is also a map.

Proof

Of course there exists a map Ο‡ ! C:0β†’PC\chi_{!_C}: 0 \to P C that classifies the map ! C:0β†’C!_C: 0 \to C is the unique arrow ! PC:0β†’PC!_{P C}: 0 \to P C. Then, we have Οƒ C! C=! PC\sigma_C !_C = !_{P C}, so we have a counit Οƒ C! PC! PC oΟƒ C o≀1\sigma_C !_{P C} !_{P C}^o \sigma_C^o \leq 1, which implies

! C! C o≀σ C oΟƒ C=βˆ‹ CΟƒ CΟƒ C oΟƒ C=βˆ‹ CΟƒ C=1!_C !_C^o \leq \sigma_C^o \sigma_C = \ni_C \sigma_C \sigma_C^o \sigma_C = \ni_C \sigma_C = 1

giving a counit for a putative adjunction ! C⊣! C o!_C \dashv !_C^o. On the other hand, we also have a unit 1 0≀! C o! C1_0 \leq !_C^o !_C, in fact an equality there is only one arrow 0β†’00 \to 0 in the first place.

Lemma

The coproduct functor +:B×B→B+: \mathbf{B} \times \mathbf{B} \to \mathbf{B} preserves local meets (and in particular is PosPos-enriched).

Proof

Let A=(A 1,A 2)A = (A_1, A_2) and B=(B 1,B 2)B = (B_1, B_2) be objects of CΓ—C\mathbf{C} \times \mathbf{C}. The component at BB unit of the SetSet-enriched adjunction +βŠ£Ξ”+ \dashv \Delta is (i 1,i 2):(B 1,B 2)β†’(B 1+B 2,B 1+B 2)(i_1, i_2): (B_1, B_2) \to (B_1 + B_2, B_1 + B_2). Composition along i 1i_1 and i 2i_2 preserves meets. So all three arrows of

hom((A 1,A 2),(B 1,B 2))β†’hom((A 1,A 2),(B 1+B 2,B 1+B 2))β‰…hom(A 1,B 1+B 2)Γ—hom(A 2,B 1+B 2)β†’βˆΌhom(A 1+A 2,B 1+B 2)\hom((A_1, A_2), (B_1, B_2)) \to \hom((A_1, A_2), (B_1 + B_2, B_1 + B_2)) \cong \hom(A_1, B_1 + B_2) \times \hom(A_2, B_1 + B_2) \stackrel{\sim}{\to} \hom(A_1 + A_2, B_1 + B_2)

preserve order (the last because its (…)

Lemma

The coproduct inclusion arrows i 1,i 2:C→C+Ci_1, i_2: C \to C + C are maps.

Proof

Since C+βˆ’:Bβ†’BC + -: \mathbf{B} \to \mathbf{B} is PosPos-enriched, it takes left adjoints to left adjoints. Hence C+! C:C+0β†’C+CC + !_C: C + 0 \to C + C is a map, and this may be identified with a map i 1:Cβ†’C+Ci_1: C \to C + C, the first coproduct inclusion. Similarly, i 2i_2 is a map.

Lemma

The codiagonal βˆ‡ PC:PC+PCβ†’PC\nabla_{P C}: P C + P C \to P C is a map.

Proof

In fact we claim that the map χ≔χ (βˆ‹ C,βˆ‹ C):PC+PCβ†’PC\chi \coloneqq \chi_{(\ni_C, \ni_C)}: P C + P C \to P C must be βˆ‡\nabla. By the previous lemma, Ο‡i 1\chi i_1 and Ο‡i 2\chi i_2 are maps; they classify (βˆ‹ C,βˆ‹ C)∘i 1=βˆ‹ C(\ni_C, \ni_C) \circ i_1 = \ni_C and (βˆ‹ C,βˆ‹ C)∘i 2=βˆ‹ C(\ni_C, \ni_C) \circ i_2 = \ni_C. But 1 PC:PCβ†’PC1_{P C}: P C \to P C is the unique classifying map of βˆ‹ C\ni_C; therefore Ο‡i 1=1 PC\chi i_1 = 1_{P C} and Ο‡i 2=1 PC\chi i_2 = 1_{P C}. At the same time, βˆ‡:PC+PCβ†’PC\nabla: P C + P C \to P C is the unique arrow ff in B\mathbf{B} such that fi 1=1 PC=fi 2f i_1 = 1_{P C} = f i_2. We conclude βˆ‡=Ο‡\nabla = \chi.

Lemma

The codiagonal βˆ‡ C:C+Cβ†’C\nabla_C: C + C \to C satisfies βˆ‡ Cβˆ‡ C o=1 C\nabla_C \nabla_C^o = 1_C.

Proof

By the previous lemma, the composite Οƒ Cβˆ‡ C\sigma_C \nabla_C is a map, being a composite of maps βˆ‡ PC∘(Οƒ C+Οƒ C)\nabla_{P C} \circ (\sigma_C + \sigma_C). Thus we have a counit

Οƒ Cβˆ‡ Cβˆ‡ C oΟƒ C o≀1\sigma_C \nabla_C \nabla_C^o \sigma_C^o \leq 1

which leads to βˆ‡ Cβˆ‡ C o≀σ C oΟƒ C=1\nabla_C \nabla_C^o \leq \sigma_C^o \sigma_C = 1. On the other hand, βˆ‡ C\nabla_C retracts the map i 1:Cβ†’C+Ci_1: C \to C + C, and so

1 C=βˆ‡ Ci 1i 1 oβˆ‡ C oβ‰€βˆ‡ Cβˆ‡ C o1_C = \nabla_C i_1 i_1^o \nabla_C^o \leq \nabla_C \nabla_C^o

using the counit i 1i 1 o≀1i_1 i_1^o \leq 1. Thus 1 C=βˆ‡ Cβˆ‡ C o1_C = \nabla_C \nabla_C^o.

Lemma

The arrow βŠ₯≔! D∘! C o:Cβ†’D\bot \coloneqq !_D \circ !_C^o: C \to D is the bottom element of the poset B(C,D)\mathbf{B}(C, D).

Proof

Since ! D:0β†’D!_D: 0 \to D is a map, we have a counit ! D! D o≀1 D!_D !_D^o \leq 1_D. Hence ! D! D oS≀S!_D !_D^o S \leq S for any S∈B(C,D)S \in \mathbf{B}(C, D). But ! D oS=! C o:Cβ†’0!_D^o S = !_C^o: C \to 0 because 00 is terminal. Hence ! D! C o≀S!_D !_C^o \leq S.

Theorem

The poset B(C,D)\mathbf{B}(C, D) admits binary joins: given R,S:C→DR, S: C \to D, the composite

R∨S≔(Cβ†’βˆ‡ oC+Cβ†’R+SD+Dβ†’βˆ‡D)R \vee S \coloneqq (C \stackrel{\nabla^o}{\to} C + C \stackrel{R + S}{\to} D + D \stackrel{\nabla}{\to} D)

is the join of RR and SS.

Proof

For now we give a sketch. It is clear that Rβˆ¨βˆ’:B(C,D)β†’B(C,D)R \vee -: \mathbf{B}(C, D) \to \mathbf{B}(C, D) is a poset morphism, as is βˆ’βˆ¨S- \vee S. One checks that R∨βŠ₯=RR \vee \bot = R and βŠ₯∨S=S\bot \vee S = S, so we have R=R∨βŠ₯≀R∨SR = R \vee \bot \leq R \vee S and S=βŠ₯∨S≀R∨SS = \bot \vee S \leq R \vee S. Next, for any T:Cβ†’DT: C \to D we have T∨T=TT \vee T = T as may be seen from the diagram

C β†’βˆ‡ o C+C β†’T+T D+D 1β†˜= βˆ‡β†“ β†“βˆ‡ C β†’T D\array{ C & \stackrel{\nabla^o}{\to} & C + C & \stackrel{T + T}{\to} & D + D \\ & \mathllap{1} \searrow = & \mathllap{\nabla} \downarrow & & \downarrow \mathrlap{\nabla} \\ & & C & \underset{T}{\to} & D }

where the commutativity of the triangle is Lemma 6. Thus if R≀TR \leq T and S≀TS \leq T, we have R∨S≀T∨T=TR \vee S \leq T \vee T = T. This completes the proof.

Lemma

If R:PCβ†’PCR: P C \to P C is an arrow such that βˆ‹ CRβ‰€βˆ‹ C\ni_C R \leq \ni_C, then 1 PC∨R1_{P C} \vee R also satisfies βˆ‹ C(1∨R)β‰€βˆ‹ C\ni_C (1 \vee R) \leq \ni_C.

Proof

We have a commutative diagram

PC β†’βˆ‡ o PC+PC β†’1+R PC+PC β†’βˆ‡ PC βˆ‹ C+βˆ‹ CR↓ (βˆ‹ C,βˆ‹ C)↓ β†™βˆ‹ C C+C β†’βˆ‡ C\array{ P C & \stackrel{\nabla^o}{\to} & P C + P C & \stackrel{1 + R}{\to} & P C + P C & \stackrel{\nabla}{\to} & P C \\ & & \mathllap{\ni_C + \ni_C R} \downarrow & & \mathllap{(\ni_C, \ni_C)} \downarrow & \swarrow \mathrlap{\ni_C} \\ & & C + C & \underset{\nabla}{\to} & C }

which shows that βˆ‹ C(1∨R)=βˆ‹ Cβˆ¨βˆ‹ CR=βˆ‹ C\ni_C (1 \vee R) = \ni_C \vee \ni_C R = \ni_C, as desired.

Theorem

A power allegory with coproducts is a division allegory.

Proof

First we establish the residuation, i.e. the division operations // and \\backslash. According to Proposition 1, we need only exhibit βˆ‹ C\βˆ‹ C\ni_C \backslash \ni_C, which we claim is [⇐]=βˆ‹ PC⋃ C o[\Leftarrow] = \ni_{P C} \bigcup_C^o. That is, we need only show that for R:PCβ†’PCR: P C \to P C, we have βˆ‹ CRβ‰€βˆ‹ C\ni_C R \leq \ni_C if and only if R≀[⇐]R \leq [\Leftarrow]. The β€œif” follows from Proposition 3. For the only if, use the fact that βˆ‹ CRβ‰€βˆ‹ C\ni_C R \leq \ni_C implies βˆ‹ C(1∨R)β‰€βˆ‹ C\ni_C (1 \vee R) \leq \ni_C by Lemma 8, and since 1∨R1 \vee R is reflexive, we have 1∨R≀[⇐]1 \vee R \leq [\Leftarrow] by Proposition 4, whence R≀1∨R≀[⇐]R \leq 1 \vee R \leq [\Leftarrow] as desired.

We have seen that B(C,D)\mathbf{B}(C, D) 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 B(C,D)\mathbf{B}(C, D) is a distributive lattice, that 0β†’C0 \to C and βˆ‡:C+Cβ†’C\nabla: C + C \to C 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 βˆ‹:iPβ†’1\ni: i P \to 1 are satisfied. (Hmm…)

Bicategories of relations with power objects

Proposition

If the power allegory B\mathbf{B} is a bicategory of relations, then P(BΓ—C)P(B \times C) is an exponential P(C) BP(C)^B in Map(B)Map(\mathbf{B}) for all objects B,CB, C. In particular, P(B)β‰…P(1) BP(B) \cong P(1)^B for all BB.

Proof

There are natural isomorphisms

Map(B)(AΓ—B,P(C)) β‰… B(AΓ—B,C) β‰… B(A,BΓ—C) bycompactclosure β‰… Map(B)(A,P(BΓ—C))\array{ Map(\mathbf{B})(A \times B, P(C)) & \cong & \mathbf{B}(A \times B, C) & \\ & \cong & \mathbf{B}(A, B \times C) & by\; compact\; closure\\ & \cong & Map(\mathbf{B})(A, P(B \times C)) }

whence P(BΓ—C)P(B \times C) satisfies the universal property that characterizes an exponential P(C) BP(C)^B in Map(B)Map(\mathbf{B}).

Revised on October 29, 2016 at 13:16:56 by Todd Trimble