Semilattice
From Free net encyclopedia
In mathematical order theory, a semilattice is a partially ordered set (poset) within which either all binary sets have 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
Semilattices can be characterized both in terms of order theory and of universal algebra. Each of these descriptions is given below.
Semilattices as posets
A partially ordered set (S, ≤) is a meet-semilattice if
- for all elements x and y of S, the greatest lower bound of the set {x, y} exists.
In this situation, the greatest lower bound of the set {x, y} is called the meet of x and y and is denoted by x<math>\wedge</math>y.
Join-semilattices are defined dually as those posets within which for all binary sets the least upper bound exists. The least upper bound of the set {x, y} is called the join of x and y and is denoted by x<math>\vee</math>y. Meet and join define binary operations on semilattices.
The existence of binary suprema implies the existence of all non-empty finite suprema and vice versa. The same holds true for infima, as can be shown by a simple induction argument. A given meet- or join-semilattice need not have a least or greatest element.
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
An algebraic structure (S,<math>\wedge</math>) consisting of a set S and a binary operation <math>\wedge</math> on this set is a semilattice if it is an idempotent, commutative semigroup, i.e. if for all elements x, y, and z in S the following identities hold:
- <math>x \wedge (y \wedge z) = (x \wedge y) \wedge z</math> (associativity)
- <math>x \wedge y = y \wedge x</math> (commutativity)
- <math>x \wedge x = x</math> (idempotency)
In this situation, <math>\wedge</math> is called meet, and (S,<math>\wedge</math>) is called a meet-semilattice. 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.
Any meet-semilattice (S, <math>\wedge</math>) can be extended to a meet-semilattice with greatest element by adding an additional constant 1 and requiring that
- <math> x \wedge 1 = x</math>
for all x in S, thereby making (S,<math>\wedge</math>,1) an idempotent, commutative monoid. Again, join-semilattices with least element are defined dually, although in this case one prefers 0 to denote the neutral element.
Connection between both definitions
Any order theoretic meet-semilattice (S, ≤) gives rise to a binary operation <math>\wedge</math> that makes (S, <math>\wedge</math>) a meet-semilattice in the algebraic sense. Conversely, any algebraically defined meet-semilattice (S,<math>\wedge</math>) can be ordered by setting
- x ≤ y iff x = x<math>\wedge</math>y
for all elements x and y in S. 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 entirely interchangeably, 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 root 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:半格