nLab semilattice

Redirected from "join semilattice".
Contents

Contents

Definition

General

A join-semilattice is a poset which admits all finite joins, or equivalently which admits a bottom element \bot and binary joins aba\vee b. If we think of a poset as a category, a join-semilattice is the same as a poset with finite colimits, or equivalently, a poset with finite coproducts.

In a join-semilattice the binary join \vee is commutative, associative, has \bot as a unit, and is idempotent: aa=aa\vee a =a. And in fact, given any commutative and idempotent monoid (A,,)(A,\vee,\bot), we can define aba\le b to mean ab=ba \vee b = b to make it into a poset with finite joins; thus we have an equivalent algebraic definition of a join-semilattice.

Dually, a meet-semilattice is a poset which admits all finite meets, including a top element \top and binary meets \wedge. Once again \wedge is commutative, associative, unital for \top, and idempotent. Once again we can recover the order from it, but this time defining aba\le b to mean ab=aa \wedge b = a. If we think of a poset as a category, a meet-semilattice is the same as a poset with finite limits, or equivalently, a poset with finite products.

If we treat join- and meet-semilattices purely algebraically there is no difference: they are both just idempotent commutative monoids. The difference comes in how we define the order starting the commutative monoid structure, or in the notation we use (just as we distinguish additive and multiplicative groups notationally).

Since the opposite of a join-semilattice is a meet-semilattice, it would be possible to take one as standard and call the other a cosemilattice (compare directed and codirected sets), but this may not have ever been done.

If a poset is both a join- and a meet-semilattice, then we call it a lattice.

Bounded semilattices and semipseudolattices

Traditionally, a semilattice need have only finite inhabited meets/joins; that is, it need not have a top/bottom element. Algebraically, this means that a semilattice need not be a monoid, but is any commutative idempotent semigroup.

One might call a semilattice that does have a top/bottom element a bounded semilattice; the problem with this is that a bounded poset already means a poset that has both top and bottom elements, whereas here we really only want to require one.

Another approach is to define a semilattice, as above, to require a top/bottom element and then use the term pseudosemilattice or semipseudolattice to allow for the possibility that it might not.

See lattice for more discussion of this issue.

Semilattice homomorphisms

A homomorphism of join-semilattices f:ABf: A \to B is a function that preserves finite joins, or equivalently:

f(xy)=f(x)f(y),f()=. f(x \vee y) = f(x) \vee f(y),\; f(\bot) = \bot .

Note that such a homomorphism is necessarily a monotone function, but the converse fails. Thus, a semilattice is a poset with property-like structure.

A homomorphism of meet-semilattices is defined in an analogous (i.e., dual) way. In what follows we take join-semilattices as the default, but all results apply to meet-semilattices with slight modifications.

The category of semilattices

Semilattices and semilattice homomorphims form a concrete category SemiLat. By the remarks above, this is equivalent to the category of commutative idempotent monoids. Since these are algebras of a Lawvere theory, or equivalently a finitary monad on SetSet, the category SemiLatSemi Lat has all the properties that finitary monadic categories enjoy.

The poset {F,T}\{F,T\} where FTF \le T becomes a commutative rig with \vee and meet \wedge as addition and multiplication, respectively; let us call this rig BoolBool. We can define a module of a rig much as we define a module of a ring, but with the module’s underlying abelian group generalized to be a commutative monoid (thus eliminating the need for negatives). The underlying commutative monoid of a BoolBool-module is idempotent because, writing addition in this monoid as ++, we have a+a=(TT)a=Ta=aa + a = (T \vee T)a = T a = a. Conversely, any idempotent commutative monoid becomes a BoolBool-module in a unique way. Thus, the category SemiLatSemi Lat is equivalent to the category of BoolBool-modules.

Properties

The free join-semilattice on a poset

There is a forgetful functor

U:SemiLatPoset U \colon SemiLat \to Poset

This has a left adjoint

F:PosetSemiLat F \colon Poset \to SemiLat

where for any poset PP, the join-semilattice F(P)F(P) is the poset of finitely generated downsets of PP, ordered by inclusion. Here a downset of a poset PP is a subset SPS \subseteq P such that

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

This set of all downsets in PP, say P^\hat{P}, is ordered by inclusion, and it’s a suplattice: any union of downsets is a downset. 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 \}. A downset is finitely generated if it is the union of finitely many principal downsets. (To give a finitely generated downset is to give a finite antichain, and so the free join-semilattice is sometimes described equivalently as the set of finite antichains in PP equipped with a certain partial order.)

To understand this description of the free join-semilattice on a poset, some enriched category theory is useful. A preorder is the same as a BoolBool-enriched category, where now BoolBool stands for 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, but in terms of enriched category theory these are precisely the BoolBool-enriched functors 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. Thus, the embedding y:PP^y \colon P \to \hat{P} that sends each pPp \in P to its principal downset 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} is the free cocomplete BoolBool-enriched category on PP. But a cocomplete BoolBool-enriched category that happens to be a poset (instead of a mere preorder) is the same as a suplattice. Thus, the free suplattice on PP is P^\hat{P}.

Similarly, the free join-semilattice on a poset PP is the BoolBool-enriched analogue of the free finitely cocomplete category on a category CC, since objects in this category are presheaves that are finite colimits of representables.

Examples

Last revised on May 19, 2022 at 05:27:41. See the history of this page for a list of all contributions to it.