Proof
We first have to show that the ascending Kleene chain of f exists in L. To show that, we prove the following lemma:
- Lemma 1:If L is CPO, and f : L → L is a Scott-continuous, then
Proof by induction:
- Assume n = 0. Then, since ⊥ is the least element.
- Assume n > 0. Then we have to show that . By rearranging we get . By inductive assumption, we know that holds, and because f is monotone (property of Scott-continuous functions), the result holds as well.
Immediate corollary of Lemma 1 is the existence of the chain.
Let M be the set of all elements of the chain: . This set is clearly directed. From definition of CPO follows that this set has a supremum, we will call it m. What remains now is to show that m is the fixpoint. that is, we have to show that f(m) = m. Because f is continuous, f(sup(M)) = sup(f(M)), that is f(m) = sup(f(M)). But sup(f(M)) = sup(M) (from the property of the chain) and from that f(m) = m, making m a fixpoint.
The proof that m is the least fixpoint can be done by contradiction. Assume k is a fixpoint and k < m. Than there has to be i such that . But than for all j > i the result would never be greater than k and so m cannot be a supremum of M, which is a contradiction.
Read more about this topic: Kleene Fixed-point Theorem
Famous quotes containing the word proof:
“The proof of a poet is that his country absorbs him as affectionately as he has absorbed it.”
—Walt Whitman (1819–1892)
“The insatiable thirst for everything which lies beyond, and which life reveals, is the most living proof of our immortality.”
—Charles Baudelaire (1821–1867)
“If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
—Thomas Jefferson (1743–1826)