Lab for Automated Reasoning and Analysis LARA

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
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