Theory and Applications of Categories, Vol. 30, No. 9, 2015, pp. 305–331.

PARTIAL-SUP LATTICES

TOBY KENNEY

Abstract. The study of sup lattices teaches us the important distinction between the algebraic part of the structure (in this case suprema) and the coincidental part of the structure (in this case infima). While a sup lattice happens to have all infima, only the suprema are part of the algebraic structure.

Extending this idea, we look at posets that happen to have all suprema (and therefore all infima), but we will only declare some of them to be part of the algebraic structure (which we will call joins). We find that a lot of the theory of complete distributivity for sup lattices can be extended to this context. There are a lot of natural examples of completely join-distributive partial lattice complete partial orders, including for example, the lattice of all equivalence relations on a set X, and the lattice of all subgroups of a group G. In both cases we define the join operation as union. This is a partial operation, because for example, the union of subgroups of a group is not necessarily a subgroup. However, sometimes it is, and keeping track of this can help with topics such as the inclusion-exclusion principle.

Another motivation for the study of sup lattices is as a simplified model for the study of presheaf categories. The construction of downsets is a form of the Yoneda embedding, and the study of downset lattices can be a useful guide for the study of presheaf categories. In this context, partial lattices can be viewed as a simplified model for the study of sheaf categories.

1. Introduction and Preliminaries

A large number of naturally-occurring complete lattices occur as meet sublattices of other lattices. Examples include: the lattice of subalgebras of an algebra as a sublattice of the lattice of all subsets of the algebra; and the lattice of closed sets of a topological space as a sublattice of the lattice of all subsets of the space. In these examples, we have two notions of joins — one from the original larger lattice, and one derived from the new sublattice. This construction always produces a complete lattice with all suprema, because the existence of arbitrary infima implies the existence of arbitrary suprema. However, the newly created suprema may not be naturally occurring constructions, instead, they are induced by the closure operation that results from the existence of arbitrary infima.

Sometimes, however, the new suprema happen to coincide with the original joins. Often when this occurs we can say a lot more about the resulting joins — for example,

The author gratefully acknowledges financial support from the Canadian NSERC. Received by the editors 2014-10-29 and, in revised form, 2015-03-17. Transmitted by Susan Niefeld. Published on 2015-03-18. 2010 Mathematics Subject Classification: 18A25. Key words and phrases: Partial Sup Lattice, Complete Distributivity. \begin{matrix}c \\ ◯ \end{matrix} Toby Kenney, 2015. Permission to copy for private use granted.

we can apply the inclusion-exclusion principle to measure the size of the join from the sizes of the elements. It is therefore desirable to keep track of these special joins as part of the structure. For this purpose, we define a partial sup lattice as a partial order which in addition has a partial join operation, representing these special joins.

It turns out that much of the theory for sup lattices, in particular the theory relating to distributivity, applies to partial sup lattices. We can view sup lattices as a subcategory in partial sup lattices, and show how to extend much of the theory to partial sup lattices.

In Section 2, we provide a definition of what it means to be a partial sup lattice, and what the appropriate definition is for homomorphisms between partial sup lattices. Finally, we will look into the relationship between partial sup lattices and total sup lattices, showing how we can freely extend any partial sup lattice to a total sup lattice by adjoining the necessary joins.

In Section 3, we look at alternative ways in which we can describe partial sup lattices. We start by extending the totally below relation to partial sup lattices. Recall that the totally below relation (defined by [3], first called “totally below” in [1]) on a complete lattice is defined by a b if and only if for any set X with X b, we have some x X with a x. The totally below relation is crucial for our understanding of complete distributivity for sup lattices, and we see that it has the same relation to complete distributivity in partial sup lattices, with many of the results for sup lattices extending directly to partial sup lattices. In addition, the partial join structure of a given partial sup lattice is entirely determined by its totally below relation. That is, if we know the partial order on L, and its totally below relation, then we can reconstruct the partial join structure on L. Therefore, we can use the totally below relation as a means to describe a partial lattice structure. We use this to show that on a given finite lattice L, there is a largest partial lattice structure which makes L completely join-distributive. We then look at other ways to describe the partial sup lattice structure — one through a closure operation, and another in a purely algebraic way, without any reference to the partial order (in the same way that lattices can be described by just the join and meet operations, without any reference to the underlying partial order).

Another invaluable tool in the study of sup lattices is the downset construction. This has been systematically studied in the series of papers [1], [5], [6], [7], [4], for its advantages of defining complete distributivity in a constructive context without any requirement for the axiom of choice. In Section 3.20, we find the correct way to extend this downset construction to partial sup lattices, and recover most of the results of the above papers in this context.

Finally in Section 4 we look at the interplay between several different categories of partial sup lattices, with the relevant functors and adjoints.

At this point, we fix notation for the rest of the paper: For a poset X, and an element x X, we will write x to denote the principal downset generated by x, that is, the set x a X a x . Similarly, we will write x a X a x . Downsets are important for understanding sup lattices, and we will write A X to mean that A is a downset of X. We will write DX to represent the complete lattice of all downsets of X, ordered by set inclusion.

2. Basic Definition

2.1. Partial Sup Lattices. We start by defining partial sup structure on a partial order.

2.2. Definition. A pre-partial-sup partial order is a poset X with a partial operation : DX ^{}X, which is the supremum whenever it is defined, and satisfies the sandwich

condition: if A B  A then B  A.

2.3. Remark. We have defined joins only for downsets here. We will however sometimes refer to joins for general subsets of X. When we do this, we will mean the join of the downset generated by this subset.

2.4. Definition. For a pre-partial-sup partial order X, the collection JX of unioned downsets of X is the collection of downsets D of X with the property that for any x X,

if x  x D, then x  x D.

This definition may at first seem a little strange. If the underlying partial order X has all suprema, we would like JX to be the collection of downsets which have joins. As we will show below, in the case when X is a partial sup lattice, the definition above makes JX into the collection of sets for which join is defined. However, this is the right generalisation for the case where X does not have all suprema. Whenever we equip the Dedekind-MacNeille completion DX^{}of X with a partial sup lattice structure, where we will let JDX^{}be the set of downsets for which is defined in DX^{}, we can restrict this structure back to X. This restriction map from partial sup structures on DX^{}to partial sup structures on X has a right adjoint. A unioned downset of X is the intersection of a unioned downset in DX^{}with this adjoint structure, with X.

2.5. Definition. A pre-partial-sup partial order X is a partial sup partial order if the collection JX of unioned downsets of X has the following properties:

• If A is defined, then A JX.

• JX contains all principal downsets.

• JX is closed under arbitrary intersections.

• if A JX, Y x and for any a Y, there is some A A with A a, then there is some B A with B x.

If L is a partial sup poset in which every subset has a supremum, then we say L is a partial sup lattice.

2.6. Lemma. For a partial sup lattice L, JL is the set of downsets for which join is defined.

Proof. Clearly, for X JL, let x  X. We have that x  x X  X.

Therefore, join is defined for X. Conversely, if X is defined, then part of the definition gives that X JL.

2.7. Proposition. A poset L equipped with a partial operation : P L ^{}L is a partial sup lattice if and only if every subset X L has a least upper bound (denoted X) such that X X whenever it is defined and the following properties hold.

• If A B, A is defined, and B A then B is also defined (and equal to A).

• The set JL of downsets on which join is defined, satisfies the following properties:

