# 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> | ||

+ | )] |

Trace: