• English only

# Differences

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

sav08:lattices [2011/05/03 16:46]
vkuncak
sav08:lattices [2015/04/21 17:30] (current)
Line 5: Line 5:
**Lemma:** In a lattice every non-empty finite set has a lub ($\sqcup$) and glb ($\sqcap$). **Lemma:** In a lattice every non-empty finite set has a lub ($\sqcup$) and glb ($\sqcap$).

-**Proof:** is by ++| **induction!** ++ \\+**Proof:** is by induction!\\
Case where the set S has three elements x,y and z:\\ Case where the set S has three elements x,y and z:\\
Let $a=(x \sqcup y) \sqcup z$. \\ By definition of $\sqcup$ we have $z \sqsubseteq a$ and $x \sqcup y \sqsubseteq a$.\\ Let $a=(x \sqcup y) \sqcup z$. \\ By definition of $\sqcup$ we have $z \sqsubseteq a$ and $x \sqcup y \sqsubseteq a$.\\
Line 28: Line 28:
Note: if you know that you have least upper bounds for all sets, it follows that you also have greatest lower bounds. Note: if you know that you have least upper bounds for all sets, it follows that you also have greatest lower bounds.

-**Proof:​** ​++|by taking the least upper bound of the lower bounds. Converse also holds, dually.+++**Proof:** by taking the least upper bound of the lower bounds. Converse also holds, dually.

**Example:​** Every subset of the set of real numbers has a lub.  This is an axiom of real numbers, the way they are defined (or constructed from rationals). **Example:​** Every subset of the set of real numbers has a lub.  This is an axiom of real numbers, the way they are defined (or constructed from rationals).
Line 39: Line 39:

**Definition:​** A lattice is //​distributive//​ iff **Definition:​** A lattice is //​distributive//​ iff
-$+\begin{equation*} \begin{array}{l} \begin{array}{l} x \sqcap (y \sqcup z) = (x \sqcap y) \sqcup (x \sqcap z) \\ x \sqcap (y \sqcup z) = (x \sqcap y) \sqcup (x \sqcap z) \\ x \sqcup (y \sqcap z) = (x \sqcup y) \sqcap (x \sqcup z) x \sqcup (y \sqcap z) = (x \sqcup y) \sqcap (x \sqcup z) \end{array} \end{array} -$+\end{equation*}

**Example:​** ​ Lattice of all subsets of a set is distributive. ​ Linear order is a distributive lattice. See examples of non-distributive lattices in [[wk>​Distributive lattice]] and the characterization of non-distributive lattices. **Example:​** ​ Lattice of all subsets of a set is distributive. ​ Linear order is a distributive lattice. See examples of non-distributive lattices in [[wk>​Distributive lattice]] and the characterization of non-distributive lattices.