Talk:Kleene fixed-point theorem

Latest comment: 7 years ago by Geochini in topic Proof

Proof

edit

I added the proof. If you find any mistakes, or if I'm overly vague at some points, please fix it or write a note here. 89.176.188.206 (talk) 21:39, 12 May 2012 (UTC)Reply

Proof that this is in fact the least fixed Point is wrong, since another fixed point might not be of the form  ... I'm fixing this. — Preceding unsigned comment added by 134.130.115.148 (talk) 16:14, 1 May 2013 (UTC)Reply

The equation   is wrong if   is a fixed point of  . Geochini (talk) 10:22, 9 October 2017 (UTC)Reply

Continuity

edit

I think this is wrong: continuity does not imply monotonicity.

Igrant 12:15, 31 December 2005 (UTC)Reply

Now I think it's right :-). I'll change the link to 'continuous' to point to the article on Scott continuity instead.

Igrant 12:31, 31 December 2005 (UTC)Reply

Ascending Kleene chain

edit

The above page currently redirects to this one, but I can't see any mention of that exact phrase in the article. As someone who knows nothing about the subject this would be important to me to have it explained somewhere. Could something be inserted, or should we delink the redirect? -- Francs2000   12:31, 18 January 2006 (UTC)Reply

The ascending Kleene chain is the chain that starts with the bottom element of L and goes up through applications of the monotone function f. I've made the term explicit now. Is that beter?

Igrant 12:27, 4 March 2006 (UTC)Reply

Knaster–Tarski theorem

edit

What is the difference? 81.249.161.2 (talk) 07:43, 7 April 2008 (UTC)Reply

The difference is that in the Kleene fixed-point theorem, f has to be Scott-continuous (i.e. has to preserve directed suprema), while in Knaster-Tarski, it only needs to be monotonic, which is weaker. -- 132.231.199.50 (talk) 15:24, 16 August 2012 (UTC)Reply
The difference is that Tarski is interested in the structure of the set of all fixed-points: they form a lattice, you can talk of greatest fixpoint, the sup of all fixpoints is a fixpoint, etc. He is not concerned about reaching fixpoints by iterating a function, starting from some seed, and building a converging sequence, which is the point of Kleene's theorem.
The issue between requiring continuity or just monotonicity is not the central difference (with just monotonicity you can have a Kleene fixpoint theorem by iterating in the transfinite). PhS (talk) 10:39, 19 July 2016 (UTC)Reply

Reference

edit

This article has no references at all, and I could not find any myself. Anyone? 131.155.232.180 (talk) 15:41, 27 February 2012 (UTC)Reply

Did you try just searching for it on google books? There are lots of hits. — Carl (CBM · talk) 16:10, 27 February 2012 (UTC)Reply
... So, why didn't you add those references? 145.120.19.244 (talk) 23:00, 16 March 2012 (UTC)Reply
I found a paper on the who discovered what, called "Fixed point theorems and semantics: a folk tale". I do not have the time to read it, but it should fix the problem of a lack of references. The link is http://www.sciencedirect.com/science/article/pii/0020019082900655 131.155.234.39 (talk) 13:12, 23 April 2012 (UTC)Reply