– All principal downsets are in JL.

– JL is closed under arbitrary intersections.

– If A JL, and X  A A A JL, then there is some Y  A with

Y X.

Proof. The conditions are clearly the same conditions as for a poset. We showed in Lemma 2.6 that JL is the collection of unioned downsets as defined in Definition 2.4.

The idea is that a partial sup lattice can represent a meet-sublattice of a chosen lattice. The partial join operation represents the joins in the original larger lattice.

2.8. Examples.

• For any complete lattice L, we can form a partial sup lattice by taking all joins to be defined.

• For any complete lattice L, we can form a partial sup lattice where only joins of principal downsets are defined.

• The lattice of subgroups of a group G, with joins being unions.

• The lattice of convex sets in a metric space, with joins being unions.

2.9. Theorem. Let L be a completely distributive complete lattice, and let M be a complete meet sublattice of L. If we equip M with the partial order acquired from L, and the partial joins from L, whenever the join is in M, then M is a partial sup lattice.

Proof. We clearly have that is the supremum whenever it is defined. Furthermore, if X is a subset of Y, and X x, and Y x in M, then we have that in L, X x, and since Y contains X, we have Y X x in L, and since Y x in M, we have that x is an upper bound for Y in L, so Y x in L. Thus Y x in L, and Y x in M.

Clearly x x in L, so x x in M.

Let A be a family of downsets of M for which join is defined. That is, for any A A, A M. Now since M is a meet-sublattice of L, A A A A M (by complete distributivity of L) so the intersection does have a join.

Finally, let A be a family of subsets of M for which join is defined, and let X y, and for any x X, we have x A for some A A. By complete distributivity of L, we have x x A in L, and since M is closed under meets, we have x A is the downset generated by x A M, so x x A in M. This means

X  x A x X  x  A .

2.10. Proposition. If L is a frame, and M is a complete meet sublattice of L, then there is a partial sup lattice whose underlying poset is L, and whose joins are defined by A exists (and is equal to A) if and only if A contains all elements of M below A.

Proof. By definition, agrees with sup whenever it is defined, and the sandwich condition clearly holds. We need to show that the necessary conditions on JL hold. Obviously x contains all elements of M below x, so its join is defined. Suppose A JL, and

let A  A. Let a  A. Now let x a, and x M. For any A A, we know
x  A and x M, so by definition, we have x A. Therefore, x  A. This means

that A a.

Finally suppose A JL, X JL with X y, and for any x X, there is some A A with A x. Since L is a frame, we have x x A . Let a M with a y. Since X y, we know that a X. Therefore, there is some A A with A a. Since

a a and a M, this means that a A, so we must have a  A. Therefore, x  A
contains all elements of M below x, and has supremum x, so x  x  A as

required.

2.11. Definition. A partial sup lattice is completely join-distributive if for any collection D_{i} i I of downsets in L, such that every D_{i} is defined, we have D_{i} i I D_{i} i I

2.12. Example. A complete meet sublattice of a completely distributive complete lattice, with joins given by suprema in the larger lattice is completely join-distributive.

2.13. Homomorphisms. There are three plausible notions of homomorphisms of partial sup lattices based on the three notions of when partial functions f and g should be considered the same:

1. f and g are the same if whenever f x and g x are both defined, we have f x g x .

2. f and g are the same if whenever f x is defined, so is g x , and f x g x .

3. f and g are the same if f x is defined if and only if g x is defined, and in that case f x g x .

Based on these we get the following three notions of homomorphism:

2.14. Definition. A function f : L, , [figure]M, , is:

1. a weak homomorphism if f is order-preserving, and whenever A JL and Df A JM, we have f A Df A .

2. a homomorphism if whenever A JL we have Df A JM, and f A Df A .

3. a strict homomorphism if whenever A JL we have Df A JM, and f A Df A , and conversely, whenever Df A JM, we have A JL.

With this definition of homomorphism, the collection of partial sup lattices and homomorphisms forms a category, which we denote PartSup.

2.15. Remark. Since joins of principal downsets are always defined, the last two definitions imply that f is an order-preserving function.

2.16. Examples. The lattice of subgroups of a group has an embedding into the lattice of equivalence relations on the underlying set. This is a strict homomorphism.

For any meet homomorphism f : L [figure] M to a partial sup lattice, there is a partial sup lattice structure on L that makes this a strict homomorphism.

2.17. Example. Let X, O be a topological space. Let P X be the collection of subsets of X ordered by inclusion, where we define A A if A A and A contains all closed subsets of A. (So the totally below relation is the smallest possible totally below relation which makes closed subsets totally compact.) This is a partial sup lattice by Proposition 2.10.

For another topological space Y and a function f : X [figure] Y, we can define P f : P X [figure] P Y by P f A f a a A . P f is a partial sup homomorphism if and only if f is continuous. (This will follow easily from Proposition 2.28 in the next subsection.)

2.17.1. Monos, Epis and Factorisation. We can look at which homomorphisms of partial sup lattices are monomorphisms and epimorphisms in the category PartSup of partial sup lattices and homomorphisms.

2.18. Proposition. A partial sup lattice homomorphism f is a monomorphism if and only if it is injective (as a function).

Proof. Since composition is function composition, the if part is obvious. Conversely, let f be a monomorphism. If f x f y , then we consider the homomorphisms from the 1-element partial sup lattice that send the unique element to x and y respectively. These have the same composite with f, so they must be equal, i.e. x y, so f is injective.

2.19. Proposition. A partial sup homomorphism f : L [figure] M is an epimorphism if and only if every element of M is the join of elements in the image of f.

Proof. Clearly, if every element of M is the join of elements in the image of f, then any

two homomorphisms \xymatrix{M \ar[r]^{g} \ar[r]_{h} & N} with gf hf must agree on all elements in the image of

f. Since g and h are partial sup homomorphisms, whenever x X, if g X h X , then we must have g x h x . For any x, we can choose an X with g X h X and x X, by choosing X to be generated by a subset of the image of f, so we get g x h x , i.e. g h as required.

Conversely, suppose that f is an epimorphism. Suppose that x M is not the join of elements in the image of f. Let I be the ideal generated by elements in the image of f below x (that is, the smallest downset closed under joins that contains all elements in the image of f below x). We define homomorphisms g : M [figure] 2 and h : M [figure] 2 by g a 0 if and only if a I and h a 0 if and only if a x. Clearly gf y 0 and hf y 0 both occur if and only if f y x. Therefore, gf hf, so g h, so x I, contradicting our assumption that x is not the join of elements in the image of f. Therefore, x must be a join of elements in the image of f.

2.20. Proposition. A partial sup homomorphism f : A [figure] C is a strong epimorphism if and only if f is surjective and creates joins — that is if we have X x in C, we have Y A with f Y X and Y y for some y A.

Proof. Suppose f is surjective and creates joins. Suppose we have a commutative square

[figure: A; a; f; B; g; C; b; D]

where g is injective. We want to construct C [figure: h] B that makes both triangles commute. Clearly, h is uniquely defined because g is injective, so h x must be the unique y B with g y b x , we need to show that this exists. However, since f is surjective, there is some z A with f z x, so we have g a z b f z b x , so y a z is an element of B satisfying g y b x as required. We now need to show that h is a partial sup homomorphism. Suppose that X x in C. We want to show that h X h x in B. However, since f creates joins, we have some Y A with Y y, f Y X and f y x. Applying the above definition of h, we see that h X hf Y a Y and h x a y , so since a is a partial sup homomorphism, we have h X a Y a Y a y h x .

