nLab presemilattice

Idea

Presemilattices are semilattices which do not necessarily satisfy antisymmetry.

Definition

In the same way as semilattices, presemilattices can be defined in an algebraic or an order-theoretic fashion. In the algebraic definition, one uses an equivalence relation $\equiv$ instead of equality $=$ to define the equational axioms of the algebraic structure (commutativity, associativity, etc) as well as axioms that the algebraic operations are $\equiv$-extensional, similarly to the setoid approach to algebra. In the order-theoretic definition, one assumes a preorder instead of a partial order, and defines a join-presemilattice as a preorder with binary joins and a meet-presemilattice as a preorder with binary meets.

Definition

An algebraic presemilattice is a set $A$ with an equivalence relation $\equiv$ and a binary operation $\cdot$ on $A$ which is

1. $\equiv$-extensional in that for all elements $w \in A$, $x \in A$, $y \in A$, $z \in A$, if $w \equiv y$ and $x \equiv z$, then $w \cdot x \equiv y \cdot z$.

2. associative in that for all elements $x \in A$, $y \in A$, $z \in A$, $(x \cdot y) \cdot z \equiv x \cdot (y \cdot z)$.

3. commutative in that for all elements $x \in A$ and $y \in A$, $x \cdot y \equiv y \cdot x$.

4. idempotent in that for all elements $x \in A$, $x \cdot x \equiv x$.

Definition

A join-presemilattice is a set $A$ with a preorder $\leq$ and a binary operation $\vee$ on $A$ such that for all $x \in A$ and $y \in A$, $x \leq x \vee y$ and $y \leq x \vee y$.

Definition

A meet-presemilattice is a set $A$ with a preorder $\leq$ and a binary operation $\wedge$ on $A$ such that for all $x \in A$ and $y \in A$, $x \wedge y \leq x$ and $x \wedge y \leq y$.

These definitions of a presemilattice are equivalent to each other. Given a join-presemilattice, the opposite preorder on the set is a meet-presemilattice, and given a meet-presemilattice, the opposite preorder on the set is a join-presemilattice. The equivalence relation on a join-presemilattice or a meet-presemilattice is defined as $x \equiv y \coloneqq x \leq y \wedge y \leq x$, and the binary relation on a join-presemilattice or a meet-presemilattice is an algebraic presemilattice with respect to the equivalence relation $\equiv$. Conversely, every algebraic presemilattice can be made into a join-presemilattice by defining $x \leq y \coloneqq x \cdot y \equiv y$ or a meet-presemilattice by defining $x \leq y \coloneqq x \cdot y \equiv x$.

The quotient set of a presemilattice by its equivalence relation $x \equiv y$ is a semilattice.

Bounded and unbounded presemilattices

Similarly to semilattices, there is also the question of whether presemilattices are bounded or not, in the sense of a bounded lattice. With the algebraic definition of a presemilattice, one could either assume that presemilattices have neutral elements $1$ or absorbing elements $0$ or both. This yields four different kinds of presemilattices:

• those presemilattices without either neutral elements or absorbing elements are unbounded presemilattices

• those presemilattices with only neutral elements are bounded presemilattices

• those presemilattices with only absorbing elements do not seem to have a name in the literature, but are still bounded from the opposite direction

• those presemilattices with both neutral and absorbing elements are 01-bounded presemilattices

In a join-presemilattice, the top element, if it exists, is a neutral element and the bottom element, if it exists, is an absorbing element for the join operation. Likewise, in a meet-presemilattice, the bottom element, if it exists, is a neutral element and the top element, if it exists, is an absorbing element for the meet operation.

As a category

• A bounded meet-presemilattice is equivalently a cartesian monoidal preorder, a thin cartesian monoidal category.

• A bounded join-presemilattice is equivalently a cocartesian monoidal preorder, a thin cocartesian monoidal category.

• An unbounded meet-presemilattice is equivalently a thin locally cartesian category.

• An unbounded join-presemilattice is equivalently a thin category whose opposite category is a locally cartesian category.

 Related concepts

• preorder

• prelattice

• semilattice

References

• Norman R. Reilly, Enlarging the Munn representation of inverse semigroups, Journal of the Australian Mathematical Society. 1977;23(1):28-41. [doi:10.1017/S1446788700017316]

• Uri Andrews, Andrea Sorbi, Effective Inseparability, Lattices, and Preordering Relations, The Review of Symbolic Logic. 2021;14(4):838-865. [doi:10.1017/S1755020319000273, arXiv:1901.06136]