A BASIC DISTRIBUTIVE LAW

F. MARMOLEJO, R.D. ROSEBRUGH AND R.J. WOOD

ABSTRACT. We pursue distributive laws between monads, particularly in the context of KZ-doctrines, and show that a very basic distributive law has (constructively) completely distributive lattices for its algebras. Moreover, the resulting monad is shown to be also the double dualization monad (with respect to the subobject classifier) on ordered sets.

1. Introduction

1.1. In February of 1984, at a meeting in San Juan, two of us heard Fred Linton describe the category of frames as the category of algebras for a distributive law between monads on the category of ordered sets (while at the same time he pointed out that no such result holds over the category of sets). A moment’s reflection on this suggests that an analogous result must hold for the category of completely distributive lattices. It does. The distributive law in question is particularly interesting though and warrants both description and study.

1.2. Distributive laws between monads in a bicategory can lead to rather large diagrams, especially by way of the ‘pentagon’ conditions. In [RW4] it was shown that for idempotent monads (and comonads) there is a major simplification — one triangle suffices. In this paper the distributive law on which we focus involves a ‘KZ’ monad and a ‘co-KZ’ monad. Such monads (or ‘doctrines’ as they are often called) are generalizations of idempotent monads, requiring one further categorical dimension to define them, so it is not too surprising that we are able to simplify the study of distributive laws between them. This we do in Section 4. We express our results for such monads on an object in an ord-cat-category, where ord denotes the 2-category of antisymmetric ordered sets.

1.3. A brief word on the level of generality may be helpful. In [STR] Street defined and studied monads on objects in an arbitrary 2-category. His results are easily extended to monads on objects in bicategories — either directly or by using the coherence theorem which states that each bicategory is biequivalent to a 2-category. It has become clear that KZ-doctrines should be studied in the context of pseudomonads on objects in a tricategory. Given the coherence result of [GPS], it suffices to study them in Gray-categories and this development has begun in [MO1], [MO2] and [MO3]. There is no doubt that substantial results of the kind we present can be proved in general Gray-categories, however, their pursuit here would take us too far afield from the main applications we have in mind.

The authors gratefully acknowledge financial support from the Canadian NSERC. Diagrams typeset using M. Barr’s diagram macros.

1991 Mathematics Subject Classification: 06D10, 18B35, 18C15.

Key words and phrases: KZ-doctrine, adjunction, completely distributive.

Our modifications (3-cells) are mere inequalities and we assume that any instance of ≤ is antisymmetric.

1.4. Section 3 is in the spirit of [STR] and the results are valid in any bicategory. We add a new formulation of distributive laws that is useful when the ambient bicategory does not necessarily admit the ‘construction of algebras’ in the terminology of [STR] (or, said otherwise, Eilenberg-Moore objects are not known to exist). This formulation is frequently useful and also clarifies the characterization of distributive laws in terms of Kleisli objects. (In this last connection we have in mind recent work of Pisani [PIS] and Johnstone [JOH].)

1.5. In Section 5 we introduce our ‘basic distributive law’ r : UD \overline{}DU, where D and U underlie the ‘down-set’ KZ-doctrine D, respectively the ‘up-set’ co-KZ-doctrine U, on the 2-category of ordered sets. We show that this law restricts to a number of important submonads of D and U. From our results in Section 4 it follows that the basic law gives rise to the only possible distributive law in each case. In particular, leaving D unaltered and replacing U by the ‘finitely-generated up-set’ monad we obtain Linton’s distributive law which captures frames in terms of sup-lattices and meet-semi-lattices, over the 2-category of (antisymmetric) ordered sets.

1.6. In Section 6 we show that the algebras for the monad arising from our basic law are precisely the constructively completely distributive — CCD — lattices introduced in [F&W] and further studied in [RW1], [RW2], [RW3] and [P&W]. The distributive law r : UD \overline{}DU has a left adjoint which is also a distributive law and its algebras are those lattices whose dual is CCD. The distinction between such lattices and CCD lattices is not apparent with respect to boolean set theory but as with other papers that deal with CCD lattices our results are intuitionistically valid. Using our techniques of Section 5 we are also able to answer an interesting question of Paul Taylor: the algebras over ordered sets for double dualization with respect to the subobject classifier are also the CCD lattices.

2. KZ-Doctrines

2.1. Let K be an ord-cat-category. Thus, for each pair of objects A, B in K, we have an ord-category K(A, B), meaning that for each pair of arrows (1-cells) A, B from A to B we have an ordered set K(A, B)(A, B) of transformations (2-cells) from A to B. To fix notation, write

a ≤ b : A \overline{}B : A \overline{}B

for an inequality providing a typical modification of K. Composition of arrows in the underlying ordinary category of K is denoted by juxtaposition; we use −·− for composition in the K(A, B). Since we assume the ≤ to be antisymmetric, K has an underlying 2category. So given x : X \overline{}Y : X \overline{}A and a : A \overline{}B : A \overline{}B, we have Bx · aX = aY · Ax in the ordered set K(X , B)(AX, BY) providing a well-defined ax : AX \overline{}BY : X \overline{}B. When we speak of a monad on an object K in K we are in the first instance considering the underlying 2-category of K and we have immediate access to the formal theory of monads as described in [STR]. (It should be stressed that replacing K by a general Gray-category considerably complicates this discussion.)

2.2. Definition. A KZ-doctrine on an object K in K consists of an arrow D : K \overline{}K and a transformation d : 1_{K} \overline{}D which admit a fully-faithful adjoint string, in the sense of [RW4], Dd ⊣ m ⊣ dD : D \overline{}DD (in K(K, K)).

Precisely because our Gray-category K is merely ordered at the level of modifications, we are able to dispense with the coherence equation in the general definition of KZ-doctrine given in [MO1]. We also avoid having to consider the adjunctions Dd ⊣ m and m ⊣ dD as data. Note that if K is ord-cat then our definition of KZ-doctrine coincides with that in [KOK].

2.3. It is convenient to say that a co-KZ-doctrine on an object K in K consists of an arrow U : K \overline{}K and a transformation u : 1_{K} \overline{}U which admit a fully-faithful adjoint string uU ⊣ n ⊣ Uu : U \overline{}UU. A KZ-doctrine (D, d), [co-KZ-doctrine (U, u)] gives rise to a monad, (D, d, m) [(U, u, n)]. We note that fully-faithfullness in the definition gives a modification Dd ≤ dD [uU ≤ Uu]. A T-algebra for a monad T = (T, t, c) on K in K with domain X is an arrow X : X \overline{}K, together with a transformation x : T X \overline{}X satisfying the usual axioms, which for convenience we have stated in 3.3. It is now classical, in fact the starting point of KZ study by Kock, that if (T, t, c) is KZ then (X, x) is a T-algebra if and only if x ⊣ tX (in K(X , K)), with tX fully-faithful. Similarly, if (T, t, c) is co-KZ then (X, x) is a T-algebra if and only if tX ⊣ x, with tX fully-faithful. Of course, if t is fully-faithful then the fully-faithful requirement is satisfied automatically and a similar remark applies to Definition 2.2 if d itself is known to be fully-faithful.

3. Distributive Laws

3.1. For monads D = (D, d, m) and U = (U, u, n) on K a transformation r : UD \overline{}DU is a distributive law of U over D if it satisfies the following four axioms of Beck as found in [BEK]:

[figure: UD; DU; r; U; Ud; dU; D; uD; Du; UD; DU; r; UDD; DDU; Um; mU; DUD; rD; Dr; UUD; DUU; nD; Dn; UDU; Ur; rU]

Observe that each axiom involves precisely one of the structural transformations d, m, u, n of the monads in question. We will write r[s], for s in {d, m, u, n} to indicate that a mere transformation r : UD \overline{}DU does at least satisfy the axiom involving s. (So, for example, r[d] is the equation expressed by the top triangle above.)

3.2. In [BEK] it is shown that distributive laws r : UD \overline{}DU involving monads on a category K are in bijective correspondence with multiplications p : DUDU \overline{}DU for which: (DU, du, p) is a monad; dU : U \overline{}DU \overline{}D : Du provide monad transformations; and the middle unitary law

[figure: DU; DUDU; DudU; 1_{DU}; DU; p]

holds. It is further shown that distributive laws r : UD \overline{}DU are in bijective correspondence with ‘liftings’ D̃ of the monad D to K^{U}, the category of U-algebras. ‘Laws’ and ‘multiplications’ are in a sense quite different from ‘liftings’. The first two involve only a (natural) transformation satisfying equations while the last requires construction of an endo-functor on a category which is best viewed as a (lax) limit. It is obvious that the formal theory of monads, [STR], applies to the first two without reservation but we can only hope to speak of the last in a bicategory in which the requisite lax limit exists. It is fair to say that laws and multiplications are syntactic entities while liftings live at the level of semantics. There are results about distributive laws that are immediately apparent when translated as liftings but which require some opaque diagram chasing when considered directly. A good example is provided by: ‘If U is an idempotent monad on K then, for any monad D on K there is at most one distributive law UD \overline{}DU’. Proof: The forgetful functor from the algebras for an idempotent monad is fully-faithful, so a lifting is a restriction and a functor either restricts or it doesn’t. (In [RW4] a less memorable, but syntactic, proof is given.)

3.3. It transpires however that there is a syntactic formulation of ‘lifting’ that enables reasonably memorable proofs of results such as that at the end of 3.2 above. For a U-algebra with domain X, say x : UX \overline{}X : X \overline{}K, the requisite equations are:

[figure: X; UX; x; UX; UUX; nX; Ux; X; uX; 1_{X}; x]

In particular, in the context of monads (D, d, m) and (U, u, n), we can examine U-algebras on DU : K \overline{}K. Let us write a : UDU \overline{}DU for such an algebra. We will consider such algebras satisfying, in addition to the two basic equations above, the following three equations:

