Theory and Applications of Categories, Vol. 1, No. 6, 1995, pp. 119–145.

DISTRIBUTIVE ADJOINT STRINGS

ROBERT ROSEBRUGH AND R. J. WOOD

Transmitted by Michael Barr

ABSTRACT. For an adjoint string V ⊣ W ⊣ X ⊣ Y : B ⟶ C, with Y fully faithful, it is frequently, but not always, the case that the composite V Y underlies an idempotent monad. When it does, we call the string distributive. We also study shorter and longer ‘distributive’ adjoint strings and how to generate them. These provide a new construction of the simplicial 2-category, Δ.

1. Introduction

Consider a string of adjoint functors, V ⊣ W ⊣ X ⊣ Y : B ⟶ C, with Y fully faithful. The composite V Y is a well-pointed endofunctor so that it is natural to ask whether it underlies an idempotent monad on B. Somewhat surprisingly, in light of the examples that come readily to mind, this is an additional property for a string of adjoint functors.

If the string above has also Y ⊣ Z then it is equivalent to ask whether the composite ZW underlies an idempotent comonad. Since the question makes sense in any bicategory and any functor Y has a right adjoint in the larger bicategory of profunctors, it follows that the question can be asked for a shorter string of adjoint functors, W ⊣ X ⊣ Y : B ⟶ C, with Y fully faithful, the situation that Lawvere [8] refers to as a unity and identity of adjoint opposites and abbreviates by UIAO.

In fact, these observations allow us to ask our question for a UIAO in a 2-category with proarrow equipment.

We begin with a section of examples and a counterexample. After a brief section on comonads and distributive laws we settle the original question and prove some related exactness results. Here the point of view is that certain adjoint strings, which we call distributive, admit a calculus of what might be called cosimplicial kernels. We speak here of constructing “shorter” adjoint strings.

It transpires that the same set of conditions also permit the construction of cosimplicial cokernels. We speak of constructing “longer” adjoint strings. The shortening and lengthening constructions are related, as we note. It becomes clear that our distributivity conditions find their paradigm in Δ, the simplicial 2-category and we close with a section that addresses this point.

Research partially supported by grants from NSERC Canada. Diagrams typeset using M. Barr’s diagram macros.

Received by the editors 26 June 1995.

Published on 8 September 1995

1991 Mathematics Subject Classification : 18A40, 18C15 .

Key words and phrases: adjoint functor, distributivity, simplicial 2-category.

\begin{matrix}c \\ ◯ \end{matrix} Robert Rosebrugh and R. J. Wood 1995. Permission to copy for private use granted.

Throughout this paper we work in a 2-category K equipped with proarrows (−)_{∗} : K ⟶ M which satisfy the axioms in [21], restated below without comment. In Section 4 we introduce Axiom 5, a weakening of the Axiom (S) which appeared in [16]. Thus, our results apply not only to functors but also, for example, to geometric morphisms between toposes. However, we will refer to the arrows of K as functors and to the arrows of M as profunctors, whenever possible, so that familiarity with [21] is a prerequisite only for the fullest extent of the results.

Axiom 1 (−)_{∗} : K ⟶ M is a homomorphism of bicategories which is the identity on objects and locally fully faithful.

Axiom 2 For every arrow Y : B ⟶ C in K, there is an adjunction η_{Y} , ϵ_{Y} : Y ⊣ Y^{∗} in M.

Axiom 3 M has finite sums with injections in K. Universality restricts to K and the right adjoints of injections provide also product projections in M.

Axiom 4 M has Kleisli objects for monads with injections in K. Universality restricts to K and the right adjoints of injections provide also Eilenberg-Moore projections in M.

Arrows of M that are not assumed to be arrows of K are denoted by slashed arrows of the form C \overline{}B.

2. Examples and a Counterexample

1) For B any category, take C to be B^{2} and V = codomain : C ⟶ B. Then V ⊣ (W = identity) ⊣ (X = domain). If B has a terminal object then we have also X ⊣ Y where Y B = (B ⟶ 1). Here V Y B = 1, for all B, so that V Y underlies an idempotent monad.

2) Consider V = connectedcomponents ⊣ discrete ⊣ objects ⊣ indiscrete = Y : set ⟶ cat. Now V Y S = 1 for S ≠ ∅ and V Y ∅ = ∅ so that V Y is idempotent.

3) In Example 2) replace cat by ord. The same conclusion holds.

4) In Example 2) replace cat by top and rename objects as points. However, if top is to be understood as the category of all topological spaces then we do not have a functor V left adjoint to W = discrete. We have merely a UIAO as in the second paragraph of the Introduction. Here the profunctor Z, right adjoint to Y = indiscrete in the bicategory of categories and profunctors, has, for a set S and a topological space T, Z(S, T) = top(Y S, T). The composite ZW, for sets S_{1}, S_{2}, is given by ZW (S_{1}, S_{2}) = top(Y S_{1}, W S_{2}). Write π_{S_{1},S_{2}} : top(Y S_{1}, W S_{2}) ⟶ set(S_{1}, S_{2}) for the inclusion. This defines the components of a transformation π : ZW ⟶ 1_{set}. (Recall that the identity profunctor is the hom functor.) An element of ZW ZW (S_{1}, S_{2}) is an equivalence class of pairs (Y S_{1} ⟶ W S, Y S ⟶ W S_{2}) (equivalence being defined by the usual ⊗-condition). It is a generality, to be established shortly, that ZW π = πZW. The effect of this transformation on an equivalence class is to provide the composite Y S_{1} ⟶ W S ⟶ Y S ⟶ W S_{2}, where W S ⟶ Y S is the canonical continuous function. Thus, idempotence of (ZW, π) amounts to the assertion that any Y S_{1} ⟶ W S_{2} admits a factorization as above, unique up to the equivalence in question. This is easily verifed after noting that any Y S_{1} ⟶ W S_{2}, for non-empty S_{1} and S_{2}, is given by a constant.

5) Let L be a constructively completely distributive lattice as in [15]. Write Y : L ⟶ DL for the down-segment embedding of L into its lattice of down-closed subsets. Then X is the supremum function and W, the defining adjoint for constructive complete distributivity, classifies the totally below relation, which is an order ideal ≪: L \overline{}L. In this example the ambient 2-category is ord and the relevant proarrows are order ideals. Moreover, the composite ZW is ≪. Its idempotence expresses the fact that a ≪ b implies there exists c such that a ≪ c ≪ b.

6) In Example 5) replace L by an ordered set and DL by IL, the ordered set of downclosed and up-directed subsets of L. With Y as before the adjoint string now prescribes that L is a continuous ordered set and ≪ is known as the way below relation. The theorem which asserts that ≪ is idempotent is often known as the Interpolation Lemma.

7) Entirely analogous to Example 6) is the idempotence of the “wavy hom” for a continuous category as in [4].

8) Also related to Example 5) is the string U ⊣ V ⊣ W ⊣ X ⊣ Y : set ⟶ set^{set^{op}}, with Y the Yoneda embedding, which was shown in [13] to characterize set among categories with set-valued homs. Here V Y has constant value 1 and XU has constant value ∅.

9) In [17] cofibrations were studied in the context of proarrow equipment. It was observed there that the defining adjoint strings for both left cofibrations and right cofibrations have the property in question. For the particular case of toposes, geometric morphisms and left exact functors this example was first pointed out in [14].

10) In the simplicial 2-category, Δ, any UIAO of the form n ⟶ n + 1 satisfies the idempotence condition. This example provides the paradigm for Sections 4, 5 and 6 of this paper. In Example 1) the string V ⊣ W ⊣ X is obtained from a string in Δ by exponentiation.

11) We display below the counterexample promised earlier. In the following, B is the ordered set of natural numbers and C is the ‘long fork’ above h. The effects (from the left in the diagram) of V, W, X and Y are indicated by the tailed arrows. Note that V Y (n) = n + 2 which shows that V Y is not idempotent.

[figure: h; s; 1; t; st; ts; s; st; ts; t; sts; tst; st; sts; tst; ts; ⋮; ⋮; 0; 1; 2; 3; 4; ⋮; h; s; 1; t; st; ts; s; st; ts; t; sts; tst; st; sts; tst; ts; ⋮; ⋮; 0; 1; 2; 3; 4; ⋮; h; s; 1; t; st; ts; s; st; ts; t; sts; tst; st; sts; tst; ts; ⋮; ⋮; h; 1; ts; tst; st; sts; st; sts; t; ts; tst; C; B; V; B; C; W; C; B; X; B; C; Y]

This counterexample exhibits other aspects of our problem and will be referenced later.

3. Idempotents and Distributive Laws