Conversely, suppose that f is a strong epimorphism (orthogonal to all monomorphisms). Suppose x C is not in the image of f. We can form B [figure: g] C by saying B has the same elements as C, but that x is totally compact in B (and all other joins in B are as in C) and g is the identity function on elements. The function f clearly factors through g, but g is not the identity, so the identity on C cannot factor through g. Therefore f is surjective. Suppose that f does not create the join X x, then we can form a new partial sup lattice with the same elements as C, but with this join excluded. f will factor through this new partial sup structure, but this is not an isomorphism.

2.21. Theorem. Any partial sup homomorphism f : L [figure] M factors as a strong epimorphism followed by a monomorphism.

Proof. We form the factorisation N as the subposet of M consisting of elements in the image of f, with joins exactly the joins created by f. It is now clear that this factorisation consists of a strong epimorphism followed by a monomorphism.

2.22. Theorem. The collection of completely join-distributive partial sup lattices is closed under inf-preserving subobjects and inf-preserving strong epimorphic images

Proof. Let L [figure: f] M be an inf-preserving partial sup monomorphism, and let M be completely join-distributive. Let X be a family of downsets in L such that for each X X, X is defined. Since f is a partial sup homomorphism, we have that f X is also defined, and is equal to f X . Since the collection of downsets whose join is defined

is closed under intersection, we have that  X is defined. Let x  X. We want
to show that x  _{X X} X. Let y  _{X X} X. Since f is injective, we just need

to show that f x f y . However, since f is inf-preserving, we have that f y X X f X . Since M is completely join-distributive, this gives _{X X} f X X X f X . Clearly, since f is injective, _{X X} f X f X , so since f preserves joins, we have _{X X} f X f X f x . Therefore, since f is injective, we have x y as required. Therefore, L is completely join-distributive.

Now let L [figure: f] M be an inf-preserving strong epimorphic partial sup homomorphism, and let L be completely join-distributive. Let X be a family of downsets in M such that for each X X, X is defined. Since f is strongly epimorphic, it creates each of these joins. That is, we have a family Y_{X} X X , of downsets in L with f Y_{X} X and f Y_{X} X. Since L is completely join-distributive, we have _{X X} Y_{X} X X Y_{X}. Applying f to both sides gives

_{X X} X  f _{X X} Y_{X}  _{X X} f Y_{X}  _{X X} X

so M is completely join-distributive.

2.23. Ideals and Total sup lattices. There is clearly a full subcategory of PartSup, consisting of total sup lattices, where all joins are defined. It is clear that this is isomorphic to the category Sup of sup lattices, since a partial sup lattice homomorphism between sup lattices must preserve all joins that are defined, which in this case means all suprema. We will show:

2.24. Theorem. The subcategory of total sup lattices is reflective in the category of partial sup lattices.

To show this, we will need the concept of an ideal for a partial sup lattice.

2.25. Definition. Let L be a partial sup lattice. An ideal in L is a downset of L, closed under .

2.26. Lemma. For a partial sup lattice L, the set IL of ideals in L is a complete lattice (as an order) under set inclusion.

Proof. Let I be a set of ideals in L. We want to show that I is an ideal. It is clearly a downset. Furthermore, for any X I, for any I I, we have X I, so since I is an ideal, we have X I. Since this holds for all I I, this gives X I. Therefore, I is closed under , so it is an ideal.

2.27. Lemma. For any element x L, the principal downset x of all elements below x,

is an ideal. Furthermore, the inclusion L [figure: ]IL sending every element to the principal downset it generates is a partial lattice homomorphism

Proof. It is easy to check that x is an ideal. Suppose we have X x in L. Then we want to show that x is the ideal generated by _{y X} y . We know that X _{y X} y , so the ideal generated by this set must contain X x. It must therefore contain x , and since x is an upper bound for _{y X} y , x must be the ideal generated by _{y X} y . Therefore is a partial sup lattice homomorphism.

Proof of Theorem. We have shown that the set IL of ideals in L is a complete lattice. We need to show that for any total lattice M, morphisms from L to M correspond to morphisms from IL to M.

Given a partial sup lattice homomorphism L [figure: f] M, where M is a total sup lattice, we want to show that f factors uniquely through . Uniqueness is obvious, since any

I IL must satisfy I _{x I} x . Therefore, we are forced to define IL [figure: f̂] M by f̂ I _{x I} f x . It just remains to check that this is a sup homomorphism. Suppose I I in IL. We need to show that f̂ I _{J I} f̂ J . Since f̂ is obviously orderpreserving, we just need to show f̂ I _{J I} f̂ J . That is _{x I} f x _{J I} _{x J} f x . We can rewrite the right-hand side as _{x I} f x . Furthermore, we know that I is the

ideal generated by I, so for any x I, there is some X  I with x  X. Since f is
a partial sup homomorphism, we have that f x  _{y X} f y  _{y I} f y . Therefore,
we get f̂ I  _{x I} f x  _{y I} f y as required.

2.28. Proposition. A function L [figure: f] M between partial sup lattices, is a homomorphism if and only if its inverse image preserves ideals.

Proof. If f is a partial sup homomorphism and I is an ideal in M, then let X f^{1} I . We want to show that X f^{1} I if it is defined. If X is defined, then since f is a partial sup homomorphism, we must have Df X f X , and Df x I, so since I is an ideal, f X I. Therefore, X f^{1} I , so f^{1} I is an ideal.

Conversely, suppose that f^{1} preserves ideals. We first need to show that f is order preserving. However, principal downsets are ideals, so f^{1} f x is an ideal, and in particular a downset. Therefore, if a x, then a f^{1} f x , since x f^{1} f x . This means f a f x , i.e. f a f x , so f is order-preserving. Now suppose X is defined for some downset X L. We want to show that f X Df X . Certainly f X is an upper bound for Df X . Also for any ideal I containing Df X , we must have f X I, since otherwise f^{1} I would be an ideal in L containing X but not X, which cannot happen. Therefore, f X is the smallest ideal containing Df X , so f X Df X as required.

We see easily that PartSup has products, given by L M is the product of L and M as posets, with a_{i}, b_{i} i I a_{i} i I , b_{i} i I , i.e., the join is defined whenever the joins of both projections are defined. However, there is an interesting tensor product, L M, given by also taking the poset L M, but only defining joins for rectangular families — that is, families of the form A B, where A and B both exist (and any other joins required to satisfy the sandwich condition). It is easy to see that this is a partial sup lattice.

This clearly has the following “universal property”: partial sup lattice homomorphisms from L M to N are functions which preserve all joins of the form A y and x B. When L and M are sup lattices, these are bi-sup homomorphisms, so we see that I L M is the tensor product of sup lattices.

Furthermore, we can extend this:

2.29. Theorem. I is a monoidal functor from PartSup with this tensor product to Sup with the usual tensor product of sup lattices.

