Differences
This shows you the differences between two versions of the page.
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). |