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]
@@ Line 1: / Line 1: @@
-====== Lattices ======
-**Definition:** A lattice is a [[:Partial order]] in which every two-element set has a least upper bound and a greatest lower bound.
-**Lemma:** In a lattice every non-empty finite set has a lub ($\sqcup$) and glb ($\sqcap$).
-**Proof:** is by ++| **induction!** ++ \\
-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 $.\\
-The we have again by definition of $\sqcup$, $x \sqsubseteq x \sqcup y$ and $y \sqsubseteq x \sqcup y$. Thus by transitivity we have $x \sqsubseteq a$ and $y \sqsubseteq a$.\\
-Thus we have $S \sqsubseteq a$ and a is an upper bound.\\
-Now suppose that there exists $a^\prime$ such that $S \sqsubseteq a^\prime$. We want $a \sqsubseteq a^\prime$ (a least upper bound):\\
-We have $x \sqsubseteq a^\prime $ and $x \sqsubseteq a^\prime $, thus $x \sqcup y \sqsubseteq a^\prime$. But $z \sqsubseteq a^\prime $, thus $((x \sqcup y) \sqcup z) \sqsubseteq a^\prime $.\\
-Thus $a$ is the lub of our 3 elements set.
-**Lemma:** Every [[Homework08#Problem 2|linear order]] is a lattice.
-If a lattice has least and greatest element, then every finite set (including empty set) has a lub and glb.
-This does not imply there are lub and glb for infinite sets.
-**Example:** In the oder $([0,1),\le)$ with standard ordering on reals is a lattice, the entire set has no lub.
-The set of all rationals of interval $[0,10]$ is a lattice, but the set $\{ x \mid 0 \le x \land x^2 < 2 \}$ has no lub.
-**Definition:** A **complete** lattice is a lattice where every set $S$ of elemenbts has lub, denoted $\sqcup S$, and glb, denoted $\sqcap S$
-(this implies that there is top and bottom as $\sqcup \emptyset = \bot$ and $\sqcap \emptyset = \top$. This is because every element is an upper bound and a lower bound of $\emptyset$ : $\forall x. \forall y \in \emptyset. y \sqsubseteq x$ is valid, as well as $\forall x. \forall y \in \emptyset. y \sqsupseteq x$).
-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.++
-**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).
-**Lemma:** In every lattice, $x \sqcup (x \sqcap y) = x$.\\
-**Proof:** \\
-We trivially have $x \sqsubseteq x \sqcup (x \sqcap y)$.\\
-Let's prove that $x \sqcup (x \sqcap y) \sqsubseteq x$:\\
-$x$ is an upper bound of $x$ and $x \sqcap y$, $x \sqcup (x \sqcap y)$ is the least upper bound of $x$ and $x \sqcap y$, thus $x \sqcup (x \sqcap y) \sqsubseteq x $.
-**Definition:** A lattice is //distributive// iff
-\[
-\begin{array}{l}
-    x \sqcap (y \sqcup z) = (x \sqcap y) \sqcup (x \sqcap z) \\
-    x \sqcup (y \sqcap z) = (x \sqcup y) \sqcap (x \sqcup z)
-\end{array}
-\]
-**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.
-===== References =====
-  * [[wp>Lattice (order)]]
-  * [[http://bigcheese.math.sc.edu/~mcnulty/alglatvar/lat0.pdf|lecture notes by J.B. Nation]] or
-  * [[http://bigcheese.math.sc.edu/~mcnulty/alglatvar/burrissanka.pdf|Chapter I of a Course in Universal Algebra]].