Difference between revisions of "Distributive lattice"
(Importing text file) |
(links) |
||
Line 1: | Line 1: | ||
− | A [[ | + | A [[lattice]] in which the [[distributive law]] |
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d0335701.png" /></td> </tr></table> | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d0335701.png" /></td> </tr></table> | ||
− | holds. This equation is equivalent to | + | holds. This equation is equivalent to the dual distributive law |
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d0335702.png" /></td> </tr></table> | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d0335702.png" /></td> </tr></table> | ||
− | and | + | and to the property |
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d0335703.png" /></td> </tr></table> | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d0335703.png" /></td> </tr></table> | ||
Line 27: | Line 27: | ||
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d0335708.png" /></td> </tr></table> | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d0335708.png" /></td> </tr></table> | ||
− | Here the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d0335709.png" /> are finite sets and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357010.png" /> is the set of all single-valued functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357011.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357012.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357013.png" /> such <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357014.png" /> for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357015.png" />. In a complete lattice the above equations also have a meaning if the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357017.png" /> are infinite. However, they do not follow from the distributive law. Distributive complete lattices (cf. [[ | + | Here the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d0335709.png" /> are finite sets and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357010.png" /> is the set of all single-valued functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357011.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357012.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357013.png" /> such <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357014.png" /> for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357015.png" />. In a complete lattice the above equations also have a meaning if the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357017.png" /> are infinite. However, they do not follow from the distributive law. Distributive complete lattices (cf. [[Complete lattice]]) which satisfy the two last-mentioned identities for all sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357019.png" /> are called completely distributive. |
====References==== | ====References==== | ||
− | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> G. Birkhoff, "Lattice theory" , ''Colloq. Publ.'' , '''25''' , Amer. Math. Soc. (1973)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> L.A. Skornyakov, "Elements of lattice theory" , Hindushtan Publ. Comp. (1977) (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> G. Grätzer, "General lattice theory" , Birkhäuser (1978) (Original: Lattice theory. First concepts and distributive lattices. Freeman, 1978)</TD></TR></table> | + | <table> |
+ | <TR><TD valign="top">[1]</TD> <TD valign="top"> G. Birkhoff, "Lattice theory" , ''Colloq. Publ.'' , '''25''' , Amer. Math. Soc. (1973)</TD></TR> | ||
+ | <TR><TD valign="top">[2]</TD> <TD valign="top"> L.A. Skornyakov, "Elements of lattice theory" , Hindushtan Publ. Comp. (1977) (Translated from Russian)</TD></TR> | ||
+ | <TR><TD valign="top">[3]</TD> <TD valign="top"> G. Grätzer, "General lattice theory" , Birkhäuser (1978) (Original: Lattice theory. First concepts and distributive lattices. Freeman, 1978)</TD></TR> | ||
+ | </table> | ||
Line 43: | Line 47: | ||
In addition to the general references [[#References|[1]]]–[[#References|[3]]] above, [[#References|[a5]]] may also be recommended as a general account of distributive lattice theory. | In addition to the general references [[#References|[1]]]–[[#References|[3]]] above, [[#References|[a5]]] may also be recommended as a general account of distributive lattice theory. | ||
− | For completely distributive lattices see [[ | + | For completely distributive lattices see [[Completely distributive lattice]]. |
====References==== | ====References==== | ||
− | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> G. Birkhoff, "On the combination of subalgebras" ''Proc. Cambr. Philos. Soc.'' , '''29''' (1933) pp. 441–464</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> M.H. Stone, "Topological representation of distributive lattices and Brouwerian logics" ''Časopis Pešt. Mat. Fys.'' , '''67''' (1937) pp. 1–25</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> H.A. Priestley, "Ordered topological spaces and the representation of distributive lattices" ''Proc. Lond. Math. Soc. (3)'' , '''24''' (1972) pp. 507–530</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> H.A. Priestley, "Ordered sets and duality for distributive lattices" , ''Orders: Description and Roles'' , ''Ann. Discrete Math.'' , '''23''' , North-Holland (1984) pp. 39–60</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> R. Balbes, P. Dwinger, "Distributive lattices" , Univ. Missouri Press (1974)</TD></TR></table> | + | <table> |
+ | <TR><TD valign="top">[a1]</TD> <TD valign="top"> G. Birkhoff, "On the combination of subalgebras" ''Proc. Cambr. Philos. Soc.'' , '''29''' (1933) pp. 441–464</TD></TR> | ||
+ | <TR><TD valign="top">[a2]</TD> <TD valign="top"> M.H. Stone, "Topological representation of distributive lattices and Brouwerian logics" ''Časopis Pešt. Mat. Fys.'' , '''67''' (1937) pp. 1–25</TD></TR> | ||
+ | <TR><TD valign="top">[a3]</TD> <TD valign="top"> H.A. Priestley, "Ordered topological spaces and the representation of distributive lattices" ''Proc. Lond. Math. Soc. (3)'' , '''24''' (1972) pp. 507–530</TD></TR> | ||
+ | <TR><TD valign="top">[a4]</TD> <TD valign="top"> H.A. Priestley, "Ordered sets and duality for distributive lattices" , ''Orders: Description and Roles'' , ''Ann. Discrete Math.'' , '''23''' , North-Holland (1984) pp. 39–60</TD></TR> | ||
+ | <TR><TD valign="top">[a5]</TD> <TD valign="top"> R. Balbes, P. Dwinger, "Distributive lattices" , Univ. Missouri Press (1974)</TD></TR> | ||
+ | </table> |
Revision as of 19:32, 24 January 2016
A lattice in which the distributive law
![]() |
holds. This equation is equivalent to the dual distributive law
![]() |
and to the property
![]() |
Distributive lattices are characterized by the fact that all their convex sublattices can occur as congruence classes. Any distributive lattice is isomorphic to a lattice of (not necessarily all) subsets of some set. An important special case of such lattices are Boolean algebras (cf. Boolean algebra). For any finite set in a distributive lattice the following equalities are valid:
![]() |
and
![]() |
as well as
![]() |
and
![]() |
Here the are finite sets and
is the set of all single-valued functions
from
into
such
for each
. In a complete lattice the above equations also have a meaning if the sets
and
are infinite. However, they do not follow from the distributive law. Distributive complete lattices (cf. Complete lattice) which satisfy the two last-mentioned identities for all sets
and
are called completely distributive.
References
[1] | G. Birkhoff, "Lattice theory" , Colloq. Publ. , 25 , Amer. Math. Soc. (1973) |
[2] | L.A. Skornyakov, "Elements of lattice theory" , Hindushtan Publ. Comp. (1977) (Translated from Russian) |
[3] | G. Grätzer, "General lattice theory" , Birkhäuser (1978) (Original: Lattice theory. First concepts and distributive lattices. Freeman, 1978) |
Comments
The distributive property of lattices may be characterized by the presence of enough prime filters: A lattice is distributive if and only if its prime filters separate its points, or, equivalently, if, given
in
, there exists a lattice homomorphism
with
and
, [a1]. In the study of distributive lattices, their topological representation plays an important role; this was first established by M.H. Stone [a2], and reformulated in more convenient terms by H.A. Priestley [a3] — both versions generalize the Stone duality for Boolean algebras (cf. also Stone space). To describe Priestley's version, let
denote the set of prime filters of a distributive lattice
, partially ordered by inclusion and topologized by declaring the sets
![]() |
and their complements to be subbasic open sets. Then the assignment is a lattice-isomorphism from
to the set of clopen (i.e. closed and open) subsets of
which are upward closed in the partial order. Moreover, the partially ordered spaces which occur as
for some
are precisely the compact spaces in which, given
, there exists a clopen upward-closed set containing
but not
— such spaces are sometimes called Priestley spaces. Note that a Priestley space
is discretely ordered if and only if every prime filter of
is maximal, if and only if
is a Boolean algebra. Other important classes of distributive lattices can similarly be characterized by order-theoretic and/or topological properties of their Priestley spaces (see [a4]).
In addition to the general references [1]–[3] above, [a5] may also be recommended as a general account of distributive lattice theory.
For completely distributive lattices see Completely distributive lattice.
References
[a1] | G. Birkhoff, "On the combination of subalgebras" Proc. Cambr. Philos. Soc. , 29 (1933) pp. 441–464 |
[a2] | M.H. Stone, "Topological representation of distributive lattices and Brouwerian logics" Časopis Pešt. Mat. Fys. , 67 (1937) pp. 1–25 |
[a3] | H.A. Priestley, "Ordered topological spaces and the representation of distributive lattices" Proc. Lond. Math. Soc. (3) , 24 (1972) pp. 507–530 |
[a4] | H.A. Priestley, "Ordered sets and duality for distributive lattices" , Orders: Description and Roles , Ann. Discrete Math. , 23 , North-Holland (1984) pp. 39–60 |
[a5] | R. Balbes, P. Dwinger, "Distributive lattices" , Univ. Missouri Press (1974) |
Distributive lattice. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Distributive_lattice&oldid=37637