Kleene fixpoint theorem

In the mathematical areas of order and lattice theory, the Kleene fixed-point theorem, named after American mathematician Stephen Cole Kleene, states the following::"Let L be a complete partial order, and let f : L → L be a continuous (and therefore monotone) function. Then the least fixed point of f is the supremum of the ascending Kleene chain of f.

It is often attributed to Alfred Tarski, but the original statement of Tarski's fixed point theorem is about monotone functions on complete lattices.

The ascending Kleene chain of "f" is the chain

: $ot ; le ; f(ot) ; le ; fleft(f(ot)
ight) ; le ; dots ; le ; f^n(ot) ; le ; dots$

obtained by iterating "f" on the least element ⊥ of "L". Expressed in a formula, the theorem states that

: $extrm{lfp}(f) = sup left(left{f^n(ot) mid ninmathbb{N}
ight}
ight)$

where $extrm{lfp}$ denotes the least fixed point.

See also

* Knaster–Tarski theorem
* Other fixed-point theorems

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

Knaster–Tarski theorem — In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:: Let L be a complete lattice and let f : L → L be an order preserving function. Then the set … Wikipedia
Stephen Cole Kleene — Infobox Scientist name = Stephen Kleene caption = birth date = birth date|1909|1|5 birth place = USA death date = death date and age|1994|1|25|1909|1|5 death place = residence = USA nationality = USA field = Mathematics work institutions =… … Wikipedia
Fixed point theorem — In mathematics, a fixed point theorem is a result saying that a function F will have at least one fixed point (a point x for which F ( x ) = x ), under some conditions on F that can be stated in general terms. Results of this kind are amongst the … Wikipedia
List of mathematics articles (K) — NOTOC K K approximation of k hitting set K ary tree K core K edge connected graph K equivalence K factor error K finite K function K homology K means algorithm K medoids K minimum spanning tree K Poincaré algebra K Poincaré group K set (geometry) … Wikipedia
Complete partial order — In mathematics, directed complete partial orders and ω complete partial orders (abbreviated to dcpo, ωcpo or sometimes just cpo) are special classes of partially ordered sets, characterized by particular completeness properties. Complete partial… … Wikipedia
Least fixed point — In order theory, a branch of mathematics, the least fixed point (lfp or LFP) of a function is the fixed point which is less than or equal to all other fixed points, according to some partial order. For example, the least fixed point of the real… … Wikipedia
Mohamed Amine Khamsi — is an American/Moroccan mathematician. He was born in Morocco in 1959. His research interests include nonlinear functional analysis, the fixed point theory and metric spaces. In particular, he has made notable contributions to the fixed point… … Wikipedia

Academic Dictionaries and Encyclopedias

Kleene fixpoint theorem

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Kleene fixpoint theorem

Look at other dictionaries:

Share the article and excerpts

Direct link