Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Made a start on an article fixed point, which might need to be farmed out to “sub-pages” (as this is a mighty big general topic).
Nice, thanks!
Thanks! It gives me a good excuse to record Pataraia’s theorem, which I found in Paul Taylor’s book. It’s pretty, isn’t it? :-)
Yes, it is. Can it be categorified to yield fixed points for (accessible) endofunctors, like the Knaster-Tarski theorem can?
Was the juxtaposition of
Fixed points of endofunctors frequently arise as solutions to “recursive equations”, especially in the form of initial algebras and terminal coalgebras
and the fixed point theorem for contracting maps intended, seeing that the latter is an example of the former?
@David: I wasn’t thinking that when I wrote that; thanks. There are various unifications and generalizations that are possible; see for example this paper, which combines Banach fixed point and Tarski fixed point via a quantalic version of Pataraia’s theorem. I’d like to think more before I write them down.
@Mike: the adjustments needed might be obvious, but I’d like to think about it some more. In the meantime, I have recorded a statement and proof of the categorified Knaster-Tarski theorem at fixed point.
We need to disambiguate “fixed point” better. I have removed the redirect of “fixed point” to “fixed point of an endofunctor” and instead created a small disambiguation page fixed point.
Re #7: I’m not sure about that redirect. The associations I have with “fixed point of an endofunctor” are certainly different to what is on that page (I would never think of searching for the Knaster-Tarski or Pataraia theorems by typing in “fixed point of an endofunctor”.) And examples from analysis and topology do not fit very well under that title, in my opinion.
Hi Todd, not sure if you mean to disagree or agree with anything I did. The page I created just lists all nLab entries that talk about something called fixed points. I certainly agree that most people would never think of most of the entries listed there when they hear “fixed point”, and in particular most people wouldn’t think of fixed points of an endofunctor. That’s why I changed the previous situation where “fixed point” was redirecting to “fixed point of an endofunctor”.
Probably we don’t disagree in any serious sense. What it looks like is that the page that was formerly titled “fixed point” (which discussed multifarious versions of the notion) is now titled “fixed points of an endofunctor”, and that title I find misleading with regard to what is inside there. I’m fine with the idea of fixed point serving as a disambiguation page and farming out separate topics to separate pages, but I think we should either rename “fixed points of an endofunctor” page, or sift further through its contents and maybe install some of it on new pages.
Oh, now I see. Just a sec, I’ll fix it…
Okay, I have removed the new entry again, re-installed the former redirect situation, renamed the former “fixed point of an endofunctor” (this used to be the title for a long time, not just since yesterday) back to just “fixed point” and then expanded the Idea-section there a little such as to contain the further pointers such as to homotopy fixed point and fixed point spectrum.
tried to add missing cross-links between all our fixed point theorem entries:
Probably I am still missing some, though.
Are Kleene’s fixed point theorem (every Scott-continuous endomorphism of a dcpo has a least fixed point) and Pataraia’s theorem (every monotone self-map of an ipo has a least fixed point) really distinct theorems? The Wikipedia page for Kleene’s fixed point theorem mentions the extension to monotone self-maps, and https://www.paultaylor.eu/domains/hombsd.pdf states that ipo is just Taylor(/Plotkin 1976)’s term for cpo (=dcpo)…
I’ve never heard of “Pataraia’s theorem”, maybe Taylor is saying that Pataraia proved it before Kleene? Also this reference to “Taylor’s book” on this page is very problematic. What book is it referring to? Presumably “Practical Foundations of Mathematics”
From what I can gather from a bit of DuckDuckGoing, Kleene’s fixed point theorem seems to be any fixed point theorem proved using the usual transfinite-iteration-up-to-ω-and-continuity proof (e.g. this paper). Cousot and Cousot (1979: 43) ascribe this idea to Kleene, who used it show the existence of recursive functions in his Introduction to metamathematics (1974: 348; first published 1952); they then use the transfinite version of it to dispense with the continuity hypothesis (so that’s a new idea I guess?), but still only use it to prove Tarski’s theorem that monotone self-maps of a complete lattice have a complete lattice’s worth of fixed points).
According to this blog post, Pataraia’s cute recursionless proof for dcpos went unpublished until it was reproduced by Escardó (2003: 119); it was apparently presented by Pataraia at the 65th Peripatetic Seminar on Sheaves and Logic in 1997 (Escardó 2003: 123, which also calls it Pataraia’s theorem).
Does anyone have a clearer historical picture of what ‘Kleene’s fixed point theorem’ is (and must be :) )?
Adding reference
Anonymouse
1 to 21 of 21