[figure: DUU; DU; Dn; UDUU; UDU; UDn; aU; a; U; DU; dU; UU; UDU; UdU; n; a; UDUDU; UDDU; UDU; UmU; UDuDU; DUDU; aDU; DDU; DU; mU; Da; a]

Replacing the generic (X, x) in the basic U-algebra equations by (DU, a), we will label the resulting five equations for (DU, a) that have appeared above as a[u], a[n], a[Dn], a[dU] and a[mU] respectively. Each of a[Dn], a[dU] and a[mU] asserts that the arrow on the bottom side of the square in question is a homomorphism of U-algebras. That the domain of the first is in fact a U-algebra by way of structure aU follows from the general fact that if x : UX \overline{}X : X \overline{}K is an algebra, then for any Y : Y \overline{}X, xY : UXY \overline{}XY : Y \overline{}K is a U-algebra. (We may see such as the Y ’th instance of (X, x).) Of course (UU, n) is a U-algebra and for the third we note:

3.4. Lemma. If (U, u, n) is a monad on an object K in a 2-category, D : K \overline{}K is any arrow, and a : UDU \overline{}DU is a U-algebra structure satisfying a[Dn] then

UDDU ^{\overline{}^{UDuDU}} UDUDU ^{\overline{}^{aDU}} DUDU ^{\overline{}^{Da}} DDU

is a U-algebra.

Proof. The proof is a large diagram chase that is nevertheless easily found using the DU’th instance of a[Dn].

3.5. Proposition. Given monads (D, d, m) and (U, u, n) on an object in a 2-category, there is a bijective correspondence between distributive laws r : UD \overline{}DU and Ualgebras a : UDU \overline{}DU satisfying a[Dn], a[dU], and a[mU]; given by:

r \overline{}α(r) = (UDU ^{\overline{}^{rU}} DUU ^{\overline{}^{Dn}} DU)

with inverse given by:

a \overline{}ρ(a) = (UD ^{\overline{}^{UDu}} UDU ^{\overline{}^{a}} DU)

Proof. We will just give the equations (other than monad equations and ‘interchange’) that are relevant at each step.

i) To show that α(ρ(a)) = a, use a[Dn];

ii) For ρ(α(r)) = r, no ‘r’ equations are needed; iii) To show that α(r) satisfies α(r)[Dn], no ‘r’ equations are needed; iv) For α(r)[u], use r[u];

v) For α(r)[n], use r[n]; vi) For α(r)[dU], use r[d]; vii) For α(r)[mU], use r[m]; viii) For ρ(a)[u], use a[u]; ix) For ρ(a)[n], use a[n] and a[Dn];

x) For ρ(a)[d], use a[dU]; xi) For ρ(a)[m], use a[mU].

The following result is sometimes helpful. 3.6. Lemma. For a = α(r), the U-algebra structure on DDU given in Lemma 3.4 is

UDDU ^{\overline{}^{rDU}} DUDU ^{\overline{}^{DrU}} DDUU ^{\overline{}^{DDn}} DDU.

3.7. The considerations of 3.3, in which we have isolated special left U-algebra structures on DU, suggest that it is reasonable to examine right D-algebra structures on DU. Quite generally, given a monad (D, d, m) on an object K in a 2-category and an arrow X : K \overline{}X, a right D-algebra structure on X — which we would prefer to call a D-opalgebra structure following the terminology of [STR] — is a transformation x : XD \overline{}X which is unitary and associative. In the case of X = DU and a transformation b : DUD \overline{}DU we will write

b[d] for b · DUd = 1_{DU}

b[m] for b · DUm = b · bD

(the unitary and assciative conditions respectively) and to these add b[mU] for mU.Db = b · mUD

b[Du] for Du · m = b · DuD
b[Dn] for Dn · bU · DUb · DUdUD = b · DnD

quite analogously to the extra equations in 3.3. With these at hand a dualization of Proposition 3.5 gives:

3.8. Proposition. Given monads (D, d, m) and (U, u, n) on an object in a 2-category, there is a bijective correspondence between distributive laws r : UD \overline{}DU and Dopalgebras b : DUD \overline{}DU satisfying b[mU], b[Du], and b[Dn]; given by:

r \overline{}β(r) = (DUD ^{\overline{}^{Dr}} DDU ^{\overline{}^{mU}} DU)

with inverse given by:

b \overline{}σ(b) = (UD ^{\overline{}^{dUD}} DUD ^{\overline{}^{b}} DU)

We will sketch below how the U-algebra structures of 3.3 are in bijective correspondence with liftings of D to the Eilenbeg-Moore object K^{U}. From this point of view it is clear that the D-opalgebra structures of 3.7 are in bijective correspondence with extensions of U to the Kleisli object K_{D}. This last observation seems to have been largely overlooked but bears on recent work of others, for example [PIS] and [JOH]. Accordingly, we summarize formally:

