The n-Category Café

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.

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.

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.

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.

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.

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.

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.

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).

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.

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].$$