Differences

This shows you the differences between two versions of the page.

lattices [2010/07/29 18:30]
127.0.0.1 external edit
lattices [2016/01/27 11:48] (current)
jipsen
Line 2: Line 2:
Abbreviation: **Lat** Abbreviation: **Lat**
 +
 +
====Definition==== ====Definition====
A \emph{lattice} is a structure $\mathbf{L}=\langle L,\vee ,\wedge A \emph{lattice} is a structure $\mathbf{L}=\langle L,\vee ,\wedge
Line 7: Line 9:
called the \emph{join} and \emph{meet}, such that called the \emph{join} and \emph{meet}, such that
- +$\vee ,\wedge $ are associative:  $(x\vee y)\vee z=x\vee (y\vee z)$, $(x\wedge y)\wedge z=x\wedge (y\wedge z)$
-$\vee ,\wedge $ are associative:  $(x\vee y)\vee z=x\vee (y\vee z)$,$\ (x\wedge y)\wedge z=x\wedge (y\wedge z)$ +
$\vee ,\wedge $ are commutative:  $x\vee y=y\vee x$, $x\wedge y=y\wedge x$ $\vee ,\wedge $ are commutative:  $x\vee y=y\vee x$, $x\wedge y=y\wedge x$
- 
$\vee ,\wedge $ are absorbtive:  $(x\vee y)\wedge x=x$, $(x\wedge y)\vee x=x$. $\vee ,\wedge $ are absorbtive:  $(x\vee y)\wedge x=x$, $(x\wedge y)\vee x=x$.
Remark: Remark:
-It follows that $\vee $ and $\wedge $ are idempotent: $x\vee x=x$, $x\wedge +It follows that $\vee $ and $\wedge $ are idempotent: $x\vee x=x$, $x\wedge x=x$.
-x=x$.+
This definition shows that lattices form a variety. This definition shows that lattices form a variety.
Line 28: Line 26:
==Morphisms== ==Morphisms==
Let $\mathbf{L}$ and $\mathbf{M}$ be lattices. A morphism from $\mathbf{L}$ Let $\mathbf{L}$ and $\mathbf{M}$ be lattices. A morphism from $\mathbf{L}$
-to $\mathbf{M}$ is a function $h:Larrow M$ that is a homomorphism: +to $\mathbf{M}$ is a function $h:L\to M$ that is a homomorphism:
$h(x\vee y)=h(x)\vee h(y)$, $h(x\wedge y)=h(x)\wedge h(y)$ $h(x\vee y)=h(x)\vee h(y)$, $h(x\wedge y)=h(x)\wedge h(y)$
 +
 +
====Definition==== ====Definition====
A \emph{lattice} is a structure $\mathbf{L}=\langle L,\vee ,\wedge A \emph{lattice} is a structure $\mathbf{L}=\langle L,\vee ,\wedge
Line 37: Line 37:
$\langle L,\vee \rangle $ and $\langle L,\wedge $\langle L,\vee \rangle $ and $\langle L,\wedge
\rangle $ are \rangle $ are
-[[Semilattices]], and +[[semilattices]], and
$\vee ,\wedge $ are absorbtive:  $(x\vee y)\wedge x=x$, $(x\wedge y)\vee x=x$ $\vee ,\wedge $ are absorbtive:  $(x\vee y)\wedge x=x$, $(x\wedge y)\vee x=x$
 +
====Definition==== ====Definition====
A \emph{lattice} is a structure $\mathbf{L}=\langle L,\leq A \emph{lattice} is a structure $\mathbf{L}=\langle L,\leq
\rangle $ that is a \rangle $ that is a
-[[Partially ordered sets]] in which all elements $x,y\in L$ have a+[[partially ordered set]] in which all elements $x,y\in L$ have
 + 
 +least upper bound:  $z=x\vee y\Longleftrightarrow x\leq z$, $y\leq z\ \mbox{and}\ \forall w\ (x\leq w$, $y\leq w\Longrightarrow z\leq w)$ and a
