Kleene fixed-point theorem: Difference between revisions

Revision as of 07:57, 16 February 2012

Revision as of 16:48, 8 April 2012

Line 2:

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:

:''Let L be a [[complete partial order]], and let f : L → L be a (Scott-[[Scott continuity|continuous]] (and therefore [[monotone function|monotone]]) [[function (mathematics)|function]]. Then thef has a [[least fixed point]], of fwhich 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. Since all complete lattices are complete partial orders but not vice-versa (a complete lattice is a complete partial order with the additional property that every pair of lattice-elements has a supremum and an infimum in the lattice), and since all monotone functions on complete lattices are Scott-continuous, Tarski's fixed point theorem is a special case of the present result.

The '''ascending Kleene chain''' of ''f'' is the [[chain (order theory)|chain]]