Lab for Automated Reasoning and Analysis LARA

Differences

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

Link to this comparison view

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.
 
sav08/lattices.txt · Last modified: 2015/04/21 17:30 (external edit)
 
© EPFL 2018 - Legal notice