Distributive lattice
Encyclopedia
In mathematics
, distributive lattices are lattices
for which the operations of join and meet distribute
over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union
and intersection
. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is – up to isomorphism
– given as such a lattice of sets.
or of universal algebra
. Both views and their mutual correspondence are discussed in the article on lattices
. In the present situation, the algebraic description appears to be more convenient:
A lattice (L,
, 
) is distributive if the following additional identity holds for all x, y, and z in L:
Viewing lattices as partially ordered sets, this says that the meet operation preserves
non-empty finite joins. It is a basic fact of lattice theory that the above condition is equivalent to its dual
:
More information on the relationship of this condition to other distributivity conditions of order theory can be found in the article on distributivity (order theory)
.
, i.e. a function that is compatible with the two lattice operations. Because such a morphism of lattices preserves the lattice structure, it will consequently also preserve the distributivity (and thus be a morphism of distributive lattices).
the following holds for all elements x, y, z in L:
Similarly, L is distributive if and only if
The simplest non-distributive lattices are M3, the "diamond lattice", and N5, the "pentagon lattice". A lattice is distributive if and only if none of its sublattices is isomorphic to M3 or N5; a sublattice is a subset that is closed under the meet and join operations of the original lattice. Note that this is not the same as being a subset that is a lattice under the original order (but possibly with different join and meet operations). Further characterizations derive from the representation theory in the next section.
Finally distributivity entails several other pleasant properties. For example, an element of a distributive lattice is meet-prime if and only if it is meet-irreducible, though the latter is in general a weaker property. By duality, the same is true for join-prime and join-irreducible elements. If a lattice is distributive, its covering relation
forms a median graph
.
Furthermore, every distributive lattice is also modular
.
and intersection
). That set union and intersection are indeed distributive in the above sense is an elementary fact. The other direction is less trivial, in that it requires the representation theorems stated below. The important insight from this characterization is that the identities (equations) that hold in all distributive lattices are exactly the ones that hold in all lattices of sets in the above sense.
Birkhoff's representation theorem
for distributive lattices states that every finite distributive lattice is isomorphic to the lattice of lower set
s of the poset
of its join-prime (equivalently: join-irreducible) elements. This establishes a bijection
(up to isomorphism
) between the class of all finite posets and the class of all finite distributive lattices. This bijection can be extended to a duality of categories
between homomorphisms of finite distributive lattices and monotone function
s of finite posets. Generalizing this result to infinite lattices, however, requires adding further structure.
Another early representation theorem is now known as Stone's representation theorem for distributive lattices (the name honors Marshall Harvey Stone
, who first proved it). It characterizes distributive lattices as the lattices of compact
open
sets of certain topological space
s. This result can be viewed both as a generalization of Stone's famous representation theorem for Boolean algebras
and as a specialization of the general setting of Stone duality
.
A further important representation was established by Hilary Priestley in her representation theorem for distributive lattices. In this formulation, a distributive lattice is used to construct a topological space with an additional partial order on its points, yielding a (completely order-separated) ordered Stone space
(or Priestley space
). The original lattice is recovered as the collection of clopen
lower sets of this space.
As a consequence of Stone's and Priestley's theorems, one easily sees that any distributive lattice is really isomorphic to a lattice of sets. However, the proofs of both statements require the Boolean prime ideal theorem
, a weak form of the axiom of choice.
distributive lattice over a set of generators G can be constructed much more easily than a general free lattice. The first observation is that, using the laws of distributivity, every term formed by the binary operations
and 
on a set of generators can be transformed into the following equivalent normal form:
where the Mi are finite meets of elements of G. Moreover, since both meet and join are commutative
and idempotent
, one can ignore duplicates and order, and represent a join of meets like the one above as a set of sets:
where the Ni are finite subsets of G. However, it is still possible that two such terms denote the same element of the distributive lattice. This occurs when there are indices j and k such that Nj is a subset of Nk. In this case the meet of Nk will be below the meet of Nj, and hence one can safely remove the redundant set Nk without changing the interpretation of the whole term. Consequently, a set of finite subsets of G will be called irredundant whenever all of its elements Ni are mutually incomparable (with respect to the subset ordering); that is, when it forms an antichain
of finite sets.
Now the free distributive lattice over a set of generators G is defined on the set of all finite irredundant sets of finite subsets of G. The join of two finite irredundant sets is obtained from their union by removing all redundant sets. Likewise the meet of two sets S and T is the irredundant version of { N
M | N in S, M in T}. The verification that this structure is a distributive lattice with the required universal property
is routine.
The number of elements in free distributive lattices with n generators is given by the Dedekind number
s. These numbers grow rapidly, and are known only for n ≤ 8; they are
The numbers above count the number of free distributive lattices in which the lattice operations are joins and meets of finite sets of elements, including the empty set. If empty joins and empty meets are disallowed, the resulting free distributive lattices have two fewer elements; their numbers of elements form the sequence
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, distributive lattices are lattices
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
for which the operations of join and meet distribute
Distributivity
In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalizes the distributive law from elementary algebra.For example:...
over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
and intersection
Intersection (set theory)
In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is – up to isomorphism
Order isomorphism
In the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets . Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that one of...
– given as such a lattice of sets.
Definition
As in the case of arbitrary lattices, one can choose to consider a distributive lattice L either as a structure of order theoryOrder theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
or of universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
. Both views and their mutual correspondence are discussed in the article on lattices
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
. In the present situation, the algebraic description appears to be more convenient:
A lattice (L,
, ) is distributive if the following additional identity holds for all x, y, and z in L:
Viewing lattices as partially ordered sets, this says that the meet operation preserves
Limit-preserving function (order theory)
In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i.e. certain suprema or infima. Roughly speaking, these functions map the supremum/infimum of a set to the supremum/infimum of the image of the set...
non-empty finite joins. It is a basic fact of lattice theory that the above condition is equivalent to its dual
Duality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...
:
More information on the relationship of this condition to other distributivity conditions of order theory can be found in the article on distributivity (order theory)
Distributivity (order theory)
In the mathematical area of order theory, there are various notions of the common concept of distributivity, applied to the formation of suprema and infima...
.
Morphisms
A morphism of distributive lattices is just a lattice homomorphism as given in the article on latticesLattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
, i.e. a function that is compatible with the two lattice operations. Because such a morphism of lattices preserves the lattice structure, it will consequently also preserve the distributivity (and thus be a morphism of distributive lattices).
Examples
Distributive lattices are ubiquitous but also rather specific structures. As already mentioned the main example for distributive lattices are lattices of sets, where join and meet are given by the usual set-theoretic operations. Further examples include:- The Lindenbaum algebraLindenbaum–Tarski algebraIn mathematical logic, the Lindenbaum–Tarski algebra of a logical theory T consists of the equivalence classes of sentences of the theory...
of most logicLogicIn philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
s that support conjunctionLogical conjunctionIn logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
and disjunctionLogical disjunctionIn logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
is a distributive lattice, i.e. "and" distributes over "or" and vice versa.
- Every Boolean algebra is a distributive lattice.
- Every Heyting algebraHeyting algebraIn mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...
is a distributive lattice. Especially this includes all localesComplete Heyting algebraIn mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, and its opposite, the category Frm of frames...
and hence all open setOpen setThe concept of an open set is fundamental to many areas of mathematics, especially point-set topology and metric topology. Intuitively speaking, a set U is open if any point x in U can be "moved" a small amount in any direction and still be in the set U...
lattices of topological spaceTopological spaceTopological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
s. Also note that Heyting algebras can be viewed as Lindenbaum algebras of intuitionistic logicIntuitionistic logicIntuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...
, which makes them a special case of the above example.
- Every totally ordered setTotal orderIn set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
is a distributive lattice with max as join and min as meet. - The natural numberNatural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s form a distributive lattice (complete as a meet-semilattice) with the greatest common divisorGreatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
as meet and the least common multipleLeast common multipleIn arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...
as join.
- Given a positive integer n, the set of all positive divisorDivisorIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
s of n forms a distributive lattice, again with the greatest common divisor as meet and the least common multiple as join. This is a Boolean algebra if and only if n is square-freeSquare-free integerIn mathematics, a square-free, or quadratfrei, integer is one divisible by no perfect square, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32...
.
- A lattice-ordered vector spaceRiesz spaceIn mathematics a Riesz space, lattice-ordered vector space or vector lattice is an ordered vector space where the order structure is a lattice....
is a distributive lattice.
- Young's latticeYoung's latticeIn mathematics, Young's lattice is a partially ordered set and a lattice that is formed by all integer partitions. It is named after Alfred Young, who in a series of papers On quantitative substitutional analysis developed representation theory of the symmetric group...
given by the inclusion ordering of Young diagrams representing integer partitionsPartition (number theory)In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a...
is a distributive lattice.
Characteristic properties
Various equivalent formulations to the above definition exist. For example, L is distributive if and only ifIf and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
the following holds for all elements x, y, z in L:
- (x
y)
(y
z)
(z
x) = (x
y)
(y
z)
(z
x).
Similarly, L is distributive if and only if
- x
z = y
z and x
z = y
z always imply x=y.
The simplest non-distributive lattices are M3, the "diamond lattice", and N5, the "pentagon lattice". A lattice is distributive if and only if none of its sublattices is isomorphic to M3 or N5; a sublattice is a subset that is closed under the meet and join operations of the original lattice. Note that this is not the same as being a subset that is a lattice under the original order (but possibly with different join and meet operations). Further characterizations derive from the representation theory in the next section.
Finally distributivity entails several other pleasant properties. For example, an element of a distributive lattice is meet-prime if and only if it is meet-irreducible, though the latter is in general a weaker property. By duality, the same is true for join-prime and join-irreducible elements. If a lattice is distributive, its covering relation
Covering relation
In mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours...
forms a median graph
Median graph
In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m that belongs to shortest paths between any two of a, b, and c.The concept of median graphs has long been studied, for instance by or ...
.
Furthermore, every distributive lattice is also modular
Modular lattice
In the branch of mathematics called order theory, a modular lattice is a lattice that satisfies the following self-dual condition:Modular law: x ≤ b implies x ∨ = ∧ b,where ≤ is the partial order, and ∨ and ∧ are...
.
Representation theory
The introduction already hinted at the most important characterization for distributive lattices: a lattice is distributive if and only if it is isomorphic to a lattice of sets (closed under set unionUnion (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
and intersection
Intersection (set theory)
In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
). That set union and intersection are indeed distributive in the above sense is an elementary fact. The other direction is less trivial, in that it requires the representation theorems stated below. The important insight from this characterization is that the identities (equations) that hold in all distributive lattices are exactly the ones that hold in all lattices of sets in the above sense.
Birkhoff's representation theorem
Birkhoff's representation theorem
In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets...
for distributive lattices states that every finite distributive lattice is isomorphic to the lattice of lower set
Upper set
In mathematics, an upper set of a partially ordered set is a subset U with the property that x is in U and x≤y imply y is in U....
s of the poset
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
of its join-prime (equivalently: join-irreducible) elements. This establishes a bijection
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
(up to isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
) between the class of all finite posets and the class of all finite distributive lattices. This bijection can be extended to a duality of categories
Equivalence of categories
In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences from many areas of mathematics...
between homomorphisms of finite distributive lattices and monotone function
Monotonic function
In mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....
s of finite posets. Generalizing this result to infinite lattices, however, requires adding further structure.
Another early representation theorem is now known as Stone's representation theorem for distributive lattices (the name honors Marshall Harvey Stone
Marshall Harvey Stone
Marshall Harvey Stone was an American mathematician who contributed to real analysis, functional analysis, and the study of Boolean algebras.-Biography:...
, who first proved it). It characterizes distributive lattices as the lattices of compact
Compact space
In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...
open
Open set
The concept of an open set is fundamental to many areas of mathematics, especially point-set topology and metric topology. Intuitively speaking, a set U is open if any point x in U can be "moved" a small amount in any direction and still be in the set U...
sets of certain topological space
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
s. This result can be viewed both as a generalization of Stone's famous representation theorem for Boolean algebras
Stone's representation theorem for Boolean algebras
In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Stone...
and as a specialization of the general setting of Stone duality
Stone duality
In mathematics, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. Today, these dualities are usually collected under the label Stone duality, since they form a natural generalization of Stone's representation...
.
A further important representation was established by Hilary Priestley in her representation theorem for distributive lattices. In this formulation, a distributive lattice is used to construct a topological space with an additional partial order on its points, yielding a (completely order-separated) ordered Stone space
Stone's representation theorem for Boolean algebras
In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Stone...
(or Priestley space
Priestley space
In mathematics, a Priestley space is an ordered topological space with special properties. Priestley spaces are named after Hilary Priestley who introduced and investigated them. Priestley spaces play a fundamental role in the study of distributive lattices...
). The original lattice is recovered as the collection of clopen
Clopen set
In topology, a clopen set in a topological space is a set which is both open and closed. That this is possible for a set is not as counter-intuitive as it might seem if the terms open and closed were thought of as antonyms; in fact they are not...
lower sets of this space.
As a consequence of Stone's and Priestley's theorems, one easily sees that any distributive lattice is really isomorphic to a lattice of sets. However, the proofs of both statements require the Boolean prime ideal theorem
Boolean prime ideal theorem
In mathematics, a prime ideal theorem guarantees the existence of certain types of subsets in a given abstract algebra. A common example is the Boolean prime ideal theorem, which states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on...
, a weak form of the axiom of choice.
Free distributive lattices
The freeFree object
In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of universal algebra, in the sense that it relates to all types of algebraic structure . It also has a formulation in terms of category theory, although this is in yet more abstract terms....
distributive lattice over a set of generators G can be constructed much more easily than a general free lattice. The first observation is that, using the laws of distributivity, every term formed by the binary operations
and on a set of generators can be transformed into the following equivalent normal form:- M1
M2 
... 
Mn
where the Mi are finite meets of elements of G. Moreover, since both meet and join are commutative
Commutativity
In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
and idempotent
Idempotence
Idempotence is the property of certain operations in mathematics and computer science, that they can be applied multiple times without changing the result beyond the initial application...
, one can ignore duplicates and order, and represent a join of meets like the one above as a set of sets:
- {N1, N2, ..., Nn},
where the Ni are finite subsets of G. However, it is still possible that two such terms denote the same element of the distributive lattice. This occurs when there are indices j and k such that Nj is a subset of Nk. In this case the meet of Nk will be below the meet of Nj, and hence one can safely remove the redundant set Nk without changing the interpretation of the whole term. Consequently, a set of finite subsets of G will be called irredundant whenever all of its elements Ni are mutually incomparable (with respect to the subset ordering); that is, when it forms an antichain
Antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
of finite sets.
Now the free distributive lattice over a set of generators G is defined on the set of all finite irredundant sets of finite subsets of G. The join of two finite irredundant sets is obtained from their union by removing all redundant sets. Likewise the meet of two sets S and T is the irredundant version of { N
M | N in S, M in T}. The verification that this structure is a distributive lattice with the required universal propertyUniversal property
In various branches of mathematics, a useful construction is often viewed as the “most efficient solution” to a certain problem. The definition of a universal property uses the language of category theory to make this notion precise and to study it abstractly.This article gives a general treatment...
is routine.
The number of elements in free distributive lattices with n generators is given by the Dedekind number
Dedekind number
Image:Monotone Boolean functions 0,1,2,3.svg|400px|thumb|right| The free distributive lattices of monotonic Boolean functions on 0, 1, 2, and 3 arguments, with 2, 3, 6, and 20 elements respectively...
s. These numbers grow rapidly, and are known only for n ≤ 8; they are
- 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 .
The numbers above count the number of free distributive lattices in which the lattice operations are joins and meets of finite sets of elements, including the empty set. If empty joins and empty meets are disallowed, the resulting free distributive lattices have two fewer elements; their numbers of elements form the sequence
- 1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786 .