## 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 $P$ is its set of downsets, i.e subsets $S \subseteq P$ such that

$s \in S, s' \le s \quad \implies \quad s' \in S.$

The set of all downsets in $P$, say $\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 $Bool$-enriched categories where $Bool$ is the monoidal category with two objects $F$, $T$ and one nontrivial morphism $F \implies T$, its monoidal structure being “and”. The downsets of a poset $P$ correspond in a one-to-one way with order-preserving maps $f \colon P^{op} \to Bool$, just as presheaves on a category $C$ are functors $f \colon C^{op} \to Set$. There’s an embedding of $P$ in $\hat{P}$ that sends each $p \in P$ to its principal downset $\{s \in P : \; s \le p \}$. The principal downsets are the $Bool$-enriched version of representable presheaves, and the embedding of $P$ in $\hat{P}$ is the $Bool$-enriched version of the Yoneda embedding. So, just as the category of presheaves on a category $C$ is the free cocomplete category on $C$, $\hat{P}$ should be the free cocomplete $Bool$-enriched category with on $P$. But a cocomplete $Bool$-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 $P$ 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

### 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^*$ on a partially ordered set $P$ as the set of all non-empty finite discrete subsets of P, with ordering defined by letting $S_1 \leq S_2$ if for all $p \in S_2$ there is a $q \in S_1$ such that $q \leq p$ in $P$. 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 $P$ 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^*$ on a partially ordered set $P$ as the set of all non-empty finite discrete subsets of P, with ordering defined by letting $S_1 \leq S_2$ if for all $p \in S_2$ there is a $q \in S_1$ such that $q \leq p$ in $P$. 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 $P$ as well.

It must.

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

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

He guessed that the free join-semilattice on $P$ is the set of downsets that are the union of finitely many principal downsets, meaning those of the form $\{p \in P : \; p \le x\}$ for some $x \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 $\{p \in P : \; p \le x\}$ where $x$ 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 $P$ 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)$ over a poset $P$ has been described by Tunnicliffe (The free completely distributive lattice over a poset, Algebra Universalis, 21 (1985, 133-135, Theorem 2).

$CP(P)$ can be described as the as the lattice of downsets of the lattice $D(P)$ of proper non-empty downsets of $P$. 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)$ on a poset $P$ one first needs to construct a lattice into which the poset $P$ embeds, as a partial lattice. This can be done by considering the collection $Id_0(P)$ of all ideals, i.e., downsets closed under existing finite joins, of $P$ together with the empty set. Thus $Id_0(P)$ is similar to the set $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 $P$ into $F_L(P)$ not just to preserve the order but also to preserve all finite meets and joins which exist in $P$. 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, y$ and $z$ be elements of a complete lattice $L$. For any ordinal $\alpha$, we define elements $p_{\alpha}$ of $L$ as follows:

We set $p_0 = x$. If $\alpha = \beta+1$, then $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_{\alpha} = \bigvee_{\beta \lt \alpha} p_{\beta}$. The map $\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.

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)_{p \in P}$ where meet distributes over join. Then any word in the $x_p$ can be written in the form $\bigvee_{j \in J} \bigwedge_{i \in I_j} x_i \qquad (\ast)$ for some index set $J$ and some collection $I_j$ of subsets of $P$. If we restrict meets and/or joins to be finite, we should restrict $I_j$ and/or $J$ to be finite.

Replacing $I_j$ by the order ideal it generates won’t change $(\ast)$, and then replacing $J$ 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 $J$ by the order ideal it generates in the poset of order ideals won’t change $(\ast)$ either.

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

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

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

What’s astounding about this is there there’s an endofunctor $T: 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^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 $I$ in a poset $P$ is a subset such that

• $I$ is non-empty

• $I$ is a downset: if $i \in I$ and $p \le i$ then $p \in I$

and

• for every $i, j \in I$ there exists $k \in I$ such that $i, 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 $P$ is the poset of filters on the poset of order ideals in $P$. If this is right, it must also be the poset of order ideals on the poset of filters in $P$.

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

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

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.

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 $n$Lab 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. 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 here.

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 $n$-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 $P$ is indeed the poset of downsets of $P$, and this is indeed distributive since it can be identified with the internal poset hom $[P^{op}, 2]$ which has meets and joins defined pointwise. Then, because $2$ is distributive, so must be $[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 $P$, I think it works like this. In the finite case, the functor $[-, 2]: FinPos^{op} \to FinDist$ is an equivalence. Thus the forgetful functor $U: FinDist \to Pos$ may be identified with $[-, 2]: FinPos^{op} \to FinPos$. The latter has a left adjoint $[-, 2]^{op}: FinPos \to FinPos^{op}$. Thus the left adjoint to $U$ becomes the composite

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

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

$\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