-least upper bound:  $z=x\vee y\Longleftrightarrow x\leq z$, $y\leq z \mbox{and}\ \forall w\ (x\leq w$, $y\leq w\Longrightarrow z\leq w)$+greatest lower bound:  $z=x\wedge y\Longleftrightarrow z\leq x$, $z\leq y\ \mbox{and}\ \forall w\ (w\leq x$, $w\leq y\Longrightarrow w\leq z)$
-greatest lower bound:  $z=x\wedge y\Longleftrightarrow z\leq x$, $z\leq y \mbox{and}\ \forall w\ (w\leq x$, $w\leq y\Longrightarrow w\leq z)$ 
====Definition==== ====Definition====
A \emph{lattice} is a structure $\mathbf{L}=\langle L,\vee ,\wedge A \emph{lattice} is a structure $\mathbf{L}=\langle L,\vee ,\wedge
,\leq \rangle $ such that $\langle L,\leq \rangle $ is a ,\leq \rangle $ such that $\langle L,\leq \rangle $ is a
-[[Partially ordered sets]] and the following quasiequations hold:+[[partially ordered set]] and the following quasiequations hold:
-$\vee $-left:  $x\leq z$, $y\leq z\ \Longrightarrow x\vee y\leq z$+$\vee $-left:  $x\leq z$ and $y\leq z\ \Longrightarrow x\vee y\leq z$
$\vee $-right:  $z\leq x\Longrightarrow z\leq x\vee y$, $\quad z\leq y\Longrightarrow z\leq x\vee y$ $\vee $-right:  $z\leq x\Longrightarrow z\leq x\vee y$, $\quad z\leq y\Longrightarrow z\leq x\vee y$
-$\wedge $-right:  $z\leq x$, $z\leq y\Longrightarrow z\leq x\wedge y$+$\wedge $-right:  $z\leq x$ and $z\leq y\Longrightarrow z\leq x\wedge y$
$\wedge $-left:  $x\leq z\Longrightarrow x\wedge y\leq z$, $\quad y\leq z\Longrightarrow x\wedge y\leq z$ $\wedge $-left:  $x\leq z\Longrightarrow x\wedge y\leq z$, $\quad y\leq z\Longrightarrow x\wedge y\leq z$
Line 67: Line 68:
These quasiequations give a cut-free Gentzen system to decide the equational These quasiequations give a cut-free Gentzen system to decide the equational
theory of lattices. theory of lattices.
 +
====Examples==== ====Examples====
Line 72: Line 74:
subsets of a sets $S$, ordered by inclusion. subsets of a sets $S$, ordered by inclusion.
-[[Lattices (mace)]]+/*[[Lattices (mace)]]*/
Line 85: Line 87:
^[[Locally finite]]  |no | ^[[Locally finite]]  |no |
^[[Residual size]]  |unbounded | ^[[Residual size]]  |unbounded |
-Congruence distributive & yes +^[[Congruence distributive]]  |yes [(Nenosuke Funayama,Tadasi Nakayama,\emph{On the distributivity of a lattice of lattice-congruences},
- +
-Nenosuke Funayama,Tadasi Nakayama,\emph{On the distributivity of a lattice of lattice-congruences},+
Proc. Imp. Acad. Tokyo, Proc. Imp. Acad. Tokyo,
-\textbf{18}1942,553--554[[MRreview]+\textbf{18} 1942, 553--554)] |
-\\\hline+
^[[Congruence modular]]  |yes | ^[[Congruence modular]]  |yes |
^[[Congruence n-permutable]]  |no | ^[[Congruence n-permutable]]  |no |
Line 99: Line 98:
^[[Equationally def. pr. cong.]]  |no | ^[[Equationally def. pr. cong.]]  |no |
^[[Amalgamation property]]  |yes | ^[[Amalgamation property]]  |yes |
-Strong amalgamation property & yes +^[[Strong amalgamation property]]  |yes [(Bjarni J\'onsson,\emph{Universal relational systems}, 
- +Math. Scand., \textbf{4} 1956, 193--208)] |
-Bjarni J\'onsson,\emph{Universal relational systems}, +
-Math. Scand., +
-\textbf{4}1956,193--208[[MRreview]+
-\\\hline+
^[[Epimorphisms are surjective]]  |yes | ^[[Epimorphisms are surjective]]  |yes |
====Finite members==== ====Finite members====
Line 127: Line 122:
f(17)= &15150569446\\ f(17)= &15150569446\\
f(18)= &165269824761\\ f(18)= &165269824761\\
-\end{array}$ +f(19)= &1901910625578 
- +\end{array}$[(Jobst Heitzig, J\"urgen Reinhold, \emph{Counting finite lattices},
-Jobst Heitzig, J\"urgen Reinhold, \emph{Counting finite lattices},+
Algebra Universalis, Algebra Universalis,
-\textbf{48}, 2002, 43--53[[MRreview]]+\textbf{48}, 2002, 43--53)][(Peter Jipsen, Nathan Lawless, \emph{Generating all finite modular lattices of a given size},  
 +Algebra Universalis, \textbf{74}, 2015, 253--264)]
-[[Lattices of size 1 to 6]] 
-[[Finite lattices]] of size $\le 7$+[[http://math.chapman.edu/~jipsen/posets/lattices77.html|Diagrams of lattices of size 2 to 7]] 
 + 
 +/*[[Finite lattices]] of size $\le 7$
[[Subdirectly irreducible lattices]] of size $\le 7$ [[Subdirectly irreducible lattices]] of size $\le 7$
[[Lattices not in some subclasses]] of size $\le 7$ [[Lattices not in some subclasses]] of size $\le 7$
 +*/
====Subclasses==== ====Subclasses====
Line 161: Line 157:
====References==== ====References====
-[(Ln19xx> 
-)]