Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

March 6, 2019

Left Adjoints Between Categories of Posets

Posted by John Baez

I have a bunch of related questions about things like “the free lattice on a poset”, and so on. I would hope that at least some of these questions have nice answers, at least for finite posets. But I’m not having much luck finding them!

Specifically:

1) What’s the free join-semilattice (i.e. a poset where any finite subset has a supremum) on a poset?

2) What’s the free complete join-semilattice (i.e. a poset where any subset has a supremum) on a poset?

3) What’s the free lattice) (i.e. a poset where any finite subset has a supremum and infimum) on a poset?

4) What’s the free complete lattice (i.e. a poset where any subset has a supremum and infimum) on a poset?

5) What’s the free distributive lattice (i.e. a lattice where finite infs distribute over finite sups) on a poset?

6) What’s the free locale (i.e. a poset where any finite subset has an infimum and any subset has a supremum, and finite infs distribute over arbitrary sups) on a poset?

7) What’s the free completely distributive lattice (i.e. a complete lattice where arbitrary infs distribute over arbitrary sups) on a poset?

Of course these questions require specifying the allowed morphisms between the various kinds of objects; in many cases there are standard choices. There are also many other questions of this sort I’d be happy to hear insights about, like “what’s the free distributive lattice on a lattice?” Anyway, I’ll take whatever theorems you can tell me.

Mike Shulman suggests, quite believably, that the free complete join-semilattice on a poset PP is its set of downsets, i.e subsets SPS \subseteq P such that

sS,sssS. s \in S, s' \le s \quad \implies \quad s' \in S.

The set of all downsets in PP, say P^\hat{P}, is ordered by inclusion, and it’s a complete join-semilattice: any union of downsets is a downset.

This makes a lot of sense because it’s analogous to how the category of presheaves on a category is its free cocompletion. In fact we can make this analogy quite precise, using enriched categories.

We can think of posets, or more generally preorders, as BoolBool-enriched categories where BoolBool is the monoidal category with two objects FF, TT and one nontrivial morphism FTF \implies T, its monoidal structure being “and”. The downsets of a poset PP correspond in a one-to-one way with order-preserving maps f:P opBoolf \colon P^{op} \to Bool, just as presheaves on a category CC are functors f:C opSetf \colon C^{op} \to Set. There’s an embedding of PP in P^\hat{P} that sends each pPp \in P to its principal downset {sP:sp}\{s \in P : \; s \le p \}. The principal downsets are the BoolBool-enriched version of representable presheaves, and the embedding of PP in P^\hat{P} is the BoolBool-enriched version of the Yoneda embedding. So, just as the category of presheaves on a category CC is the free cocomplete category on CC, P^\hat{P} should be the free cocomplete BoolBool-enriched category with on PP. But a cocomplete BoolBool-enriched category should be just the same as a complete join-semilattice, since joins are colimits.

Mike adds that probably the free sup-semilattice on PP likewise consists of downsets that are the union of finitely many principal ones.

So, maybe questions 1) and 2) have nice answers. Are they in the literature somewhere? What about the rest?

Posted at March 6, 2019 8:06 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3093

17 Comments & 0 Trackbacks

Re: Left Adjoints Between Categories of Posets

Horn and Kimura (The category of semilattices, Algebra Universalis 1 (1971) no. 1, 26–38, Theorem 4.1) describe the free meet-semilattice P *P^* on a partially ordered set PP as the set of all non-empty finite discrete subsets of P, with ordering defined by letting S 1S 2S_1 \leq S_2 if for all pS 2p \in S_2 there is a qS 1q \in S_1 such that qpq \leq p in PP. A subset is discrete if no two distinct members are comparable.

I guess that considering order-duals this will give you a description of the free join-semilattice on PP as well.

Posted by: Frederik Lauridsen on March 6, 2019 9:48 AM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

Frederik wrote:

Horn and Kimura (The category of semilattices, Algebra Universalis 1 (1971) no. 1, 26–38, Theorem 4.1) describe the free meet-semilattice P *P^* on a partially ordered set PP as the set of all non-empty finite discrete subsets of P, with ordering defined by letting S 1S 2S_1 \leq S_2 if for all pS 2p \in S_2 there is a qS 1q \in S_1 such that qpq \leq p in PP. A subset is discrete if no two distinct members are comparable.

