Semilattice

A semilattice is a mathematical concept with two definitions, one as a type of ordered set, the other as an algebraic structure. In mathematical order theory, a semilattice is a partially ordered set (poset) closed under one of two binary operations, either supremum (join) or infimum (meet). Hence we speak of either a join-semilattice or a meet-semilattice. If an ordered set is both a meet- and join-semilattice, it is also a lattice.

Semilattices as posets

Let S be a set partially ordered by the binary relation ≤. Failed to parse (Missing texvc executable; please see math/README to configure.): \lang S,\leq \rang

is a meet-semilattice if

For all elements x and y of S, the greatest lower bound of the set {x, y} exists.

The greatest lower bound of the set {x,y} is called the meet of x and y, denoted xFailed to parse (Missing texvc executable; please see math/README to configure.): \wedge y.

Replacing "greatest lower bound" with "least upper bound" results in the dual concept of a join-semilattice. The least upper bound of {x, y} is called the join of x and y, denoted xFailed to parse (Missing texvc executable; please see math/README to configure.): \vee y. Meet and join are binary operations on S. A simple induction argument shows that the existence of all possible pairwise suprema (infima), as per the definition, implies the existence of all non-empty finite suprema (infima).

A join-semilattice is bounded if it has a least element, the join of the empty set. Dually, a meet-semilattice is bounded if it has a greatest element, the meet of the empty set.

Other properties may be assumed; see the article on completeness in order theory for more discussion on this subject. That article also discusses how we may rephrase the above definition in terms of the existence of suitable Galois connections between related posets — an approach of special interest for category theoretic investigations of the concept.

Semilattices as algebraic structures

A "meet-semilattice" is an algebraic structure Failed to parse (Missing texvc executable; please see math/README to configure.): \lang S,\wedge \rang

consisting of a set S with the binary operation Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge

, called meet, such that for all members x, y, and z of S, the following identities hold:

• Associativity: Failed to parse (Missing texvc executable; please see math/README to configure.): x \wedge (y \wedge z) = (x \wedge y) \wedge z

• Commutativity: Failed to parse (Missing texvc executable; please see math/README to configure.): x \wedge y = y \wedge x

• Idempotency: Failed to parse (Missing texvc executable; please see math/README to configure.): x \wedge x = x

If Failed to parse (Missing texvc executable; please see math/README to configure.): \vee , denoting join, replaces Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge

in the definition just given, a join-semilattice results. Meet and join form a dual pair of binary operations, and meet-semilattice and join-semilattice are dual algebraic structures.

A meet-semilattice Failed to parse (Missing texvc executable; please see math/README to configure.): \lang S,\wedge \rang

is bounded if S includes the distinguished element 1 such that for all x in S, 

Failed to parse (Missing texvc executable; please see math/README to configure.): x \wedge 1 = x

.

1 is the greatest element of S. Dually, Failed to parse (Missing texvc executable; please see math/README to configure.): \lang S,\vee,0 \rang

is a join-semilattice with least element 0 if Failed to parse (Missing texvc executable; please see math/README to configure.): \vee
and 0 replace Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge
and 1, respectively, in the definition just given.

A semilattice is an idempotent, commutative semigroup, and a bounded semilattice is an idempotent commutative monoid. Alternatively, a semilattice is a commutative band. Hence semilattices are magmas.

Connection between both definitions

An order theoretic meet-semilattice Failed to parse (Missing texvc executable; please see math/README to configure.): \lang S,\leq \rang

gives rise to a binary operation Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge
such that Failed to parse (Missing texvc executable; please see math/README to configure.): \lang S,\wedge \rang 
is an algebraic meet-semilattice. Conversely, the meet-semilattice Failed to parse (Missing texvc executable; please see math/README to configure.): \lang S,\wedge \rang 
gives rise to a binary relation ≤ that partially orders S in the following way. For all elements x and y in S,

Failed to parse (Missing texvc executable; please see math/README to configure.): x \leq y \harr x = x \wedge y

.

The relation ≤ introduced in this way defines a partial ordering from which the binary operation Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge

may be recovered. Conversely, the order induced by the algebraically defined semilattice Failed to parse (Missing texvc executable; please see math/README to configure.): \lang S,\wedge \rang 
coincides with that induced by ≤.

