nLab semilattice

The article is about bounded semilattices in the sense of join-semilattices having a bottom element or meet-semilattices having a top element. For “bounded semilattices” which have both a top element and a bottom element and thus are a bounded poset, see 01-bounded semilattice.

---

Definition

General

A join-semilattice is a poset which admits all finite joins, or equivalently which admits a bottom element $\bot$ and binary joins $a\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: $a\vee a =a$. And in fact, given any commutative and idempotent monoid $(A,\vee,\bot)$, we can define $a\le b$ to mean $a \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 $a\le b$ to mean $a \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 and unbounded semilattices

There is also the question of whether semilattices are bounded or not, in the sense of a bounded lattice. With the algebraic definition of a semilattice, one could either assume that semilattices have neutral elements $1$ or absorbing elements $0$ or both or neither. In the order-theoretic definition, one can assume that semilattices have top elements or bottom elements or both or neither. This yields four different kinds of semilattices:

• those semilattices without either neutral elements or absorbing elements are unbounded semilattices or pseudosemilattices.

• those semilattices with only neutral elements are bounded semilattices

• those semilattices with only absorbing elements do not seem to have a name in the literature, but are still bounded from the opposite direction.

• those semilattices with both neutral and absorbing elements are 01-bounded semilattices

In a join-semilattice, the top element, if it exists, is a neutral element and the bottom element, if it exists, is an absorbing element for the join operation. Likewise, in a meet-semilattice, the bottom element, if it exists, is a neutral element and the top element, if it exists, is an absorbing element for the meet operation.

Semilattice homomorphisms

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

$$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 $Set$, the category $Semi Lat$ has all the properties that finitary monadic categories enjoy.

The poset $\{F,T\}$ where $F \le T$ becomes a commutative rig with $\vee$ and meet $\wedge$ as addition and multiplication, respectively; let us call this rig $Bool$. 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 $Bool$-module is idempotent because, writing addition in this monoid as $+$, we have $a + a = (T \vee T)a = T a = a$. Conversely, any idempotent commutative monoid becomes a $Bool$-module in a unique way. Thus, the category $Semi Lat$ is equivalent to the category of $Bool$-modules.

Properties

The free join-semilattice on a poset

There is a forgetful functor

$$U \colon SemiLat \to Poset$$

This has a left adjoint

$$F \colon Poset \to SemiLat$$

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

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

This set of all downsets in $P$, say $\hat{P}$, is ordered by inclusion, and it’s a suplattice: any union of downsets is a downset. 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 \}$. 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 $P$ 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 $Bool$-enriched category, where now $Bool$ stands for 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$, but in terms of enriched category theory these are precisely the $Bool$-enriched functors $f \colon P^{op} \to Bool$, just as presheaves on a category $C$ are functors $f \colon C^{op} \to Set$. Thus, the embedding $y \colon P \to \hat{P}$ that sends each $p \in P$ to its principal downset 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}$ is the free cocomplete $Bool$-enriched category on $P$. But a cocomplete $Bool$-enriched category that happens to be a poset (instead of a mere preorder) is the same as a suplattice. Thus, the free suplattice on $P$ is $\hat{P}$.

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

Examples

• semilattice of commutative subalgebras

• suplattice

• 01-bounded semilattice

Related concepts

• band, idempotent monoid

• enriched poset

• presemilattice

• semilattice object

• join-semilattice object

• meet-semilattice object

References

See also:

• Wikipedia: Semilattice