# Differences

This shows you the differences between two versions of the page.

semilattices [2010/07/29 18:30] (current)
Line 1: Line 1:
+=====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.
+
+
+====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\}$.
+==Morphisms==
+Let $\mathbf{S}$ and $\mathbf{T}$ be semilattices. A morphism from $\mathbf{S}$ to $\mathbf{T}$ is a function $h:Sarrow T$ that is a homomorphism:
+
+$h(xy)=h(x)h(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]]  | |
+^[[Definable principal congruences]]  | |
+^[[Equationally def. pr. cong.]]  | |
+^[[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--53[[MRreview]]
+
+[[Search for finite semilattices]]
+
+====Subclasses====
+[[One-element algebras]]
+
+[[Semilattices with zero]]
+
+[[Semilattices with identity]]
+
+====Superclasses====
+[[Commutative semigroups]]
+
+[[Partial semilattices]]
+
+
+====References====
+
+[(Ln19xx>
+)]