Nice!

I guess that considering order-duals this will give you a description of the free join-semilattice on PP as well.

It must.

So, it’s interesting to compare this to Mike Shulman’s description of the free join-semilattice on PP, given in my post.

He guessed that the free complete join-semilattice on a poset PP is the set of downsets of PP, ordered by inclusion.

He guessed that the free join-semilattice on PP is the set of downsets that are the union of finitely many principal downsets, meaning those of the form {pP:px}\{p \in P : \; p \le x\} for some xPx \in P.

I believe a downset of this particular form is characterized by its set of maximal elements. It should be the union of the principal downsets {pP:px}\{p \in P : \; p \le x\} where xx ranges over these maximal elements.

These maximal elements form a discrete set.

So, I think there’s a 1-1 correspondence between finite discrete subsets of PP and downsets that are the union of finitely many principal downsets.

This would make Mike’s ideas compatible with what you just said. (Though he is leaving out the word ‘non-empty’, since he is a category theorist, not an order theorist: order theorists are happy for their lattices to have sups and infs of finite nonempty sets, while category theorists want them to have sups and infs of all finite sets. This is no big deal if we’re careful about the difference.)

Posted by: John Baez on March 6, 2019 8:03 PM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

The completely distributive lattice CD(P)CD(P) over a poset PP has been described by Tunnicliffe (The free completely distributive lattice over a poset, Algebra Universalis, 21 (1985, 133-135, Theorem 2).

CP(P)CP(P) can be described as the as the lattice of downsets of the lattice D(P)D(P) of proper non-empty downsets of PP. Morphisms between complete distributive lattices are here taken to be functions preserving all infima and suprema of non-empty sets.

I believe that you can find a similar description of free lattices over a poset in Chapter 1.5 of the book “Lattice Theory: Foundation” by Grätzer.

Posted by: Frederik Lauridsen on March 6, 2019 10:37 AM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

I’m not sure what “similar” means, but the free lattice on three generators with no relations is infinite, so you need constructions which get out of finite sets to reach it.

Posted by: David Speyer on March 6, 2019 4:39 PM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

Yes, you are right, I was not be very precise and I see now that my comment was misleading.

I was thinking that the construction in Gräzter’s book is somewhat similar to the one by Tunnicliffe for distributive lattices, not the one by Horn and Kimura for the semi-lattices.

The similarity with Grätzer is that to prove the existence of the free lattice F L(P)F_L(P) on a poset PP one first needs to construct a lattice into which the poset PP embeds, as a partial lattice. This can be done by considering the collection Id 0(P)Id_0(P) of all ideals, i.e., downsets closed under existing finite joins, of PP together with the empty set. Thus Id 0(P)Id_0(P) is similar to the set D(P)D(P) in Tunnicliffe’s construction, only not necessarily distributive.

However, from this point onwards things gets more complicate in the lattice setting. I was misreading Grätzer earlier today which caused me to call the two constructions similar which is a bit of a stretch to put it mildly.

Note also that Grätzer requires the embedding of the poset PP into F L(P)F_L(P) not just to preserve the order but also to preserve all finite meets and joins which exist in PP. Of course, with this requirement the free distributive lattice over a poset might not exist.

Posted by: Frederik Lauridsen on March 6, 2019 5:39 PM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

Regarding (4), defining the “free complete lattice”, even on a three generators, has set theoretic issues. Namely, let x,yx, y and zz be elements of a complete lattice LL. For any ordinal α\alpha, we define elements p αp_{\alpha} of LL as follows:

We set p 0=xp_0 = x. If α=β+1\alpha = \beta+1, then p α=x(y(z(x(y(zp β)))))p_{\alpha} = x \vee (y \wedge (z \vee (x \wedge (y \vee (z \wedge p_{\beta}))))); if α\alpha is a limit ordinal we set p α= β<αp βp_{\alpha} = \bigvee_{\beta \lt \alpha} p_{\beta}. The map αp α\alpha \mapsto p_{\alpha} is weakly increasing and, for any ordinal γ\gamma, we can find a complete lattice so that it is strictly increasing up to γ\gamma.

So, if there were a “free complete lattice”, it would contain sub-posets isomorphic to every ordinal, and hence is too large to be a set.

See link 1 and link 2 for more.

Mike Shulman will be pleased to know that this issue is one of the ones that convinced me I actually had to care about set theory.

Posted by: David Speyer on March 6, 2019 3:49 PM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

Zounds!

I guess we’ll have to content ourselves with the free α\alpha-complete lattice where α\alpha is an inaccessible cardinal.

Posted by: John Baez on March 6, 2019 7:50 PM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

Regarding 5, 6 and 7: Consider a lattice where generated by (x p) pP(x_p)_{p \in P} where meet distributes over join. Then any word in the x px_p can be written in the form jJ iI jx i(*)\bigvee_{j \in J} \bigwedge_{i \in I_j} x_i \qquad (\ast) for some index set JJ and some collection I jI_j of subsets of PP. If we restrict meets and/or joins to be finite, we should restrict I jI_j and/or JJ to be finite.

Replacing I jI_j by the order ideal it generates won’t change (*)(\ast), and then replacing JJ by the order ideal it generates in the poset of order ideals won’t change (*)(\ast) either. So the answer to 7 should be order ideals in the poset of order ideals of P. For 5 and 6, insert the adjective “finitely generated” in the appropriate places.

Posted by: David Speyer on March 6, 2019 5:54 PM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

David wrote:

replacing JJ by the order ideal it generates in the poset of order ideals won’t change (*)(\ast) either.

Sorry, that’s not parsing for me: JJ is a humble ‘index set’, not a subset of the poset of order ideals. Do you mean {I j} jJ\{\langle I_j \rangle \}_{j \in J}, where I j\langle I_j \rangle is the order ideal generated by the set I jPI_j \subseteq P?

So the answer to 7 should be order ideals in the poset of order ideals of PP.

Wow! For those who aren’t keeping score, 7 asks for the free completely distributive lattice on the poset PP. You seem to be saying this is the poset of order ideals in the poset of order ideals in PP!

What’s astounding about this is there there’s an endofunctor T:PosetPosetT: Poset \to Poset sending any poset to its poset of order ideals. So, you seem to be saying that the “underlying poset of the free completely distributive lattice on a poset” functor is T 2T^2.

I have a bit of trouble believing this is exactly right, because the concept of ‘order ideal’ knows the difference between up and down, while the concept of ‘completely distributive lattice’ does not. According to Wikipedia an order ideal II in a poset PP is a subset such that

  • II is non-empty

  • II is a downset: if iIi \in I and pip \le i then pIp \in I

and

  • for every i,jIi, j \in I there exists kIk \in I such that i,jki, j \le k.

(I don’t think we want that non-emptiness condition, since this gives our collection of order ideals a bottom element, and if we want all subsets to have suprema, even the empty set — and we do — we need a bottom element. This is one place where category theorists differ from ordinary order theorists.)

In other words: the concept of completely distributive lattice is self-dual, while that of order ideal is not. The dual of the concept of order ideal, defined by replacing \le by \ge above, is the concept of filter.

So, I might suspect that the free completely distributive lattice on a poset PP is the poset of filters on the poset of order ideals in PP. If this is right, it must also be the poset of order ideals on the poset of filters in PP.

All this makes me want to know more about the functor T:PosetPosetT: Poset \to Poset sending any poset to its poset of order ideals. What universal property does the poset of order ideals on PP have?

In other words: T(P)T(P) is the free what on PP?

Posted by: John Baez on March 6, 2019 7:44 PM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

Regarding (2). This article by Winskel discusses three characterizations of the free complete join-semilattices. Firstly as the posets of downsets, as you already pointed out. Secondly as the completely distributive algebraic lattices. Thirdly as the prime algebraic lattices: every element is a join of its complete primes — maybe it’s good to think of this as an analogue of Bunge’s characterization of presheaf categories.

Incidentally, constructions (1) and (2) play a key role in the Nygaard/Winskel Domain theory for concurrency. That paper ends with the tantalizing possibility of moving from 2-enrichment to Set-enrichment, as you mentioned in your post.

Posted by: Sam Staton on March 7, 2019 7:53 AM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

The answers to almost all of these are conveniently found in PTJ’s Stone Spaces; in brief:

1) What’s the free join-semilattice (i.e. a poset where any finite subset has a supremum) on a poset?

