Semilattice
A semilattice is an algebraic structure consisting of a set S equipped with a binary operation * that is associative (x * (y * z) = (x * y) * z), commutative (x * y = y * x), and idempotent (x * x = x) for all x, y, z \in S.[1] Equivalently, from an order-theoretic perspective, a semilattice is a partially ordered set (poset) in which every pair of elements has a least upper bound, called a join-semilattice, or a greatest lower bound, called a meet-semilattice.[2] The two characterizations are linked by defining the order x \leq y if and only if x * y = y (for a join operation) or x * y = x (for a meet operation), yielding a poset where the operation corresponds to the supremum or infimum.[3] Semilattices form the foundation of lattice theory, with lattices extending them by including both a join (\vee) and meet (\wedge) operation that satisfy absorption laws, such as x \wedge (x \vee y) = x.[4] The broader field of lattice theory traces its origins to Richard Dedekind's work on "Dualgruppen" in the 1890s (published 1897 and 1900), which connected algebraic structures to order theory, and was formalized and advanced by Garrett Birkhoff in the 1930s as part of the development of universal algebra alongside lattices, groups, and rings. The concept of semilattice as a distinct structure was introduced around 1937 by Grigore Moisil.[4][5] Finite meet-semilattices with a greatest element are themselves lattices, and complete semilattices—where every subset has a supremum or infimum—underlie more advanced structures like complete lattices.[1] Notable examples include the power set \mathcal{P}(X) of a set X under union (a join-semilattice) or intersection (a meet-semilattice), where the order is subset inclusion.[1] The free join-semilattice generated by a finite set with n elements consists of all nonempty finite subsets of that set under union, totaling $2^n - 1 elements.[3] Semilattices appear in diverse applications, including universal algebra for studying varieties of algebras, computer science for modeling domains in denotational semantics, and combinatorics for analyzing poset extensions and geometric structures.[3]Fundamental Definitions
Order-Theoretic Definition
A partially ordered set, or poset, is a set equipped with a binary relation \leq that is reflexive (x \leq x for all x), antisymmetric (if x \leq y and y \leq x, then x = y), and transitive (if x \leq y and y \leq z, then x \leq z).[6] A join-semilattice is a poset in which every pair of elements has a least upper bound, called the supremum or join and denoted x \vee y, satisfying x \leq x \vee y, y \leq x \vee y, and for any z with x \leq z and y \leq z, x \vee y \leq z.[6] Dually, a meet-semilattice is a poset in which every pair of elements has a greatest lower bound, called the infimum or meet and denoted x \wedge y, satisfying x \wedge y \leq x, x \wedge y \leq y, and for any z with z \leq x and z \leq y, z \leq x \wedge y.[6] Semilattices are often understood as join-semilattices by convention unless otherwise specified, with meet-semilattices treated symmetrically via order reversal.[6] In a join-semilattice (or meet-semilattice), the existence of binary suprema (or infima) extends to all finite nonempty subsets by iterated application, provided the poset is such that these operations are well-defined; for instance, in bounded posets with a top element, the full supremum of a finite set aligns with the join structure.[7] To illustrate suprema in a simple poset, consider a chain \{a, b, c\} with a \leq b \leq c: the supremum of \{a, b\} is b, and of \{a, c\} is c. In an antichain \{p, q, r\} where no two elements are comparable, adding a top element t above all yields p \vee q = t.For infima, reverse the order: in the chain, the infimum of \{b, c\} is b; in a bottom-bounded antichain, all pairs meet at the bottom.[6]t /|\ p q r (antichain with top)t /|\ p q r (antichain with top)
Algebraic Definition
In universal algebra, a join-semilattice is a set S together with a binary operation \vee: S \times S \to S satisfying the following axioms for all x, y, z \in S:- Associativity: x \vee (y \vee z) = (x \vee y) \vee z,
- Commutativity: x \vee y = y \vee x,
- Idempotence: x \vee x = x.
Relationships and Equivalences
Connection Between the Two Definitions
The order-theoretic and algebraic definitions of a semilattice are equivalent under standard conditions, allowing the two perspectives to be interchanged freely. Specifically, for a join-semilattice, given a partially ordered set (S, \leq) where every pair of elements has a least upper bound (supremum) denoted x \vee y, this supremum operation induces a binary operation on S that is associative, commutative, and idempotent. Conversely, starting from an algebraic structure (S, \vee) where \vee is a binary operation satisfying associativity (x \vee (y \vee z) = (x \vee y) \vee z), commutativity (x \vee y = y \vee x), and idempotence (x \vee x = x) for all x, y, z \in S, one can define a partial order by x \leq y if and only if x \vee y = y; this yields a poset where the original \vee serves as the supremum operation.[6][2] To establish this equivalence, consider the forward direction: the supremum \vee in the poset satisfies the required algebraic properties by the universal mapping property of least upper bounds. For instance, idempotence follows from x \leq x \vee x and x \vee x \leq x, while associativity arises because the supremum of three elements equals the iterated supremum of pairs. In the reverse direction, the induced relation \leq is reflexive (x \vee x = x), antisymmetric (if x \vee y = y and y \vee x = x, then x = y), and transitive (if x \vee y = y and y \vee z = z, then x \vee z = (x \vee y) \vee z = y \vee z = z), forming a partial order; moreover, for any x, y, x \vee y is the least upper bound since it exceeds both and any common upper bound z satisfies x \vee y \leq z by the operation's properties. The associativity x \vee (y \vee z) = (x \vee y) \vee z in the algebraic structure can be verified in the induced order via absorption-like arguments, where the order ensures the iterated suprema coincide.[10][11] The dual holds for meet-semilattices: in a poset (S, \leq) with greatest lower bounds (infima) x \wedge y, the meet operation is associative, commutative, and idempotent. Conversely, from an algebraic (S, \wedge) with these properties, define x \leq y if and only if x \wedge y = x, yielding a poset where \wedge is the infimum. The verification mirrors the join case, with antisymmetry and transitivity following analogously.[6][2] In edge cases, bounded semilattices incorporate top or bottom elements, enhancing the structure toward lattices. A join-semilattice with a top element (greatest element $1 such that x \vee 1 = 1) or a meet-semilattice with a bottom element (least element $0 such that $0 \wedge x = 0) satisfies the respective order definitions with these bounds. When both join and meet operations are present and compatible (satisfying absorption laws like x \vee (x \wedge y) = x), the structure becomes a lattice, bridging semilattices to the full algebraic framework.[10][11]Equivalence with Algebraic Lattices
A lattice can be viewed as a semilattice equipped with both a join operation \vee and a meet operation \wedge that are compatible, satisfying absorption laws such as x \vee (x \wedge y) = x and x \wedge (x \vee y) = x, along with associativity, commutativity, and idempotence for both operations.[12] In contrast to a semilattice, which has only one such binary operation, the full lattice structure ensures the existence of both suprema and infima for every pair of elements, with the operations interacting via the distributive law x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z) (and its dual).[12] An algebraic lattice is a complete lattice in which every element is the join of compact elements beneath it, where the compact elements form a join-semilattice closed under finite joins and the lattice operations. This structure establishes an equivalence: an algebraic lattice corresponds precisely to a join-semilattice of compact elements such that every element in the lattice is a join of these compact elements, with the compact elements being join-dense in the lattice.[13] Specifically, the category of algebraic lattices and continuous lattice homomorphisms is equivalent to the category of join-semilattices with zero and certain morphisms, highlighting how the semilattice of compact elements generates the full lattice via arbitrary joins.[14] Every algebraic lattice L is isomorphic to the lattice of ideals of the join-semilattice C(L) formed by its compact elements, where ideals are down-directed subsets closed under finite joins; this representation, akin to Birkhoff's theorem for the distributive case but generalized, links the lattice directly to the semilattice ideals of its compact elements.[15] In this isomorphism, principal ideals generated by compact elements correspond to the compact elements themselves, and arbitrary ideals represent arbitrary joins of compacts, preserving the algebraic structure.[15] In the finite case, every finite semilattice embeds order-preservingly into a finite lattice via its Dedekind-MacNeille completion, which adds the necessary meet operation (and dual joins if needed) to form a complete lattice while preserving the original join-semilattice structure and order.[16] This completion ensures that the semilattice's joins remain intact, extending it minimally to a full lattice where both absorption laws hold alongside the distributive property.[16]Examples and Operations
Basic Examples
One fundamental example of a meet-semilattice is the set of positive integers ordered by divisibility, where a \leq b if and only if a divides b, and the meet operation is the greatest common divisor (gcd).[17] In this structure, the infimum of any two elements a and b is \gcd(a, b), which is the largest integer dividing both, and the order ensures that every pair has a greatest lower bound. Dually, the positive integers form a join-semilattice under the same order, with the join given by the least common multiple (lcm), the smallest integer divisible by both a and b.[18] Another classic illustration is the power set \mathcal{P}(S) of a set S, ordered by inclusion, which serves as both a join-semilattice and a meet-semilattice. The join operation is set union (\cup), providing the least upper bound as the smallest set containing both elements, while the meet is set intersection (\cap), yielding the greatest lower bound as the largest set contained in both.[2] This structure is distributive and bounded, with the empty set as the bottom element and S as the top element. For a finite example, consider the divisor lattice of a positive integer n, consisting of all positive divisors of n ordered by divisibility. This forms a finite distributive lattice, hence both a join- and meet-semilattice, where the join of two divisors is their lcm (also a divisor of n) and the meet is their gcd.[19] It is bounded below by 1 and above by n. The free join-semilattice on a set X is generated by taking all finite non-empty subsets of X and closing under unions, with the join operation as set union; this provides a universal construction where elements of X act as generators without relations beyond associativity and idempotence.[20] Total orders, such as the real numbers under the usual order, form trivial semilattices: the join-semilattice under maximum (where \max(x, y) is the least upper bound) or the meet-semilattice under minimum. However, structures with non-associative binary operations, like certain magmas where (a \cdot b) \cdot c \neq a \cdot (b \cdot c), fail to be semilattices since the operation must be associative.| Structure | Operation | Order Relation | Boundedness |
|---|---|---|---|
| Positive integers | gcd (meet) or lcm (join) | Divisibility (a \mid b) | Bounded below by 1, unbounded above |
| Power set \mathcal{P}(S) | Union (join) or intersection (meet) | Inclusion (\subseteq) | Bounded below by \emptyset, above by S |
| Divisors of n | lcm (join) or gcd (meet) | Divisibility (a \mid b) | Bounded below by 1, above by n (finite) |
| Free join-semilattice on X | Union on finite non-empty subsets | Inclusion (\subseteq) | Bounded below by singletons, unbounded above if X infinite |