Proof. We need to show that for any X, Y PartSup, we have an isomorphism I X Y [figure: ]IX IY. This isomorphism is given by the homomorphism I X Y [figure: R] IX IY given by R J A, B IX IY A B J . (Here we interpret elements of the tensor product in Sup as downsets of the product where every rectangle is contained in a principal rectangle, as in [2].) We need to show that this actually defines a homomorphism. Since joins are unions in this context, it is easy to see that they are preserved. On the other hand, we need to show that R defines a function at all. That is, we need to show that R J has the property that any rectangle in R J D IX IY is contained in a principal rectangle. Let A B be a rectangle in R J . We want to show that the element A, B is also in R J , i.e. that A B is a subset of J. Let x, y A B. Then we have x A A and y B B. Therefore, we have x, y A B J, so x, y J. Since x, y was arbitrary, this gives that A B is a subset of J as required.

The inverse to this homomorphism is the homomorphism U : IX IY [figure] I X Y given by U W A B A, B W . Since joins are unions, it is clear that U is a homomorphism. We want to show that U is a function, that is that any U W is an ideal in X Y. Suppose we have Z U W , and Z x. By definition of X Y, we have that Z A B, A a, B b, and x a, b . We want to show that x U W . For any y A and z B, we have y, z U W , so there is some A_{yz}, B_{yz} W with y, z A_{yz} B_{yz}. We now consider A_{y} _{z B} A_{yz}. This is an intersection of ideals, so is an ideal itself. On the other hand, we know that for any z B, we have A_{y}, B_{yz} A_{yz}, B_{yz} W, so we have the rectangle A_{y} B_{yz} z B in W. Since W is in the tensor product, this rectangle is contained in a principal rectangle. That is, there is some { \atop B_{y}} such that _{z B} B_{yz} { \atop B_{y}}, and A_{y}, { \atop B_{y}} W. Since W is a downset and B { \atop B_{y}}, { \atop B_{y}} must contain the ideal B, generated by B in Y. We therefore have A_{y}, B W for every y Y. This means the rectangle A_{y} y Y B W, so this rectangle is contained in a principal rectangle, which must contain A, B . Since A and B are ideals containing A and B respectively, they must contain A a and B b respectively. Since we have A, B W, we have x a, b A B U W . Therefore, U W is indeed an ideal.

Finally, we need to show that U and R are inverse to one-another. We easily have UR J J and RU W W. Conversely, let x a, b J. Then a b J, and so a , b R J , so a, b a b UR J .

Now let A, B RU W . We have that A B U W . This means that A B P Q P, Q W . Let a A. Consider the set Q IY a , Q W . Since a B U W , we see that B Q IY a , Q W , so since rectangles in W are all contained in principal rectangles, we see that a , Q IY a , Q W W, and therefore, a , B W. Since this holds for any a A, we have that a , B a A W. This is a rectangle, so it is contained in a principal rectangle in W, which must contain A, B . Therefore, A, B W, so RU W W.

2.30. Theorem. L is completely join-distributive if and only if IL is completely distributive.

We will prove this in Section 3.1.

3. Alternative Ways to Describe Partial Sup Lattices

3.1. The totally below relation. For sup lattices, a very useful relation is the totally below relation , defined by a b if whenever X b, we have a x for some x X. This definition lifts directly to our partially defined join case:

3.2. Definition. For a partial sup lattice L, we say a b if for any downset X L with b X, we have a X. We denote the set a L a b by b .

3.3. Lemma.

(i)

(ii) is an order-ideal — that is, whenever a b c, then a c, and whenever a b c, we have a c.

(iii) If every x L satisfies x x , then is idempotent.

(iv) (Assuming AC) If some x L satisfies x x , then for any a x, there is some b L with a b x.

Proof. (i) Let a x. We know that x x, so we must have a x , so a x.

(ii) Suppose a b c. Then if C c, then C b, so a C. Therefore we have a c. Suppose instead that a b c. Now if C c, we have b C. Since a b, we have a C. Therefore a c.

(iii) Recall [7] that a relation is idempotent if and only if it is both transitive and interpolative, where is called interpolative if and only if whenever a b, there is some c such that a c b.

Transitivity obviously holds from (i) and (ii), so we just need to show interpolation. Consider a a b . We have that a a , so by the third condition for the joins that must exist, we get that a a b exists, and is equal to b. Thus, for any x b, we have x a a b , so x a b, and therefore x a b.

(iv) Let a x. Since x x , suppose for every b x, we have a b. Then we have some downset X_{b} with a X_{b} and X_{b} b. Now there is some B _{b x} X_{b} with B x, but a _{b x} X_{b}, so a B, contradicting a x.

Recall [3] that a complete lattice is completely distributive if and only if every element is the join of the elements totally below it. We can extend this condition to the partial lattice case:

3.4. Theorem. A partial sup lattice, L is completely join-distributive if and only if for every x L we have x x .

Proof. Suppose that we have for every x L, x x , and suppose we have a family D_{i} i I of downsets, such that every D_{i} exists. Let x D_{i} i I . We want to

show that x  D_{i}. This will be the case if x  D_{i}. However, let a x, then we
also have a  D_{i} for every i. Therefore, for every i we have a D_{i}, so a  D_{i} i I

as required.

Conversely, suppose that L is completely join-distributive, and let x L. Consider the set P_{x} A DL A x . By definition, we have that x A A P_{x} (P_{x} contains x so there are joins that equal x exactly) so by complete distributivity,

x  P_{x}. Now, P_{x}  x , so we have shown x  x .

3.5. Theorem. For a partial sup lattice, L, the following are equivalent:

(i) L is completely join-distributive.

(ii) is interpolative (the definition of this was recalled in the proof of Lemma 3.3) and is an injective function L [figure] DL.

(iii) is interpolative, and is an order-reflecting function L [figure] DL.

(iv) For every x L, we have x x .

(v) For every x L, we have x x Proof. We have already shown the equivalence of (i) and (v). It is clear that (v) implies (iv). For the converse, note that x A DL A x is an intersection of downsets whose join is defined, so its join is defined.

We have shown that (v) implies that is interpolative, and since we have x x , if z x , then we have z z x x. It is obvious that (iii) implies (ii).

To show (ii) implies (iii), suppose that x z . Now let y x z. If a x, then a z, and by interpolation, we have some b such that a b x. Since x z , we have b z. Therefore, b y. Thus we have a b y, so a y. Since y x, this gives x y , so by injectivity, x y and x z.

If (iii) holds, then for any x L, let x z , so z is an upper bound for x . We need to show that x z. However, this will follow from (iii) if we have x z . Let a x. Then we have a y x for some y L. Therefore, a y z, so since is an order ideal, this gives that a z as required.

Proof of Theorem 2.30. If IL is completely distributive, then since the inclusion L [figure] IL preserves infima and all joins that exist, L must also be completely joindistributive.

Now suppose that L is completely join-distributive. The totally below relation on IL is given by X Y if and only if X x for some x in the intersection of all sets whose join-closure contains Y. This can only happen if we have x y for some y Y. We want to show that Y is the join of all ideals totally below it. For any x Y, we have that x x , so x a a x , and for a x, we have a Y. Therefore, the join of all ideals totally below Y contains x. Since this holds for all x Y, we have that this join is equal to Y. Therefore any Y IL is the join of ideals totally below it, i.e. IL is completely distributive.