3.9. Theorem. For monads D = (D, d, m) and U = (U, u, n) on an object K in a 2-category, the following structures are in bijective correspondence:

i) Distributive laws UD \overline{}DU;

ii) Monad structures as in 3.2 on DU;

iii) U-algebra structures as in 3.3 on DU;

iv) D-opalgebra structures as in 3.7 on DU;

and, if the 2-category admits Eilenberg-Moore algebras then i) through iv) are in bijective correspondence with

v) Liftings of D through K^{U} \overline{}K;

and, if the 2-category admits Klesili opalgebras then i) through iv) are in bijective correspondence with

vi) Extensions of U along K \overline{}K_{D}.

Proof. In view of the discussion above and the account in [BEK], it suffices to sketch the correspondence between iii) and v); that of iv) and vi) being a dual. To give a lifting of D through K^{U} \overline{}K is to prescribe a monad on K^{U} whose structure commutes with that of D via K^{U} \overline{}K, where K^{U} \overline{}K (the forgetful functor when the 2-category is CAT) is the arrow part of the universal U-algebra

[figure: K^{U}; K; K; U]

Thus to give even an arrow D̃ : K^{U} \overline{}K^{U} with

[figure: K; K; D; K^{U}; K^{U}; D̃]

is to give a U-algebra structure on K^{U} \overline{}K ^{\overline{}^{D}} K. Such an algebra structure when preceded by the left adjoint to K^{U} \overline{}K (whose existence follows from the universal property of K^{U}, see [STR]) gives a U-algebra structure on DU, since the composite K \overline{}K^{U} \overline{}K is U. It should be clear now how the required correspondence is constructed.

By way of illustration of the use of iii) of 3.9 let us return to the fact stated at the end of 3.2: ‘If U is an idempotent monad on an object K in any 2-category then, for any monad D on K, there is at most one distributive law UD \overline{}DU’. Proof: For any X : X \overline{}K there is a U-algebra structure on X if and only if uX : X \overline{}UX is invertible, in which case it is given by (uX)^{−1}. In particular this holds for X = DU. To illustrate the use of vi) we note that it would sometimes seem to be desirable to extend a monad T on set, the category of sets and functions, along set \overline{}rel, where rel is the category of sets and relations and the functor interprets a function as the relation given by its graph. However set \overline{}rel is the Kleisli opalgebra set \overline{}set_{P}, where P is the power-set monad, so it follows that the desired extensions correspond to distributive laws T P \overline{}P T.

4. KZ-Doctrines and Distributive Laws

4.1. Proposition. For an object K in any ord-cat-category K,

i) If U is either a KZ-doctrine or a co-KZ-doctrine on K and D is any monad on K then there is at most one distributive law UD \overline{}DU;

ii) If D is either a KZ-doctrine or a co-KZ-doctrine on K and U is any monad on K then there is at most one distributive law UD \overline{}DU.

Proof. For i) and the case in which U is co-KZ apply iii) of Theorem 3.9 and recall 2.3. The arrow DU supports a U-algebra structure (not a priori satisfying all the requirements of iii) of Theorem 3.9) if and only if uDU has a right adjoint, which in this case is the structure arrow. The other case of i) appeals to existence of left adjoints and ii) is similar except that it uses iv) of Theorem 3.9.

4.2. It is natural to conjecture that if a distributive law r : UD \overline{}DU involves KZdoctrines or co-KZ-doctrines then the conditions r[m] and r[n] can be derived from r[d] and r[u]. In the diagrams which follow it is convenient to display instances of modifications with unlabelled arrows \overline{}rather than inequality symbols ≤.

4.3. Lemma. For monads D and U and a transformation r : UD \overline{}DU,

i) If (D, d, m) is either KZ or co-KZ then r[d] implies r[m];

ii) If (U, u, n) is either KZ or co-KZ then r[u] imples r[n].

Proof. For i) assume that (D, d, m) is KZ and consider the two modifications below whose conjunction is r[m].

[figure: UD; DU; r; UDD; DDU; Um; mU; DUD; rD; Dr]

Using simple instances of mates as in [K&S], we see that existence of the first of the modifications above follows from the first below and similarly for the second.

[figure: UD; DU; r; UDD; DDU; UDd; DdU; DUD; rD; Dr; DUd; UD; DU; r; UDD; DDU; UdD; dDU; DUD; rD; Dr; dUD]

Now to assume r[d] is to assume r·Ud ≤ dU and dU ≤ r·Ud. The first of these inequalities upon application of D gives Dr · DUd ≤ DdU — the first triangle above. The second inequality applied to D gives dUD ≤ rD · UdD — the second triangle. This completes the proof of i) in the case (D, d, m) is KZ. The proof when (D, d, m) is co-KZ is entirely similar (in fact dual), as is that of ii).

In fact, we can do slightly better in reducing the requirements for a distributive law r : UD \overline{}DU in the present context. Of the original two triangles and two pentagons in 3.1, ‘one and half triangles suffice’.

