|
In mathematical order theory, a semilattice is a
partially ordered set (poset) within which all binary
sets have a supremum (join) or infimum
(meet), respectively. Consequently, one speaks of either a join-semilattice or a
meet-semilattice. Semilattices provide a generalization of the more prominent concept of a lattice and as such provide a natural way to introduce this concept as a
partial order which is both a meet- and a join-semilattice.
In the literature, join-semilattices sometimes are additionally required to have a least element (the join of the empty set). Dually, meet-semilattices may include a greatest element. Wikipedia adheres to the more general
definitions of these concepts and states the existence of least and greatest elements explicitly if needed. Yet, the definitions
below will also discuss the more special cases explicitly in order to provide a convenient reference.
Formal Definition
As a natural consequence of the fact that semilattices are among the most basic "lattice-like" structures, they can be
characterized both in terms of order theory and of universal
algebra. Each of these descriptions is given below.
Semilattices as posets
Consider a partially ordered set (S, ≤). S is a meet-semilattice if
- for all elements x and y of S, the greatest lower bound (meet) of the set {x, y}
exists.
In this situation, the meet of x and y is denoted by x y. Join-semilattices are defined dually as those
posets within which all binary joins exist. The join of two elements will be written as x y. These considerations clearly define binary operations and on semilattices.
As mentioned before, it will be stated explicitly whenever a meet- or join-semilattice is required to have a least or greatest
element. Using an easy induction argument, on can also
conclude the existence of all suprema of non-empty finite subsets in any join-semilattice. Further conclusions may be possible in
the presence of other properties. See the article on completeness in order theory for more discussion on this subject. This article also discusses
how one may rephrase the above definition in terms of the existence of suitable Galois connections between related posets -- an approach that is of special interest for category theoretic investigations of the concept.
Semilattices as algebraic structures
Consider an algebraic structure in the sense of universal algebra, given by (S, ), being a binary operation. S is a meet-semilattice if the following identities hold for all elements x, y, and z in S:
In this situation, is called meet. A
join-semilattice is an algebraic structure (S, ), where satisfies the same axioms as
above -- the difference in notation is only for
convenience, since one has of cause dual interpretations in mind for the two semilattice operations.
Note that the above axioms can be described by saying that (S, ) is an idempotent, commutative semigroup. To define meet-semilattices with greatest elements, one introduces an additional constant 0, that
makes (S, ,0) an idempotent, commutative
monoid. Explicitly, one requires that
- x 0 = x
for all x in S, in addition to (S, ) being a meet-semilattice as introduced before. Again,
join-semilattices with least element are defined similarly, although in this case one prefers 1 to denote the neutral
element.
Connection between both definitions
Obviously, an order theoretic meet-semilattice gives rise to a binary operation . It now can be seen very easily that this operation really makes
(S, ) a meet-semilattice in the
algebraic sense. Maybe more surprisingly, one can also obtain the converse of this result: consider any algebraically defined
meet-semilattice (T, ). Now one can
define a partial order ≤ on T by setting
- x ≤ y iff x = x y
for all elements x and y in T. One can check that the relation ≤ introduced in this way
defines a partial ordering within which binary meets are given through the original operation . Conversely, the order induced by the algebraically defined
semilattice (S, ) that was derived from
the order theoretic formulation above coincides with the original ordering of S.
Hence, the two definitions can be used in an entirely interchangeable way, depending on which of them appears to be more
convenient for a particular purpose. Similar conclusion hold for join-semilattices, where one just derives the order ≤ in a
dual way.
Examples
Semilattices are often used as tools in the contruction of other order structures or in conjunction with further completeness
properties.
- 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 no greatest
but a least element: the roots is the meet of all other elements.
- Of course, any lattice is also an example of both a join- and
a meet-semilatice.
- The compact elements of an algebraic lattice under the
induced order constitute a join-semilattice with bottom.
Morphisms of semilattices
Considering the algebraic definition above, it is easily seen what morphisms
between semilattices should be considered: given two join-semilattices (S, ) and (T, ), a homomorphisms of (join-) semilattices is a function
f : S → T with the property that
- f(x y) =
f(x)
f(y),
i.e. f is just a homomorphism of the two semigroups. If the join-semilattices are furthermore equipped with a least
element 0, then f should also be a morphism of monoids, i.e. one additionally requires that
- f(0) = 0
In the order-theoretical formulation, these conditions just state that a homomorphism of join-semilattices is a function that
preserves binary
joins and in the latter case also least elements. The conditions for homomorphisms of meet-semilattices are the obvious duals
of these definitions.
Note that any homomorphism of (both join- and meet-) semilattices is necessarily monotone with respect to the associated ordering relation. For an explanation see the article on preservation of
limits.
Distributive semilattices
It may be somewhat surprising that there is indeed an established notion of "distributivity" for semilattices, since one
usually considers distributivity as an interaction of two operations. Yet, it turns out that there is a convenient generalization
of the distributivity condition for lattices, which can be stated in presence of a single operation.
See the article on distributivity
(order theory) for a discussion of this concept and its interaction with related notions.
Complete semilattices
Today, the term "complete semilattice" is not a generally established notion and various inconsistent definitions exist. The
main reason for this is that the obvious requirement of the existence of all (finite and infinite) joins and meets, respectively,
immediately leads to partial orders that are in fact complete
lattices. For an explanation why the presence of all joins entails the existence of all meets (and vice versa), see the
article on completeness (order
theory).
Still it is common in some parts of the literature that complete join- or meet-semilattices are taken to be complete lattices.
In this case one usually uses the different names for this concept in order to emphasize a different notion of homomorphism. In a
complete join-semilattice, where one would primarily require the existence of joins, the homomorphisms are required to preserve
only all joins. Contrary to the situation one finds for completeness properties, this does not imply that such a morphism will
preserve all meets. On the other hand, one 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.
In another usage, the term complete meet-semilattice refers to a bounded complete cpo. This definition is justified by the observation
that 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. Whenever such a structure has also a greatest element (the meet of the empty set), it will
certainly be 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. In the light of the above definition, Scott
domains have been called algebraic semilattices.
Free semilattices
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) = {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, one just adds the empty set to the above
colletion 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 fom the category of distributive lattice and lattice-homomorphism have a left adjoint.
Literature
The standard literature contains most of the information given here, although some first introductions may avoid
semilattices. See the article on order theory.
|