# Lattices

HomePage | RecentChanges | Preferences

### Definition

A lattice is a structure L = (L,∨,∧), where and are infix binary operations called the join and meet, such that
∨,∧ are associative:   (xy)∨z = x∨(yz), (xy)∧z = x∧(yz)
∨,∧ are commutative:   xy = yx, xy = yx, and
∨,∧ are absorbtive:   (xy)∧x = x, (xy)∨x = x.

Remark: It follows that and are idempotent: xx = x, xx = x.
This definition shows that lattices form a variety.
A partial order  ≤  is definable in any lattice by x ≤ y  ⇔   xy = x, or equivalently by x ≤ y  ⇔   xy = y.

### Morphisms

Let L and M be lattices. A morphism from L to M is a function h : LM that is a homomorphism: h(xy) = h(x)∨h(y)  and  h(xy) = h(x)∧h(y).

### Definition

A lattice is a structure L = (L,∨,∧) of type (2,2) such that
(L,∨) and (L,∧) are semilattices, and
∨,∧ are absorbtive:   (xy)∧x = x, (xy)∨x = x.

### Definition

A lattice is a structure L = (L, ≤ ) that is a poset in which all elements x,y ∈ L have a
least upper bound:   z = xy  ⇔   x ≤ z  and  y ≤ z  and   ∀w (x ≤ w  and  y ≤ w  ⇒  z ≤ w), and
greatest lower bound:   z = xy  ⇔   z ≤ x  and  z ≤ y  and   ∀w (w ≤ x  and  w ≤ y  ⇒  w ≤ z).

### Definition

A lattice is a structure L = (L,∨,∧, ≤ ) such that (L, ≤ ) is a poset and the following quasiequations hold:
-left:   x ≤ z  and  y ≤ z   ⇒  xy ≤ z,
-right:   z ≤ x  ⇒  z ≤ xy,     z ≤ y  ⇒  z ≤ xy,
-right:   z ≤ x  and  z ≤ y  ⇒  z ≤ xy,
-left:   x ≤ z  ⇒  xy ≤ z,     y ≤ z  ⇒  xy ≤ z.

Remark: These quasiequations give a cut-free Gentzen system to decide the equational theory of lattices.

### Examples

(P(S),∪,∩, ⊆ ), the collection of subsets of a sets S, ordered by inclusion.

### Properties

 Classtype variety Equational theory decidable in polynomial time Quasiequational theory decidable First-order theory undecidable Locally finite no Residual size unbounded Congruence distributive yes [Nenosuke Funayama, Tadasi Nakayama, On the distributivity of a lattice of lattice-congruences, Proc. Imp. Acad. Tokyo 18 (1942) 553--554 MRreview] Congruence modular yes Congruence n-permutable no Congruence regular no Congruence uniform no Congruence extension property no Definable principal congruences no Equationally definable principal congruences no Amalgamation property yes Strong amalgamation property yes [Bjarni Jónsson, Universal relational systems, Math. Scand. 4 (1956) 193--208 MRreview] Epimorphisms are surjective yes

### Finite members

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

[Jobst Heitzig, Jürgen Reinhold, Counting finite lattices, Algebra Universalis 48 (2002) 43--53 MRreview]

[Lattices of size 1 to 6]
Finite lattices of size  ≤ 7
[Subdirectly irreducible lattices]? of size  ≤ 7
[Lattices not in some subclasses]? of size  ≤ 7

### Subclasses

Modular lattices
Semidistributive lattices
Neardistributive lattices
[Join-complete lattices]?
[Meet-complete lattices]?

### Superclasses

Semilattices
[Weakly associative lattices]?

HomePage | RecentChanges | Preferences