semilattices

−Table of Contents

Semilattices

Semilattices

Abbreviation: Slat

Definition

A \emph{semilattice} is a structure $\mathbf{S}=\langle S,\cdot \rangle$ , where $\cdot$ is an infix binary operation, called the \emph{semilattice operation}, such that

$\cdot$ is associative: $(xy)z=x(yz)$

$\cdot$ is commutative: $xy=yx$

$\cdot$ is idempotent: $xx=x$

Remark: This definition shows that semilattices form a variety.

Morphisms

Let $\mathbf{S}$ and $\mathbf{T}$ be semilattices. A morphism from $\mathbf{S}$ to $\mathbf{T}$ is a function $h:S\to T$ that is a homomorphism:

$h(xy)=h(x)h(y)$

Definition

A \emph{join-semilattice} is a structure $\mathbf{S}=\langle S,\leq,\vee\rangle$ , where $\vee$ is an infix binary operation, called the \emph{join}, such that

$\leq$ is a partial order,

$x\leq y\implies x\vee z\leq y\vee z$ and $z\vee x\leq z\vee y$ ,

$x\le x\vee y$ and $y\leq x\vee y$ ,

$x\vee x\leq x$ .

This definition shows that semilattices form a partially-ordered variety.

Definition

A \emph{join-semilattice} is a structure $\mathbf{S}=\langle S,\vee \rangle$ , where $\vee$ is an infix binary operation, called the \emph{join}, such that

$\leq$ is a partial order, where $x\leq y\Longleftrightarrow x\vee y=y$

$x\vee y$ is the least upper bound of $\{x,y\}$ .

Definition

A \emph{meet-semilattice} is a structure $\mathbf{S}=\langle S,\wedge \rangle$ , where $\wedge$ is an infix binary operation, called the \emph{meet}, such that

$\leq$ is a partial order, where $x\leq y\Longleftrightarrow x\wedge y=x$

$x\wedge y$ is the greatest lower bound of $\{x,y\}$ .

Examples

Example 1: $\langle \mathcal{P}_\omega(X)-\{\emptyset\},\cup\rangle$ , the set of finite nonempty subsets of a set $X$ , with union, is the free join-semilattice with singleton subsets of $X$ as generators.

Basic results

Properties

Classtype	variety
Equational theory	decidable in polynomial time
Quasiequational theory	decidable
First-order theory	undecidable
Locally finite	yes
Residual size	2
Congruence distributive	no
Congruence modular	no
Congruence meet-semidistributive	yes
Congruence n-permutable	no
Congruence regular	no
Congruence uniform	no
Congruence extension property	yes
Definable principal congruences	yes
Equationally def. pr. cong.	no
Amalgamation property	yes
Strong amalgamation property	yes
Epimorphisms are surjective	yes

\end{table}

Finite members

$\begin{array}{lr} f(1)= &1 f(2)= &1 f(3)= &2 f(4)= &5 f(5)= &15 f(6)= &53 f(7)= &222 f(8)= &1078 f(9)= &5994 f(10)= &37622 f(11)= &262776 f(12)= &2018305 f(13)= &16873364 f(14)= &152233518 f(15)= &1471613387 f(16)= &15150569446 f(17)= &165269824761 \end{array}$

These results follow from the paper below and the observation that semilattices with $n$ elements are in 1-1 correspondence to lattices with $n+1$ elements.

Jobst Heitzig,J\“urgen Reinhold,\emph{Counting finite lattices}, Algebra Universalis, \textbf{48}2002,43–53MRreview