3.5.1. Different partial sup structures on a fixed sup lattice. When we consider a fixed complete partial order, there are many possible partial sup lattice structures on it, and they can be ordered by inclusion of the sets for which join is defined. On the other hand, we have the set of possible totally below relations on it, ordered by inclusion. We will denote the poset of partial lattice structures on L by PartLat L and the poset of totally below relations (that is, order ideals contained in and containing the totally below relation for the total sup lattice, that occur as the totally below relation for some partial sup lattice structure on L) TBelow L . We will characterise these relations in Theorem 3.8. In the following discussion, we will consider both these possible totally below relations on L, and the totally below relation from the total sup lattice structure on L. To minimise confusion, in the rest of this section (up to Subsection 3.12), we will refer to these possible totally below relations as “entirely below”, and denote them by . We will also denote the set of elements entirely below x as x .

Given a partial sup lattice structure on L, we can define the entirely below relation by a b if for any X DL with b X, we have a X. Given an entirely below relation on L, we can define a partial sup lattice structure on L by defining X X whenever X X. These constructions are order-reversing. Furthermore, they are inverses.

3.6. Theorem. The functions PartLat L [figure: t] TBelow L defined by a t b if and only if for any X with b X, we have a x X, and TBelow L [figure: c] PartLat L defined by X J_{c} X if and only if X contains X , are inverse, in that the composite ct is the identity function. (We defined TBelow L as the image of c, so we must also have tc is the identity.)

Proof. Let  PartLat L . Let t , and let  ct . Suppose x  X.

Then x X, so X x. Conversely, suppose X x. Then we have x X and X x. Suppose a x but a X, so a x. Then we have x a x since there is some Y with a Y and Y y x, so by the sandwich condition

Y  x  a  y, and therefore x  a Y  x  a  x JL. Let
X_{a}  x  a for each a  x . Now X  _{a x X} X_{a}. Since we have X_{a} x for

all a x X, and sets with defined join are closed under intersection, this gives that X x as required.

We have shown that there is a duality between partial sup lattice structures on L and entirely below relations on L, but we have not yet identified which relations are valid entirely below relations on L. We will now give a characterisation.

3.7. Lemma. For a partial sup lattice L, a downset I is an ideal if and only if, for any x L with x I and x I x, we have x I.

Proof. Suppose that for any x L with x I and x I x, we have x I. Now suppose x A for some A I. By definition, we have x A, so x x I, and we have x A I, so x I. This means I is an ideal.

Conversely, suppose I is an ideal, and x x I, and x I. Then certainly, x I is a downset whose supremum is x and which contains x . It must therefore have join x, so x I.

For a relation , which is contained in , contains on the underlying lattice, and is an order ideal, we can define the associated ideals by a downset I is an ideal if and only if any x L with x I and x x I satisfies x I.

3.8. Theorem. A relation on a sup lattice L (with partial order and totally below relation ) is the entirely below relation for a partial sup lattice structure if and only if it satisfies the following conditions:

• a b implies a b.

• is an order ideal.

• For a b, let U_{a,b} x b x  x  a . We have a b if and only if for

any x U_{a,b}, we have a x.

• For any downset A, if y is in every ideal that contains A, then there is some z y with z A and z z A.

Proof. Let satisfy the above conditions. We will show that c is a partial sup lattice structure on L, and that tc .

First we want to show that tc . Clearly, if a b, then we have whenever X b in c , we must have that b X, so in particular, a X. Therefore a b.

Conversely, suppose a b in tc . For any c U_{a,b}, by definition, c  c  a .
Now, if c  c  a , then c  c  a . This would be a family that does not

contain a, whose join is greater than or equal to b, contradicting a b. Therefore, we cannot have c c a , so since c c , we must have some x c a . Since is an order ideal, this gives a c. Since this holds for all c U_{a,b}, we have a b.

Next, we show that c is a partial sup lattice. The sandwich condition is clear. Since is contained in , all principal downsets have joins. Let X JL. Let A X. Now suppose a A. Then we have a X for all X X, so we have a X, and therefore a A. Therefore A contains A , so A is defined. Now suppose that X y, and that for all x X, we have some A A with A x. Now if I is an ideal containing A, then for any A A, we have A I. Since I is a downset, we have X I, so y I. Therefore, y is in every ideal that contains A, so there is some z y with z A and z z A . This means that z z A , so c is a partial sup lattice.

Conversely, to show that these conditions hold for the entirely below relation on a partial lattice, let be the entirely below relation on a partial lattice L, and let be the totally below relation on the corresponding total sup lattice. We have proven the first two in Lemma 3.3.

If we have a c for every c U_{a,b}, we want to show that a b. Suppose we have X b. This means that X b, so either a X, or c X U_{a,b}. Since c U_{a,b}, this means a c, so a X. Therefore, we have that a b. Conversely, since is an order ideal, if a b, then we must have a c for every c U_{a,b}.

Finally, for a partial sup lattice, ideal completion is idempotent, so the last condition clearly holds.

3.9. Remark. The condition regarding U_{a,b} ensures that the totally below relation on the underlying sup lattice L is contained in all valid entirely below relations, since if a b in the sup lattice L, then U_{a,b} is empty, so the condition implies a b.

Given that the entirely below relation can be used to describe partial lattice structures on a given underlying lattice, we can use this to describe certain partial lattice structures.

3.10. Lemma. Let be an order ideal contained in , with the property that for any downset A, if y is in every ideal that contains A, then there is some z y with z A and z z A. The structure c is a partial lattice structure, and is the largest partial lattice structure whose entirely below relation contains .

Proof. By definition, X X whenever it is defined. The sandwich condition is obvious, and since is contained in , it is clear that principal downsets are unioned. Suppose A is a collection of unioned downsets. Let x A, and suppose a x. Now

for any A A, we have a x  A, so a  A. Since A is a unioned downset, this
means a A. Therefore, we have a  A, so  A  A, and therefore A is a

unioned downset. Finally, suppose A is a collection of unioned downsets, X is a unioned downset, and for any x X, there is some A A with A x. We need to find some y X, so that y y A and y y A . This will follow if X is in every ideal that contains A. Let I be an ideal containing A. By definition, we know that for any A A, we have A I. Since I is a downset, this gives X I, so X I as required.

Finally, it is clear that this is the largest partial sup structure for which is contained in the entirely below relation, since if a b, then for any X with X x b in c , we have a b x X, so a b in c . On the other hand, if is another partial sup lattice structure on L, such that is contained in the entirely below relation, and X x, then for any a x, we certainly have a x, so a X. This means that x X and X x, so X x in c . Therefore, as required.

3.11. Proposition. For a finite lattice L, there is a largest partial lattice structure which makes L completely join-distributive.

Proof. A largest total lattice structure corresponds to a smallest entirely below relation. For a finite lattice, this entirely below relation is generated by the entirely compact elements (elements that are entirely below themselves). We are looking for the smallest set of such elements, such that L is completely join-distributive, i.e. every element is the join of the elements entirely below it. We certainly need an element which is not the supremum of the elements strictly less than it to be entirely compact. If we define x to be entirely compact if and only if it is sup indecomposable, then we need to show that this defines a completely join-distributive partial lattice.

Clearly, for a finite lattice, any element is the sup of all sup irreducible elements below it. Therefore, each element is the join of all elements entirely below it, so L is completely join-distributive with this partial lattice structure.

Clearly, any other partial lattice structure for which L is completely join-distributive must set all join irreducible elements to be entirely compact, so this is the smallest entirely below relation that makes L completely join-distributive.

3.12. Totally Below on Upsets. The totally below relation is defined on elements of L. However, the definition naturally extends to upsets on L.

