Namespaces
Variants
Actions

Difference between revisions of "Lattice"

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎References: expand bibliodata)
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
<!--
 +
l0576301.png
 +
$#A+1 = 88 n = 1
 +
$#C+1 = 88 : ~/encyclopedia/old_files/data/L057/L.0507630 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}}
 +
 
''structure''
 
''structure''
  
Line 5: Line 17:
 
===Examples.===
 
===Examples.===
  
 +
1) A linearly ordered set (or chain)  $  M $
 +
where for  $  a, b \in M $,
 +
if  $  a \leq  b $,
 +
then
  
1) A linearly ordered set (or chain) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l0576301.png" /> where for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l0576302.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l0576303.png" />, then
+
$$
 
+
\sup  \{ a, b \}  = b,\ \
<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/l/l057/l057630/l0576304.png" /></td> </tr></table>
+
\inf  \{ a, b \}  = a.
 +
$$
  
 
2) The subspaces of a vector space ordered by inclusion, where
 
2) The subspaces of a vector space ordered by inclusion, where
  
<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/l/l057/l057630/l0576305.png" /></td> </tr></table>
+
$$
 +
\sup  \{ A, B \}  = \{ {x } : {x = a + b, a \in A, b \in B } \}
 +
,
 +
$$
  
<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/l/l057/l057630/l0576306.png" /></td> </tr></table>
+
$$
 +
\inf  \{ A, B \}  = A \cap B.
 +
$$
  
 
3) The subsets of a given set ordered by inclusion, where
 
3) The subsets of a given set ordered by inclusion, where
  
<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/l/l057/l057630/l0576307.png" /></td> </tr></table>
+
$$
 +
\sup  \{ A, B \}  = A \cup B,
 +
$$
  
<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/l/l057/l057630/l0576308.png" /></td> </tr></table>
+
$$
 +
\inf  \{ A, B \}  = A \cap B.
 +
$$
  
4) The non-negative integers ordered by divisibility: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l0576309.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763010.png" /> for a certain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763011.png" />; where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763012.png" /> is the least common multiple of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763014.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763015.png" /> is the greatest common divisor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763017.png" />.
+
4) The non-negative integers ordered by divisibility: $  a \leq  b $
 +
if $  b = ac $
 +
for a certain $  c $;  
 +
where $  \sup  \{ a, b \} $
 +
is the least common multiple of $  a $
 +
and $  b $,  
 +
and $  \inf  \{ a, b \} $
 +
is the greatest common divisor of $  a $
 +
and $  b $.
  
5) The real-valued functions defined on the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763018.png" /> and ordered by the condition: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763019.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763020.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763021.png" />, where
+
5) The real-valued functions defined on the interval $  [ 0, 1] $
 +
and ordered by the condition: $  f \leq  g $
 +
if $  f( t) \leq  g( t) $
 +
for all $  t \in [ 0, 1] $,
 +
where
  
<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/l/l057/l057630/l05763022.png" /></td> </tr></table>
+
$$
 +
\sup  \{ f, g \}  = u ,
 +
$$
  
 
in which
 
in which
  
<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/l/l057/l057630/l05763023.png" /></td> </tr></table>
+
$$
 +
u( t)  = \max  \{ f( t), g( t) \} ,
 +
$$
  
 
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/l/l057/l057630/l05763024.png" /></td> </tr></table>
+
$$
 +
\inf  \{ f, g \}  = v,
 +
$$
  
 
in which
 
in which
  
<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/l/l057/l057630/l05763025.png" /></td> </tr></table>
+
$$
 +
v( t)  = \min  \{ f( t) , g( t) \} .
 +
$$
 +
 
 +
Let  $  M $
 +
be a lattice. $  M $
 +
becomes a [[Universal algebra|universal algebra]] with two binary operations if one defines
 +
 
 +
$$
 +
a + b  =  \sup  \{ a, b \} ,
 +
$$
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763026.png" /> be a lattice. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763027.png" /> becomes a [[Universal algebra|universal algebra]] with two binary operations if one defines
+
$$
 +
a \cdot b  = \inf  \{ a, b \}
 +
$$
  
<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/l/l057/l057630/l05763028.png" /></td> </tr></table>
+
(the symbols  $  \cup $
 +
and  $  \cap $
 +
or  $  \lor $
 +
and  $  \wedge $
 +
are often used instead of  $  + $
 +
and  $  \cdot $).
 +
This universal algebra satisfies the following identities:
  
<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/l/l057/l057630/l05763029.png" /></td> </tr></table>
+
$$
 +
\begin{array}{l}
 +
( 1)  a + a  = a; \\
 +
( 2)  a + b  = b + a; \\
 +
( 3)  ( a +
 +
b) + c  = a + ( b + c); \\
 +
( 4)  a( a + b)  = a;  
 +
\end{array}
  
(the symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763031.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763032.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763033.png" /> are often used instead of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763035.png" />). This universal algebra satisfies the following identities:
+
\  \begin{array}{l}
 +
( 1  ^  \prime  )  a \cdot a  = a; \\
 +
( 2  ^  \prime  )  a \cdot b  = b
 +
\cdot
 +
a; \\
 +
( 3  ^  \prime  )  ( a \cdot b) \cdot c  = a \cdot ( b \cdot c); \\
 +
( 4
 +
^  \prime  )  a + a \cdot b  = a.  
 +
\end{array}
  
<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/l/l057/l057630/l05763036.png" /></td> </tr></table>
+
$$
  
Conversely, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763037.png" /> is a set with two binary operations that have the properties –, (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763038.png" />)–(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763039.png" />) mentioned above, then an order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763040.png" /> can be imposed on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763041.png" /> by setting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763042.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763043.png" /> (it turns out in this case that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763044.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763045.png" />). The resulting partially ordered set will be a lattice in which
+
Conversely, if $  M $
 +
is a set with two binary operations that have the properties –, ( $  1  ^  \prime  $)–(
 +
$  4  ^  \prime  $)  
 +
mentioned above, then an order $  \leq  $
 +
can be imposed on $  M $
 +
by setting $  a \leq  b $
 +
if $  a + b = b $(
 +
it turns out in this case that $  a \leq  b $
 +
if and only if $  a \cdot b = a $).  
 +
The resulting partially ordered set will be a lattice in which
  
<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/l/l057/l057630/l05763046.png" /></td> </tr></table>
+
$$
 +
\sup  \{ a, b \}  = a + b \ \
 +
\textrm{ and } \  \inf  \{ a, b \}  = a \cdot b.
 +
$$
  
In this way a lattice can be defined as a universal algebra satisfying the identities –, (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763047.png" />)–(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763048.png" />), i.e. lattices form a [[Variety of universal algebras|variety of universal algebras]].
+
In this way a lattice can be defined as a universal algebra satisfying the identities –, ( $  1  ^  \prime  $)–(
 +
$  4  ^  \prime  $),  
 +
i.e. lattices form a [[Variety of universal algebras|variety of universal algebras]].
  
 
If a partially ordered set is regarded as a [[Small category|small category]], then it is a lattice if and only if has products and coproducts of pairs of objects.
 
If a partially ordered set is regarded as a [[Small category|small category]], then it is a lattice if and only if has products and coproducts of pairs of objects.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763049.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763050.png" /> are lattices and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763051.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763052.png" /> is an isomorphism of partially ordered sets, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763053.png" /> is also an isomorphism of the corresponding universal algebras, i.e.
+
If $  P $
 +
and $  P  ^  \prime  $
 +
are lattices and if $  f $:  
 +
$  P \rightarrow P  ^  \prime  $
 +
is an isomorphism of partially ordered sets, then $  f $
 +
is also an isomorphism of the corresponding universal algebras, i.e.
  
<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/l/l057/l057630/l05763054.png" /></td> </tr></table>
+
$$
 +
f( x + y)  = f( x) + f( y) \ 
 +
\textrm{ and } \  f( xy)  = f( x) \cdot f( y)
 +
$$
  
for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763055.png" />. However, an arbitrary [[Isotone mapping|isotone mapping]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763056.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763057.png" /> is not necessarily a homomorphism of these lattices considered as universal algebras. Thus, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763058.png" />, the mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763059.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763060.png" /> are isotone mappings of the lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763061.png" /> into itself, but they are homomorphisms if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763062.png" /> is a [[Distributive lattice|distributive lattice]]. However, the first of these mappings is a homomorphism of the semi-lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763063.png" /> with the operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763064.png" />, and the second is a homomorphism of the [[Semi-lattice|semi-lattice]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763065.png" /> with the operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763066.png" />. The class of all lattices forms a category if homomorphisms are taken as morphisms.
+
for any $  x, y \in P $.  
 +
However, an arbitrary [[Isotone mapping|isotone mapping]] of $  P $
 +
into $  P  ^  \prime  $
 +
is not necessarily a homomorphism of these lattices considered as universal algebras. Thus, for any $  a \in P $,  
 +
the mappings $  f( x) = x + a $
 +
and $  g( x) = x \cdot a $
 +
are isotone mappings of the lattice $  P $
 +
into itself, but they are homomorphisms if and only if $  P $
 +
is a [[Distributive lattice|distributive lattice]]. However, the first of these mappings is a homomorphism of the semi-lattice $  P $
 +
with the operation $  + $,  
 +
and the second is a homomorphism of the [[Semi-lattice|semi-lattice]] $  P $
 +
with the operation $  \cdot $.  
 +
The class of all lattices forms a category if homomorphisms are taken as morphisms.
  
An anti-homomorphism of a lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763067.png" /> into a lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763068.png" /> is a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763069.png" /> such that
+
An anti-homomorphism of a lattice $  P $
 +
into a lattice $  P  ^  \prime  $
 +
is a mapping $  f: P \rightarrow P  ^  \prime  $
 +
such that
  
<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/l/l057/l057630/l05763070.png" /></td> </tr></table>
+
$$
 +
f( x + y)  = f( x) \cdot f( y) \ 
 +
\textrm{ and } \  f( x \cdot y )  = f( x) + f( y) ,
 +
$$
  
for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763071.png" />. A composite of two anti-homomorphisms is a homomorphism. A partially ordered set that is anti-isomorphic to a lattice is a lattice.
+
for any $  x, y \in P $.  
 +
A composite of two anti-homomorphisms is a homomorphism. A partially ordered set that is anti-isomorphic to a lattice is a lattice.
  
 
By coordinatization of a lattice is meant the finding of an [[Algebraic system|algebraic system]] (most often a universal algebra) such that the given lattice is isomorphic to the lattice of subsystems, to the lattice of congruences or to some other lattice associated with this algebraic system or universal algebra. An arbitrary lattice with a 0 and a 1 is coordinatized by the partially ordered semi-group of its residual mappings (cf. [[Residual mapping|Residual mapping]]) into itself, and turns out to be isomorphic to the lattice of right annihilators of this semi-group. The semi-group itself is a [[Baer semi-group]], i.e. the right and left annihilators of each of its elements are generated by idempotents.
 
By coordinatization of a lattice is meant the finding of an [[Algebraic system|algebraic system]] (most often a universal algebra) such that the given lattice is isomorphic to the lattice of subsystems, to the lattice of congruences or to some other lattice associated with this algebraic system or universal algebra. An arbitrary lattice with a 0 and a 1 is coordinatized by the partially ordered semi-group of its residual mappings (cf. [[Residual mapping|Residual mapping]]) into itself, and turns out to be isomorphic to the lattice of right annihilators of this semi-group. The semi-group itself is a [[Baer semi-group]], i.e. the right and left annihilators of each of its elements are generated by idempotents.
Line 85: Line 203:
 
<TR><TD valign="top">[6]</TD> <TD valign="top">  L.A. Skornyakov,  "Lattice theory"  ''Itogi Nauk. Algebra, 1964''  (1966)  pp. 237–274</TD></TR>
 
<TR><TD valign="top">[6]</TD> <TD valign="top">  L.A. Skornyakov,  "Lattice theory"  ''Itogi Nauk. Algebra, 1964''  (1966)  pp. 237–274</TD></TR>
 
<TR><TD valign="top">[7]</TD> <TD valign="top">  M.M. Glukhov,  I.V. Stelletskii,  T.S. Fofanova,  "Lattice theory"  ''Progress in Math.'' , '''12'''  (1972)  pp. 111–170  ''Itogi Nauk. Algebra Topol. Geom. 1968''  (1970)  pp. 101–154</TD></TR>
 
<TR><TD valign="top">[7]</TD> <TD valign="top">  M.M. Glukhov,  I.V. Stelletskii,  T.S. Fofanova,  "Lattice theory"  ''Progress in Math.'' , '''12'''  (1972)  pp. 111–170  ''Itogi Nauk. Algebra Topol. Geom. 1968''  (1970)  pp. 101–154</TD></TR>
<TR><TD valign="top">[8a]</TD> <TD valign="top"> Saliĭ, V.N. (ed.), ''Ordered sets and lattices'' , '''3''' , Saratov (1975) (In Russian) {{ZBL|0339.00008}}</TD></TR>
+
<TR><TD valign="top">[8a]</TD> <TD valign="top"> Saliĭ, V.N. (ed.), ''Ordered sets and lattices'' , Uporyad. Mnozhestva Reshetki '''3'''  (1975) 75-100 (In Russian) {{ZBL|0339.00008}}</TD></TR>
<TR><TD valign="top">[8b]</TD> <TD valign="top"> ?, ''Ordered sets and lattices'' , '''7''' , Saratov  (1983) (In Russian)</TD></TR>
+
<TR><TD valign="top">[8b]</TD> <TD valign="top"> Saliĭ, V.N. (ed.), ''Ordered sets and lattices'' , Uporyad. Mnozhestva Reshetki '''7''' (1983) 121-142 (In Russian) {{ZBL|0547.06002}}</TD></TR>
 
<TR><TD valign="top">[9]</TD> <TD valign="top">  T.S. Blyth,  M.F. Janowitz,  "Residuation theory" , Pergamon  (1972)</TD></TR>
 
<TR><TD valign="top">[9]</TD> <TD valign="top">  T.S. Blyth,  M.F. Janowitz,  "Residuation theory" , Pergamon  (1972)</TD></TR>
 
<TR><TD valign="top">[10]</TD> <TD valign="top"> T. Katriňák (ed.), ''Ordered sets and lattices (Bratislava, 1985)'' , Bratislava  (1989)  (In Russian) {{ZBL|0653.00003}}</TD></TR>
 
<TR><TD valign="top">[10]</TD> <TD valign="top"> T. Katriňák (ed.), ''Ordered sets and lattices (Bratislava, 1985)'' , Bratislava  (1989)  (In Russian) {{ZBL|0653.00003}}</TD></TR>
 
<TR><TD valign="top">[11]</TD> <TD valign="top">  V.N. Salii,  "Lattices with unique complements" , Moscow  (1984)  (In Russian)</TD></TR>
 
<TR><TD valign="top">[11]</TD> <TD valign="top">  V.N. Salii,  "Lattices with unique complements" , Moscow  (1984)  (In Russian)</TD></TR>
 
<TR><TD valign="top">[12]</TD> <TD valign="top">  L. Beran,  "Orthomodular lattices" , Reidel  (1985)</TD></TR>
 
<TR><TD valign="top">[12]</TD> <TD valign="top">  L. Beran,  "Orthomodular lattices" , Reidel  (1985)</TD></TR>
<TR><TD valign="top">[13]</TD> <TD valign="top">  G. Gierz,  K.H. Hofmann,  K. Keimel,  J.D. Lawson,  M.V. Mislove,  D.S. Scott,  "A compendium of continuous lattices" , Springer  (1980)</TD></TR>
+
<TR><TD valign="top">[13]</TD> <TD valign="top">  G. Gierz,  K.H. Hofmann,  K. Keimel,  J.D. Lawson,  M.V. Mislove,  D.S. Scott,  "A compendium of continuous lattices" , Springer  (1980) {{ISBN|3-540-10111-X}}  {{ZBL|0452.06001}}</TD></TR>
 
<TR><TD valign="top">[14]</TD> <TD valign="top">  G. Kalmbach,  "Orthomodular lattices" , Acad. Press  (1983)</TD></TR>
 
<TR><TD valign="top">[14]</TD> <TD valign="top">  G. Kalmbach,  "Orthomodular lattices" , Acad. Press  (1983)</TD></TR>
 
<TR><TD valign="top">[15]</TD> <TD valign="top">  G. Kalmbach,  "Measures and Hilbert lattices" , World Sci.  (1986)</TD></TR>
 
<TR><TD valign="top">[15]</TD> <TD valign="top">  G. Kalmbach,  "Measures and Hilbert lattices" , World Sci.  (1986)</TD></TR>
Line 99: Line 217:
  
 
====Comments====
 
====Comments====
Naturally, most theorems in lattice theory require some hypothesis about the lattice. The remarkable exception is the Funayama–Nakayama theorem: The lattice of congruence relations on any lattice is distributive (see e.g. [[#References|[1]]] or [[#References|[2]]]). There is also one major unsolved (in 1989) problem about arbitrary finite lattices. Every finite lattice is complete and algebraic, and therefore is representable as the lattice of congruence relations on some [[Universal algebra|universal algebra]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763072.png" />. Can <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763073.png" /> be taken finite? P.P. Pálfy and P. Pudlák showed [[#References|[a4]]] that this is closely related to a problem in finite group theory, which they solved for solvable groups. W. Feit [[#References|[a1]]] began the study of the problem in simple groups.
+
Naturally, most theorems in lattice theory require some hypothesis about the lattice. The remarkable exception is the Funayama–Nakayama theorem: The lattice of congruence relations on any lattice is distributive (see e.g. [[#References|[1]]] or [[#References|[2]]]). There is also one major unsolved (in 1989) problem about arbitrary finite lattices. Every finite lattice is complete and algebraic, and therefore is representable as the lattice of congruence relations on some [[Universal algebra|universal algebra]] $  A $.  
 +
Can $  A $
 +
be taken finite? P.P. Pálfy and P. Pudlák showed [[#References|[a4]]] that this is closely related to a problem in finite group theory, which they solved for solvable groups. W. Feit [[#References|[a1]]] began the study of the problem in simple groups.
  
In topology, the awkwardness of Krull dimension (called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763074.png" /> in [[Dimension|Dimension]] of an associative ring) has been shown to reside only in the rigidity of the definition. Instead, define the dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763075.png" /> of a distributive lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763076.png" />, like <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763077.png" />, as the maximum length of a chain of prime ideals of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763078.png" />. Define the dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763079.png" /> of a topological space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763080.png" /> as the minimum of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763081.png" /> over lattices of open sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763082.png" /> which form a basis for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763083.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763084.png" /> for the Noetherian spaces for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763085.png" /> is really used; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763086.png" /> for separable metrizable spaces [[#References|[a2]]]; for general metrizable spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763087.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763088.png" />, [[#References|[a3]]].
+
In topology, the awkwardness of Krull dimension (called $  \mathop{\rm adim} $
 +
in [[Dimension|Dimension]] of an associative ring) has been shown to reside only in the rigidity of the definition. Instead, define the dimension $  \mathop{\rm dim}  L $
 +
of a distributive lattice $  L $,  
 +
like $  \mathop{\rm Kdim} $,  
 +
as the maximum length of a chain of prime ideals of $  L $.  
 +
Define the dimension $  \mathop{\rm gdim} X $
 +
of a topological space $  X $
 +
as the minimum of $  \mathop{\rm dim}  L $
 +
over lattices of open sets $  L $
 +
which form a basis for $  X $.  
 +
Then $  \mathop{\rm gdim} = \mathop{\rm adim} $
 +
for the Noetherian spaces for which $  \mathop{\rm adim} $
 +
is really used; $  \mathop{\rm gdim} = \mathop{\rm dim} $
 +
for separable metrizable spaces [[#References|[a2]]]; for general metrizable spaces $  X $,  
 +
$  \mathop{\rm ind}  X \leq  \mathop{\rm gdim}  X \leq  \mathop{\rm dim}  X $,  
 +
[[#References|[a3]]].
  
 
The first significant work on lattices was done by E. Schröder [[#References|[a5]]] and R. Dedekind [[#References|[a6]]]. The development of the subject in the 1930-s was largely the work of G. Birkhoff [[#References|[a7]]] and O. Ore ; the latter used the term  "structure"  instead of  "lattice" , but this quickly became obsolete except in Russia, where it survived until the 1960-s.
 
The first significant work on lattices was done by E. Schröder [[#References|[a5]]] and R. Dedekind [[#References|[a6]]]. The development of the subject in the 1930-s was largely the work of G. Birkhoff [[#References|[a7]]] and O. Ore ; the latter used the term  "structure"  instead of  "lattice" , but this quickly became obsolete except in Russia, where it survived until the 1960-s.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W. Feit,  "An interval in the subgroup lattice of a finite group which is isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057630/l05763089.png" />"  ''Alg. Univ.'' , '''17'''  (1983)  pp. 220–221</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R. Galián,  "Theoriá de la dimensión" , Madrid  (1979)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.R. Isbell,  "Graduation and dimension in locales"  I.H. James (ed.)  E.H. Kronheimer (ed.) , ''Aspects of Topology: in Memory of Hugh Dowker'' , ''Lect. notes London Math. Soc.'' , '''93''' , Cambridge Univ. Press  (1985)  pp. 195–210</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  P.P. Pálfy,  P. Pudlák,  "Congruence lattices of finite algebras and intervals in subgroup lattices of finite groups"  ''Alg. Univ.'' , '''11'''  (1980)  pp. 22–27</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  E. Schröder,  "Verlesungen über die Algebra der Logik" , Teubner  (1890)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R. Dedekind,  "Ueber die von drei Moduln erzeugte Dualgruppe"  ''Math. Ann.'' , '''53'''  (1900)  pp. 371–403</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  G. Birkhoff,  "On the combination of subalgebras"  ''Proc. Cambridge Philos. Soc.'' , '''29'''  (1933)  pp. 441–464</TD></TR><TR><TD valign="top">[a8a]</TD> <TD valign="top">  O. Ore,  "On the foundation of abstract algebra I"  ''Ann. of Math.'' , '''36'''  (1935)  pp. 406–437</TD></TR><TR><TD valign="top">[a8b]</TD> <TD valign="top">  O. Ore,  "On the foundation of abstract algebra II"  ''Ann. of Math.'' , '''37'''  (1936)  pp. 265–292</TD></TR></table>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W. Feit,  "An interval in the subgroup lattice of a finite group which is isomorphic to $M_7$"  ''Alg. Univ.'' , '''17'''  (1983)  pp. 220–221</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R. Galián,  "Theoriá de la dimensión" , Madrid  (1979)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.R. Isbell,  "Graduation and dimension in locales"  I.H. James (ed.)  E.H. Kronheimer (ed.) , ''Aspects of Topology: in Memory of Hugh Dowker'' , ''Lect. notes London Math. Soc.'' , '''93''' , Cambridge Univ. Press  (1985)  pp. 195–210</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  P.P. Pálfy,  P. Pudlák,  "Congruence lattices of finite algebras and intervals in subgroup lattices of finite groups"  ''Alg. Univ.'' , '''11'''  (1980)  pp. 22–27</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  E. Schröder,  "Verlesungen über die Algebra der Logik" , Teubner  (1890)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R. Dedekind,  "Ueber die von drei Moduln erzeugte Dualgruppe"  ''Math. Ann.'' , '''53'''  (1900)  pp. 371–403</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  G. Birkhoff,  "On the combination of subalgebras"  ''Proc. Cambridge Philos. Soc.'' , '''29'''  (1933)  pp. 441–464</TD></TR><TR><TD valign="top">[a8a]</TD> <TD valign="top">  O. Ore,  "On the foundation of abstract algebra I"  ''Ann. of Math.'' , '''36'''  (1935)  pp. 406–437</TD></TR><TR><TD valign="top">[a8b]</TD> <TD valign="top">  O. Ore,  "On the foundation of abstract algebra II"  ''Ann. of Math.'' , '''37'''  (1936)  pp. 265–292</TD></TR></table>

Latest revision as of 15:31, 11 November 2023


structure

A partially ordered set in which each two-element subset has both a least upper and a greatest lower bound. This implies the existence of such bounds for every non-empty finite subset.

Examples.

1) A linearly ordered set (or chain) $ M $ where for $ a, b \in M $, if $ a \leq b $, then

$$ \sup \{ a, b \} = b,\ \ \inf \{ a, b \} = a. $$

2) The subspaces of a vector space ordered by inclusion, where

$$ \sup \{ A, B \} = \{ {x } : {x = a + b, a \in A, b \in B } \} , $$

$$ \inf \{ A, B \} = A \cap B. $$

3) The subsets of a given set ordered by inclusion, where

$$ \sup \{ A, B \} = A \cup B, $$

$$ \inf \{ A, B \} = A \cap B. $$

4) The non-negative integers ordered by divisibility: $ a \leq b $ if $ b = ac $ for a certain $ c $; where $ \sup \{ a, b \} $ is the least common multiple of $ a $ and $ b $, and $ \inf \{ a, b \} $ is the greatest common divisor of $ a $ and $ b $.

5) The real-valued functions defined on the interval $ [ 0, 1] $ and ordered by the condition: $ f \leq g $ if $ f( t) \leq g( t) $ for all $ t \in [ 0, 1] $, where

$$ \sup \{ f, g \} = u , $$

in which

$$ u( t) = \max \{ f( t), g( t) \} , $$

and

$$ \inf \{ f, g \} = v, $$

in which

$$ v( t) = \min \{ f( t) , g( t) \} . $$

Let $ M $ be a lattice. $ M $ becomes a universal algebra with two binary operations if one defines

$$ a + b = \sup \{ a, b \} , $$

$$ a \cdot b = \inf \{ a, b \} $$

(the symbols $ \cup $ and $ \cap $ or $ \lor $ and $ \wedge $ are often used instead of $ + $ and $ \cdot $). This universal algebra satisfies the following identities:

$$ \begin{array}{l} ( 1) a + a = a; \\ ( 2) a + b = b + a; \\ ( 3) ( a + b) + c = a + ( b + c); \\ ( 4) a( a + b) = a; \end{array} \ \begin{array}{l} ( 1 ^ \prime ) a \cdot a = a; \\ ( 2 ^ \prime ) a \cdot b = b \cdot a; \\ ( 3 ^ \prime ) ( a \cdot b) \cdot c = a \cdot ( b \cdot c); \\ ( 4 ^ \prime ) a + a \cdot b = a. \end{array} $$

Conversely, if $ M $ is a set with two binary operations that have the properties –, ( $ 1 ^ \prime $)–( $ 4 ^ \prime $) mentioned above, then an order $ \leq $ can be imposed on $ M $ by setting $ a \leq b $ if $ a + b = b $( it turns out in this case that $ a \leq b $ if and only if $ a \cdot b = a $). The resulting partially ordered set will be a lattice in which

$$ \sup \{ a, b \} = a + b \ \ \textrm{ and } \ \inf \{ a, b \} = a \cdot b. $$

In this way a lattice can be defined as a universal algebra satisfying the identities –, ( $ 1 ^ \prime $)–( $ 4 ^ \prime $), i.e. lattices form a variety of universal algebras.

If a partially ordered set is regarded as a small category, then it is a lattice if and only if has products and coproducts of pairs of objects.

If $ P $ and $ P ^ \prime $ are lattices and if $ f $: $ P \rightarrow P ^ \prime $ is an isomorphism of partially ordered sets, then $ f $ is also an isomorphism of the corresponding universal algebras, i.e.

$$ f( x + y) = f( x) + f( y) \ \textrm{ and } \ f( xy) = f( x) \cdot f( y) $$

for any $ x, y \in P $. However, an arbitrary isotone mapping of $ P $ into $ P ^ \prime $ is not necessarily a homomorphism of these lattices considered as universal algebras. Thus, for any $ a \in P $, the mappings $ f( x) = x + a $ and $ g( x) = x \cdot a $ are isotone mappings of the lattice $ P $ into itself, but they are homomorphisms if and only if $ P $ is a distributive lattice. However, the first of these mappings is a homomorphism of the semi-lattice $ P $ with the operation $ + $, and the second is a homomorphism of the semi-lattice $ P $ with the operation $ \cdot $. The class of all lattices forms a category if homomorphisms are taken as morphisms.

An anti-homomorphism of a lattice $ P $ into a lattice $ P ^ \prime $ is a mapping $ f: P \rightarrow P ^ \prime $ such that

$$ f( x + y) = f( x) \cdot f( y) \ \textrm{ and } \ f( x \cdot y ) = f( x) + f( y) , $$

for any $ x, y \in P $. A composite of two anti-homomorphisms is a homomorphism. A partially ordered set that is anti-isomorphic to a lattice is a lattice.

By coordinatization of a lattice is meant the finding of an algebraic system (most often a universal algebra) such that the given lattice is isomorphic to the lattice of subsystems, to the lattice of congruences or to some other lattice associated with this algebraic system or universal algebra. An arbitrary lattice with a 0 and a 1 is coordinatized by the partially ordered semi-group of its residual mappings (cf. Residual mapping) into itself, and turns out to be isomorphic to the lattice of right annihilators of this semi-group. The semi-group itself is a Baer semi-group, i.e. the right and left annihilators of each of its elements are generated by idempotents.

The most important results are obtained for lattices subjected to some kind of additional restrictions (see Algebraic lattice; Atomic lattice; Brouwer lattice; Vector lattice; Modular lattice; Distributive lattice; Multiplicative lattice; Orthomodular lattice; Complete lattice; Continuous lattice; Free lattice; Lattice with complements; Boolean algebra). For specific problems in the theory of lattices see Ideal; Filter; Completion, MacNeille (of a partially ordered set). Algebraic systems that are at the same time lattices play a special role (see Lattice-ordered group). The majority of applications of the theory of lattices are associated with Boolean algebras. Other classes of lattices have been used in quantum mechanics and physics.

The concept of a lattice first arose in the late 19th century and was connected with the fact that many results about the set of ideals of a ring or the set of normal subgroups of a group seemed analogous and could be proved in the framework of modular lattices. As an independent branch of algebra, the theory of lattices was developed in the 1930s.

References

[1] G. Birkhoff, "Lattice theory" , Colloq. Publ. , 25 , Amer. Math. Soc. (1973)
[2] G. Grätzer, "General lattice theory" , Birkhäuser (1978) (Original: Lattice theory. First concepts and distributive lattices. Freeman, 1978)
[3] V.N. Salii, "Lectures on lattice theory" , Saratov (1970) (In Russian)
[4] L.A. Skornyakov, "Complemented modular lattices and regular rings" , Oliver & Boyd (1964) (Translated from Russian)
[5] L.A. Skornyakov, "Elements of lattice theory" , A. Hilger (1977) (Translated from Russian)
[6] L.A. Skornyakov, "Lattice theory" Itogi Nauk. Algebra, 1964 (1966) pp. 237–274
[7] M.M. Glukhov, I.V. Stelletskii, T.S. Fofanova, "Lattice theory" Progress in Math. , 12 (1972) pp. 111–170 Itogi Nauk. Algebra Topol. Geom. 1968 (1970) pp. 101–154
[8a] Saliĭ, V.N. (ed.), Ordered sets and lattices , Uporyad. Mnozhestva Reshetki 3 (1975) 75-100 (In Russian) Zbl 0339.00008
[8b] Saliĭ, V.N. (ed.), Ordered sets and lattices , Uporyad. Mnozhestva Reshetki 7 (1983) 121-142 (In Russian) Zbl 0547.06002
[9] T.S. Blyth, M.F. Janowitz, "Residuation theory" , Pergamon (1972)
[10] T. Katriňák (ed.), Ordered sets and lattices (Bratislava, 1985) , Bratislava (1989) (In Russian) Zbl 0653.00003
[11] V.N. Salii, "Lattices with unique complements" , Moscow (1984) (In Russian)
[12] L. Beran, "Orthomodular lattices" , Reidel (1985)
[13] G. Gierz, K.H. Hofmann, K. Keimel, J.D. Lawson, M.V. Mislove, D.S. Scott, "A compendium of continuous lattices" , Springer (1980) ISBN 3-540-10111-X Zbl 0452.06001
[14] G. Kalmbach, "Orthomodular lattices" , Acad. Press (1983)
[15] G. Kalmbach, "Measures and Hilbert lattices" , World Sci. (1986)
[16] R.M. McKenzie, G.F. McNulty, R. Taylor, "Algebras, lattices, varieties" , 1 , Wadsworth (1987)
[17] E.T. Schmidt, "A survey on congruence lattice representations" , Teubner (1982)

Comments

Naturally, most theorems in lattice theory require some hypothesis about the lattice. The remarkable exception is the Funayama–Nakayama theorem: The lattice of congruence relations on any lattice is distributive (see e.g. [1] or [2]). There is also one major unsolved (in 1989) problem about arbitrary finite lattices. Every finite lattice is complete and algebraic, and therefore is representable as the lattice of congruence relations on some universal algebra $ A $. Can $ A $ be taken finite? P.P. Pálfy and P. Pudlák showed [a4] that this is closely related to a problem in finite group theory, which they solved for solvable groups. W. Feit [a1] began the study of the problem in simple groups.

In topology, the awkwardness of Krull dimension (called $ \mathop{\rm adim} $ in Dimension of an associative ring) has been shown to reside only in the rigidity of the definition. Instead, define the dimension $ \mathop{\rm dim} L $ of a distributive lattice $ L $, like $ \mathop{\rm Kdim} $, as the maximum length of a chain of prime ideals of $ L $. Define the dimension $ \mathop{\rm gdim} X $ of a topological space $ X $ as the minimum of $ \mathop{\rm dim} L $ over lattices of open sets $ L $ which form a basis for $ X $. Then $ \mathop{\rm gdim} = \mathop{\rm adim} $ for the Noetherian spaces for which $ \mathop{\rm adim} $ is really used; $ \mathop{\rm gdim} = \mathop{\rm dim} $ for separable metrizable spaces [a2]; for general metrizable spaces $ X $, $ \mathop{\rm ind} X \leq \mathop{\rm gdim} X \leq \mathop{\rm dim} X $, [a3].

The first significant work on lattices was done by E. Schröder [a5] and R. Dedekind [a6]. The development of the subject in the 1930-s was largely the work of G. Birkhoff [a7] and O. Ore ; the latter used the term "structure" instead of "lattice" , but this quickly became obsolete except in Russia, where it survived until the 1960-s.

References

[a1] W. Feit, "An interval in the subgroup lattice of a finite group which is isomorphic to $M_7$" Alg. Univ. , 17 (1983) pp. 220–221
[a2] R. Galián, "Theoriá de la dimensión" , Madrid (1979)
[a3] J.R. Isbell, "Graduation and dimension in locales" I.H. James (ed.) E.H. Kronheimer (ed.) , Aspects of Topology: in Memory of Hugh Dowker , Lect. notes London Math. Soc. , 93 , Cambridge Univ. Press (1985) pp. 195–210
[a4] P.P. Pálfy, P. Pudlák, "Congruence lattices of finite algebras and intervals in subgroup lattices of finite groups" Alg. Univ. , 11 (1980) pp. 22–27
[a5] E. Schröder, "Verlesungen über die Algebra der Logik" , Teubner (1890)
[a6] R. Dedekind, "Ueber die von drei Moduln erzeugte Dualgruppe" Math. Ann. , 53 (1900) pp. 371–403
[a7] G. Birkhoff, "On the combination of subalgebras" Proc. Cambridge Philos. Soc. , 29 (1933) pp. 441–464
[a8a] O. Ore, "On the foundation of abstract algebra I" Ann. of Math. , 36 (1935) pp. 406–437
[a8b] O. Ore, "On the foundation of abstract algebra II" Ann. of Math. , 37 (1936) pp. 265–292
How to Cite This Entry:
Lattice. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Lattice&oldid=39464
This article was adapted from an original article by L.A. Skornyakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article