Content deleted Content added
More specific hatnote |
Citation bot (talk | contribs) Altered volume. Add: doi, issue, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Order theory | #UCB_Category 105/179 |
||
| (16 intermediate revisions by 14 users not shown) | |||
Line 1:
{{Short description|Theorem in order theory and lattice theory}}
{{otheruses4|Kleene's fixed-point theorem in lattice theory|the fixed-point theorem in computability theory|Kleene's recursion theorem}}
[[File:Kleene fixpoint svg.svg|thumb|Computation of the least fixpoint of ''f''(''x'') = {{sfrac|1|10}}''x''<sup>2</sup>+[[arctangent|atan]](''x'')+1 using Kleene's theorem in the real [[interval (mathematics)|interval]] [0,7] with the usual order]]
In the [[mathematics|mathematical]] areas of [[order theory|order]] and [[lattice theory]], the '''Kleene fixed-point theorem''', named after American mathematician [[Stephen Cole Kleene]], states the following:
Line 15 ⟶ 16:
where <math>\textrm{lfp}</math> denotes the least fixed point.
does not consider how fixed points can be computed by iterating ''f'' from some seed (also, it pertains to [[monotone function]]s on [[complete lattices]]), this result is often attributed to [[Alfred Tarski]] who proves it for additive functions.<ref>{{cite journal | author=Alfred Tarski | url=http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1103044538 | title=A lattice-theoretical fixpoint theorem and its applications | journal = [[Pacific Journal of Mathematics]] | volume=5 | year=1955 | issue=2 | pages=285–309| doi=10.2140/pjm.1955.5.285 }}, page 305.</ref> Moreover, the Kleene fixed-point theorem can be extended to [[monotone function]]s using transfinite iterations.<ref>{{cite journal | author=Patrick Cousot and Radhia Cousot | url=https://projecteuclid.org/euclid.pjm/1102785059 | title=Constructive versions of Tarski's fixed point theorems | journal = Pacific Journal of Mathematics | volume=82 | year=1979 | issue=1 | pages=43–57| doi=10.2140/pjm.1979.82.43 }}</ref>
== Proof ==
We first have to show that the ascending Kleene chain of <math>f</math> exists in <math>L</math>. To show that, we prove the following:
Line 34 ⟶ 36:
From the definition of a dcpo it follows that <math>\mathbb{M}</math> has a supremum, call it <math>m.</math> What remains now is to show that <math>m</math> is the least fixed-point.
First, we show that <math>m</math> is a fixed point, i.e. that <math>f(m) = m</math>. Because <math>f</math> is [[Scott continuity|Scott-continuous]], <math>f(\sup(\mathbb{M})) = \sup(f(\mathbb{M}))</math>, that is <math>f(m) = \sup(f(\mathbb{M}))</math>. Also, since <math>
The proof that <math>m</math> is in fact the ''least'' fixed point can be done by showing that any element in <math>\mathbb{M}</math> is smaller than any fixed-point of <math>f</math> (because by property of [[supremum]], if all elements of a set <math>D \subseteq L</math> are smaller than an element of <math>L</math> then also <math>\sup(D)</math> is smaller than that same element of <math>L</math>). This is done by induction: Assume <math>k</math> is some fixed-point of <math>f</math>. We now prove by induction over <math>i</math> that <math>\forall i \in \mathbb{N}: f^i(\bot) \sqsubseteq k</math>. The base of the induction <math>(i = 0)</math> obviously holds: <math>f^0(\bot) = \bot \sqsubseteq k,</math> since <math>\bot</math> is the least element of <math>L</math>. As the induction hypothesis, we may assume that <math>f^i(\bot) \sqsubseteq k</math>. We now do the induction step: From the induction hypothesis and the monotonicity of <math>f</math> (again, implied by the Scott-continuity of <math>f</math>), we may conclude the following: <math>f^i(\bot) \sqsubseteq k ~\implies~ f^{i+1}(\bot) \sqsubseteq f(k).</math> Now, by the assumption that <math>k</math> is a fixed-point of <math>f,</math> we know that <math>f(k) = k,</math> and from that we get <math>f^{i+1}(\bot) \sqsubseteq k.</math>
== See also ==
* Other [[fixed-point theorem]]s
== References ==
{{Reflist}}
| |||