3.13. Definition. For upsets U and V of L, we say U V (U is totally below V) if for any downset X with X V, we have x X U.

It is easy to see that when we restrict this to principal upsets, we get the usual definition of totally below on L.

3.14. Lemma. For a lattice, this is the totally below relation on the collection of upsets ordered by reverse inclusion.

Proof. Suppose U is totally below V in this order. We will show that U is totally below V in the collection of upsets. Suppose that U V. We want to show that some A U is a subset of U. Suppose not. Then for any A U, we can find some x_{A} A U. Now consider _{A U} x_{A} . Clearly, this is a subset of _{A U} A V. Therefore, _{A U} x_{A} V, but x_{A} A U has empty intersection with U, contradicting U V. Therefore, we have shown that U is totally below V in the reverse inclusion order on upsets.

Conversely, suppose that U is totally below V in the reverse inclusion order. Suppose A V. We want to show that A U . However, we have _{a A} a V, so we have some a A with a U, i.e. a U, so U V.

3.15. Proposition. A downset I is an ideal in L if and only if its complement is a totally compact upset on L.

Proof. Let I be an ideal, and let I^{c} be its complement. We want to show I^{c} I^{c}, that is if A I^{c}, then A I, but the definition of ideal states that if A I, then A I, so this is obvious.

Suppose conversely, that I^{c} is totally compact. Then if A I, and A is defined, then since A I^{c} , we must have A I^{c}, so A I. Therefore, I is an ideal.

3.16. The Join-Closure Operation. Another way to represent a partial lattice is by

the function DL [figure: ]DL which sends a downset to the downset generated by the set of joins of subsets of it. That is

D  x L ;  ; E D x  E

It is easy to calculate from this function by X x whenever X x . We translate the conditions for a partial lattice into conditions about this function. Firstly, we are given that is generated by a partial function : DL ^{}L. This means that whenever x A , we must have x B for some B A. We can rephrase this as the diagram

[figure: JL; ; DL; ^{}; ; DL; DL; ]

is a Kan extension, where JL is the equaliser of and .

Another way to express the condition that is generated by a partial join operation is that the diagram:

\xymatrix{DDL \ar[r]^{JL} & DJL \ar[r]^{D} & DDL \ar[d]^{} \\ DL \ar[u]^{} \ar[rr]|{} &  & DL}

commutes.

Next we have the condition that agrees with whenever it is defined. We can begin to express this condition with the assertion . The fact that all principal downsets have joins is given by 1 . Finally, to see the assertion that JL is closed under intersections, we define JL as the inverter (or equivalently the equaliser) of in the category of partial functions between posets. Then the condition that JL is closed under intersection means that the inclusion has a right adjoint. We can also define IL to be the inverter of 1 , that is the set of downsets which are closed under joins. We then have the diagram:

[figure: L; JL; ; IL; ; ; DL; ; ; ; ; _{}; ; 1; ; DL]

3.17. Theorem. is idempotent.

Proof. It is clear that A A , so we just need to show the converse inclusion.

Suppose x  A , then by definition, x  B for some B  A, and for each
b B, we have b  A, so b b̂  A_{b} for some A_{b} A. Now by Condition (iii)

from the definition of a partial sup lattice, we let A A_{b} b B JL, and we have B A_{b} A_{b} A JL, so we have that there is some Y _{b B} A_{b} JL, such that the join of Y is greater than or equal to x. Therefore, x A .

This means that join-closure sends every downset to an ideal. It can therefore also be viewed as a kind of ideal completion.

3.18. Theorem. An endofunction DL [figure: ]DL is the join-closure operation for a partial sup lattice structure on L if and only if

• is order-preserving.

• is inflationary.

• is idempotent.

• is contained in sup-closure (the principal downset generated by the supremum).

• preserves principal downsets.

• The equaliser JL [figure] DL of and has a left adjoint.

• The diagram

[figure: JL; ; DL; ^{}; ; DL; DL; ]

is a Kan extension.

Proof. We have already shown that the join-closure operation satisfies all these properties. Conversely, suppose that is an endofunction of DL satisfying all these properties. We want to construct a partial lattice structure on L for which it is the joinclosure operation. We do this by defining X x if and only if X x . It is clear that this agrees with the supremum whenever it is defined, since if X x then X x , so x is an upper bound for x, and if y is another upper bound, then X y , so x X y y , so x y. The sandwich condition follows because is order-preserving. We already have that join is defined for principal downsets. We need to show that is the join-closure operation for this . That is x A if and only if there is some x^{}x and A^{}A with A^{}x^{}. Let Â x L x^{}L, A^{}A x x^{}, A^{}x^{}. The function f A Â clearly satisfies f A A for all A JL, so by the Kan extension, we have that f, i.e. if x A, then x Â, so x x^{}for x^{}A^{}for some A^{}A.

The equaliser of and is the set of downsets whose join-closure is a principal downset. If this equaliser has a left adjoint, then it preserves infima, which are intersections, so the collection of downsets for which join is defined is closed under arbitrary intersections. Now suppose we have X y and some family A such that for any x X there is an A A with A x. We need to show that there is some B A with B x. We know that X A, so x A A. This means x B for some B A.

3.19. Proposition. L is a partial frame (binary infima distribute over joins, i.e. a X a x x X ) if and only if : DL [figure] IL is a fibration in the sense that for any ideal I A, there is some downset B A such that B I.

Proof. First suppose L is a partial frame. Then for I  A, we will show I  I A .

Since I A I and I is an ideal, we have that I A I. On the other hand, for

x I, we have x  A, so x  B for some B A. Since L is a partial frame, we have
x B  x b b B x B x, so x  A I , since x B A I.

Therefore I A I .

Conversely, suppose : DL [figure] IL is a fibration. In particular, this means that

whenever x  A, we have x  A, so we must have x  B for some B A.
Since B  x , this means B  x , so x  C for some C B, and so by the

sandwich condition, x B. Also, we have B A x , so by the sandwich condition,

x  A x . We therefore have that x  x a a A , so L is a partial frame.

3.20. The Partial Lattice of Unioned Downsets. One of the most useful tools for the study of sup lattices is the downset construction DX. This downset construction does not retain the partial sublattice structure, so is not so useful in this context. Instead, the object that plays the role of the downset in the theory of partial sup lattices is the partial sup lattice of unioned downsets, which is the partial order JX defined in Definition 2.4.

We can equip JX with a partial sup lattice structure, with order given by inclusion of sets, and joins given by unions, whenever they yield a set in JX. It is clear that JX is a partial sup lattice because it is a meet-closed subset of the completely distributive sup lattice DX.

3.21. Proposition. For a partial-sup partial order X, there is a poset morphism

X [figure: ]JX, sending x to its principal downset. This morphism has a left adjoint if and only if X is a partial sup lattice.

Proof. We know that is a poset morphism from X to JX. If X is a partial sup lattice, then any unioned downset in D JX has a supremum x, which is therefore also the join of D. Sending D to this join is clearly left adjoint to the downset construction.