Hence both definitions may be used interchangeably, depending on which one is more convenient for a particular purpose. A similar conclusion holds for join-semilattices and the dual ordering ≥.

Examples

Semilattices are employed to construct other order structures, or in conjunction with other completeness properties.

• A lattice is both a join- and a meet-semilattice. The interaction of these two semilattices via the absorption law is what truly distinguishes a lattice from a semilattice.
• The compact elements of an algebraic lattice, under the induced partial ordering, form a bounded join-semilattice.
• Any tree structure (with the root as the least element) is a meet-semilattice. Consider for example the set of finite words over some alphabet, ordered by the prefix ordering. It has a least but no greatest element: the root is the meet of all other elements.
• A Scott domain is a meet-semilattice.
• Membership in any set L can be taken as a model of a semilattice with base set L, because a semilattice captures the essence of set extensionality. Let a∧b denote a∈L & b∈L. Two sets differing only in one or both of the:

1. Order in which their members are listed;
2. Multiplicity of one or more members,

are in fact the same set. Commutativity and associativity of ∧ assure (1), idempotence, (2). This semilattice is not bounded by L, because a set is not a member of itself.

• Classical extensional mereology defines a join semilattice, with join read as binary fusion. This semilattice is bounded from above by the world individual.

Semilattice morphisms

The above algebraic definition of a semilattice suggests a notion of morphism between two semilattices. Given two join-semilattices (S,Failed to parse (Missing texvc executable; please see math/README to configure.): \vee ) and (T,Failed to parse (Missing texvc executable; please see math/README to configure.): \vee ), a homomorphism of (join-) semilattices is a function f: S → T such that

Failed to parse (Missing texvc executable; please see math/README to configure.): f(x \vee y) = f(x) \vee f(y)

.

Hence f is just a homomorphism of the two semigroups associated with each semilattice. If S and 'T both include a least element 0, then f should also be a monoid homomorphism, i.e. we additionally require that

Failed to parse (Missing texvc executable; please see math/README to configure.): f(0) = 0

.

In the order-theoretic formulation, these conditions just state that a homomorphism of join-semilattices is a function that preserves binary joins and least elements, if such there be. The obvious dual--replacing Failed to parse (Missing texvc executable; please see math/README to configure.): \wedge

with Failed to parse (Missing texvc executable; please see math/README to configure.): \vee
and 0 with 1--transforms this definition of a join-semilattice homomorphism into its meet-semilattice equivalent.

Note that any semilattice homomorphism is necessarily monotone with respect to the associated ordering relation. For an explanation see the entry preservation of limits.

Equivalence with algebraic lattices

There is a well-known equivalence between the category Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{S}

of join-semilattices with zero with Failed to parse (Missing texvc executable; please see math/README to configure.): (\vee,0)

-homomorphisms and the category Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{A}

of algebraic lattices with compactness-preserving complete join-homomorphisms, as follows. With a join-semilattice Failed to parse (Missing texvc executable; please see math/README to configure.): S
with zero, we associate its ideal lattice Failed to parse (Missing texvc executable; please see math/README to configure.): \mathrm{Id}\ S

. With a Failed to parse (Missing texvc executable; please see math/README to configure.): (\vee,0) -homomorphism Failed to parse (Missing texvc executable; please see math/README to configure.): f : S \to T

of Failed to parse (Missing texvc executable; please see math/README to configure.): (\vee,0)

-semilattices, we associate the map Failed to parse (Missing texvc executable; please see math/README to configure.): \mathrm{Id}\ f : \mathrm{Id}\ S \to \mathrm{Id}\ T , that with any ideal Failed to parse (Missing texvc executable; please see math/README to configure.): I

of Failed to parse (Missing texvc executable; please see math/README to configure.): S
associates the ideal of Failed to parse (Missing texvc executable; please see math/README to configure.): T
generated by Failed to parse (Missing texvc executable; please see math/README to configure.): f(I)

. This defines a functor Failed to parse (Missing texvc executable; please see math/README to configure.): \mathrm{Id} : \mathcal{S} \to \mathcal{A} . Conversely, with every algebraic lattice Failed to parse (Missing texvc executable; please see math/README to configure.): A

we associate the Failed to parse (Missing texvc executable; please see math/README to configure.): (\vee,0)

-semilattice Failed to parse (Missing texvc executable; please see math/README to configure.): K(A)