The poset of finitely generated downsets.

2) What’s the free complete join-semilattice (i.e. a poset where any subset has a supremum) on a poset?

The poset of all downsets.

3) What’s the free lattice (i.e. a poset where any finite subset has a supremum and infimum) on a poset?

This one is more complicated and quite interesting. The theory is finitary, so the free lattice does always exist. There are papers of Whitman from the 40s about this. Joyal and Hu have some related work about free bicompletion of categories.

4) What’s the free complete lattice (i.e. a poset where any subset has a supremum and infimum) on a poset?

This does not exist basically for size reasons (it would be the coproduct of two monads without rank on Set). Levy and Bowler (with others) have some interesting papers about coproducts of monads without rank.

5) What’s the free distributive lattice (i.e. a lattice where finite infs distribute over finite sups) on a poset?

First take finitely generated upsets with the reverse ordering (free finite meet completion). Then take finitely generated downsets in that.

6) What’s the free locale (i.e. a poset where any finite subset has an infimum and any subset has a supremum, and finite infs distribute over arbitrary sups) on a poset?

First take finitely generated upsets with reverse ordering. Then take arbitrary downsets in that.

7) What’s the free completely distributive lattice (i.e. a complete lattice where arbitrary infs distribute over arbitrary sups) on a poset?

First take arbitrary upsets with reverse ordering. Then take arbitrary downsets.