Conversely, suppose JX [figure: f] X is left adjoint to . This means that D f D , so f D must be an upper bound for D, and if x is any other upper bound for D, then D x , so by the adjunction f D x. This means that f D is a least upper bound for D. Therefore, any D JX has a supremum (which must therefore be its join), and f must be the function sending a unioned downset to its join. This does not yet prove that X is a partial sup lattice, since that requires the existence of all suprema and infima, not just those for elements of JX. We will show that X has infima. Let A X. We know that a a A JX, so a a A JX. Therefore, a a A has a supremum x. Any lower bound for A is in a a A , so is less than x, which is therefore the supremum of the lower bounds for A, and therefore, and infimum for A. Since A was arbitrary, this shows that the underlying poset of X is a lattice, so X is a partial sup lattice.

3.22. Proposition. For a partial sup lattice L, the totally below relation defines an

order-preserving function L [figure: ]JL.

Proof. We first need to show that for any x L we have x JL, but by definition, we have x X JL x X is an intersection of elements of JL, so it is in JL. The function is order-preserving because is an order ideal.

3.23. Theorem. L is completely join-distributive if and only if is left adjoint to .

Proof. The counit of the adjunction clearly always holds by definition, since X is the intersection of a family that contains X, and so must be smaller than X. The unit of the adjunction is the assertion that for all x L, we have x x (technically, we have shown x x , but the reverse inclusion is obvious) which is equivalent to complete distributivity from Theorem 3.5.

Recall [7] that a lattice is completely distributive if and only if it is the lattice of downsets for an idempotent antisymmetric relation. We can extend this to deal with partial sup lattices. We need to recall [7], the definition of a downset for an idempotent relation.

3.24. Definition. For an idempotent relation on a set X a set D X is a downset if we have x D if and only if there is some y D with x y.

We start by defining a partial sup idempotent relation.

3.25. Definition. For an idempotent relation on a set X, we say that z is a supremum for a downset A if:

• a A, a z

• for any x X, such that a A, a x, we have for any y z, also y x.

3.26. Definition. For a set X with an idempotent relation and a partial function : DX ^{}X, a downset D X is a unioned downset if for any x X, if x is a supremum of a subset A D, then there is some B D with B x.

3.27. Definition. A partial sup idempotent relation is a set X equipped with an idem-

potent antisymmetric relation , and a partial function DX ^{^{}}X which sends every downset A of X to a supremum for A whenever A is defined, and satisfies the sandwich condition. Furthermore, the set JX of unioned downsets of X satisfies the following properties:

• All principal downsets are in JX

• JX is closed under infima of downsets (for idempotent relations, these infima are not necessarily intersections).

• if A JX, and X JX, with for all x X, we have some A A with x A,

then there is some B  A with x  B.

3.28. Lemma. For a completely join-distributive partial sup lattice L, if A x then b a A b a x.

Proof. We have that for any a A, a a , so there is some subset of _{a A} a whose join is at least x. Since x is clearly an upper bound for _{a A} a , the sandwich condition implies that _{a A} a x.

3.29. Proposition. If L, , is a completely join-distributive partial lattice, then L, , is a partial sup idempotent relation (where the join here is restricted to downsets for the totally below relation).

Proof. From Theorem 3.5, Condition (iii), we know that is idempotent, and that A is a supremum for A whenever it is defined. We therefore just need to show that the conditions on JL hold.

By Theorem 3.5, Condition (v), we have that is defined for all principal downsets. Let A JL, be a collection of downsets for which is defined. The infimum A is given by a a b for some b A . We want to show that this also has a join. We know that in L, A has a join x. We want to show that x is also the join of A. Since L is completely join-distributive, we have x x , so we just need to show that

x  A, or for any a x, there is some b  A with a b. Since is idempotent,
we have some b with a b x, and since  A x, we must have b  A, since A is
a downset for . This gives that a b  A, so a  A as required.

Finally, suppose A JL, and X y, and x X A A x A , then in the the partial sup lattice L, there is B A with B y. We then have a b b B B y, by complete distributivity. This is a unioned downset in the partial sup idempotent.

3.30. Theorem. A partial sup lattice L, , is completely join-distributive if and only if it is of the form D X, , for some partial sup interpolative relation X, , .

Proof. First let X, , be a partial sup idempotent relation. We want to show that D X, , is a completely join-distributive partial sup lattice.

First we consider the partial order on . For an idempotent relation , we have an operation on subsets of X, given by A x X x a for some a A . Given a collection A JX of unioned downsets for , we know that their infimum as downsets is also unioned, so the partial order JX has arbitrary infima (and therefore arbitrary suprema). We therefore just need to show that the partial join operation on JX satisfies the required properties. This join is the union of sets whenever it is defined, so it must also be the supremum in JX. Suppose for a downset A JX we have another downset B A with B X and for every A A, A X, then since the join is union, we have that A X also. Finally, let V be the collection JDX of unioned downsets in D X, , . That is, the collection of downsets of unioned downsets in X whose union is also a unioned downset. It is obvious that V contains all principal downsets.

Let \underline{A} V. We want to show that \underline{A} V. That is, we want to show that

\underline{A} JX. We first show that  \underline{A}  A A \underline{A} . Let X  \underline{A}. This
means X A for all A \underline{A}. This means X  A for all A \underline{A}, so X  A A \underline{A} ,

and since X is a downset, this means X A A \underline{A} . The reverse inclusion is obvious, so we have shown \underline{A} A A \underline{A} , and since JX is closed under infima, this gives that \underline{A} JX as required.

Finally, we need to show that if \underline{A} V, and X V and for all Y X, there is

some B \underline{A} with B Y, then there is some C  \underline{A} such that C  X. This
holds because we can take C  x x  X . For any x X X, there is some

B \underline{A} with B X, so x B, so there is some B B with x B. Now we have

x B B  \underline{A}, and since \underline{A} is a downset, we have x  \underline{A}. We have
therefore shown that for x  X, we have some y  X with x y. Now y C by
definition, so x  C, so C  X as required.

Now, we have shown that D X, , is a partial sup lattice. It just remains to show that it is completely join-distributive. Let A be a unioned downset of X. We want to show that A is the union of the unioned downsets of X that are totally below A. The totally below relation on unioned downsets of X is given by A B if and only if A x for x B. Therefore, since A _{x A} x , we have that A is the union of all sets totally below it, so D X, , is completely join-distributive.

Conversely, suppose L, , is a completely join-distributive partial lattice. We know that L, , is a partial sup idempotent relation. Furthermore, let D be a unioned downset for this relation. We will show that D is a principal downset for L, . By definition, D has a join x. This is a join in L. We therefore have that x D. Since D is a downset for , we have for any a D, there is some b D with a b. Since x D, we must have b x, and therefore a x. Thus we have shown D x, so D x is a principal downset. Conversely, all principal downsets are unioned, and since L is completely join-distributive, by Theorem 3.5(ii), principal downsets for different elements of L are distinct, so unioned downsets are in bijection with elements of L. Furthermore, by Theorem 3.5(iii), the inclusion partial order on these unioned downsets is the same as the original partial order on L, so as a poset this is the original poset we started with. We now just need to confirm that the joins agree with the joins of L.

Let U be a downset of L with join x. We need to show that _{a U} a x. Clearly, if y a U, then since x is an upper bound for U, we have y x, so _{a U} a x. Since L is completely join-distributive, we know that for any a U, a a , so a a U is a subset of JL, the joins of whose elements form a set in JL, so the union must also be in JL. That is _{a U} a x. Therefore, by definition, x _{a U} a, so _{a U} a x.

