Semilattice
|
|
In mathematical order theory, a semilattice is a partially ordered set (poset) within which either all binary sets have either a supremum (join) or all binary sets have an infimum (meet). 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.
| Contents |
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<math>\wedge<math>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<math>\vee<math>y. These considerations clearly define binary operations <math>\wedge<math> and <math>\vee<math> 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, one 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. That 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,<math>\wedge<math>), <math>\wedge<math> being a binary operation. S is a meet-semilattice if the following identities hold for all elements x, y, and z in S:
- x<math>\wedge<math>(y<math>\wedge<math>z) = (x<math>\wedge<math>y)<math>\wedge<math>z (associativity)
- x<math>\wedge<math>y = y <math>\wedge<math> x (commutativity)
- x<math>\wedge<math>x = x (idempotency)
In this situation, <math>\wedge<math> is called meet. A join-semilattice is an algebraic structure (S, <math>\vee<math>), where <math>\vee<math> satisfies the same axioms as <math>\wedge<math> above -- the difference in notation is only for convenience, since one has of course dual interpretations in mind for the two semilattice operations.
Note that the above axioms can be described by saying that (S,<math>\wedge<math>) is an idempotent, commutative semigroup. To define meet-semilattices with greatest elements, one introduces an additional constant 0, that makes (S,<math>\wedge<math>,0) an idempotent, commutative monoid. Explicitly, one requires that
- x <math>\wedge<math> 0 = x
for all x in S, in addition to (S, <math>\wedge<math>) 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 <math>\wedge<math>. It now can be seen very easily that this operation really makes (S, <math>\wedge<math>) 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,<math>\wedge<math>). Now one can define a partial order ≤ on T by setting
- x ≤ y iff x = x<math>\wedge<math>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 <math>\wedge<math>. Conversely, the order induced by the algebraically defined semilattice (S,<math>\wedge<math>) 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. A similar conclusion holds for join-semilattices, where one just derives the order ≤ in a dual way.
Examples
Semilattices are often used as tools in the construction 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-semilattice.
- Any Scott domain is a meet-semilattice.
- 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,<math>\vee<math>) and (T,<math>\vee<math>), a homomorphisms of (join-) semilattices is a function f : S → T with the property that
- f(x<math>\vee<math>y) = f(x) <math>\vee<math> 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) = <math>\vee<math>{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 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 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.it:Semireticolo zh:半格