Semilattice

 ( Lattice Theory ) 

In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty set finite set subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a meet (or greatest lower bound) for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.

Semilattices can also be defined algebra: join and meet are associativity, commutativity, idempotency , and any such operation induces a partial order (and the respective inverse order) such that the result of the operation for any two elements is the least upper bound (or greatest lower 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 .

---

Order-theoretic definition A set partially ordered by the binary relation is a meet-semilattice if

For all elements and of , the infimum of the set exists.

The greatest lower bound of the set is called the meet of and denoted

Replacing "greatest lower bound" with "supremum" results in the dual concept of a join-semilattice. The least upper bound of is called the join of and , denoted . Meet and join are on 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 theory investigations of the concept.

---

Algebraic definition A meet-semilattice is an algebraic structure $\backslash langle\; S,\; \backslash land\; \backslash rangle$ consisting of a set with a binary operation , called meet, such that for all members and of the following identities hold:

Associativity

Commutativity

Idempotency

A meet-semilattice $\backslash langle\; S,\; \backslash land\; \backslash rangle$ is bounded if includes an identity element 1 such that for all in

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 commutativity, idempotency 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 Similarly, an identity element in a join semilattice is a least element.

---

Connection between the two 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 in the following way: for all elements and in if and only if

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 the two 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 of an algebraic lattice, under the induced partial ordering, form a bounded join-semilattice.
• By induction on the number of elements, any non-empty finite meet semilattice has a least element and any non-empty finite join semilattice has a greatest element. (In neither case will the semilattice necessarily be bounded.)
• A totally ordered set is a distributive lattice, hence in particular a meet-semilattice and join-semilattice: any two distinct elements have a greater and lesser one, which are their meet and join.
• A well-ordered set is further a bounded join-semilattice, as the set as a whole has a least element, hence it is bounded.
• The natural numbers $\backslash mathbb\{N\}$, with their usual order are a bounded join-semilattice, with least element 0, although they have no greatest element: they are the smallest infinite well-ordered set.
• Any single-rooted tree (with the single root as the least element) of height $\backslash leq\; \backslash omega$ is a (generally unbounded) meet-semilattice. Consider for example the set of finite words over some alphabet, ordered by the prefix order. It has a least element (the empty word), which is an annihilator element of the meet operation, but no greatest (identity) element.
• A Scott domain is a meet-semilattice.
• Membership in any set can be taken as a model theory of a semilattice with base set because a semilattice captures the essence of set extensionality. Let denote & Two sets differing only in one or both of the:
• Order in which their members are listed;
• Multiplicity of one or more members,

are in fact the same set. Commutativity and associativity of assure (1), idempotence, (2). This semilattice is the free semilattice over It is not bounded by 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.
• Given a set the collection of partitions $\backslash xi$ of is a join-semilattice. In fact, the partial order is given by $\backslash xi\; \backslash leq\; \backslash eta$ if $\backslash forall\; Q\; \backslash in\; \backslash eta,\; \backslash exists\; P\; \backslash in\; \backslash xi$ such that $Q\; \backslash subset\; P$ and the join of two partitions is given by $\backslash xi\; \backslash vee\; \backslash eta\; =\; \backslash \{\; P\; \backslash cap\; Q\; \backslash mid\; P\; \backslash in\; \backslash xi\; \backslash \; \backslash land\; \backslash \; Q\; \backslash in\; \backslash eta\; \backslash \}$. This semilattice is bounded, with the least element being the singleton partition $\backslash \{\; S\; \backslash \}$.

---

Semilattice morphisms The above algebraic definition of a semilattice suggests a notion of morphism between two semilattices. Given two join-semilattices and , a homomorphism of (join-) semilattices is a function such that

Hence is just a homomorphism of the two semigroups associated with each semilattice. If and both include a least element 0, then 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.

Any semilattice homomorphism is necessarily monotone with respect to the associated ordering relation.

---

Equivalence with algebraic lattices There is a well-known equivalence between the category $\backslash mathcal\{S\}$ of join-semilattices with zero with $(\backslash vee,0)$-homomorphisms and the category $\backslash mathcal\{A\}$ of algebraic lattices with compact element-preserving complete join-homomorphisms, as follows. With a join-semilattice $S$ with zero, we associate its ideal lattice $\backslash operatorname\{Id\}\backslash \; S$. With a $(\backslash vee,0)$-homomorphism $f\; \backslash colon\; S\; \backslash to\; T$ of $(\backslash vee,0)$-semilattices, we associate the map $\backslash operatorname\{Id\}\backslash \; f\; \backslash colon\; \backslash operatorname\{Id\}\backslash \; S\; \backslash to\; \backslash operatorname\{Id\}\backslash \; T$, that with any ideal $I$ of $S$ associates the ideal of $T$ generated by $f(I)$. This defines a functor $\backslash operatorname\{Id\}\; \backslash colon\; \backslash mathcal\{S\}\; \backslash to\; \backslash mathcal\{A\}$. Conversely, with every algebraic lattice $A$ we associate the $(\backslash vee,0)$-semilattice $K(A)$ of all of $A$, and with every compactness-preserving complete join-homomorphism $f\; \backslash colon\; A\; \backslash to\; B$ between algebraic lattices we associate the restriction $K(f)\; \backslash colon\; K(A)\; \backslash to\; K(B)$. This defines a functor $K\; \backslash colon\; \backslash mathcal\{A\}\; \backslash to\; \backslash mathcal\{S\}$. The pair $(\backslash operatorname\{Id\},K)$ defines a category equivalence between $\backslash mathcal\{S\}$ and $\backslash 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. A join-semilattice is distributive if for all and with there exist and such that 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 (order theory).

A join-semilattice is distributive if and only if the lattice of its ideals (under inclusion) is distributive.

---

Complete semilattices Nowadays, the term "complete semilattice" has no generally accepted meaning, and various mutually 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 . 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 . 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 set 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 poset cpos are studied as . Hence Scott domains have been called algebraic semilattices.

Cardinality-restricted notions of completeness for semilattices have been rarely considered in the literature.E. G. Manes, Algebraic theories, Graduate Texts in Mathematics Volume 26, Springer 1976, p. 57

---

Free semilattices This section presupposes some knowledge of category theory. In various situations, free object semilattices exist. For example, the forgetful functor from the category of join-semilattices (and their homomorphisms) to the category theory of sets (and functions) admits a adjoint functors. Therefore, the free join-semilattice over a set is constructed by taking the collection of all non-empty finite of ordered by subset inclusion. Clearly, can be embedded into by a mapping that takes any element in to the singleton set Then any function from a to a join-semilattice (more formally, to the underlying set of ) induces a unique homomorphism between the join-semilattices and such that Explicitly, is given by $f\text{'}(A)\; =\; \backslash bigvee\backslash \{f(s)\; |\; s\; \backslash in\; A\backslash \}.$ Now the obvious uniqueness of suffices to obtain the required adjunction—the morphism-part of the functor 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.

---

See also

• generalization of join semilattice

---

Notes

• (2025). 9780521784511, Cambridge University Press. ISBN 9780521784511
• Steven Vickers (1989). 9780521360623, Cambridge University Press. ISBN 9780521360623

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 .

---

External links

• Jipsen's algebra structures page: Semilattices.

Post Comment