12.2: Lattices

Last updated
Save as PDF

Page ID: 86178

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

In this section, we restrict our discussion to lattices, those posets for which every pair of elements has both a greatest lower bound and least upper bound. We first introduce some notation.

Definition $\PageIndex{1}$: Join, Meet

Let $(L, \preceq)$ be a poset, and $a, b \in L\text{.}$ We define:

$a \lor b\text{,}$ read “$a$ join $b$”, as the least upper bound of $a$ and $b\text{,}$ if it exists. and
$a \land b\text{,}$ read “$a$ meet $b$”, as the greatest lower bound of $a$ and $b\text{,}$ if it exists.

Since the join and meet produce a unique result in all cases where they exist, by Theorem 13.1.1, we can consider them as binary operations on a set if they always exist. Thus the following definition:

Definition $\PageIndex{2}$: Lattice

A lattice is a poset $(L, \preceq)$ for which every pair of elements has a greatest lower bound and least upper bound. Since a lattice $L$ is an algebraic system with binary operations $\lor$ and $\land\text{,}$ it is denoted by $[L; \lor, \land]\text{.}$ If we want to make it clear what partial ordering the lattice is based on, we say it is a lattice under $\preceq\text{.}$

Example $\PageIndex{1}$: The Power Set of a Three Element Set

Consider the poset $(\mathcal{P}(A),\subseteq)$ we examined in Example 13.1.3. It isn't too surprising that every pair of sets had a greatest lower bound and least upper bound. Thus, we have a lattice in this case; and $A\lor B = A \cup B$ and $A\land B = A \cap B\text{.}$ The reader is encouraged to write out the operation tables $[\mathcal{P}(A); \cup, \cap]\text{.}$

Our first concrete lattice can be generalized to the case of any set $A\text{,}$ producing the lattice $[\mathcal{P}(A); \lor, \land]\text{,}$ where the join operation is the set operation of union and the meet operation is the operation intersection; that is, $\lor =\cup$ and $\land =\cap\text{.}$

It can be shown (see the exercises) that the commutative laws, associative laws, idempotent laws, and absorption laws are all true for any lattice. A concrete example of this is clearly $[\mathcal{P}(A); \cup, \cap ]\text{,}$ since these laws hold in the algebra of sets. This lattice also has distributive property in that join is distributive over meet and meet is distributive over join. However, this is not always the case for lattices in general.

Definition $\PageIndex{3}$: Distributive Lattice

Let $\mathcal{L}=[L; \lor, \land ]$ be a lattice under $\preceq$ . $\mathcal{L}$ is called a distributive lattice if and only if the distributive laws hold; that is, for all $a, b, c \in L$ we have

\begin{equation*} \begin{array}{c} a \lor (b \land c) = (a \lor b) \land (a \lor c)\\ and \\ a \land (b \lor c) = (a \land b) \lor (a \land c)\\ \end{array} \end{equation*}

Example $\PageIndex{2}$: A Nondistributive Lattice

We now give an example of a lattice where the distributive laws do not hold. Let $L = \{\pmb{0},a,b,c,\pmb{1}\}\text{.}$ We define the partial ordering $\preceq$ on $L$ by the set

\begin{equation*} \{(\pmb{0},\pmb{0}),(\pmb{0},a),(\pmb{0},b),(\pmb{0},c),(\pmb{0},\pmb{1}),(a,a),(a,\pmb{1}),(b,b),(b,\pmb{1}),(c,c),(c,\pmb{1}),(\pmb{1},\pmb{1})\} \end{equation*}

The operation tables for $\lor$ and $\land$ on $L$ are:

\begin{equation*} \begin{array}{cc} \begin{array}{c|ccccc} \lor & \pmb{0} & a & b & c & \pmb{1} \\ \hline \pmb{0} & \pmb{0} & a & b & c & \pmb{1} \\ a & a & a & \pmb{1} & \pmb{1} & \pmb{1} \\ b & b & \pmb{1} & b & \pmb{1} & \pmb{1} \\ c & c & \pmb{1} & \pmb{1} & c & \pmb{1} \\ \pmb{1} & \pmb{1} & \pmb{1} & \pmb{1} & \pmb{1} & \pmb{1} \\ \end{array} & \begin{array}{c|ccccc} \land & \pmb{0} & a & b & c & \pmb{1} \\ \hline \pmb{0} & \pmb{0} & \pmb{0} & \pmb{0} & \pmb{0} & \pmb{0} \\ a & \pmb{0} & a & \pmb{0} & \pmb{0} & a \\ b & \pmb{0} & \pmb{0} & b & \pmb{0} & b \\ c & \pmb{0} & \pmb{0} & \pmb{0} & c & c \\ \pmb{1} & \pmb{0} & a & b & c & \pmb{1} \\ \end{array}\\ \end{array} \end{equation*}

Since every pair of elements in $L$ has both a join and a meet, $[L; \lor , \land ]$ is a lattice (under divides). Is this lattice distributive? We note that: $a \lor (c \land b) = a \lor \pmb{0} = a$ and $(a \lor c) \land (a \lor b) = \pmb{1} \land \pmb{1} = \pmb{1}\text{.}$ Therefore, $a \lor (b \land c) \neq (a \lor b) \land (a \lor c)$ for some values of $a, b, c \in L\text{.}$ Thus, this lattice is not distributive.

Our next observation uses the term “sublattice”, which we have not defined at this point, but we would hope that you could anticipate a definition, and we will leave it as an exercises to do so.

It can be shown that a lattice is nondistributive if and only if it contains a sublattice isomorphic to one of the lattices in Figure $\PageIndex{1}$. The ordering diagram on the right of this figure, produces the diamond lattice, which is precisely the one that is defined in Example $\PageIndex{2}$. The lattice based on the left hand poset is called the pentagon lattice.

$clipboard_ed6294eb14e1c07499d036e6ed2294341.png$ Figure $\PageIndex{1}$: Nondistributive lattices, the pentagon and diamond lattices

13.2.1: Exercises

Exercise $\PageIndex{1}$

Let $L$ be the set of all propositions generated by $p$ and $q\text{.}$ What are the meet and join operations in this lattice under implication? What are the maximum and minimum elements?

Exercise $\PageIndex{2}$

Which of the posets in Exercise 13.1.3 are lattices? Which of the lattices are distributive?

Exercise $\PageIndex{3}$

State the commutative laws, associative laws, idempotent laws, and absorption laws for lattices.
Prove laws you stated.

Exercise $\PageIndex{4}$

Demonstrate that the pentagon lattice is nondistributive.

Exercise $\PageIndex{5}$

What is a reasonable definition of the term sublattice?

Answer: One reasonable definition would be this: Let $[L; \lor, \land ]$ be a lattice and let $K$ be a nonempty subset of $L\text{.}$ Then $K$ is a sublattice of $L$ if and only if $K$ is closed under both $\lor$ and $\land$

Exercise $\PageIndex{6}$

Let $[L; \lor , \land ]$ be a lattice based on a partial ordering $\preceq\text{.}$ Prove that if $a, b, c \in L\text{,}$

$a \preceq a \lor b \text{.}$
$a \land b \preceq a\text{.}$
$b \preceq a$ and $c \preceq a \Rightarrow b \lor c \preceq a\text{.}$

Search

Text Color

Text Size

Margin Size

Font Type

13.2.1: Exercises