of all compact elements of Failed to parse (Missing texvc executable; please see math/README to configure.): A

, and with every compactness-preserving complete join-homomorphism Failed to parse (Missing texvc executable; please see math/README to configure.): f : A \to B

between algebraic lattices we associate the restriction Failed to parse (Missing texvc executable; please see math/README to configure.): K(f) : K(A) \to K(B)

. This defines a functor Failed to parse (Missing texvc executable; please see math/README to configure.): K : \mathcal{A} \to \mathcal{S} . The pair Failed to parse (Missing texvc executable; please see math/README to configure.): (\mathrm{Id},K)

defines a category equivalence between Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{S}
and Failed to parse (Missing texvc executable; please see math/README to configure.): \mathcal{A}

.

Distributive semilattices

Surprisingly, there is a notion of "distributivity" applicable to semilattices, even though distributivity conventionally requires the interaction of two binary operations. This notion requires but a single operation, and generalizes the distributivity condition for lattices. See the entry distributivity (order theory).

Complete semilattices

Nowadays, the term "complete semilattice" has no generally accepted meaning, and various inconsistent definitions exist. If completeness is taken to require the existence of all infinite joins and meets, whichever the case may be, as well as finite ones, this immediately leads to partial orders that are in fact complete lattices. For why the existence of all possible infinite joins entails the existence of all possible infinite meets (and vice versa), see the entry completeness (order theory).

Nevertheless, the literature on occasion still takes complete join- or meet-semilattices to be complete lattices. In this case, "completeness" denotes a restriction on the scope of the homomorphisms. Specifically, a complete join-semilattice requires that the homomorphisms preserve all joins, but contrary to the situation we find for completeness properties, this does not require that homomorphisms preserve all meets. On the other hand, we can conclude that every such mapping is the lower adjoint of some Galois connection. The corresponding (unique) upper adjoint will then be a homomorphism of complete meet-semilattices. This gives rise to a number of useful categorical dualities between the categories of all complete semilattices with morphisms preserving all meets or joins, respectively.

Another usage of "complete meet-semilattice" refers to a bounded complete cpo. A complete meet-semilattice in this sense is arguably the "most complete" meet-semilattice that is not necessarily a complete lattice. Indeed, a complete meet-semilattice has all non-empty meets (which is equivalent to being bounded complete) and all directed joins. If such a structure has also a greatest element (the meet of the empty set), it is also a complete lattice. Thus a complete semilattice turns out to be "a complete lattice possibly lacking a top". This definition is of interest specifically in domain theory, where bounded complete algebraic cpos are studied as Scott domains. Hence Scott domains have been called algebraic semilattices.

Free semilattices

This section presupposes some knowledge of category theory. In various situations, free semilattices exist. For example, the forgetful functor from the category of join-semilattices (and their homomorphisms) to the category of sets (and functions) admits a left adjoint. Therefore, the free join-semilattice F(S) over a set S is constructed by taking the collection of all non-empty finite subsets of S, ordered by subset inclusion. Clearly, S can be embedded into F(S) by a mapping e that takes any element s in S to the singleton set {s}. Then any function f from a S to a join-semilattice T (more formally, to the underlying set of T) induces a unique homomorphism f' between the join-semilattices F(S) and T, such that f = f' o e. Explicitly, f' is given by f' (A) = Failed to parse (Missing texvc executable; please see math/README to configure.): \vee {f(s) | s in S}. Now the obvious uniqueness of f' suffices to obtain the required adjunction -- the morphism-part of the functor F can be derived from general considerations (see adjoint functors). The case of free meet-semilattices is dual, using the opposite subset inclusion as an ordering. For join-semilattices with bottom, we just add the empty set to the above collection of subsets.

In addition, semilattices often serve as generators for free objects within other categories. Notably, both the forgetful functors from the category of frames and frame-homomorphisms, and from the category of distributive lattices and lattice-homomorphisms, have a left adjoint.

References

Regrettably, it is often the case that standard treatments of lattice theory define a semilattice, if that, and then say no more. See the references in the entries order theory and lattice theory. Moreover, there is no literature on semilattices of comparable magnitude to that on semigroups.

See also

• order theory
• list of order topics
• lattice theory
• join
• meet

External links

• Jipsen's algebra structures page: Semilattices.it:Semireticolo