Conversely, suppose that _{a A} a JL. Let x _{a A} a . Since for each a A, we have a a , this gives a x. Therefore, x is an upper bound for A, and the downset generated by A contains _{a A} a , so A must have join x as required.

3.31. Example. Let X be a partial order. We can define the Dedekind-MacNeille completion of X by taking joins only for principal downsets. The unioned downsets for the resulting partial-sup partial order form the Dedekind-MacNeille completion of X (with joins only defined for principal downsets).

3.32. Algebraic Definition. We know that the supremum operation is sufficient to define a sup lattice — the underlying partial order can be deduced from it. We show here that the same is true for a partial sup lattice — the partial order (and therefore also the supremum) can be recovered from just the partial sup.

3.33. Definition. A partial sup lattice is a set L with a partial operation P L ^{^{}}L satisfying:

• For any x L, there is a largest X P L, such that X x. This largest such X is closed under .

• If X x, and we have A P L such that for every y X, we have a set X_{y} P L with y X_{y} and X_{y} A for some A A, then there is some B A and Y P L with x Y and B Y.

• The collection of sets A satisfying A x for some x L is convex in the sense that if A B C and A C x, then B x.

• The collection of subsets for which is defined is closed under intersection.

We want to show that this corresponds to our usual definition. First we construct the relation by x y if and only if there is some A P L such that x A and A y.

3.34. Lemma. This is a partial order.

Proof. We need to show that it is reflexive, transitive and antisymmetric. We define x to be the largest X P L such that X x.

For reflexivity, we have that X is closed under , so in particular, it contains x. Therefore, x x.

For transitivity, suppose x y z. By definition, we have some Z P L with y Z and Z z, and we have some Y P L with x Y and Y y. In particular, x y . Now we know that _{y^{}Z} y^{}z, and this union contains x, so x z.

Finally, for antisymmetry, suppose x y and y x. We have x y , y x , and x _{z x} z . Clearly, _{z x} z contains y , and since x is the largest

subset whose join is x, we get y  x . Similarly, x  y , so x  y .
Therefore, we have x  x  y y.

3.35. Lemma. Whenever X is defined, it is the least upper bound of X.

Proof. Let X x. By definition, for any y X, we have y x, so x is an upper bound for X. Suppose z is another upper bound for X. Then for any y X, we have y z, so y z . Therefore X z . Since z is closed under , this means that X z , i.e., x z. Therefore, x is the least upper bound for X.

The sandwich condition is clear from the conditions and the fact that joins are defined for principal downsets. Closure under intersections is one of the conditions, so it just remains to show the final condition that join-closure is transitive. This is also one of the conditions given. By definition of , the condition y X_{y} and X_{y} A is equivalent to A y (we can take X_{y} A ). We have therefore shown that this partial operation defines a partial sup lattice.

4. Relation Between Ideal and Unioned Downset Functors

4.1. Proposition. I is an endofunctor on the category of partial sup lattices.

Proof. It is clear that taking the inverse image of functions gives a contravariant functor into the category of posets, since it is a restriction of the inverse image functor on the

power set. Let L [figure: f] M be a partial sup homomorphism. We define IL [figure: If] IM by If A is the ideal generated by f x x A . It is easy to see that If f^{1} , so since adjoints compose, this means that If is a sup homomorphism and I is a functor.

4.2. Proposition. J is an endofunctor on the category of partial sup lattices.

Proof. Let L [figure: f] M be a partial sup homomorphism. We define JL [figure: Jf] JM by Jf A is the downset generated by f x x A . This is a unioned downset by definition of partial sup homomorphisms. Also, this is a restriction of the downset homomorphism, so we know that it satisfies the functoriality condition. We still need to show that Jf is a partial sup homomorphism, but this is obvious since Jf preserves unions.

4.3. Proposition. The inclusion L [figure: ]IL has a right adjoint.

Proof. The right adjoint is given by supremum. It is easy to see that this is an adjoint because for any x L, x is an ideal, and its join is X. On the other hand, we clearly have X X .

4.4. Theorem. The natural transformations IJ [figure: ]D and D [figure: _{J}] IJ given by X Y JL Y X are inverse isomorphisms.

Proof. First, we need to show that these functions are well-defined. A union of downsets is clearly a downset. We need to show that for any downset X, Y JL Y X is an ideal in JL. That is, it is closed under unions that lie in JL. This is clear since X is closed under unions.

Next we need to show that they are inverse. For X DL, and for any x X, we have x JL, so X _{x X} x shows that _{J} is the identity. On the other hand, given an ideal I in JL, let X I. We want to show that I X _{J}. Suppose V X _{J}, we want to show that V I. Since I is an ideal, it is sufficient to show that for any x V, there is some A I with x A. Since x X I, this will hold. Conversely, for any V I, we have V X, so V X _{J}.

4.5. Theorem. The square:

[figure: JL; ; DL; ; L; ; IL]

is both a pullback and a pushout in the category PartSup of partial sup lattices and homomorphisms.

Proof. Firstly, it is straightforward to see that it is a commutative square, and that all the morphisms are partial sup lattice homomorphisms.

For the pushout. Let

[figure: JL; ; DL; f; L; g; X]

commute in PartSup (the category of partial sup lattices and partial sup homomorphisms). We want to show that if A B, then f A f B . It is sufficient to show this for B A . This holds, because for any C A with C defined, we must have C JL, so f C g C f A . That is for any x A, we have g x f A . However, A x x A , so f preserves this union, so, f A _{x A} g x . On the other hand, we know that g x f A for any x A. Also since f is order preserving, we know that f A f A , so they must be equal. Therefore, f must

factor through DL [figure: ]IL as required.

For the pullback, we need to show that for A DL, we have A is a principal downset if and only if A is defined. Clearly, if A x, then A x . On the other hand, if A x , then x is certainly an upper bound for A, and x must be the join of some subset of A, so it must be the join of the whole of A.

References

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

[2] T. Kenney and R. J. Wood. Tensor products of sup-lattices and generalised sup-arrows. Th. App. Cat., 24:266–287, 2010.

[3] G. N. Raney. A subdirect-union representation for completely distributive complete lattices. Proc. Amer. Math. Soc., 4:518–522, 1953.

[4] R. Rosebrugh and R. J. Wood. Boundedness and complete distributivity. App. Cat. Structures, 9:437–456, 2001.

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

[6] R. Rosebrugh and R.J. Wood. Constructive complete distributivity III. Canadian Math. Bull., 35:534–547, 1992.

[7] R. Rosebrugh and R.J. Wood. Constructive complete distributivity IV. App. Cat. Structures, 2(2):119–144, 1994.

Department of Mathematics and Statistics Dalhousie University Halifax, NS, B3H 3J5 Canada

Email: tkenney@mathstat.dal.ca
This article may be accessed at http://www.tac.mta.ca/tac/

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. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information Individual subscribers receive abstracts of articles by e-mail as they are published. 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 L^{A}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis: cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown(at)btinternet.com

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Kathryn Hess, Ecole Polytechnique Fédérale de Lausanne: kathryn.hess@epfl.ch Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Edinburgh: Tom.Leinster@ed.ac.uk Ieke Moerdijk, Radboud University Nijmegen: i.moerdijk@math.ru.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Giuseppe Rosolini, Università di Genova: rosolini@disi.unige.it Alex Simpson, University of Edinburgh: Alex.Simpson@ed.ac.uk James Stasheff, University of North Carolina: jds@math.upenn.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca