- English only

# Lab for Automated Reasoning and Analysis LARA

# Differences

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

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. |