4.4. Proposition. For monads D and U and a transformation r : UD \overline{}DU:

i) If (D, d, m) is KZ and (U, u, n) is either KZ or co-KZ then r : UD \overline{}DU is a distributive law if it satisfies r[d] and r · uD ≤ Du;

ii) If (U, u, n) is co-KZ and (D, d, m) is either KZ or co-KZ then r : UD \overline{}DU is a distributive law if it satisfies r[u] and r · Ud ≤ dU Proof. For i) consider the following diagram, in which the triangle surmounting the square is D applied to r[d].

[figure: Dd; D; DD; dD; DUD; DuD; UD; DU; r; DDU; Dr; dUD; dDU; DdU; DU; DUd; DU; mU; 1_{DU}; Du; uD; 1_{DU}]

All regions commute except for that given by Dd ≤ dD, which we have since (D, d, m) is KZ. So the diagram gives Du ≤ r · uD. This inequality and the given inequality then provide r[u], so that invoking Lemma 4.3 we have a distributive law. The second statement is dual.

In case we have an adjunction l ⊣ r : UD \overline{}DU, the task of checking that either l or r is a distributive law is facilitated somewhat by the following:

4.5. Lemma. For monads (D, d, m) and (U, u, n) on K and l ⊣ r : UD \overline{}DU,

i) If (D, d, m) is either KZ or co-KZ then l[d] implies r[m];

i) If (U, u, n) is either KZ or co-KZ then l[u] implies r[n];

i) If (D, d, m) is either KZ or co-KZ then r[d] implies l[m];

i) If (U, u, n) is either KZ or co-KZ then r[u] implies l[n].

Proof. We prove just the first half of the first implication. Again, the other calculations are similar. The equality r[m], see the first diagram in the proof of Lemma 4.3, is equivalently given as an equality between left adjoints and in the case that (D, d, m) is KZ and l[d] holds we have

[figure: UD; DU; l; UDD; DDU; UDd; DdU; DUD; lD; Dl; DUd]

5. Ordered Sets

5.1. For the rest of the paper D : ord \overline{}ord will denote the 2-functor which sends an ordered set X to the set of down-sets of X ordered by inclusion and which is defined on arrows by down-closure of direct image. Of course DX is naturally isomorphic to [X^{op}, Ω], the ordered set of functors from X^{op} to to the subobject classifier. To help clarify notation, let f : X \overline{}A be an arrow in ord. Here, for S ∈ DX we have

Df(S) = {fx|x ∈ S} ^{}= {a ∈ A|(∃x ∈ S)(a ≤ fx)}.

We will write D = [(−)^{op}, Ω] : ord^{coop} \overline{}ord. Then, modulo identification of [X^{op}, Ω] with DX, Df is given by inverse image. For all f : X \overline{}A in ord, we have Df ⊣ Df. In the context of D as above we will understand dX : X \overline{}DX to be the yoneda functor that sends x to {y|y ≤ x}. We may write ↓x for dX(x). It is well known that D = (D, d) is a KZ-doctrine and that the 2-category of D-algebras is sup, the 2-category of complete lattices, sup-preserving functors and inequalities. See, for example, Chapter III.3 of [J&T].

5.2. It is convenient to write

U = (D(−)^{op})^{op} : ord \overline{}ord and U = (D(−)^{op})^{op} : ord \overline{}ord^{coop}.

So UX is the set of up-sets of X ordered by reverse inclusion and is naturally isomorphic to [X, Ω]^{op}. From this last observation it follows easily that U is the left 2-adjoint of D. For reference later, note that UD : ord \overline{}ord is simply double dualization with respect to Ω, that is [[−, Ω], Ω], which we regard as a 2-monad on ord via the structure of the 2-adjunction. For all f : X \overline{}A in ord, we have Uf ⊣ Uf but note that it is Uf which is given by inverse image while Uf is up-closure of direct image. In the context of U we will understand uX : X \overline{}UX to be the coyoneda functor that sends x to \{y|x ≤ y\}. We may write ↑x for uX(x). Now U = (U, u) is a co-KZ-doctrine, the 2-category of algebras for which is inf, the 2-category of complete lattices, inf-preserving functors and inequalities.

5.3. The elegant notion of yoneda structure on a 2-category as defined in [S&W] has ord together with the yoneda functors dX : X \overline{}DX of 5.1 as an important example. Following [S&W] we recall that for any f : X \overline{}A in ord we have a diagram

[figure: X; A; f; dX; DX; A(f, 1)]

which is both a left (kan) extension and an absolute left lifting. (Extensions and liftings are carefully explained in [S&W].) Here it is straightforward to show that A(f, 1) sends

12

a to the down-set \{x ∈ X|fx ≤ a\}. Now taking UdX : UX \overline{}UDX for f : X \overline{}A above and writing rX for UDX(UdX, 1) we have, for each X in ord

[figure: UX; UDX; UdX; dUX; DUX; rX]

The left extension triangle commutes because UdX is fully-faithful, which we have since dX is so. It is clear that the construction defines r : UD \overline{}DU, 2-naturally.

