Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
tarski_fixed_point_theorem [2007/04/15 18:19] vkuncak |
tarski_fixed_point_theorem [2007/05/11 17:32] ghid.maatouk |
||
|---|---|---|---|
| Line 12: | Line 12: | ||
| $\mbox{Post} = \{x \mid G(x) \sqsubseteq x \}$ the set of postfix points of $G$ (e.g. $\top$ is a postfix point) | $\mbox{Post} = \{x \mid G(x) \sqsubseteq x \}$ the set of postfix points of $G$ (e.g. $\top$ is a postfix point) | ||
| - | $\mbox{Fix} = \{x \mid G(x) = x\}$ the set of fixed points of $G$ | + | $\mbox{Fix} = \{x \mid G(x) = x\}$ the set of fixed points of $G$. Note that $\mbox{Fix} \subseteq \mbox{Post}$. |
| **Theorem**: Let $a = \sqcap \mbox{Post}$. Then $a$ is the least element of $\mbox{Fix}$. | **Theorem**: Let $a = \sqcap \mbox{Post}$. Then $a$ is the least element of $\mbox{Fix}$. | ||
| Line 28: | Line 28: | ||
| More information: | More information: | ||
| - | * Constructive proof using ordinals, by Cousot & Cousot [[http://www.di.ens.fr/~cousot/COUSOTpapers/Tarski-79.shtml]] | + | * [[http://www.di.ens.fr/~cousot/COUSOTpapers/Tarski-79.shtml|Constructive proof using ordinals, by Cousot & Cousot]] |
| - | * A shorter constructive proof using ordinals, [[http://129.3.20.41/eps/ge/papers/0305/0305001.pdf]] | + | * [[http://129.3.20.41/eps/ge/papers/0305/0305001.pdf|A shorter constructive proof using ordinals]] |
| * Many more details on lattices: J.B.Nation's notes [[http://bigcheese.math.sc.edu/~mcnulty/alglatvar/lat0.pdf|0]], [[http://bigcheese.math.sc.edu/~mcnulty/alglatvar/lat1.pdf|1]] | * Many more details on lattices: J.B.Nation's notes [[http://bigcheese.math.sc.edu/~mcnulty/alglatvar/lat0.pdf|0]], [[http://bigcheese.math.sc.edu/~mcnulty/alglatvar/lat1.pdf|1]] | ||