Semilattice


In mathematics, a join-semilattice is a partially ordered set that has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.
Semilattices can also be defined algebraically: join and meet are associative, commutative, idempotent binary operations, and any such operation induces a partial order such that the result of the operation for any two elements is the least upper bound of the elements with respect to this partial order.
A lattice is a partially ordered set that is both a meet- and join-semilattice with respect to the same partial order. Algebraically, a lattice is a set with two associative, commutative idempotent binary operations linked by corresponding absorption laws.

Order-theoretic definition

A set S partially ordered by the binary relation ≤ is a meet-semilattice if
The greatest lower bound of the set is called the meet of x and y, denoted.
Replacing "greatest lower bound" with "least upper bound" results in the dual concept of a join-semilattice. The least upper bound of is called the join of x and y, denoted. Meet and join are binary operations on S. A simple induction argument shows that the existence of all possible pairwise suprema, as per the definition, implies the existence of all non-empty finite suprema.
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.

Algebraic definition

A meet-semilattice is an algebraic structure consisting of a set S with a binary operation ∧, called meet, such that for all members x, y, and z of S, the following identities hold:
; Associativity: x ∧ = ∧ z
; Commutativity: x ∧ y = y ∧ x
; Idempotency: x ∧ x = x
A meet-semilattice is bounded if S includes an identity element 1 such that for all x in S.
If the symbol ∨, called join, replaces ∧ in the definition just given, the structure is called a join-semilattice. One can be ambivalent about the particular choice of symbol for the operation, and speak simply of semilattices.
A semilattice is a commutative, idempotent semigroup; i.e., a commutative band. A bounded semilattice is an idempotent commutative monoid.
A partial order is induced on a meet-semilattice by setting whenever. For a join-semilattice, the order is induced by setting whenever. In a bounded meet-semilattice, the identity 1 is the greatest element of S. Similarly, an identity element in a join semilattice is a least element.

Connection between both definitions

An order theoretic meet-semilattice gives rise to a binary operation ∧ such that is an algebraic meet-semilattice. Conversely, the meet-semilattice gives rise to a binary relation ≤ that partially orders S in the following way: for all elements x and y in S, x ≤ y if and only if x = x ∧ y.
The relation ≤ introduced in this way defines a partial ordering from which the binary operation ∧ may be recovered. Conversely, the order induced by the algebraically defined semilattice 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.
  1. Order in which their members are listed;
  2. Multiplicity of one or more members,
The above algebraic definition of a semilattice suggests a notion of morphism between two semilattices. Given two join-semilattices and, a homomorphism of semilattices is a function f: S → T such that
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
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 ∧ with ∨ 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 of join-semilattices with zero with -homomorphisms and the category of algebraic lattices with compactness-preserving complete join-homomorphisms, as follows. With a join-semilattice with zero, we associate its ideal lattice. With a -homomorphism of -semilattices, we associate the map, that with any ideal of associates the ideal of generated by. This defines a functor. Conversely, with every algebraic lattice we associate the -semilattice of all compact elements of, and with every compactness-preserving complete join-homomorphism between algebraic lattices we associate the restriction. This defines a functor. The pair defines a category equivalence between and.

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. A join-semilattice is distributive if for all a, b, and x with there exist and such that x = a' ∨ b' . Distributive meet-semilattices are defined dually. These definitions are justified by the fact that any distributive join-semilattice in which binary meets exist is a distributive lattice. See the entry distributivity.
A join-semilattice is distributive if and only if the lattice of its ideals is distributive.

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, or all infinite 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, see the entry completeness.
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 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 and all directed joins. If such a structure has also a greatest element, 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.
Cardinality-restricted notions of completeness for semilattices have been rarely considered in the literature.

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 to the category of sets admits a left adjoint. Therefore, the free join-semilattice F 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 by a mapping e that takes any element s in S to the singleton set. Then any function f from a S to a join-semilattice T induces a unique homomorphism f' between the join-semilattices F and T, such that f = f' o e. Explicitly, f' is given by f' =. 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. 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.