We start with a functor Y : B ⟶ C. There may or may not be a functor right adjoint to Y but in any event we have an adjunction η, ϵ : Y ⊣ Z with Z a profunctor. (Note that we cannot assume that Z has a right adjoint.) We refer to Y as an adjoint string of length 1 from B to C. A functor X and an adjunction α, β : X ⊣ Y provide an adjoint string of length 2 from B to C. A further functor W and an adjunction γ, δ : W ⊣ X produces a string of length 3 and so on. Note that our somewhat informal definition is not to convey any notion of maximality: a string of length n starting from Y might very well underly a string of length n + 1 starting from Y. Obviously, a very systematic, integer-labelled definition could be provided but it would transcend our present needs.

The functor Y : B ⟶ C is always assumed to be fully faithful. In the generality of proarrow equipment this means that the unit, η, for the adjunction Y ⊣ Z is an isomorphism. (For strings of length greater than 1 this definition agrees with that given in terms of representability.) In fact, fully faithfulness is really a property of an adjoint string. For if we have X ⊣ Y then the counit, β, is an isomorphism if and only if the unit for Y ⊣ Z, η, is an isomorphism. This follows by dualizing the following folk-lemma. We have used it in a variety of earlier papers. Some history of it and a detailed proof can be found in [5].

3.1. Lemma. If W ⊣ X ⊣ Y : B ⟶ C then the counit for X ⊣ Y, β, is an isomorphism if and only if the unit for W ⊣ X, γ, is an isomorphism. When this is the case there is a transformation σ : W ⟶ Y, unique with the property

β · Xσ = γ^{−1}.

Note that the characterizing equation for σ can be solved explicitly to give

σ = δY · W β^{−1}

and similarly

σ = Y γ^{−1}.αW.

It follows that for longer strings, ⋯ U ⊣ V ⊣ W ⊣ X ⊣ Y, the functors ⋯ U, W, Y : B ⟶ C are all fully faithful and there are canonical transformations ⋯ U ⟶ W ⟶ Y as above. The latter give rise, by adjointness, to transformations ⋯ V ⟵ X ⟵ Z satisfying characterizing equations which will be introduced as required.

For a sufficiently long string, write G = Y Z, T = Y X, H = W X, S = W V and so on, giving rise to an adjoint string, ⋯ S ⊣ H ⊣ T ⊣ G : C \overline{}C, of arrows (note that G is typically merely a profunctor) which underly idempotent comonads and monads. Indeed, with the nomenclature above, the counit for G is ϵ, the unit for T is α and the counit for H is δ. Recall that a pointed endoarrow, α : 1_{C} ⟶ T, is said to be well-pointed if T α = αT. Idempotent comonads and monads are much simpler than their general counterparts. The following lemma will serve to summarize.

3.2. Lemma. For a monad (T, α, μ), μ : T T ⟶ T is an isomorphism if and only if (T, α) is a well-pointed endoarrow. A well-pointed endoarrow (T, α) underlies a monad if and only if T α = αT : T ⟶ T T is an isomorphism.

Of course, a similar lemma holds for comonads and we will not always comment on obvious dualizations in the sequel. Idempotence also greatly simplifies the equations required of distributive laws.

3.3. Lemma. For idempotent comonads, (G, ϵ) and (H, δ), a transformation λ : GH ⟶ HG is a distributive law if it satisfies either of the following equations.

[figure: GH; HG; G; Gδ; δG; λ; H; ϵH; Hϵ]

Proof. Write κ for the comultiplication of (G, ϵ) and ι for the comultiplication of (H, δ). So Gϵ = κ^{−1} = ϵG and Hδ = ι^{−1} = δH. Recall the equations for a distributive law and label them ‘ϵ’,‘κ’, ‘δ’,‘ι’ according to the single structural transformation that appears in each. Thus ‘ϵ’ and ‘δ’ are the displayed triangles and ‘κ’ and ‘ι’ are pentagons. From idempotence of G it is easy to show that ‘ϵ’ implies ‘κ’ and similarly ‘δ’ implies ‘ι’. Now given ‘ϵ’ construct the ‘κ’ diagram and adjoin the diagrams G‘ϵ’ and ‘ϵ’G. Adjoin G to the resultant diagram via evident arrows from each instance of GH and HG. Join GHG to G via GHG ⟶ GG ⟶ G. Now ‘δ’ follows from a few naturality observations. A similar diagram chase produces ‘ϵ’ from ‘δ’.

In fact, idempotence can be characterized in terms of distributivity.

3.4. Lemma. For a comonad (G, ϵ, κ), G is idempotent if and only if 1_{GG} : GG ⟶ GG is a distributive law.

For an idempotent comonad H and a general comonad G, existence of a distributive law λ : GH ⟶ HG is a property, rather than extra structure. Semantically, this is clear in CAT. We give a syntactic proof.

3.5. Lemma. For a comonad (G, ϵ, κ) and an idempotent comonad (H, δ), there is at most one distributive law λ : GH ⟶ HG.

Proof. First observe that for any such λ, λC is an isomorphism, for any H-coalgebra C : X \overline{}C. For in this case GC is also an H-coalgebra and the inverse to δGC is λC · G(δC)^{−1}. In particular this consideration applies to the H-coalgebra H : C \overline{}C so that in the following naturality square both the top and left sides are isomorphisms.

[figure: GH; HG; λ; GHH; HGH; λH; GHδ; HGδ]

Thus λ is explicitly given by HGδ · (δGH)^{−1} · GδH · G(Hδ)^{−1} = HGδ · (δGH)^{−1}.

In an adjoint string of comonads and monads, mates of distributive laws are distributive laws.

3.6. Lemma. For an adjoint string, ⋯ S ⊣ H ⊣ T ⊣ G : C \overline{}C of comonads (⋯ H, G) and monads (⋯ S, T), the bijections

GH ⟶ HG / SG ⟶ GS / T S ⟶ ST / ⋯,

mediated by the adjunctions, restrict to distributive laws (those involving both a monad and a comonad being what have been called “mixed” distributive laws).

We note that mixed distributive laws of the form (comonad)(monad) ⟶ (monad)(comonad), which do appear in the sequence suggested above, appear to be rare in the literature. They play the same role with respect to Kleisli objects as do the more familiar form, (monad)(comonad)⟶(comonad)(monad), with respect to Eilenberg-Moore objects. An excellent reference for the latter is [11].

If any one of ⋯ S, H, T, G is idempotent then they are all idempotent. (While this is obvious in any event, it is interesting to note that it follows from Lemma 3.4 and an evident variant of Lemma 3.6.) In light of Lemma 3.5, the sense of distributivity given by Lemma 3.6 is a property of an adjoint string of idempotent comonads and monads. Bearing in mind also Lemma 3.4, we make the following definitions.

3.7. Definition. An adjoint string of length 1, Y : B ⟶ C, is said to be distributive if Y is fully faithful. An adjoint string H ⊣ T ⊣ G, where G underlies a comonad, is said to be distributive if 1_{GG} : GG ⟶ GG is a distributive law and there exists a distributive law GH ⟶ HG. A fully faithful adjoint string of length 3, in other words a UIAO, W ⊣ X ⊣ Y : B ⟶ C, is said to be distributive if the corresponding string of comonads and monads, W X ⊣ Y X ⊣ Y Z, is distributive.

Note that our terminology is also suggested by Examples 5) through 8).

4. Shorter Adjoint Strings

Given a UIAO, W ⊣ X ⊣ Y : B ⟶ C, recall the transformation σ : W ⟶ Y introduced in Lemma 3.1. We define τ : Z ⟶ X as the transformation corresponding to σ by adjointness but it is also the unique solution of

β · τY = η^{−1}

The explicit solutions

τ = Xϵ · β^{−1}Z
τ = η^{−1}X · Zα

follow from the characterizing equation. The characterizing equations for σ and τ also give Xσ · γ = β^{−1} = τY · η.

4.1. Lemma. The following diagram commutes.

[figure: ZY; 1_{B}; η^{−1}; ZW; XW; τW; Zσ; γ^{−1}]

Proof. Insert XY in the centre of the diagram and join ZY to XY by τY, XW to XY by Xσ and XY to 1_{B} by β. The resulting quadrilateral commutes by naturality and each of the triangles expresses a characterizing equation.

Define π : ZW ⟶ 1_{B} to be the composite transformation above and observe, from the proof, that it is given symmetrically by π = β · τσ.

4.2. Lemma. The arrow ZW is well-augmented by π in the sense that ZW π = πZW.

Proof. Consider the following diagram.

[figure: Y Z; 1_{C}; ϵ; W Z; W X; W τ; σZ; δ]

Insert W XY Z in the centre of the diagram and join W XY Z to Y Z by δY Z, W XY Z to W X by W Xϵ and W Z to W XY Z by W β^{−1}Z. The resulting quadrilateral commutes by naturality and each of the triangles commutes from the explicit descriptions of σ and τ.

Now apply Z(−)W to the diagram displayed above. Since δW = W γ^{−1} the topfollowed-by-right composite yields ZW π using the top-followed-by-right description of π in Lemma 4.1. Similarly, the other composite is seen to be πZW.

Of course, by duality, Lemma 4.2 establishes our earlier assertion that V Y is a wellpointed endofunctor, for adjoint strings of length 4. From either point of view we can now state and prove a Theorem which answers our opening question.