These latter ones all arise from a distributive law between a co-KZ monad adding limits and a KZ monad adding colimits.

Taking order-ideals corresponds to adding directed colimits. If you take arbitrary upsets with the reverse ordering, and then take order-ideals you get the free continuous lattice. Other variants are possible.

Posted by: Richard Garner on March 7, 2019 11:47 AM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

Wow, this is great!

For some silly reason I thought Stone Spaces was just about Stone spaces, so I haven’t been perusing it as my interest in various categories of posets has grown. I’d been looking for answers to my questions on the nnLab and not finding them. I will dutifully enter them in, adding Johnstone’s distinctive qualities to the collective.

Seriously, you’ve given me just what I was hoping for: a systematic approach to a lot of these questions! It’s all about monads, coproducts of monads (which may exist or not), and distributive laws.

Posted by: John Baez on March 7, 2019 10:32 PM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

Also worth mentioning: if you choose the maps in the category of posets correctly, then the free complete lattice on a poset is its Dedekind–Mac Neille completion. In fact, for this choice of poset morphism, complete posets become a reflective subcategory of arbitrary ones. See:

A Bishop, A universal mapping characterization of the completion by cuts. Algebra Universalis 8, 3 (1978).

Posted by: Richard Garner on March 7, 2019 11:54 AM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

Last year I asked a related question on math.stackexchange: https://math.stackexchange.com/questions/2810936/free-bounded-lattice. I didn’t find the responses very helpful. In case anyone is interested, here is some context.

In my little programming language I want to define types by their properties, and then organize them in a subtyping hierarchy with the rule that properties are compatible (commonly automatic because subtypes inherit properties from above, but also in a non-trivial sense when both types have their own version of a property). Properties must go down as you go up the hierarchy. So we start with a poset of types with some subtyping relationships. Then I wanted to extend that to a bounded lattice (just called a lattice above, which seems like a good change to me).

The way I extend this is, given two types X and Y that are not above/below each other, to define sup as a new type Union(X,Y), and so on in the obvious way for sets of more than 2 elements, and with Union() being Empty at the bottom of the hierarchy [yes it has all properties]. In the other direction the inf, Intersection(X,Y), is defined as the Union of all types that are below both X and Y. Extended in the obvious way, and with Intersection() being type Any. While the definition is asymmetric, I think the result is symmetric and Union is then the Intersection of types above X and Y (?). It doesn’t look implausible that this construction might be in correspondence with a lattice formed from upsets and/or downsets, as described above.

