• 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) Both sides previous revision Previous revision 2012/04/01 21:04 evka 2011/05/03 16:46 vkuncak 2010/04/08 11:00 vkuncak 2009/03/31 23:44 vkuncak 2009/03/31 23:41 vkuncak 2009/03/26 13:51 vkuncak 2008/05/07 22:26 giuliano 2008/05/06 23:25 giuliano 2008/05/06 23:25 giuliano 2008/05/06 23:08 giuliano 2008/05/06 23:07 giuliano 2008/04/30 10:50 vkuncak 2008/04/30 10:49 vkuncak 2008/04/30 10:13 vkuncak 2008/04/30 10:12 vkuncak 2008/04/30 10:09 vkuncak 2008/04/30 10:09 vkuncak 2008/04/30 10:08 vkuncak 2008/04/30 10:07 vkuncak 2008/04/30 10:05 vkuncak 2008/04/30 09:57 vkuncak 2008/04/30 09:57 vkuncak 2008/04/30 09:54 vkuncak 2008/04/30 09:53 vkuncak created Next revision Previous revision 2012/04/01 21:04 evka 2011/05/03 16:46 vkuncak 2010/04/08 11:00 vkuncak 2009/03/31 23:44 vkuncak 2009/03/31 23:41 vkuncak 2009/03/26 13:51 vkuncak 2008/05/07 22:26 giuliano 2008/05/06 23:25 giuliano 2008/05/06 23:25 giuliano 2008/05/06 23:08 giuliano 2008/05/06 23:07 giuliano 2008/04/30 10:50 vkuncak 2008/04/30 10:49 vkuncak 2008/04/30 10:13 vkuncak 2008/04/30 10:12 vkuncak 2008/04/30 10:09 vkuncak 2008/04/30 10:09 vkuncak 2008/04/30 10:08 vkuncak 2008/04/30 10:07 vkuncak 2008/04/30 10:05 vkuncak 2008/04/30 09:57 vkuncak 2008/04/30 09:57 vkuncak 2008/04/30 09:54 vkuncak 2008/04/30 09:53 vkuncak created 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.