−Table of Contents
Distributive lattices
Abbreviation: DLat
Definition
A \emph{distributive lattice} is a lattice L=⟨L,∨,∧⟩ such that
∧ distributes over ∨: x∧(y∨z)=(x∧y)∨(x∧z)
Definition
A \emph{distributive lattice} is a lattice L=⟨L,∨,∧⟩ such that
∨ distributes over ∧: x∨(y∧z)=(x∨y)∧(x∨z)
Definition
A \emph{distributive lattice} is a lattice L=⟨L,∨,∧⟩ such that
(x∧y)∨(x∧z)∨(y∧z)=(x∨y)∧(x∨z)∧(y∨z)
Definition
A \emph{distributive lattice} is a lattice L=⟨L,∨,∧⟩ such that L has no sublattice isomorphic to the diamond M3 or the pentagon N5
Definition
A \emph{distributive lattice} is a structure L=⟨L,∨,∧⟩ of type ⟨2,2⟩ such that
x∧(x∨y)=x and
x∧(y∨z)=(z∧x)∨(y∧x).1)
Morphisms
Let L and M be distributive lattices. A morphism from L to M is a function h:L→M that is a homomorphism:
h(x∨y)=h(x)∨h(y), h(x∧y)=h(x)∧h(y)
Examples
Example 1: ⟨P(S),∪,∩,⊆⟩, the collection of subsets of a sets S, ordered by inclusion.
Basic results
Properties
Classtype | variety |
---|---|
Equational theory | decidable |
Quasiequational theory | decidable |
First-order theory | undecidable |
Congruence distributive | yes |
Congruence modular | yes |
Congruence n-permutable | no |
Congruence regular | no |
Congruence uniform | no |
Congruence extension property | yes |
Definable principal congruences | no |
Equationally def. pr. cong. & yes, ⟨c,d⟩∈Cg(a,b)⟺(a∧b)∧c=(a∧b)∧d(a∨b)∨c=(a∨b)∨d\\\hline
Finite members
f(1)=1f(2)=1f(3)=1f(4)=2f(5)=3f(6)=5f(7)=8f(8)=15f(9)=26f(10)=47f(11)=82f(12)=151f(13)=269f(14)=494f(15)=891f(16)=1639f(17)=2978f(18)=5483f(19)=10006f(20)=18428
Values known up to size 49 2)