4.3. Theorem. For a UIAO, W ⊣ X ⊣ Y : B ⟶ C, (ZW, π) underlies an idempotent comonad if and only if the UIAO is distributive.

Proof. It suffices to show that invertibility of ZW π = πZW is equivalent to the existence of a distributive law Y ZW X ⟶ W XY Z. From invertibility of β : XY ⟶ 1_{B} and adjointness we have bijections

Y ZW X ⟶ W XY Z / Y ZW X ⟶ W Z / ZW ⟶ ZW ZW

and a diagram chase shows that if a transformation Y ZW X ⟶ W XY Z satisfies either one of the equations for a distributive law then its counterpart ZW ⟶ ZW ZW provides a section for ZW π = πZW and conversely. However, such a section is necessarily an isomorphism. This follows from naturality and the equation ZW π = πZW.

It is now possible to explain the generation of Counterexample 11) and rationalize the names of the objects of the ordered set C displayed there. For if Theorem 4.3 is stated for adjoint strings of length 4 then by Lemma 3.6 the relevant distributive law is T S ⟶ ST. Thus, in an ordered set counterexample there must not be T S ≤ ST but all composites of H and either S or T reduce by adjunction inequalities and idempotence. The remaining ideas are somewhat similar to those found in [18].

For the moment, let B be any object and let C = (C, π) be an idempotent comonad in M on B. In our working terminology, C is a profunctor. Then a C-coalgebra in M with domain Y is an arrow B : Y \overline{}B, in M, together with a C-coalgebra structure transformation b : B ⟶ CB. By idempotence, the usual requirements for such b reduce to πB.b = 1_{B} and this implies, by naturality and Cπ = πC, that b = (πB)^{−1}. Thus, being a C-coalgebra is a property of B. If both B and B′ are C-coalgebras then any transformation B ⟶ B′ is a coalgebra homomorphism in the usual sense. Write M(Y, B)_{C} for the category of C-coalgebras in M with domain Y. It is just the full subcategory of M(Y, B) determined by the B which invert π. If B : Y \overline{}B is a C-coalgebra then composition with B defines, for every object X in M, a functor M(X, Y) ⟶ M(X, B)_{C}. Recall that an Eilenberg-Moore object for C is a C-coalgebra, I : B_{C} \overline{}B, such that, for all X, composing with I provides an equivalence of categories, M(X, B_{C}) ⟶ M(X, B)_{C}. It is clear from the discussion that if I is Eilenberg-Moore for C then it also provides an inverter for the transformation π : C ⟶ 1_{B}.

Recall the proarrow equipment for toposes and geometric morphisms extensively studied in [14], namely the transformational dual of toposes and left exact functors. It does admit Eilenberg-Moore objects for comonads in M. However, it was shown in [12] that the paradigm for proarrows, namely categories and profunctors in the usual sense, does not. The paradigm does admit a weaker notion which we now describe.

For C = (C, π) an idempotent comonad on B in M, suppose that B : Y ⟶ B is a C-coalgebra with B in K. In this event, composing with B, M(X, Y) ⟶ M(X, B)_{C}, has a right adjoint which is given by composing with B^{∗}, the right adjoint of B in M. (This follows from the fact that M(X, B)_{C} is a full subcategory of M(X, B).) Write K(X, B)_{C} for the full subcategory of M(X, B)_{C} determined by the C-coalgebras in K. Henceforth we assume the following.

Axiom 5 For every idempotent comonad (B, C) in M there is a C-coalgebra I : B(C) ⟶ B in K such that, for each X, the adjunction given by composing with I, M(X, B(C)) ⟶ M(X, B)_{C} restricts to an equivalence K(X, B(C)) ⟶ K(X, B)_{C}.

One could say that the Axiom provides, for each idempotent comonad in M, an Eilenberg-Moore object as seen by K. With an obvious extension of such terminology, it is clear that I : B(C) ⟶ B provides an inverter as seen by K for π. For categories and profunctors, I : B(C) ⟶ B was first described in [20]. In that context, a variety of descriptions of B(C) were given in [12]. Note that the Axiom ensures that if the idempotent comonad C is in K then I : B(C) ⟶ B in K is a true Eilenberg-Moore object in K and may be written I : B_{C} ⟶ B. In this case, regarding C as an idempotent comonad in M, I : B_{C} ⟶ B is also an Eilenberg-Moore object in M. (The limit in question is preserved by all homomorphisms of bicategories; in particular, it is preserved by (−)_{∗} : K ⟶ M.) It may well be the case that for C in M, not necessarily in K, that I : B(C) ⟶ B provides an Eilenberg-Moore object in M. In any event, writing Q for the right adjoint of I we have IQ ⟶ C corresponding by adjointness to the coalgebra structure I ⟶ CI. In [12] the following observation was made in the case of (−)_{∗} : CAT ⟶ PRO.

4.4. Lemma. A functor I : B(C) ⟶ B as provided by Axiom 5, with right adjoint Q in M, is an Eilenberg-Moore object for C in M if and only if the canonical transformation IQ ⟶ C is an isomorphism.

Eilenberg-Moore coalgebras for idempotent comonads in a bicategory are representably fully faithful. For the weaker notion of Axiom 5 we have:

4.5. Lemma. The functors I : B(C) ⟶ B provided by Axiom 5 are fully faithful and the unit for I− ⊣ Q− : M(X, B)_{C} ⟶ M(X, B(C)) is an isomorphism.

Proof. For X = B(C), the 1_{B(C)} component of the unit of the adjunction given in Axiom 5 is 1_{B(C)} ⟶ QI, the unit for the adjunction I ⊣ Q in M and, by Axiom 5, it is an isomorphism because 1_{B(C)} is in K. Thus I is fully faithful and the rest of the statement of the Lemma follows from this.

Thus, by Theorem 4.3, a distributive UIAO, that is a distributive adjoint string of length 3, W ⊣ X ⊣ Y : B ⟶ C, gives rise to I : A = B(ZW) ⟶ B, a distributive adjoint string of length 1.

Lawvere has taken the point of view that a UIAO, W ⊣ X ⊣ Y : B ⟶ C, provides C with the structure of an oriented cylinder. Both the top and bottom are copies of B. The former is provided by W, the latter by Y and the orientation by σ : W ⟶ Y. He further points out in [9] that the top and bottom are not necessarily disjoint, in the sense that part of the top may be isomorphic to part of the bottom in C. The following theorem shows that this overlap is provided precisely by I : A = B(ZW) ⟶ B.

4.6. Theorem. If W ⊣ X ⊣ Y : B ⟶ C is a distributive UIAO then I : A = B(ZW) ⟶ B is the inverter in K of σ : W ⟶ Y : B ⟶ C.

Proof. We have already remarked that I : B(ZW) ⟶ B is the inverter as seen by K of π : ZW ⟶ 1_{B} : B \overline{}B. It suffices to show, for a functor B : X ⟶ B, that πB is an isomorphism if and only if σB is an isomorphism. Since πB = η^{−1}B.ZσB the “if” part is clear. On the other hand, if πB is an isomorphism with inverse b : B ⟶ ZW B then the transformation ϵW B.Y b : Y B ⟶ W B can be shown, with the help of Lemmas 4.1 and 4.2, to be the inverse of σB : W B ⟶ Y B.

There remains the question of whether or not I : B(ZW) ⟶ B is actually Eilenberg-Moore in M for the comonad ZW. (After all, by construction, Y : B ⟶ C is Eilenberg-Moore for G and W : B ⟶ C is Eilenberg-Moore for H.) Again writing Q for the right adjoint of I in M, Lemma 4.4 shows that this determination rests on the invertibility of the canonical transformation IQ ⟶ ZW. We will show that IQ ⟶ ZW can fail to be an isomorphism.

To explain, it is convenient to generalize, temporarily, the situation with which we are preoccupied. So let G and H be idempotent comonads in M on C, without our usual adjointness assumptioms, for which there exists a distributive law, GH ⟶ HG. Assume that H admits an Eilenberg-Moore object, W : C_{H} ⟶ C. From the general theory of comonads, the comonad G restricts to a comonad G| on C_{H}. That is we have W G| ≅ GW with G| = XGW, where X is right adjoint to W. Invoking our Axiom 5 we have

[figure: C_{H}; C; W; C_{H}(G|); C(G); J; I; Y; ⟵^{≃}]

in K. (The functor J is the “fill-in” that results from W I being a G-coalgebra in K. It is necessarily fully faithful because the composite W I is fully faithful.) Each functor has a right adjoint in M, say Q in the case of I and Z in the case of Y. The isomorphism Y J ⟶ W I gives, by adjointness, a transformation, JQ ⟶ ZW. In [1] invertibility of JQ ⟶ ZW, a Beck condition, was called distributivity for the adjoint square and the condition is satisfied when I and Y are Eilenberg-Moore coalgebras.

Returning to our case of interest, we have C_{H} = B = C(G) with Y also Eilenberg-Moore. Here G| = XGW = XY ZW ≅ ZW and we can take J = I. However, the resulting adjoint square,

[figure: B; C; W; B(ZW); B; I; I; Y; ⟵^{≃}; ,]

may fail to be distributive, even in the paradigm (−)_{∗} : CAT ⟶ PRO.

Counterexample: Let B be the rationals with the usual order. Let the objects of C be pairs (b, i), with b a rational and i in {0, 1}, ordered by (b, i) ≤ (b′, i′) if and only if b ≤ b′ and i ≤ i′ or b < b′ and i = 1 and i′ = 0. Defining W b = (b, 0), X(b, i) = b and Y b = (b, 1) produces a UIAO in ord and hence in CAT. Direct calculation shows that the profunctor ZW : B \overline{}B is the order ideal <: B \overline{}B, which is an idempotent. However, the inverter of W ≤ Y is I : 0 ⟶ B so that the composite IQ is 0 : B \overline{}B.

The reader who is familiar with [3] may find the following to be more natural.

Counterexample: Let B be the closed unit interval and Y : B ⟶ C the downsegment embedding into the lattice of down-closed subsets of B. This is a special case of 5) in Section 2. It follows from remarks in [3] that ZW : B \overline{}B is the order ideal <: B \overline{}B but, again, the inverter of W ≤ Y is empty so that the composite IQ is 0.

However, even in the general situation that we described in the second to last diagram, either diagonal composite C_{H}(G|) ⟶ C is Eilenberg-Moore as seen by K for the composite comonad GH. In short, we always have C_{H}(G|) ≃ C(GH), for idempotent comonads in M, when H admits an Eilenberg-Moore object and there exists a distributive law GH ⟶ HG.

We would like now to investigate the generation of distributive UIAOs from longer adjoint strings by several instances of the “shortening” procedure that we have just discussed. We will see that the subtlety of constructed functors actually providing Eilenberg-Moore objects in M disappears but that the longer starting string must satisfy higher order distributivity conditions. At first these conditions appear somewhat strange but they are satisfied in naturally occuring examples. Moreover, at this stage a pattern emerges which enables us in Section 6 to deal with strings of arbitrary length. It is convenient to begin with a lemma that admits Theorem 4.3 as a corollary.

4.7. Lemma. If Y : B ⟶ C and Y′ : B′ ⟶ C are fully faithful arrows in K with right adjoints Z and Z′ respectively, possibly in M, then a transformation Y ZY′Z′ ⟶ Y′Z′Y Z is a distributive law if and only if the transformation ZY′ ⟶ ZY′Z′Y ZY′, corresponding by adjointness, is the inverse of Zϵ′ϵY′ : ZY′Z′Y ZY′ ⟶ ZY′, where ϵ and ϵ′ are the respective counits.

Proof. A very direct calculation suffices.

Lemma 4.7 admits a simple interpretation in CAT. Considering B and B′ to be subcategories of C, the distributive law in question asserts that every arrow of the form c : Y B ⟶ Y′B′ in C admits a factorization,

Y B ⟶^{c_{0}} Y′B′_{0} ⟶^{s} Y B_{1} ⟶^{c_{1}} Y′B′

with unique tensor product (see [12]), c_{1}⊗_{B}s⊗_{B′}c_{0}. The UIAO situation, where Y′ = W ⊣ X ⊣ Y, simplifies this condition by the requirement that s = σB_{0} : W B_{0} ⟶ Y B_{0}. The case when GH = Y ZW X admits an Eilenberg-Moore object is the further specialization to invertible σB_{0}.

Suppose now that U ⊣ V ⊣ W ⊣ X ⊣ Y : B ⟶ C is a distributive adjoint string of length 5. This gives rise to a string of idempotents, L ⊣ S ⊣ H ⊣ T ⊣ G, where we have extended our earlier terminology with S = W V and L = UV. The distributive laws in Lemma 3.6 now continue to include explicitly LT ⟶ T L and HL ⟶ LH. Thus we can apply Theorems 4.3 and 4.6 to the distributive UIAOs W ⊣ X ⊣ Y and U ⊣ V ⊣ W to produce I : B(ZW) ⟶ B the inverter of W ⟶ Y and J : B_{XU} ⟶ B the inverter of U ⟶ W. (Of course XU is a comonad in K and we have oserved that in this case the requisite Eilenberg-Moore object exists.) But we have also the idempotent monad V Y with XU ⊣ V Y ⊣ ZW and it is convenient to revise, perhaps extend, a well-known result of [2]. We refer to the theorem which states that if a monad M is left adjoint to a comonad C (in CAT) then the category of M-algebras is isomorphic to the category of C-coalgebras via an isomorphism that identifies the forgetful functors. This theorem can be generalized in many ways. Here we collect just what we need, without proof.

4.8. Lemma. If M : B ⟶ B is an idempotent monad in K with right adjoint C (possibly not in K) then B(C) ⟶ B provides both an Eilenberg-Moore object in K for M and an Eilenberg-Moore object in M for C.

4.9. Lemma. If a monad M in K has an Eilenberg-Moore object I : B^{M} ⟶ B then I has a left adjoint, P, and if M is idempotent then P : B ⟶ B^{M} provides a Kleisli object for M.

Axiom 4 for proarrow equipment (−)_{∗} : K ⟶ M ensures that every monad M in K has a Kleisli object P : B ⟶ B_{M} in K.

4.10. Lemma. If a monad M in K has a left adjoint D then P : B ⟶ B_{M} provides a Kleisli object for the comonad D.

Finally, let us explicitly state a dual of Lemma 4.9.

4.11. Lemma. If a comonad D in K has a Kleisli object P : B ⟶ B^{D} then P has a left adjoint, J, and if D is idempotent then J : B^{D} ⟶ B provides an Eilenberg-Moore object for D.

It follows, from Lemmas 4.8 through 4.11, that if we start with an adjoint string of length 5, U ⊣ V ⊣ W ⊣ X ⊣ Y : B ⟶ C, where U ⊣ V ⊣ W, or equivalently W ⊣ X ⊣ Y, is a distributive UIAO, then our construction generates a fully faithful adjoint string of length 3, J ⊣ P ⊣ I : A ⟶ B, where we can take A to be B(ZW). Note, for future reference, that J is Eilenberg-Moore for XU and that I is Eilenberg-Moore for both V Y and ZW.

Considering just the composable UIAOs J ⊣ P ⊣ I and U ⊣ V ⊣ W and the fact that J inverts U ⟶ W we have an instance of Lawvere’s interpretation of Hegel’s “Aufhebung” as described in [9].

Note that if, as before, we write Q for the right adjoint of I in M then we do in this case have

IQ ≅ ZW

(by Lemmas 4.8 and 4.4). In fact, a distributive adjoint string of length 4 ensures this conclusion. We have also

IP ≅ V Y

and

JP ≅ XU.

To see that such compatible composable adjoints strings do not arise in the absence of distributivity, even if the construction of inverters is available generally, it is instructive to return to the Counterexample in 11) of Section 2. Inspection shows that the functor V there has a further left adjoint, U, given by U0 = h, U1 = 1, U2 = t, U3 = ts and so on up the right hand side of the long fork. (In fact this U has itself a left adjoint which does not have a further left adjoint.) The inverter of U ⟶ W is 0 : 1 ⟶ B but the inverter of W ⟶ Y is 0 ⟶ B.

Our constructed string, J ⊣ P ⊣ I : A ⟶ B, cannot be shown to be a distributive UIAO without further conditions on the given data, U ⊣ V ⊣ W ⊣ X ⊣ Y : B ⟶ C.

4.12. Lemma. Let E be either an idempotent monad or an idempotent comonad on C. Assume the same of E′ and the existence of a distributive law EE′ ⟶ E′E. If the distributive law is invertible then its inverse is also a distributive law and, conversely, if there is a distributive law E′E ⟶ EE′ then it is the inverse of the original distributive law.

4.13. Definition. A string of idempotent comonads and monads, L ⊣ S ⊣ H ⊣ T ⊣ G, is said to be distributive if there are distributive laws

\begin{aligned}GH & → & HG \\ GS & → & SG \\ GL & → & LG. \end{aligned}

A fully faithful adjoint string of length 5, U ⊣ V ⊣ W ⊣ X ⊣ Y : B ⟶ C, is said to be distributive if the corresponding string of idempotents is distributive.

The law SG ⟶ GS is an equivalent of the law GH ⟶ HG, by Lemma 3.6. Therefore, by Lemma 4.12, the law GS ⟶ SG is an isomorphism. Also T L ⟶ LT is an equivalent of GS ⟶ SG and we will find it convenient to use this formulation. Since LT ⟶ T L is another equivalent of GH ⟶ HG, T L ⟶ LT is an isomorphism too. Still another equivalent of GS ⟶ SG is LG ⟶ GL so that the last two distributivities in the definition above could be combined as a single isomorphic distributivity GL ⟶^{≃} LG.

