In
mathematicsMathematics 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
latticesIn 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
distributeIn 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
unionIn 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
intersectionIn 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
isomorphismIn 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 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 algebraUniversal 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
latticesIn 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
preservesIn 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
dualIn 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)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
latticesIn 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 algebra
In mathematical logic, the Lindenbaum–Tarski algebra of a logical theory T consists of the equivalence classes of sentences of the theory...
of most logicIn 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 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 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 algebra
In 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 localesIn 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 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 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 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 set
In 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 number
In 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 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 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 divisor
In 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-freeIn 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 space
In 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 lattice
In 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 partitionsIn 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 ifIn 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 relationIn 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 graphIn 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
modularIn 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 unionIn 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
intersectionIn 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 theoremIn 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 setIn 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
posetIn 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
bijectionA 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
isomorphismIn 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 categoriesIn 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 functionIn 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 StoneMarshall 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
compactIn 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...
openThe 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 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. This result can be viewed both as a generalization of Stone's famous
representation theorem for Boolean algebrasIn 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 dualityIn 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 spaceIn 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 spaceIn 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
clopenIn 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 theoremIn 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
freeIn 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
commutativeIn 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
idempotentIdempotence 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
antichainIn 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 propertyIn 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 numberImage: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 .