To give an example, suppose we have types Integer, Rational, ComplexInteger (=Gaussian integer), and ComplexRational, with the obvious subtyping between them. There will now be a new type Union(Rational,ComplexInteger) which is below ComplexRational. By the rule that properties must go down as you go up, it must have all the properties of ComplexRational. For example if will inherit the add property from ComplexRational, which means you can add 2 values from the Union, but this is done by converting them up to ComplexRational and getting a ComplexRational result.

I gave a talk on this last December in beautiful windy Wellington, and slides are: https://docs.google.com/presentation/d/1a72bKhCxfNBj7lqPVWfqLPDW_QPgQEKy7N0LM8RCo0o/edit?usp=sharing.

Posted by: Robert Smart on March 7, 2019 11:44 PM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

This post has been very helpful to me. I’m changing my little language. Now there will be Types, with values having only one type. Types form a partial order from the isA relationship. Then we have Modes which are up-sets of types. This is where subtyping happens (except that it is now submoding). A magic reconciliation between the desire for subtyping and the desire to have uniquely typed values. [Assuming it all works out as I currently expect].

Posted by: Robert Smart on March 9, 2019 11:58 PM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

Todd Trimble wrote something on the nn-Café that I found very helpful, because I was wondering how the “free distributive lattice on a finite poset” was related to Birkhoff duality: the equivalence between the category of finite posets and the opposite of the category of finite distributive lattices. It turns out they fit together nicely:

The free suplattice on a poset PP is indeed the poset of downsets of PP, and this is indeed distributive since it can be identified with the internal poset hom [P op,2][P^{op}, 2] which has meets and joins defined pointwise. Then, because 22 is distributive, so must be [P op,2][P^{op}, 2]. Another way of saying it: the set-theoretic intersection of two down-sets is a downset, and same for the set-theoretic union. Then use distributivity of set-theoretic operations.

For the free distributive lattice on a poset PP, I think it works like this. In the finite case, the functor [,2]:FinPos opFinDist[-, 2]: FinPos^{op} \to FinDist is an equivalence. Thus the forgetful functor U:FinDistPosU: FinDist \to Pos may be identified with [,2]:FinPos opFinPos[-, 2]: FinPos^{op} \to FinPos. The latter has a left adjoint [,2] op:FinPosFinPos op[-, 2]^{op}: FinPos \to FinPos^{op}. Thus the left adjoint to UU becomes the composite

FinPos[,2] opFinPos op[,2]FinDistFinPos \stackrel{[-, 2]^{op}}{\to} FinPos^{op} \stackrel{[-, 2]}{\to} FinDist

taking a poset PP to [[P,2],2][[P, 2], 2]. This extends to a left adjoint Φ:PosDist\Phi: Pos \to Dist by expressing an arbitrary poset as the filtered colimit of its finite subposets FF:

Φ(P)=colim fin.FP[[F,2],2].\Phi(P) = colim_{fin.\; F \hookrightarrow P} [[F, 2], 2].

Posted by: John Baez on March 8, 2019 1:22 AM | Permalink | Reply to this

Re: Left Adjoints Between Categories of Posets

So, maybe questions 1) and 2) have nice answers. Are they in the literature somewhere?

Here are my nominations, from Max Kelly’s Basic Concepts of Enriched Category Theory:

2) What’s the free complete join-semilattice (i.e. a poset where any subset has a supremum) on a poset?
Theorem 4.51

1) What’s the free join-semilattice (i.e. a poset where any finite subset has a supremum) on a poset?
Theorem 5.35

Advantages: a) They apply to a wider range of examples than just posets. b) These theorems give much more information about their situations than merely assertions of freeness. For example, the adjointness of some of the arrows being generated.

Let me now make an acknowledgment of ignorance.
Given Theorem 5.35, why is Theorem 5.37 necessary?


Posted by: Keith Harbaugh on March 26, 2019 12:00 AM | Permalink | Reply to this

Post a New Comment