5.4. Using the description of A(f, 1) in 5.3 we can calculate rX explicitly. Observe first that, for T ∈ UX,

UdX(T) = {S ∈ DX|(∃x ∈ T)(↓x ⊆ S}
= {S ∈ DX|(∃x ∈ T)(x ∈ S)}
‘ = ’ {S ∈ DX|T ∩ S is non-empty},

where the last ‘equation’ is intuitively helpful but intuitionistically unhelpful. For T ∈ UDX, we have

rX(T ) = {T ∈ UX|UdX(T) ⊇ T }
= {T ∈ UX|(∀S ∈ T )(S ∈ UdX(T))}
= {T ∈ UX|(∀S ∈ T )(∃x ∈ T)(x ∈ S)}
‘ = ’ {T ∈ UX|(∀S ∈ T )(T ∩ S is non-empty)}.

From the last ‘equation’ above it is clear that r : UD \overline{}DU has a left adjoint l : DU \overline{}UD which, for S ∈ DUX, is given by

lX(S) = {S ∈ DX|(∀T ∈ S)(∃x ∈ S)(x ∈ T)}
‘ = ’ {S ∈ DX|(∀T ∈ S)(T ∩ S is non-empty)}.

It is the case that the lX also arise by consideration of the coyoneda structure on ord given by the uX : X \overline{}UX and observations dual to those in 5.3.

5.5. Proposition. The transformation r : UD \overline{}DU : ord \overline{}ord is a distributive law of U over D and the transformation l : DU \overline{}UD : ord \overline{}ord is a distributive law of D over U.

Proof. By construction of r we have r[d], so by Proposition 4.4 it suffices, for the first claim, to show that r · uD ≤ Du. In other words, we must show that for all S in DX, rX(↑S) ⊆ {↑x|x ∈ S} ^{}. But if T is in rX(↑S) then for all S′ which contain S there is an x in T ∩ S′. In particular, there is an x in T ∩ S and now T ⊇↑x and x ∈ S shows that T ∈ {↑x|x ∈ S} ^{}. The calculations for l are similar but can be shown to follow from those above by duality.

5.6. Remark. If we write idl for the bicategory of ordered sets, order ideals and inclusions then a down-set S of X can be regarded as an arrow S : 1 \overline{}X in idl. Similarly, an up-set T of X can be regarded as an arrow T : X \overline{}1 in idl. A composite T S : 1 \overline{}1 of such admits a comparison T S ⊆ 1_{1} (because 1_{1} : 1 \overline{}1 is terminal in idl(1, 1)). To say that (∃x)(x ∈ T and x ∈ S), the condition which arises in the definitions of both r and l in 5.4 is to say that T S ⊆ 1_{1} is an equality.

5.7. Suppose now that d : 1 \overline{}D [u : 1 \overline{}U] factorizes as 1 ^{\overline{}^{d′}} D′ ^{\overline{}^{i}} D [1 ^{\overline{}^{u′}} U′ ^{\overline{}^{j}} U], with i [j] fully-faithful. From the proof of Theorem 3.8 in [RW5] it follows that if D′- [U′-] unions (in both cases) of D′- [U′-] sets are D′- [U′-] sets then D′ = (D′, d′) [U′ = (U′, u′)] is also a KZ [co-KZ] doctrine and i [j] is a monad arrow. In this situation, we can attempt to define r′ : U′D′ \overline{}D′U′ by modifying the description of r in 5.4 so as to have

r′X(T ) = {T ∈ U′X|(∀S ∈ T )(∃x ∈ T)(x ∈ S)}

and similarly for an l′ : D′U′ \overline{}U′D′. This definition of r′ certainly gives an arrow U′D′ \overline{}DU′ and it factorizes through D′U′ \overline{}DU′ if the set displayed above is a D′- set. Similarly for l′, the obvious putative definition makes sense if the defining set is a U′-set. If r does restrict to give r′ then the general considerations of Section 4 show that we have a distributive law r′ : U′D′ \overline{}D′U′ of U′ over D′ (and that this is the only possibility for such a law). It should be noted that r may restrict to give such an r′ without l restricting to give such an l′. Observe that if D′ = D then the condition is automatically satisfied for r′ : U′D \overline{}DU′ to be a distributive law. In particular take U′ to be given by finitely-generated up-sets. These are closed with respect to finite unions and the resulting co-KZ-doctrine is well known to be that for which the algebras are meet-semi-lattices. The algebras for the composite monad DU′ are frames. This is the law that we attributed to Linton in 1.1. In this case, l does not restrict to give an l′.

5.8. In [RW5] there is an extended discussion of the case where D′ is given by bounded down-sets and U′ by non-empty up-sets. There it is shown that r′ : U′D′ \overline{}D′U′ is well-defined. We note here that in this case l′ : D′U′ \overline{}U′D′ is also well-defined.

If D′ is given by finitely-generated down-sets and U′ by finitely-generated up-sets then both r′ and l′ are well-defined.

If D′ is given by up-directed down-sets and U′ by finitely-generated up-sets then r′ is well-defined.

We should point out here that the basic law r is sensitive to the base 2-category ord. In particular, r does not preserve all finite joins so that it is not possible to consider the restrictions of such monads D′ and U′ as are under under consideration to, say, the 2-category of distributive lattices and obtain a distributive law whose components are the rL, where L is a distributive lattice.

6. Complete Distributivity

6.1. By DU we will understand the monad on ord constructed on DU with the help of r. Similarly, UD is the composite monad obtained with the help of l. From [F&W] we recall that a (constructively) completely distributive lattice is an ordered set L for which dL has a left adjoint which has a left adjoint. We often call such L CCD lattices and a number of characterizations of these are given in [RW3]. Now to say that L^{op} is CCD is to say that uL has a right adjoint which has a right adjoint. Here we will call such an L an ^{op}CCD lattice. Classically the notions CCD and ^{op}CCD coincide but it was shown in [RW1] that relative to a general elementary topos, coincidence of CCD and ^{op}CCD is equivalent to booleaness of the topos in question. We write ccd [^{op}ccd] for the 2-category of CCD [^{op}CCD] lattices, functors that preserve both sups and infs, and inequalities.

6.2. Theorem.

i) ord^{DU} ≅ ccd
ii) ord^{UD} ≅ ^{op}ccd

Proof. It suffices to give a proof of i); that of ii) is dual to it. From Section 2. of [BEK] we know that a DU-algebra is a U-algebra that carries a D-algebra structure for which the D-structure arrow is a U-homomorphism. If L is a U-algebra, that is an object of inf, it is necessarily an object of sup but its D-algebra structure, that is ⋁ : DL \overline{}L, is a U-homomorphism iff ⋁ preserves infima iff ⋁ has a left adjoint iff L is CCD. Of course DU-homomorphisms are just arrows that are both U-homomorphisms (inf-preserving) and D-homomorphisms (sup-preserving).

6.3. Consider the adjunction [−, Ω] ⊣ [−, Ω] : ord^{op} \overline{}ord which gives rise to the monad on ord known as double dualization with respect to Ω. We are grateful to Paul Taylor for asking us to consider the algebras for this monad. As pointed out in 5.2 this monad admits the apparently more complicated description DU, which is obtained by composing the adjunction above with the isomorphism (−)^{op} ⊣ (−)^{op} : ord^{coop} \overline{}ord^{op}.

6.4. Lemma. DU = DU : ord \overline{}ord

Proof. Consider an arrow f : X \overline{}A in ord. As noted in 5.2, Uf ⊣ Uf and since D is a 2-functor, DUf ⊣ DUf. On the other hand, for the arrow Uf we have DUf ⊣ DUf, as noted in 5.1. Since DUf and DUf have the same right adjoint they are equal.

Lemma 6.4 is at first surprising since both D and U are defined in terms of direct image while both D and U are given by inverse image. Certainly, for a function f : X \overline{}A,

P(Pf) ≠ ∃(∃f) : PPX \overline{}PPA,

where P is the inverse-image power set functor and ∃f is direct image (the left adjoint of Pf).

6.5. Theorem. The 2-monad arising from the 2-adjunction U ⊣ D is DU.

Proof. After 6.4 we have only to check that the units and multiplications coincide. The unit η for the monad on DU is the unit for the 2-adjunction U ⊣ D. We have ηX : X \overline{}[[X, Ω], Ω] = DUX given by the familiar ‘evaluation’ formula ηX(x)(T) = T (x). In terms of subsets this translates as

ηX(x) = {T ∈ UX|x ∈ T }
= {T ∈ UX|T ⊇↑x}
= ↓↑x
= dUX(uX(x))
= (dU · u)X(x)

but dU · u = Du · d is the unit for DU.

The multiplication for the monad on DU is DϵU, where ϵ : UD \overline{}1_{ord}^{coop} is the counit for the adjunction U ⊣ D. As an arrow in ord, ϵX : X \overline{}UDX = [[X^{op}, Ω], Ω]^{op} is again given by ‘evaluation’ and arguing as we did for the units we have

[figure: U; UD; Ud; 1; D; d; u; uD; ϵ]

Now for each X in ord, DϵUX is by 5.1 the right adjoint of DϵUX. From the square above then we can write DuDU.DdU = DϵU ⊣ DϵU.

From [BEK] we know that the multiplication for DU is mn · DrU = Dn · mUU · DrU, where m is the multiplication for D and n is the multiplication for U. Now Dn·mUU ·DrU has a left adjoint given by DlU ·DdUU ·DuU. So finally, to show that the multiplications coincide we can show DuDU · DdU = DlU · DdUU · DuU. This follows from 2-naturality of u and l[d] as in the diagram below.

[figure: DDU; DUDU; DuDU; DU; DDUU; DdU; DlU; DUU; DuU; DdUU; DUdU]

6.6. Corollary. The 2-category of algebras for the double dualization with respect to Ω monad on ord is ccd.

6.7. Remark. Taking the (−)^{coop} duals of our D and U we can prove that the monad on ord arising from D^{coop} ⊣ U^{coop} is UD, whence the 2-category of algebras is ^{op}ccd.

6.8. Remark. In any topos we have an adjunction s ⊣ c : U \overline{}D, where all components of both s and c are given by complementation, giving rise to a commutative square

[figure: DD; DU; Ds; UD; UU; Us; cD; cU]

If the base topos is boolean then c and s are inverse isomorphisms and consequently Ds = (Ds)^{−1} and Us = (Us)^{−1} and we have

[figure: DD; DU; Ds; UD; UU; Us; cD; cU]

Using boolean set theory it is then easy to show that for any ordered set X, DsX ·cDX ⊆ rX ⊆ cUX · UsX. A similar result holds for l : DU \overline{}UD and it then follows that r and l are inverse isomorphisms, as mentioned in 4.2 of [RW5].

Conversely, assume only that r and l are inverse isomorphisms. Then in particular r∅ is an isomorphism. From our description of r in 5.3, it is easy to see that in any topos r∅ = ¬ : Ω^{op} \overline{}Ω. Thus in this case the base topos is boolean.

This remark extends to give another proof, quite different from the one in [RW1], that CCD = ^{op}CCD characterizes boolean toposes.

6.9. Remark. Mindful of the celebrated theorem of Paré, saying that Ω^{(−)} is monadic over the base topos, see [PAR], one might ask if [−, Ω]; ord^{op} \overline{}ord is monadic. The answer is ‘no’ and can be deduced from the results in [RW3] about those special CCD lattices of the form DX, for X an ordered set.

References

[BEK] J. Beck. Distributive laws. Springer Lecture Notes in Math 80:119–140, 1969. [F&W] B. Fawcett and R.J. Wood. Constructive complete distributivity I. Math. Proc. Cam. Phil. Soc.,

107:81–89, 1990.

[GPS] R. Gordon, A.J. Power and R. Street. Coherence for tricategories Mem. Amer. Math. Soc., Vol. 117, No. 558, 1995.

[JOH] P.T. Johnstone. Relational (co)algebras for the power-set monad. Lecture at CT99, Coimbra.

[J&T] A. Joyal and M. Tierney. An extension of the Galois theory of Grothendieck. Mem. Amer. Math. Soc., Vol. 51, No. 309, 1984.

[K&S] G.M. Kelly and R. Street. Review of the elements of 2-categories. In Lecture Notes in Math. 420, 75–103. Springer-Verlag, 1974.

[KOK] A. Kock. Monads for which structures are adjoint to units. Journal of Pure and Applied Algebra, 104:41–59, 1995.

[MO1] F. Marmolejo. Doctrines whose structure forms a fully-faithful adjoint string. Theory and Applications of Category Theory, Vol. 3, No. 2, 24–44, 1997.

[MO2] F. Marmolejo. Distributive laws for pseudomonads. Theory and Applications of Categories, Vol. 5, No. 5. 91–147. 1999.

[MO3] F. Marmolejo. Distributive laws for pseudomonads II, In progress.

[PAR] R.Paré. Colimits in topoi. Bull. Amer. Math. Soc., 80:556–561, 1974.

[P&W] M.C. Pedicchio and R.J. Wood. Groupoidal completely distributive lattices. Journal of Pure and Applied Algebra, ‘Barr volume’ to appear.

[PIS] C. Pisani. Convergence in exponentiable spaces. Theory and Applications of Categories, Vol. 5, No. 6, 148–162, 1999.

[RW1] R. Rosebrugh and R.J. Wood. Constructive complete distributivity II. Math. Proc. Cam. Phil. Soc., 110:245–249, 1991.

[RW2] R. Rosebrugh and R.J. Wood. Constructive complete distributivity III. Canad. Math. Bull., Vol.35(4):537–547, 1992.

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

[RW4] R. Rosebrugh and R.J. Wood. Distributive adjoint strings. Theory and Applications of Category Theory, Vol. 1, No. 6, 119–145, 1995.

[RW5] R. Rosebrugh and R.J. Wood. Boundedness and complete distributivity. To appear.

[STR] R. Street. The formal theory of monads. Journal of Pure and Applied Algebra, 2:149–168, 1972.

[S&W] R. Street and R.F.C. Walters. Yoneda structures on 2-categories. J. of Algebra. 50:350–379, 1978.

Instituto de Matemáticas

Area de la Investigación Científica

Circuito Exterior Ciudad Universitaria México D.F. 04510 México and Department of Mathematics and Computer Science Mount Allison University Sackville, NB, E0A 3C0 Canada and Department of Mathematics and Statistics Dalhousie University Halifax, NS, B3H 3J5 Canada

      Email: quico@matem.unam.mx and rrosebrugh@mta.ca and rjwood@mscs.dal.ca