In the proof of the following theorem we content ourselves with exhibiting the existence of the requisite arrows and isomorphisms. It should be clear to the reader by now that this, not coherence, is the central problem. In fact, a full coherence theorem for distributive adjoint strings will appear elsewhere.

4.14. Theorem. If U ⊣ V ⊣ W ⊣ X ⊣ Y : B ⟶ C is a distributive adjoint string of length 5 then J ⊣ P ⊣ I : A = B(ZW) ⟶ B is a distributive adjoint string of length 3.

Proof. The distributive law T L ⟶ LT provides a restriction of L to the Eilenberg-Moore object for T, Y : B ⟶ C. The restriction, L|, is given by L| = XLY = XUV Y ≅ JP IP ≅ J1_{A}P ≅ JP ≅ XU and the Eilenberg-Moore object for XU is J : A ≃ B_{L|} ⟶ B. Similarly, T L ⟶ LT provides the restriction T | = V T U = V Y XU ≅ IP JP ≅ I1_{A}P ≅ IP ≅ V Y of T to the Eilenberg-Moore object for L, U : B ⟶ C. The Eilenberg-Moore object for V Y is I : A ≃ B^{T |} ⟶ B. Now from [11] it can be inferred that

[figure: B; C; Y; A; B; I; J; U; ⟵^{≃}]

is a bi-pullback. In particular, we have UI ≅ Y J as displayed. Taking right adjoints, we have also QV ≅ P Z.

The distributive law GL ⟶ LG, expands to Y ZUV ⟶ UV Y Z. An application of Lemma 4.7 gives the first isomorphism in ZU ≅ ZUV Y ZU ≅ ZUIP ZU ≅ ZY JQV U ≅ 1_{B}JQ1_{B} ≅ JQ.

The distributive law GH ⟶ HG, expanded and with V (−)U applied to it, gives V Y ZW XU ⟶ V W XY ZU, which by fully faithfulness of W and Y gives an arrow V Y ZW XU ⟶ ZU. Substituting along the isomorphisms we have derived yields an arrow IP IQJP ⟶ JQ, which can be rewritten I1_{A}QJP ⟶ J1_{A}Q ≅ JP IQ. Finally, we have IQJP ⟶ JP IQ, which is distributivity for the UIAO J ⊣ P ⊣ I.

It is instructive to picture some aspects of the proof of Theorem 4.14 in terms of Lawvere’s cylinders as mentioned in the paragraph preceding Theorem 4.6. Prior to the proof of Theorem 4.14 and the assumption of further distributivity for the string B ⟶ C, we had already constructed a UIAO A ⟶ B so that we knew B to have the structure of a directed cylinder. The functors U, W and Y thus provided for three copies of the cylinder B, fully faithfully in C. Adjointness further provided for two “cylinders”, where the top and bottom of the “cylinders” each had the shape of cylinder B. Inversion of U ⟶ W by J showed that the cylinders U and W are glued at their tops in C while inversion of W ⟶ Y by I showed that cylinders W and Y are glued at their bottoms. In establishing the isomorphism UI ≅ Y J in the proof above, which explicitly used the higher order distributivity, we were joining the bottom of cylinder U to the top of cylinder Y, as suggested in the picture below.

[figure: UJ ≅ W J; UI; Y I ≅ W I; Y J; U; W; Y]

Note that the “triangle” structure bounded by cylinders, that this provides for C, is not “hollow”.

5. Longer Adjoint Strings

Given a distributive adjoint string from B to C we consider now the construction of a longer adjoint string, with domain C. Our “lengthening” construction will in fact be left adjoint to the “shortening” construction for distributive adjoint strings that we described in the last section.

In particular, suppose that we have a fully faithful Y : B ⟶ C, a distributive adjoint string of length 1. As before, write G for the composite Y Z. Now Axiom 3 ensures the coalescence of finite sums and finite products in M. Thus we use direct sum notation below and there is a profunctor, M : C ⊕ C \overline{}C ⊕ C, where M is the following matrix:

( \begin{matrix}1 & G \\ 1 & 1 \end{matrix} )

in which the 1’s denote 1_{C} : C ⟶ C. (Here and elsewhere in this section the i, jth entry of such a matrix denotes an arrow from the ith summand of the domain to the jth summand of the codomain.) Recall from [21] that Axiom 3 ensures that the hom categories of M have finite sums and that matrix multiplication, using this additive structure, provides for composition of profunctors given by matrices. In particular, the identity on C ⊕ C is:

( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} )

where the 0’s denote the initial object of M(C, C). Recall that a transformation 1_{C⊕C} ⟶ M is a matrix of transformations, given componentwise. Evidently such is provided by:

( \begin{matrix}1 & ! \\ ! & 1 \end{matrix} )

where the !’s denote the unique transformation, in each case, with domain 0. Thus M is a pointed endo-arrow of M. The composite MM : C ⊕ C \overline{}C ⊕ C is given by the matrix:

( \begin{matrix}1 + G & G + G \\ 1 + 1 & G + 1 \end{matrix} )

where the +’s denote binary sum in the hom categories of M. Consider the transformation MM ⟶ M given by:

( \begin{matrix}< 1_{1}, ϵ > & < 1_{G}, 1_{G} > \\ < 1_{1}, 1_{1} > & < ϵ, 1_{1} > \end{matrix} )

where we have used “row vectors”, bracketed by < and > to display transformations out of local sums.

5.1. Lemma. The transformations MM ⟶ M ⟵ 1 introduced above provide a monad structure on M.

It should be noted that a detailed proof of Lemma 5.1 must take into account the associativity isomorphisms of the bicategory M and the further isomorphisms that are implicit in using categorical sum, + and 0 in the matrices above, for a matrix calculus. However, note too that Lemma 5.1 holds given only that G is well-augmented by ϵ.

Now Axiom 4 provides for a Kleisli opalgebra, K : C ⊕ C ⟶ (C ⊕ C)_{M} in K and by Axiom 3 the arrow K is a 2 by 1 “column vector”:

( \begin{matrix}J \\ I \end{matrix} )

with J and I in K. Writing D for (C ⊕ C)_{M}, we have functors J, I : C ⟶ D. The opalgebra action KM ⟶ K can be analyzed by first computing the matrix KM:

( \begin{matrix}J + IG \\ J + I \end{matrix} )

and examining the unitary and associativity requirements in terms of the components. The unitary requirement says that two of the four components are identities so that KM ⟶ K amounts to, say, ρ : IG ⟶ J and σ : J ⟶ I. By associativity these satisfy:

ρ · σG = Jϵ
σ · ρ = Iϵ.

However, the transformation ρ corresponds, by adjointness, to a transformation τ : IY ⟶ JY. It is a simple calculation to show that τ is the the inverse of σY precisely when the two equations above hold.

Recall that for any arrow Y : B ⟶ C in a bicategory, the coinvertee of Y is a transformation, σ : J ⟶ I : C ⟶ D, with σY an isomorphism and which is moreover (bi-)universal with this property. The notion of coinvertee does not seem to have been explicitly studied to the same extent as the dual notion, invertee, of an arrow. As an example, the coinvertee in CAT of 0 ⟶ 1 is 0 ≤ 1 : 1 ⟶ 2.

5.2. Lemma. For Y : B ⟶ C fully faithful, the transformation σ : J ⟶ I : C ⟶ (C ⊕ C)_{M} = D above is a coinvertee in M with universality restricting to K.

Proof. Observe that the data and equational considerations in the discussion above apply to any opalgebra for M. The universality of the Kleisli opalgebra provides the universality required of a coinvertee.

Of course a particular transformation with domain C that is inverted by Y : B ⟶ C is 1_{1C} : 1_{C} ⟶ 1_{C} : C ⟶ C, so universality ensures a functor P : D ⟶ C and isomorphisms, which we may elect to direct as γ : 1_{C} ⟶^{≃} P J and β : P I ⟶^{≃} 1_{C}, satisfying β · P σ = γ^{−1}. Similar considerations produce a transformation δ : JP ⟶ 1_{D} satisfying δJ = Jγ^{−1} and δI = σ · Jβ and a transformation α : 1_{D} ⟶ IP satisfying αJ = Iγ · σ and αI = Iβ^{−1}. From these equations it follows that we have adjunctions γ, δ : J ⊣ P and α, β : P ⊣ I. Moreover, invertibility of γ and β provides that J ⊣ P ⊣ I : C ⟶ D is a UIAO.

5.3. Theorem. For Y : B ⟶ C fully faithful, the adjoint string above, J ⊣ P ⊣ I : C ⟶ D, is distributive.

Proof. Observe that ϵ : G ⟶ 1_{C} : C \overline{}C is also a transformation inverted by Y, since G = Y Z and ϵ is the counit for Y ⊣ Z. This gives rise to a Q : D \overline{}C, not necessarily in K because G is not necessarily in K, and compatible isomorphisms, QJ ⟶^{≃} G and 1_{C} ⟶^{≃} QI. Direct computation shows that I ⊣ Q and, by Theorem 4.3, the isomorphism QJ ⟶^{≃} G and idempotence of G shows that the UIAO in question is distributive.

It is interesting to note that the arrow components of P, respectively Q, as determined by the universal property of D, constitute the first, respectively second, column of the matrix M. This will be elaborated upon elsewhere.

Of course, given a functor, Y : B ⟶ C, and a transformation, σ : J ⟶ I : C ⟶ D, we can ask both whether σ is the coinvertee of Y and whether Y is the inverter of σ. When both conditions hold we have a form of 2-dimensional exactness. The “lengthening” procedure for a fully faithful Y as described above does indeed produce an exact diagram in this sense.

5.4. Corollary. For Y : B ⟶ C fully faithful, the lengthening construction under consideration, followed by the shortening construction that precedes Theorem 4.6, recovers Y. Moreover, Y satisfies the stronger property of being Eilenberg-Moore in M for the comonad QJ.

We now consider the problem of generating, from a distributive UIAO W ⊣ X ⊣ Y : B ⟶ C, a distributive adjoint string, C ⟶ D, of length 5. As in the previous section, we write H for W X, T for Y X and G for Y Z. Consider the profunctor M : C ⊕ C ⊕ C \overline{}C ⊕ C ⊕ C where M is the following matrix:

( \begin{matrix}1 & H & HG \\ 1 & 1 & G \\ T & 1 & 1 \end{matrix} )

with conventions as above. There is an evident pointing, 1_{C⊕C⊕C} ⟶ M, so consider MM, the matrix:

( \begin{matrix}1 + H + T HG & H + H + HG & HG + GH + HG \\ 1 + 1 + T G & H + 1 + G & HG + G + G \\ T + 1 + T & HT + 1 + 1 & HGT + G + 1 \end{matrix} )

and the transformation MM ⟶ M given by:

( \begin{matrix}< 1, δ, ϵ · Y βZ · T δG > & < H, H, Hϵ > & < HG, λ, HG > \\ < 1, 1, ϵ · Y βZ > & < δ, 1, ϵ > & < δG, G, G > \\ < T, α, T > & < δ · W βX, 1, 1 > & < δ · W βX · HϵT, ϵ, 1 > \end{matrix} )

where we have written 1 for 1_{1}, H for 1_{H} etc.. The calculations required to prove the next Lemma are straightforward but lengthy and tedious.

5.5. Lemma. The transformations MM ⟶ M ⟵ 1 introduced above provide a monad structure on M.

The Kleisli opalgebra for M is a 3 by 1 matrix, say:

( \begin{matrix}K \\ J \\ I \end{matrix} )

with domain C ⊕ C ⊕ C and codomain (C ⊕ C ⊕ C)_{M}. We will denote the latter by D, so that we have functors K, J, I : C ⟶ D. To analyze the opalgebra action we compute the composite of the above 3 by 1 matrix and M to be:

( \begin{matrix}K + JH + IHG \\ K + J + IG \\ KT + J + I \end{matrix} )

and, again, examine the unitary and associativity requirements in terms of the components. The unitary requirement says that all components of the form x ⟶ x are identities so that the data amounts to JH ⟶ K, IHG ⟶ K, K ⟶ J, IG ⟶ J, KT ⟶ I and J ⟶ I. The first, second, fourth and fifth of these are equivalent, by adjointness, to transformations JW ⟶ KW, IW ⟶ KY, IY ⟶ JY and KY ⟶ IW, respectively. In terms of these, associativity states that the data consists of a transformation K ⟶ J and an isomorphism KW ⟶^{≃} JW, a transformation J ⟶ I and an isomorphism JY ⟶^{≃} IY and an isomorphism KY ⟶^{≃} IW. This last will provide, as explained in the closing paragraphs of Section 4, the glue to join a chain of three linked cylinders into a triangle.

5.6. Lemma. For a distributive UIAO, W ⊣ X ⊣ Y : B ⟶ C, the functors K, J and I and transformations described above are universal in M with universality restricting to K.

Proof. Again, the data and equational considerations apply to any opalgebra for the monad M.

Now consider the first column of matrix M, remembering that the 1’s are 1_{C}’s. Trivially, we have the transformation 1_{1C} : 1_{C} ⟶ 1_{C} inverted by W. We have the unit for T, α : 1_{C} ⟶ T which, since T = Y X, is inverted by Y. We have an isomorphism 1_{C}Y ⟶^{≃} T W because T = Y X and γ^{−1} : XW ⟶^{≃} 1_{B}. Construing this data as an opalgebra defines a functor Q : D ⟶ C.

Similarly, examining the second column of M, we consider δ : H ⟶ 1 and 1 : 1 ⟶ 1. The necessary isomorphisms for an opalgebra structure are easily found and so we have a functor P : D ⟶ C.

Finally, consideration of the third column suggests δG : HG ⟶ G and ϵ : G ⟶ 1. Inversion of the first by W is equivalent to invertibility of σZW and this follows from the considerations of Section 4, in particular from the proof of Theorem 4.6. Inversion of ϵ by Y follows simply from the definition of G. An isomorphism (HG)Y ⟶^{≃} 1_{C}W is found by noting that HG = W XY Z. The opalgebra defines a profunctor R : D \overline{}C

If we note carefully the compatibility isomorphisms and equations that universality further provides in the definitions of Q, P and R, as we did in the simpler case preceding Theorem 5.3, then we can prove K ⊣ Q ⊣ J ⊣ P ⊣ I ⊣ R. For example, in the definition of Q we have isomorphisms QK ≅ 1, QJ ≅ 1 and QI ≅ T. The first of these provides a unit for K ⊣ Q. It is an isomorphism so the adjoint string of length 5 in K is fully faithful.

The isomorphism P K ≅ H, arising from the definition of P, establishes, since H is an idempotent, that the constructed string is at least distributive in the sense we defined first for a UIAO.

5.7. Theorem. For W ⊣ X ⊣ Y : B ⟶ C a distributive UIAO, the adjoint string of length 5 constructed above, K ⊣ Q ⊣ J ⊣ P ⊣ I : C ⟶ D, is distributive.

Proof. The higher order distributivity required here is the isomorphic distributivity, (IR)(KQ) ≅ (KQ)(IR). The isomorphism KY ≅ IW gives also, by taking right adjoints, ZQ ≅ XR. The definition of R gives RK ≅ HG. We have noted QI ≅ T above and HG ≅ W Z is familiar. Assembling these we have IRKQ ≅ IHGQ ≅ IW ZQ ≅ KY XR ≅ KT R ≅ KQIR.

5.8. Corollary. For W ⊣ X ⊣ Y : B ⟶ C a distributive UIAO, the lengthening construction followed by the shortening construction recovers W ⊣ X ⊣ Y.

For the cases that we have considered, evident definitions of arrows between adjoint strings allow us to say, “lengthening is fully faithful and left adjoint to shortening”.

6. Generalizing the Construction of Δ

For an adjoint string of comonads and monads, ⋯ R ⊣ L ⊣ S ⊣ H ⊣ T ⊣ G, consider the following “table” of distributive laws:

GG→GG

T G→GT GT→T G
T T→T T HG→GH GH→HG
HT→T H T H→HT SG→GS GS→SG
HH→HH ST→T S T S→ST LG→GL GL→LG
SH→HS HS→SH LT→T L T L→LT RG→GR GR→RG
SS→SS LH→HL HL→LH RT→T R T R→RT ⋯ ⋯
LS→SL SL→LS RH→HR HR→RH  ⋯
LL→LL RS→SR SR→RS  ⋯
RL→LR LR→RL  ⋯
RR→RR  ⋯

⋯ It is to be understood that in each column the entries correspond via adjointness.

Moreover, let us assume that the (1, 1) entry is 1_{GG} : GG ⟶ GG and that the first nonblank entry in column n, entry (n, n), is the inverse of entry (n, n − 1). Thus, by Lemmas 3.6 and 4.12, each column represents a single distributivity condition that a suitably long string may, or may not, possess. We call “Condition 1” that given by the first column. It is, by Lemma 3.4, simply the condition that the string is comprised of idempotents. Of course, Condition 1 is stateable for an adjoint string of length 1.

Condition 2, given by the second column of the table, is stateable for an adjoint string of length 2. Assuming Condition 1, as we have throughout, we can write G = Y Z and T = Y X, with Y : B ⟶ C fully faithful, and employ our usual conventions for units and counits. The distributive law T G ⟶ GT is the composite

Y XY Z ⟶^{Y βZ} Y Z ⟶^{Y Zα} Y ZY X

(and one should perhaps note that the isomorphisms T G ≅ G and GT ≅ T identify it with the composite G ⟶ 1_{C} ⟶ T). Since β is an isomorphism, Condition 2 holds precisely if Zα is an isomorphism which in turn is equivalent to invertibility of τ : Z ⟶ X. Thus, this distributivity condition leads to considerable degeneracy. It does not hold generally in the examples and classes of examples that we considered in Section 1. In particular, it does not hold for the adjoint strings in Δ. For a UIAO satisfying this condition, the isomorphism τ : Z ⟶^{≃} X provides that σ : W ⟶ Y is also an isomorphism so that the “cylinder” becomes a “torus”. It should not be supposed though that Y : B ⟶ C is an equivalence. For example, 1 ⊣ ! ⊣ 1 : 1 ⟶ grp is a distributive UIAO satisfying Condition 2 (and obviously grp can be replaced by any category with a zero object).

While Condition 2 is not satisfied in the examples that we have been studying, we know by Lemma 3.5 that if Condition 1 is satisfied then the condition given by the nth column is unambiguous. Condition 3, which is distributivity for a UIAO, needs no further comment. On the other hand, the table makes it clear that the isomorphic distributivity GL ≅ LG, appearing in Theorems 5.7 and 4.14, is the conjunction of Conditions 4 and 5. Clearly too, this condition only becomes stateable for adjoint strings of length at least 5. Mere inspection reveals that the adjoint strings n ⟶ n + 1 in Δ, which have length 2n + 1, satisfy all conditions i with 1 ≤ i ≤ 2n + 1 and i ≠ 2. For with 4 ≤ i, the relevant idempotents on n + 1 act independently and hence commute.

Example 8) in Section 1 provides an interesting example of a string of length 5 that satisfies the relevant higher order distributivities.

6.1. Proposition. The adjoint string of length 5, U ⊣ V ⊣ W ⊣ X ⊣ Y : set ⟶ set^{set^{op}}, with Y the Yoneda embedding, satisfies Conditions 1,3,4 and 5.

Proof. We remarked in Section 1 that this string satisfies the idempotence condition for V Y so, with our standing notation, it suffices to verify GL ≅ LG. Let Φ and Ψ be objects of set^{set^{op}}. For any U ⊣ ⋯ ⊣ Y : B ⟶ C, we have

GL(Φ, Ψ) ≅ Y (ZUV)(Φ, Ψ)
≅ ∫ ^{B} Y (Φ, B) × ZUV (B, Ψ)

≅ ∫ ^{B} C(Φ, Y B) × C(Y B, UV Ψ)
≅ ∫ ^{B} B(XΦ, B) × C(Y B, UV Ψ)

and

LG(Φ, Ψ) ≅ (UV Y)Z(Φ, Ψ)
≅ ∫ ^{B} UV Y (Φ, B) × Z(B, Ψ)
≅ ∫ ^{B} C(Φ, UV Y B) × C(Y B, Ψ).

In the case at hand, we recall from [13] that XΦ = Φ(1), V Ψ = Ψ(∅) and US = S·set(−, ∅), where S·− denotes S-fold multiple. Now, in the last coend expression for GL(Φ, Ψ), taking account of the Yoneda lemma, we have GL(Φ, Ψ) ≅ ∫^{B} set(Φ(1), B) × Ψ(∅)·set(B, ∅) ≅ set(Φ(1), ∅) × Ψ(∅). Also, LG(Φ, Ψ) ≅ ∫^{B} set^{set^{op}}(Φ, set(−, ∅)) × Ψ(B) ≅ ∫^{B} set(Φ(1), ∅) × Ψ(B), where we have invoked V Y B ≅ 1, for all B, the Yoneda lemma and X = −(1) ⊣ Y. Here, the coended expression is constant in the covariant variable so the coend reduces to a colimit. The indexing category for the colimit is set^{op}, whose terminal object is ∅, thus we have LG(Φ, Ψ) ≅ set(Φ(1), ∅) × Ψ(∅).

In a way, Proposition 6.1 should not be too surprising. For to the extent that set^{(−)^{op}} is a monad on CAT (the putative unit, the Yoneda embedding, exists only for locally small arguments) it has the Kock-Lawvere property and thus arises, roughly speaking, from a homomorphism with domain Δ, explicitly considered as a 2-category. We refer the reader to [19] for details.

The ideas of Proposition 6.1 also apply to completely distributive lattices, as in Example 5. For suppose that Y : B ⟶ C is the down-segment embedding of an ordered set, B, into its lattice of down-closed subsets and that we have an adjoint string of length 5, say U ⊣ V ⊣ W ⊣ X ⊣ Y. In [15] such strings were characterized as those arising from (constructively) completely distributive lattices, L, by application of the down-closed subsets 2-functor, D, to the defining adjoint string, ⇓ ⊣ ∨ ⊣ ↓: L ⟶ DL. In other words, the original string can be taken to be

⇓_{!}⊣ D ⇓⊣ D∨ ⊣ D ↓⊣ ↓_{∗}: DL ⟶ DDL,

where we have used (−)_{!}, respectively (−)_{∗}, to denote left, respectively right, Kan extension.

6.2. Proposition. If L is a constructively completely distributive lattice then the adjoint string ⇓_{!}⊣ D ⇓⊣ D∨ ⊣ D ↓⊣ ↓_{∗}: DL ⟶ DDL satisfies Conditions 1,3,4 and 5.

Proof. Since ↓_{∗}= (↓_{L})_{∗} =↓_{DL} is our generic Y, we have a particular instance of Example 5, so that Conditions 1 and 3 hold. Here we can take proarrows to be order ideals. Thus, it suffices to verify that the order ideals GL and LG are equal. Moreover, if we write Φ and Ψ for objects of DDL and B for an object of DL then the general calculations displayed in the proof of Proposition 6.1 adapt in this case to give

Φ(GL)Ψ iff (∃B)(XΦ ⊆ B and Y B ⊆ UV Ψ)

Φ(LG)Ψ iff (∃B)(Φ ⊆ UV Y B and Y B ⊆ Ψ).

Now we have X = ∪ and UV Ψ =⇓_{!} D ⇓ Ψ is the down-closure, with respect to containment, of the intersection of Ψ with the image of ⇓: L ⟶ DL. It follows that we have Φ(GL)Ψ if and only if (∃B)(∪Φ ⊆ B and (∃b)(B ⊆ ⇓ b ∈ Ψ)) which holds if and only if (∃B)(∃b)(∪Φ ⊆ B ⊆⇓b ∈ Ψ). Thus we have

Φ(GL)Ψ iff (∃b)(∪Φ ⊆⇓b ∈ Ψ).

On the other hand, the condition Φ ⊆ UV Y B can be seen to be

(∀A)(A ∈ Φ implies (∃b)(A ⊆ ⇓b ⊆ B)).

This condition is certainly implied by the condition (∃c)(∪Φ ⊆⇓ c ⊆ B) To see that it actually implies the latter, note that since ⇓ is a left adjoint it takes suprema in L to unions in DL so that ‘c’ can be witnessed by ∨{∨{b | A ⊆⇓ b ⊆ B} | A ∈ Φ}. It follows that we have Φ(LG)Ψ if and only if (∃B)((∃c)(∪Φ ⊆⇓ c ⊆ B) and B ∈ Ψ) which is the case if and only if (∃B)(∃c)(∪Φ ⊆⇓c ⊆ B ∈ Ψ). Using down-closedness of Ψ, this gives

Φ(LG)Ψ iff (∃c)(∪Φ ⊆⇓c ∈ Ψ).

In spite of Propositions 6.1 and 6.2 it should not be supposed that application of a Yoneda-structure 2-functor, such as set^{(−)^{op}} or D, to a distributive adjoint string of length n will always produce a distributive adjoint string of length n + 2, with the help of Kan extensions. For example, the fully faithful f : 1 ⟶ 3 which selects the middle element of the chain gives rise to a non-distributive UIAO, (∃f) ⊣ Df ⊣ (∀f) : D1 ⟶ D2. (It is easy to apply Theorem 4.3 by showing that the order ideal (∀f)^{∗}(∃f) is not an idempotent.) Since Dn = n + 1 this also shows that not all fully faithful adjoint strings in Δ are distributive. In fact, it shows further that distributivity of UIAOs is not composable. For the UIAO just described, 2 ⟶ 4, factors as 2 ⟶ 3 ⟶ 4.

There are a number of independence questions about the Conditions n of our table that should be settled. We have dealt with some already. Let us note now that Condition 4 is not a consequence of Conditions 1 and 3.

Counterexample: Consider the following lattices, C:

[figure: gh; hg; g; h; 1; s; t; ts; st; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; sg; gs]

and B:

[figure: ⊥; a; c; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; b; d; e; ⊤]

Defining Y : B ⟶ C by

\begin{matrix}x & ⊥ & a & b & c & d & e & ⊤ \\ Y x & gh & g & sg & t & gs & ts & st \end{matrix}

it is straightforward to show that an adjoint string of length 4 results which satisfies Conditions 1 and 3 but SG1 = sg ⟶ gs = GS1 is not invertible.

