Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav08:tarski_s_fixpoint_theorem [2008/04/30 09:51] vkuncak |
sav08:tarski_s_fixpoint_theorem [2008/04/30 10:49] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Tarski's fixed point theorem ====== | ====== Tarski's fixed point theorem ====== | ||
| - | |||
| - | **Definition** A complete lattice is a [[Lattices|lattice]] where every set of elements $S$ has the least upper bound $\sqcup S$ and the greatest lower bound $\sqcap S$ | ||
| - | (this implies that there is top and bottom as $\sqcup \emptyset = \bot$ and $\sqcap \emptyset = \top$). | ||
| - | |||
| - | (Note: if you know that you have least upper bounds for all sets, it follows that you also have greatest lower bounds, by taking the least upper bound of the lower bounds. Converse also holds, dually.) | ||
| Let $(A,\sqsubseteq)$ be a complete lattice and $G : A \to A$ a monotonic function. | Let $(A,\sqsubseteq)$ be a complete lattice and $G : A \to A$ a monotonic function. | ||