:''This is about
lattice theory
A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper bou ...
. For other similarly named results, see
Birkhoff's theorem (disambiguation) Birkhoff's theorem may refer to several theorems named for the American mathematician George David Birkhoff:
* Birkhoff's theorem (relativity)
* Birkhoff's theorem (electromagnetism)
* Birkhoff's ergodic theorem
It may also refer to theorems nam ...
.''
In
mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
distributive lattice
In mathematics, a distributive lattice is a lattice in 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 ...
can be represented as
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. T ...
s, in such a way that the lattice operations correspond to
unions and
intersections of sets. The theorem can be interpreted as providing a
one-to-one correspondence
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
between distributive lattices and
partial order
In mathematics, especially order theory, a partially ordered set (also poset) 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 bina ...
s, between
quasi-ordinal knowledge spaces and
preorders, or between
finite topological spaces and preorders. It is named after
Garrett Birkhoff
Garrett Birkhoff (January 19, 1911 – November 22, 1996) was an American mathematician. He is best known for his work in lattice theory.
The mathematician George Birkhoff (1884–1944) was his father.
Life
The son of the mathematician Ge ...
, who published a proof of it in 1937.
[.]
The name “Birkhoff's representation theorem” has also been applied to two other results of Birkhoff, one from 1935 on the
representation of Boolean algebras as families of sets closed under union, intersection, and complement (so-called ''fields of sets'', closely related to the ''rings of sets'' used by Birkhoff to represent distributive lattices), and
Birkhoff's HSP theorem
In universal algebra, a variety of algebras or equational class is the class of all algebraic structures of a given signature satisfying a given set of identities. For example, the groups form a variety of algebras, as do the abelian groups, the ...
representing algebras as products of irreducible algebras. Birkhoff's representation theorem has also been called the fundamental theorem for finite distributive lattices.
[.]
Understanding the theorem
Many lattices can be defined in such a way that the elements of the lattice are represented by sets, the join operation of the lattice is represented by set union, and the meet operation of the lattice is represented by set intersection. For instance, the
Boolean lattice defined from the family of all subsets of a finite set has this property. More generally any
finite topological space has a lattice of sets as its family of open sets. Because set unions and intersections obey the
distributive law
In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality
x \cdot (y + z) = x \cdot y + x \cdot z
is always true in elementary algebra.
For example, in elementary arithmetic, ...
, any lattice defined in this way is a distributive lattice. Birkhoff's theorem states that in fact ''all'' finite distributive lattices can be obtained this way, and later generalizations of Birkhoff's theorem state a similar thing for infinite distributive lattices.
Examples
![Birkhoff120](https://upload.wikimedia.org/wikipedia/commons/7/7c/Birkhoff120.svg)
Consider the
divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
s of some composite number, such as (in the figure) 120, partially ordered by divisibility. Any two divisors of 120, such as 12 and 20, have a unique
greatest common factor 12 ∧ 20 = 4, the largest number that divides both of them, and a unique
least common multiple
In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...
12 ∨ 20 = 60; both of these numbers are also divisors of 120. These two operations ∨ and ∧ satisfy the
distributive law
In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality
x \cdot (y + z) = x \cdot y + x \cdot z
is always true in elementary algebra.
For example, in elementary arithmetic, ...
, in either of two equivalent forms: (''x'' ∧ ''y'') ∨ ''z'' = (''x'' ∨ ''z'') ∧ (''y'' ∨ ''z'') and (''x'' ∨ ''y'') ∧ ''z'' = (''x'' ∧ ''z'') ∨ (''y'' ∧ ''z''), for all ''x'', ''y'', and ''z''. Therefore, the divisors form a finite
distributive lattice
In mathematics, a distributive lattice is a lattice in 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 ...
.
One may associate each divisor with the set of
prime power
In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number.
For example: , and are prime powers, while
, and are not.
The sequence of prime powers begins:
2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...
s that divide it: thus, 12 is associated with the set , while 20 is associated with the set . Then 12 ∧ 20 = 4 is associated with the set ∩ = , while 12 ∨ 20 = 60 is associated with the set ∪ = , so the join and meet operations of the lattice correspond to union and intersection of sets.
The prime powers 2, 3, 4, 5, and 8 appearing as elements in these sets may themselves be partially ordered by divisibility; in this smaller partial order, 2 ≤ 4 ≤ 8 and there are no order relations between other pairs. The 16 sets that are associated with divisors of 120 are the
lower set
In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
s of this smaller partial order, subsets of elements such that if ''x'' ≤ ''y'' and ''y'' belongs to the subset, then ''x'' must also belong to the subset. From any lower set ''L'', one can recover the associated divisor by computing the least common multiple of the prime powers in ''L''. Thus, the partial order on the five prime powers 2, 3, 4, 5, and 8 carries enough information to recover the entire original 16-element divisibility lattice.
Birkhoff's theorem states that this relation between the operations ∧ and ∨ of the lattice of divisors and the operations ∩ and ∪ of the associated sets of prime powers is not coincidental, and not dependent on the specific properties of prime numbers and divisibility: the elements of any finite distributive lattice may be associated with lower sets of a partial order in the same way.
As another example, the application of Birkhoff's theorem to the family of
subsets of an ''n''-element set, partially ordered by inclusion, produces the
free distributive lattice
In mathematics, a distributive lattice is a lattice in 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 un ...
with ''n'' generators. The number of elements in this lattice is given by the
Dedekind number
File:Monotone Boolean functions 0,1,2,3.svg, 400px, The free distributive lattices of monotonic Boolean functions on 0, 1, 2, and 3 arguments, with 2, 3, 6, and 20 elements respectively (move mouse over right diagram to see description)
circle 6 ...
s.
The partial order of join-irreducibles
In a lattice, an element ''x'' is ''join-irreducible'' if ''x'' is not the join of a finite set of other elements. Equivalently, ''x'' is join-irreducible if it is neither the bottom element of the lattice (the join of zero elements) nor the join of any two smaller elements. For instance, in the lattice of divisors of 120, there is no pair of elements whose join is 4, so 4 is join-irreducible. An element ''x'' is ''join-prime'' if it differs from the bottom element, and whenever ''x'' ≤ ''y'' ∨ ''z'', either ''x'' ≤ ''y'' or ''x'' ≤ ''z''. In the same lattice, 4 is join-prime: whenever lcm(''y'',''z'') is divisible by 4, at least one of ''y'' and ''z'' must itself be divisible by 4.
In any lattice, a join-prime element must be join-irreducible. Equivalently, an element that is not join-irreducible is not join-prime. For, if an element ''x'' is not join-irreducible, there exist smaller ''y'' and ''z'' such that ''x'' = ''y'' ∨ ''z''. But then ''x'' ≤ ''y'' ∨ ''z'', and ''x'' is not less than or equal to either ''y'' or ''z'', showing that it is not join-prime.
There exist lattices in which the join-prime elements form a proper subset of the join-irreducible elements, but in a distributive lattice the two types of elements coincide. For, suppose that ''x'' is join-irreducible, and that ''x'' ≤ ''y'' ∨ ''z''. This inequality is equivalent to the statement that ''x'' = ''x'' ∧ (''y'' ∨ ''z''), and by the distributive law ''x'' = (''x'' ∧ ''y'') ∨ (''x'' ∧ ''z''). But since ''x'' is join-irreducible, at least one of the two terms in this join must be ''x'' itself, showing that either ''x'' = ''x'' ∧ ''y'' (equivalently ''x'' ≤ ''y'') or ''x'' = ''x'' ∧ ''z'' (equivalently ''x'' ≤ ''z'').
The lattice ordering on the subset of join-irreducible elements forms a
partial order
In mathematics, especially order theory, a partially ordered set (also poset) 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 bina ...
; Birkhoff's theorem states that the lattice itself can be recovered from the lower sets of this partial order.
Birkhoff's theorem
![Birkhoff representation theorem](https://upload.wikimedia.org/wikipedia/commons/8/88/Birkhoff_representation_theorem.gif)
In any partial order, the
lower set
In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
s form a lattice in which the lattice's partial ordering is given by set inclusion, the join operation corresponds to set union, and the meet operation corresponds to set intersection, because unions and intersections preserve the property of being a lower set. Because set unions and intersections obey the distributive law, this is a distributive lattice. Birkhoff's theorem states that any finite distributive lattice can be constructed in this way.
:Theorem. Any finite distributive lattice ''L'' is isomorphic to the lattice of lower sets of the partial order of the join-irreducible elements of ''L''.
That is, there is a one-to-one order-preserving correspondence between elements of ''L'' and lower sets of the partial order. The lower set corresponding to an element ''x'' of ''L'' is simply the set of join-irreducible elements of ''L'' that are less than or equal to ''x'', and the element of ''L'' corresponding to a lower set ''S'' of join-irreducible elements is the join of ''S''.
For any lower set ''S'' of join-irreducible elements, let ''x'' be the join of ''S'', and let ''T'' be the lower set of the join-irreducible elements less than or equal to ''x''. Then ''S'' = ''T''. For, every element of ''S'' clearly belongs to ''T'', and any join-irreducible element less than or equal to ''x'' must (by join-primality) be less than or equal to one of the members of ''S'', and therefore must (by the assumption that ''S'' is a lower set) belong to ''S'' itself. Conversely, for any element ''x'' of ''L'', let ''S'' be the join-irreducible elements less than or equal to ''x'', and let ''y'' be the join of ''S''. Then ''x'' = ''y''. For, as a join of elements less than or equal to ''x'', ''y'' can be no greater than ''x'' itself, but if ''x'' is join-irreducible then ''x'' belongs to ''S'' while if ''x'' is the join of two or more join-irreducible items then they must again belong to ''S'', so ''y'' ≥ ''x''. Therefore, the correspondence is one-to-one and the theorem is proved.
Rings of sets and preorders
defined a ''ring of sets'' to be a
family of sets
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fami ...
that is
closed under the operations of set unions and set intersections; later, motivated by applications in
mathematical psychology
Mathematical psychology is an approach to psychological research that is based on mathematical modeling of perceptual, thought, cognitive and motor processes, and on the establishment of law-like rules that relate quantifiable stimulus characte ...
, called the same structure a ''quasi-ordinal
knowledge space In mathematical psychology and education theory, a knowledge space is a combinatorial structure used to formulate mathematical models describing the progression of a human learner. Knowledge spaces were introduced in 1985 by Jean-Paul Doignon and ...
''. If the sets in a ring of sets are ordered by inclusion, they form a distributive lattice. The elements of the sets may be given a
preorder in which ''x'' ≤ ''y'' whenever some set in the ring contains ''x'' but not ''y''. The ring of sets itself is then the family of lower sets of this preorder, and any preorder gives rise to a ring of sets in this way.
Functoriality
Birkhoff's theorem, as stated above, is a correspondence between individual partial orders and distributive lattices. However, it can also be extended to a correspondence between order-preserving functions of partial orders and
bounded homomorphisms of the corresponding distributive lattices. The direction of these maps is reversed in this correspondence.
Let 2 denote the partial order on the two-element set , with the order relation 0 < 1, and (following Stanley) let ''J(P)'' denote the distributive lattice of lower sets of a finite partial order ''P''. Then the elements of ''J(P)'' correspond one-for-one to the order-preserving functions from ''P'' to 2.
For, if ƒ is such a function, ƒ
−1(0) forms a lower set, and conversely if ''L'' is a lower set one may define an order-preserving function ƒ
''L'' that maps ''L'' to 0 and that maps the remaining elements of ''P'' to 1. If ''g'' is any order-preserving function from ''Q'' to ''P'', one may define a function ''g''* from ''J(P)'' to ''J(Q)'' that uses the
composition of functions
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
to map any element ''L'' of ''J(P)'' to ƒ
''L'' ∘ ''g''. This composite function maps ''Q'' to 2 and therefore corresponds to an element ''g''*(''L'') = (ƒ
''L'' ∘ ''g'')
−1(0) of ''J(Q)''. Further, for any ''x'' and ''y'' in ''J(P)'', ''g''*(''x'' ∧ ''y'') = ''g''*(''x'') ∧ ''g''*(''y'') (an element of ''Q'' is mapped by ''g'' to the lower set ''x'' ∩ ''y'' if and only if belongs both to the set of elements mapped to ''x'' and the set of elements mapped to ''y'') and symmetrically ''g''*(''x'' ∨ ''y'') = ''g''*(''x'') ∨ ''g''*(''y''). Additionally, the bottom element of ''J(P)'' (the function that maps all elements of ''P'' to 0) is mapped by ''g''* to the bottom element of ''J(Q)'', and the top element of ''J(P)'' is mapped by ''g''* to the top element of ''J(Q)''. That is, ''g''* is a homomorphism of bounded lattices.
However, the elements of ''P'' themselves correspond one-for-one with bounded lattice homomorphisms from ''J(P)'' to 2. For, if ''x'' is any element of ''P'', one may define a bounded lattice homomorphism ''j
x'' that maps all lower sets containing ''x'' to 1 and all other lower sets to 0. And, for any lattice homomorphism from ''J(P)'' to 2, the elements of ''J(P)'' that are mapped to 1 must have a unique minimal element ''x'' (the meet of all elements mapped to 1), which must be join-irreducible (it cannot be the join of any set of elements mapped to 0), so every lattice homomorphism has the form ''j
x'' for some ''x''. Again, from any bounded lattice homomorphism ''h'' from ''J(P)'' to ''J(Q)'' one may use composition of functions to define an order-preserving map ''h''* from ''Q'' to ''P''. It may be verified that ''g''** = ''g'' for any order-preserving map ''g'' from ''Q'' to ''P'' and that and ''h''** = ''h'' for any bounded lattice homomorphism ''h'' from ''J(P)'' to ''J(Q)''.
In
category theoretic terminology, ''J'' is a
contravariant hom-functor ''J'' = Hom(—,2) that defines a
duality of categories between, on the one hand, the category of finite partial orders and order-preserving maps, and on the other hand the category of finite distributive lattices and bounded lattice homomorphisms.
Generalizations
Infinite distributive lattices
In an infinite distributive lattice, it may not be the case that the lower sets of the join-irreducible elements are in one-to-one correspondence with lattice elements. Indeed, there may be no join-irreducibles at all. This happens, for instance, in the lattice of all natural numbers, ordered with the reverse of the usual divisibility ordering (so ''x'' ≤ ''y'' when ''y'' divides ''x''): any number ''x'' can be expressed as the join of numbers ''xp'' and ''xq'' where ''p'' and ''q'' are distinct
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s. However, elements in infinite distributive lattices may still be represented as sets via
Stone's representation theorem
In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a certain field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first hal ...
for distributive lattices, a form of
Stone duality in which each lattice element corresponds to a
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in British ...
open set
In mathematics, open sets are a generalization of open intervals in the real line.
In a metric space (a set along with a distance defined between any two points), open sets are the sets that, with every point , contain all points that are su ...
in a certain
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called po ...
. This generalized representation theorem can be expressed as a
category-theoretic duality between distributive lattices and
spectral space In mathematics, a spectral space is a topological space that is homeomorphic to the spectrum of a commutative ring. It is sometimes also called a coherent space because of the connection to coherent topos.
Definition
Let ''X'' be a topological ...
s (sometimes called coherent spaces, but not the same as the
coherent spaces in linear logic), topological spaces in which the compact open sets are closed under intersection and form a
base for the topology.
Hilary Priestley
Hilary Ann Priestley is a British mathematician. She is a professor at the University of Oxford and a Fellow of St Anne's College, Oxford, where she has been Tutor in Mathematics since 1972.
Hilary Priestley introduced ordered separable topo ...
showed that Stone's representation theorem could be interpreted as an extension of the idea of representing lattice elements by lower sets of a partial order, using Nachbin's idea of ordered topological spaces. Stone spaces with an additional partial order linked with the topology via
Priestley separation axiom can also be used to represent bounded distributive lattices. Such spaces are known as
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 distributiv ...
s. Further, certain
bitopological space
In mathematics, a bitopological space is a set endowed with ''two'' topologies. Typically, if the set is X and the topologies are \sigma and \tau then the bitopological space is referred to as (X,\sigma,\tau). The notion was introduced by J. C. Ke ...
s, namely
pairwise Stone space
In mathematics and particularly in topology, pairwise Stone space is a bitopological space \scriptstyle (X,\tau_1,\tau_2) which is pairwise compact, pairwise Hausdorff, and pairwise zero-dimensional.
Pairwise Stone spaces are a bitopological ...
s, generalize Stone's original approach by utilizing ''two'' topologies on a set to represent an abstract distributive lattice. Thus, Birkhoff's representation theorem extends to the case of infinite (bounded) distributive lattices in at least three different ways, summed up in
duality theory for distributive lattices.
Median algebras and related graphs
Birkhoff's representation theorem may also be generalized to finite structures other than distributive lattices. In a distributive lattice, the self-dual median operation
:
gives rise to a
median algebra In mathematics, a median algebra is a set with a ternary operation \langle x,y,z \rangle satisfying a set of axioms which generalise the notions of medians of triples of real numbers and of the Boolean majority function.
The axioms are
# \lang ...
, and the covering relation of the lattice forms a
median graph
In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest paths between each pair o ...
. Finite median algebras and median graphs have a dual structure
as the set of solutions of a
2-satisfiability
In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case ...
instance; formulate this structure equivalently as the family of initial
stable sets in a
mixed graph
In graph theory, a mixed graph is a graph consisting of a set of vertices , a set of (undirected) edges , and a set of directed edges (or arcs) .
Definitions and notation
Consider adjacent vertices u,v \in V. A directed edge, called an arc, ...
.
[A minor difference between the 2-SAT and initial stable set formulations is that the latter presupposes the choice of a fixed base point from the median graph that corresponds to the empty initial stable set.] For a distributive lattice, the corresponding mixed graph has no undirected edges, and the initial stable sets are just the lower sets of the
transitive closure
In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite ...
of the graph. Equivalently, for a distributive lattice, the
implication graph
In mathematical logic and graph theory, an implication graph is a skew-symmetric, directed graph composed of vertex set and directed edge set . Each vertex in represents the truth status of a Boolean literal, and each directed edge from verte ...
of the 2-satisfiability instance can be partitioned into two
connected components, one on the positive variables of the instance and the other on the negative variables; the transitive closure of the positive component is the underlying partial order of the distributive lattice.
Finite join-distributive lattices and matroids
Another result analogous to Birkhoff's representation theorem, but applying to a broader class of lattices, is the theorem of that any finite join-distributive lattice may be represented as an
antimatroid
In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroi ...
, a family of sets closed under unions but in which closure under intersections has been replaced by the property that each nonempty set has a removable element.
See also
*
Lattice of stable matchings, also representing every finite distributive lattice
Notes
References
*.
*.
*.
*.
*.
*.
*.
*.
*{{citation
, last = Stanley , first = R. P. , author-link = Richard P. Stanley
, title = Enumerative Combinatorics, Volume I
, series = Cambridge Studies in Advanced Mathematics 49
, publisher = Cambridge University Press
, year = 1997
, pages = 104–112.
Theorems in lattice theory