Differences
This shows you the differences between two versions of the page.
sav08:lattices [2010/04/08 11:00] 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 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]]. | ||
- | |||
- | |||