It is interesting to note that if C is collapsed by identifying sg ⟶ gs and B is collapsed by identifying b ⟶ d then the resulting adjoint string becomes distributive (in the sense that Condition 4 then holds) while at the same time distributive lattices result. We have not yet investigated the possible connections between these apparently quite different notions of “distributive”.

The reader will see from our notation above that the counterexample was freely generated in the same spirit as 11) of Section 1. These techniques can also be employed to show that Condition 5 does not follow from Conditions 1,3 and 4. Here, however, we get an infinite counterexample, as in 11) of Section 1, which is rather complicated to display. We conjecture that quite generally Condition n + 1 is independent of the conjunction of Conditions i, for 1 ≤ i ≤ n and i ≠ 2.

Let us now turn explicitly to Δ. We have already implicitly remarked that the lengthening construction, preceding Theorem 5.3, applied to 0 ⟶ 1 yields the adjoint string 1 ⟶ 2 of Δ. Similarly, it is easy to see that the lengthening construction, preceding Theorem 5.7, applied to the string 1 ⟶ 2 yields a string equivalent to the string 2 ⟶ 3 of Δ. Of course, to continue much further we do need a more appropriate notation, as we hinted at the beginning of Section 3. We defer a full treatment of this. However, let us point out here that the relevant matrix for generating a distributive string of length 7 from a distributive string of length 5 is:

( \begin{matrix}1 & L & LH & LHG \\ 1 & 1 & H & HG \\ S & 1 & 1 & G \\ T S & T & 1 & 1 \end{matrix} )

Proceding with this matrix, as we did in Section 5, the reader should be able to show how to generate a string equivalent to 3 ⟶ 4 starting with the string 2 ⟶ 3. The block structure of the family of matrices begins to emerge. In fact if the reader wishes to “square” the matrix above then the multiplication on it can be inferred from the distributive lattice below, which provides the generic category C for the “free” distributive adjoint string of length 5. (At least the reader will see the availability of the necessary component transformations with domain, or codomain, LHG.)

[figure: ghl; hglh; glh; hgl; hg; lh; h; 1; s; t; ts; st; lhg; gl; hg; g; lh; l; gh; hl; gs; lt]

Of course we are not claiming that our matrices are particularly efficient for constructing longer strings. Already we have seen that the data for the resulting monads is much simpler than what one finds for a general matrix monad. The point is that being able to organize in this fashion ensures the existence of the constructions in a rather general axiomatic context.

It is classical that, as a category, Δ is generated by the face and degeneracy operators subject to the cosimplicial identities. Lawvere in [7] showed that, as a monoidal category, Δ is generated by 0 ⟶ 1 ⟵ 2 and the equations dictating that this data forms a monoid. An account of this and the classical generation of Δ is also to be found in [10]. In [6] Kock observed that, as a monoidal 2-category, Δ is generated by Lawvere’s data and equations and the transformation ∂_{0} ≤ ∂_{1} : 1 ⟶ 2 subject to the two equations saying that this transformation is identified by both 0 ⟶ 1 and 2 ⟶ 1.

In [19] Street pointed out that Δ, regarded as a cosimplicial complex in CAT, is generated by adjunction and pushout from the unique functors 0 ⟶ 1 ⟵ 2. That is to say

[figure: n; n + 1; ∂_{0}; n − 1; n; ∂_{0}; ∂_{n−1}; ∂_{n}]

is a pushout for 1 < n and the ∂_{i} shown are the ends of the relevant adjoint strings. Our contention is that Δ, regarded as a cosimplicial complex in CAT, is generated from 0 ⟶ 1 by the lengthening constructions for adjoint strings. We note that pushout of the ends of a distributive adjoint string does not generally produce an adjoint string. (Consider, for example, the distributive UIAO 0 ⊣ ! ⊣ 1 : 1 ⟶ set and the pushout of 0 and 1.) The case n = 1 is explicitly excluded in the pushout considerations of Street above, while no exception arises with our lengthening constructions for adjoint strings.

Moreover, we are suggesting that given a distributive adjoint string, in a 2-category satisfying our axioms, that it can be completed so as to provide a surrogate for a truncation of Δ of any desired length. For exponentiable starting data in the 2-category of toposes and geometric morphisms, this generalization holds promise.

References

[1] J. Beck. Distributive laws. In Lecture Notes in Math., no. 80, pages 119–140, Springer Verlag, 1969.

[2] S. Eilenberg and J.C. Moore. Adjoint functors and triples. Ill. J. Math., 9:381–398, 1965.

[3] Barry Fawcett and R. J. Wood. Constructive complete distributivity I. Math. Proc. Cam. Phil. Soc., 107:81–89, 1990.

[4] P. T. Johnstone and A. Joyal. Continuous categories and exponentiable toposes. Journal of Pure and Applied Algebra, 25:255–296, 1982.

[5] G. M. Kelly and F. W. Lawvere. On the complete lattice of essential localizations. Bulletin de la Societe Mathematique de Belgique(Serie A), xli:289–319, 1989.

[6] A. Kock. Generators and relations for Δ as a monoidal 2-category. Aarhus Preprint Series, 1, 1993.

[7] F. W. Lawvere. Ordinal sums and equational doctrines. In Lecture Notes in Math. no. 80, pages 141–155, Springer-Verlag, 1969.

[8] F. W. Lawvere. Tools for the advancement of objective logic: closed categories and toposes. In The Logical Foundations of Cognition, Vancouver Studies in Cognitive Science, pages 43–56, Oxford University Press, 1994.

Theory and Applications of Categories, Vol. 1, No. 6 145

[9] F.W. Lawvere. Cohesive toposes and Cantor’s lauter einsen. Philosophia Mathematica, 2:5–15, 1994.

[10] S. Mac Lane. Categories for the Working Mathematician. Springer Verlag, 1971.

[11] D.H. Van Osdol. Sheaves in regular categories. In Exact Categories and categories of sheaves, Lecture Notes in Math. no 236, pages 223–239, Springer-Verlag, 1971.

[12] R. Paré, R. Rosebrugh, and R.J. Wood. Idempotents in bicategories. Bulletin of the Australian Math. Soc., 39:421–434, 1989.

[13] Robert Rosebrugh and R. J. Wood. An adjoint characterization of the category of sets. Proc. Amer. Math. Soc., 122(2):409–413, 1994.

[14] Robert Rosebrugh and R. J. Wood. Cofibrations in the bicategory of topoi. Journal of Pure and Applied Algebra, 23:71–94, 1984.

[15] Robert Rosebrugh and R. J. Wood. Constructive complete distributivity IV. Applied Categorical Structures, 2:119–144, 1994.

[16] Robert Rosebrugh and R. J. Wood. Gamuts and cofibrations. Cahiers de topologie et géometrie différentielle catégoriques, XXXI-3:197–211, 1990.

[17] Robert Rosebrugh and R. J. Wood. Proarrows and cofibrations. Journal of Pure and Applied Algebra, 53:271–296, 1988.

[18] S. Schanuel and R. Street. The free adjunction. Cahiers de topologie et géometrie différentielle catégoriques, XXVII-1:81–83, 1986.

[19] R. Street. Fibrations in bicategories. Cahiers de topologie et géometrie différentielle, XXI:111–160, 1980.

[20] M. Thiébaud. Self-dual structure-semantics. PhD thesis, Dalhousie University, 1971.

[21] R. J. Wood. Proarrows II. Cahiers de topologie et géometrie différentielle catégoriques, XXVI:135–168, 1985.

Department of Mathematics and Computer Science Mount Allison University Sackville, N.B. E0A 3C0 Canada Department of Mathematics, Statistics and Computing Science Dalhousie University Halifax, N.S. B3H 3J5 Canada

Email: rrosebrugh@mta.ca and rjwood@cs.dal.ca

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/1995/n6/v1n6.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/gopher/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi and Postscript format. Details will be emailed to new subscribers and are available by WWW/gopher/ftp. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and LaTEX is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at URL http://www.tac.mta.ca/tac/ or by anonymous ftp from ftp.tac.mta.ca in the directory pub/tac/info. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@triples.math.mcgill.ca Lawrence Breen, Université de Paris 13: breen@dmi.ens.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, University of Genoa: carboni@vmimat.mat.unimi.it P. T. Johnstone, University of Cambridge: ptj@pmms.cam.ac.uk G. Max Kelly, University of Sydney: kelly m@maths.su.oz.au Anders Kock, University of Aarhus: kock@mi.aau.dk F. William Lawvere, State University of New York at Buffalo: mthfwl@ubvms.cc.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.ruu.nl Susan Niefield, Union College: niefiels@gar.union.edu Robert Paré, Dalhousie University: pare@cs.dal.ca Andrew Pitts, University of Cambridge: ap@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@charlie.math.unc.edu Ross Street, Macquarie University: street@macadam.mpce.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca R. W. Thomason, Université de Paris 7: thomason@mathp7.jussieu.fr Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Sydney: walters b@maths.su.oz.au R. J. Wood, Dalhousie University: rjwood@cs.da.ca