In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite 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 algebraically: join and meet are associative, commutative, idempotent binary operations, 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 absorption laws.
Order-theoretic definition A set S partially ordered by the binary relation ≤ is a meet-semilattice if
For all elements x and y of S, the greatest lower bound of the set {x, y} exists. The greatest lower bound of the set {x, y} is called the meet of x and y, denoted x ∧ y. Replacing "greatest lower bound" with "least upper bound" results in the dual concept of a join-semilattice. The least upper bound of {x, y} is called the join of x and y, denoted x ∨ y. Meet and join are binary operations on S. 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 theoretic investigations of the concept.
Algebraic definition A meet-semilattice is an algebraic structure ⟨ S , ∧ ⟩ {\displaystyle \langle S,\land \rangle } consisting of a set S with a binary operation ∧, called meet, such that for all members x, y, and z of S, the following identities hold:
Associativity x ∧ (y ∧ z) = (x ∧ y) ∧ z Commutativity x ∧ y = y ∧ x Idempotency x ∧ x = x A meet-semilattice ⟨ S , ∧ ⟩ {\displaystyle \langle S,\land \rangle } is bounded if S includes an identity element 1 such that x ∧ 1 = x for all x in S. 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 commutative, idempotent 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 x ≤ y whenever x ∧ y = x. For a join-semilattice, the order is induced by setting x ≤ y whenever x ∨ y = y. In a bounded meet-semilattice, the identity 1 is the greatest element of S. Similarly, an identity element in a join semilattice is a least element.
Connection between the two definitions An order theoretic meet-semilattice ⟨S, ≤⟩ gives rise to a binary operation ∧ such that ⟨S, ∧⟩ is an algebraic meet-semilattice. Conversely, the meet-semilattice ⟨S, ∧⟩ gives rise to a binary relation ≤ that partially orders S in the following way: for all elements x and y in S, x ≤ y if and only if x = x ∧ y. 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 ⟨S, ∧⟩ 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.
… excerpt ends here. Continue reading the full article.
