Namespaces
Variants
Actions

Difference between revisions of "Distributive lattice"

From Encyclopedia of Mathematics
Jump to: navigation, search
(links)
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
d0335701.png
 +
$#A+1 = 39 n = 0
 +
$#C+1 = 39 : ~/encyclopedia/old_files/data/D033/D.0303570 Distributive lattice
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A [[lattice]] in which the [[distributive law]]
 
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>
+
$$
 +
( a + b ) c  = a c + b c
 +
$$
  
 
holds. This equation is equivalent to the dual distributive law
 
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>
+
$$
 +
a b + c  = ( a + c ) ( b + c )
 +
$$
  
 
and to the property
 
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>
+
$$
 +
( a + b ) ( a + c ) ( b + c )  = a b + a c + b c .
 +
$$
  
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|Boolean algebra]]). For any finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d0335704.png" /> in a distributive lattice the following equalities are valid:
+
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|Boolean algebra]]). For any finite set $  I $
 +
in a distributive lattice the following equalities are valid:
  
<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/d0335705.png" /></td> </tr></table>
+
$$
 +
a \sum _ {i \in I } b _ {i}  = \
 +
\sum _ {i \in I } a b _ {i}  $$
  
 
and
 
and
  
<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/d0335706.png" /></td> </tr></table>
+
$$
 +
a + \prod _ {i \in I } b _ {i}  = \prod _
 +
{i \in I } ( a + b _ {i} ) ,
 +
$$
  
 
as well as
 
as well as
  
<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/d0335707.png" /></td> </tr></table>
+
$$
 +
\prod _ {i \in I }  \sum _ {j \in J ( i) }
 +
a _ {ij}  = \sum _ {\phi \in \Phi }  \prod _ {i \in I }
 +
a _ {i \phi ( i) }
 +
$$
  
 
and
 
and
  
<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>
+
$$
 +
\sum _ {i \in I }  \prod _ {j \in J ( i) }
 +
a _ {ij}  = \prod _ {\phi \in \Phi }  \sum _ {i \in I }
 +
a _ {i \phi ( i) }  .
 +
$$
  
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.
+
Here the $  J ( i) $
 +
are finite sets and $  \Phi $
 +
is the set of all single-valued functions $  \phi $
 +
from $  I $
 +
into $  \cup J ( i) $
 +
such $  \phi ( i) \in J ( i) $
 +
for each $  i \in I $.  
 +
In a complete lattice the above equations also have a meaning if the sets $  I $
 +
and $  J ( i) $
 +
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 $  I $
 +
and $  J ( i) $
 +
are called completely distributive.
  
 
====References====
 
====References====
Line 35: Line 78:
 
<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>
 
<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>
 
 
  
 
====Comments====
 
====Comments====
The distributive property of lattices may be characterized by the presence of enough prime filters: A lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357020.png" /> is distributive if and only if its prime filters separate its points, or, equivalently, if, given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357021.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357022.png" />, there exists a lattice homomorphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357023.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357025.png" />, [[#References|[a1]]]. In the study of distributive lattices, their topological representation plays an important role; this was first established by M.H. Stone [[#References|[a2]]], and reformulated in more convenient terms by H.A. Priestley [[#References|[a3]]] — both versions generalize the Stone duality for Boolean algebras (cf. also [[Stone space|Stone space]]). To describe Priestley's version, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357026.png" /> denote the set of prime filters of a distributive lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357027.png" />, partially ordered by inclusion and topologized by declaring the sets
+
The distributive property of lattices may be characterized by the presence of enough prime filters: A lattice $  A $
 +
is distributive if and only if its prime filters separate its points, or, equivalently, if, given $  a \leq  b $
 +
in $  A $,  
 +
there exists a lattice homomorphism $  f :  A \rightarrow \{ 0 , 1 \} $
 +
with $  f ( a) = 1 $
 +
and $  f ( b) = 0 $,  
 +
[[#References|[a1]]]. In the study of distributive lattices, their topological representation plays an important role; this was first established by M.H. Stone [[#References|[a2]]], and reformulated in more convenient terms by H.A. Priestley [[#References|[a3]]] — both versions generalize the Stone duality for Boolean algebras (cf. also [[Stone space|Stone space]]). To describe Priestley's version, let $  \mathop{\rm spec} A $
 +
denote the set of prime filters of a distributive lattice $  A $,  
 +
partially ordered by inclusion and topologized by declaring the sets
  
<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/d03357028.png" /></td> </tr></table>
+
$$
 +
U ( a)  = \{ {X \in  \mathop{\rm spec} A } : {x \in X } \}
 +
$$
  
and their complements to be subbasic open sets. Then the assignment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357029.png" /> is a lattice-isomorphism from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357030.png" /> to the set of clopen (i.e. closed and open) subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357031.png" /> which are upward closed in the partial order. Moreover, the partially ordered spaces which occur as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357032.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357033.png" /> are precisely the compact spaces in which, given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357034.png" />, there exists a clopen upward-closed set containing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357035.png" /> but not <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357036.png" /> — such spaces are sometimes called Priestley spaces. Note that a Priestley space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357037.png" /> is discretely ordered if and only if every prime filter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357038.png" /> is maximal, if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033570/d03357039.png" /> 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 [[#References|[a4]]]).
+
and their complements to be subbasic open sets. Then the assignment $  a \mapsto U ( a) $
 +
is a lattice-isomorphism from $  A $
 +
to the set of clopen (i.e. closed and open) subsets of $  \mathop{\rm spec} A $
 +
which are upward closed in the partial order. Moreover, the partially ordered spaces which occur as $  \mathop{\rm spec} A $
 +
for some $  A $
 +
are precisely the compact spaces in which, given $  x \leq  y $,  
 +
there exists a clopen upward-closed set containing $  x $
 +
but not $  y $—  
 +
such spaces are sometimes called Priestley spaces. Note that a Priestley space $  \mathop{\rm spec} A $
 +
is discretely ordered if and only if every prime filter of $  A $
 +
is maximal, if and only if $  A $
 +
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 [[#References|[a4]]]).
  
 
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.

Latest revision as of 19:36, 5 June 2020


A lattice in which the distributive law

$$ ( a + b ) c = a c + b c $$

holds. This equation is equivalent to the dual distributive law

$$ a b + c = ( a + c ) ( b + c ) $$

and to the property

$$ ( a + b ) ( a + c ) ( b + c ) = a b + a c + b c . $$

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 $ I $ in a distributive lattice the following equalities are valid:

$$ a \sum _ {i \in I } b _ {i} = \ \sum _ {i \in I } a b _ {i} $$

and

$$ a + \prod _ {i \in I } b _ {i} = \prod _ {i \in I } ( a + b _ {i} ) , $$

as well as

$$ \prod _ {i \in I } \sum _ {j \in J ( i) } a _ {ij} = \sum _ {\phi \in \Phi } \prod _ {i \in I } a _ {i \phi ( i) } $$

and

$$ \sum _ {i \in I } \prod _ {j \in J ( i) } a _ {ij} = \prod _ {\phi \in \Phi } \sum _ {i \in I } a _ {i \phi ( i) } . $$

Here the $ J ( i) $ are finite sets and $ \Phi $ is the set of all single-valued functions $ \phi $ from $ I $ into $ \cup J ( i) $ such $ \phi ( i) \in J ( i) $ for each $ i \in I $. In a complete lattice the above equations also have a meaning if the sets $ I $ and $ J ( i) $ 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 $ I $ and $ J ( i) $ 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 $ A $ is distributive if and only if its prime filters separate its points, or, equivalently, if, given $ a \leq b $ in $ A $, there exists a lattice homomorphism $ f : A \rightarrow \{ 0 , 1 \} $ with $ f ( a) = 1 $ and $ f ( b) = 0 $, [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 $ \mathop{\rm spec} A $ denote the set of prime filters of a distributive lattice $ A $, partially ordered by inclusion and topologized by declaring the sets

$$ U ( a) = \{ {X \in \mathop{\rm spec} A } : {x \in X } \} $$

and their complements to be subbasic open sets. Then the assignment $ a \mapsto U ( a) $ is a lattice-isomorphism from $ A $ to the set of clopen (i.e. closed and open) subsets of $ \mathop{\rm spec} A $ which are upward closed in the partial order. Moreover, the partially ordered spaces which occur as $ \mathop{\rm spec} A $ for some $ A $ are precisely the compact spaces in which, given $ x \leq y $, there exists a clopen upward-closed set containing $ x $ but not $ y $— such spaces are sometimes called Priestley spaces. Note that a Priestley space $ \mathop{\rm spec} A $ is discretely ordered if and only if every prime filter of $ A $ is maximal, if and only if $ A $ 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)
How to Cite This Entry:
Distributive lattice. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Distributive_lattice&oldid=37637
This article was adapted from an original article by L.A. Skornyakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article