Semilattices
From Structures
Contents |
Semilattices
Slat
Definition 1
A semilattice is a commutative idempotent semigroup, i.e. a structure $\mathbf{S}=\langle S,\cdot\rangle$, where $\cdot$ is an infix binary operation, called the 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.
Definition 2
A \emph{join-semilattice} is a structure $\mathbf{S}=\left\langle S,\vee \right\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 3
A \emph{meet-semilattice} is a structure $\mathbf{S}=\left\langle S,\wedge \right\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\}$.
Morphisms
Let $\mathbf{S}$ and $\mathbf{T}$ be semilattices. A morphism from $\mathbf{S}$ to $\mathbf{T}$ is a function $h:S\rightarrow T$ that is a homomorphism:
$h(xy)=h(x)h(y)$
Basic Results
Here we phrase the results in terms of join-semilattices, but of course dual results hold for meet-semilattices.
A finite join-semilattice is a lattice iff it has a bottom element, usually denoted by 0.
Any join-semilattice can be extended to a semilattice with 0 by adding a bottom element.
Hence there is a bijective correspondence between semilattices with $n$ elements and lattices with $n+1$ elements.
If $a<b$ in a semilattice then there exists a homomorphism onto the two-element semilattice $\mathbf B_2^\vee=\langle\{0,1\},\vee\rangle$ that separates these two elements: let $h(x)=0$ if $x\le a$ and $h(x)=1$ otherwise, so $h(a)=0$ and $h(b)=1$. Since $x,y\le a$ iff $x\vee y\le a$ we have $h(x)\vee h(y)=0$ iff $h(x\vee y)=0$, hence $h$ is a homomorphism.
Therefore $\mathbf B_2^\vee$ is the only subdirectly irreducible join-semilattice.
The congruence lattice of any semilattice is dually geometric (any congruence is the meet of coatoms).
If $\text{Con}\mathbf S$ is atomic, with set of atoms $A$, then $\mathbf S$ is a unique subdirect product of $|A|$ copies of $\mathbf B_2^\vee$.
[R. Freese, J. B. Nation, Congruence lattices of semilattices, Pacific Journal of Math, 49 (1973) 51-58]
Examples
$\langle \{F\subseteq X:1\le|F|<\infty\},\cup\rangle$, the finite nonempty subsets of a set $X$, with union. This is a construction of the free semilattice generated by $X$.
Properties
Classtype & variety\\\hline Equational theory & decidable in polynomial time\\\hline Quasiequational theory & decidable\\\hline First-order theory & undecidable\\\hline Locally finite & yes\\\hline Residual size & 2\\\hline Congruence distributive & no\\\hline Congruence modular & no\\\hline Congruence meet-semidistributive & yes\\\hline Congruence n-permutable & no\\\hline Congruence regular & no\\\hline Congruence uniform & no\\\hline Congruence extension property & \\\hline Definable principal congruences & \\\hline Equationally def. pr. cong. & \\\hline Amalgamation property & yes\\\hline Strong amalgamation property & yes\\\hline Epimorphisms are surjective & yes\\\hline
Finite members
$f(n)=$ number of members of size $n$.
$\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--53
Search for finite semilattices
