# Semilattices

HomePage | RecentChanges | Preferences

### Definition

A semilattice is a structure S = (S,·), where · is an infix binary operation, called the semilattice operation, such that
· is associative:   (xy)z = x(yz),
· is commutative:   xy = yx and
· is idempotent:   xx = x.

Remark: This definition shows that semilattices form a variety.

### Definition

A join-semilattice is a structure S = (S,∨), where is an infix binary operation, called the join, such that
≤  is a partial order, where x ≤ y  ⇔   xy = y and
xy is the least upper bound of {x,y}.

### Definition

A meet-semilattice is a structure S = (S,∧), where is an infix binary operation, called the meet, such that
≤  is a partial order, where x ≤ y  ⇔   xy = xand
xy is the greatest lower bound of {x,y}.

### Morphisms

Let S and T be semilattices. A morphism from S to T is a function h : ST that is a homomorphism: h(xy) = h(x)h(y).

### Examples

(P<i>ω(X)−{Ø},∪), the set of finite nonempty subsets of a set X, with union, is the free join-semilattice with singleton subsets of X as generators.

### 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 definable principal congruences Amalgamation property yes Strong amalgamation property yes Epimorphisms are surjective yes

### Finite members

[Size 1]?:  1
[Size 2]?:  1
[Size 3]?:  2
[Size 4]?:  5
[Size 5]?:  15
[Size 6]?:  53
[Size 7]?:  222
[Size 8]?:  1078
[Size 9]?:  5994
[Size 10]?:  37622
[Size 11]?:  262776
[Size 12]?:  2018305
[Size 13]?:  16873364
[Size 14]?:  152233518
[Size 15]?:  1471613387
[Size 16]?:  15150569446
[Size 17]?:  165269824761

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ürgen Reinhold, Counting finite lattices, Algebra Universalis 48 (2002) 43--53 MRreview]

### Subclasses

[One-element algebras]?
Semilattices with zero
Semilattices with identity

### Superclasses

Commutative semigroups
[Partial semilattices]?

HomePage | RecentChanges | Preferences