[Home]Semilattices

HomePage | RecentChanges | Preferences

Abbreviation: Slat

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).

Some results

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]

Search for finite semilattices

Subclasses

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

Superclasses

Commutative semigroups
[Partial semilattices]?


HomePage | RecentChanges | Preferences
This page is read-only | View other revisions
Last edited September 4, 2008 7:47 pm (diff)
Search: