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 [2010/04/08 11:00]
vkuncak
sav08:lattices [2012/04/01 21:04]
evka
Line 3: Line 3:
 **Definition:​** A lattice is a [[:Partial order]] in which every two-element set has a least upper bound and a greatest lower bound. **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$).+**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).