Not signed in (Sign In)

Start a new discussion

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor galois-theory gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homology homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory itex k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes science set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 13th 2012

    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).

    • CommentRowNumber2.
    • CommentAuthorMike Shulman
    • CommentTimeSep 14th 2012

    Nice, thanks!

    • CommentRowNumber3.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 14th 2012

    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? :-)

    • CommentRowNumber4.
    • CommentAuthorMike Shulman
    • CommentTimeSep 14th 2012

    Yes, it is. Can it be categorified to yield fixed points for (accessible) endofunctors, like the Knaster-Tarski theorem can?

    • CommentRowNumber5.
    • CommentAuthorDavid_Corfield
    • CommentTimeSep 14th 2012

    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?

    • CommentRowNumber6.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 14th 2012

    @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.

    • CommentRowNumber7.
    • CommentAuthorUrs
    • CommentTimeNov 23rd 2015

    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.

    • CommentRowNumber8.
    • CommentAuthorTodd_Trimble
    • CommentTimeNov 24th 2015
    • (edited Nov 24th 2015)

    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.

    • CommentRowNumber9.
    • CommentAuthorUrs
    • CommentTimeNov 24th 2015

    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”.

    • CommentRowNumber10.
    • CommentAuthorTodd_Trimble
    • CommentTimeNov 25th 2015

    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.

    • CommentRowNumber11.
    • CommentAuthorUrs
    • CommentTimeNov 25th 2015

    Oh, now I see. Just a sec, I’ll fix it…

    • CommentRowNumber12.
    • CommentAuthorUrs
    • CommentTimeNov 25th 2015
    • (edited Nov 25th 2015)

    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.

    • CommentRowNumber13.
    • CommentAuthorUrs
    • CommentTimeNov 13th 2022

    tried to add missing cross-links between all our fixed point theorem entries:

    Probably I am still missing some, though.

    diff, v27, current

    • CommentRowNumber14.
    • CommentAuthorGuest
    • CommentTimeNov 13th 2022

    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)…

    • CommentRowNumber15.
    • CommentAuthormaxsnew
    • CommentTimeNov 13th 2022

    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”

    • CommentRowNumber16.
    • CommentAuthorGuest
    • CommentTimeNov 13th 2022

    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 :) )?

Add your comments
  • Please log in or leave your comment as a "guest post". If commenting as a "guest", please include your name in the message as a courtesy. Note: only certain categories allow guest posts.
  • To produce a hyperlink to an nLab entry, simply put double square brackets around its name, e.g. [[category]]. To use (La)TeX mathematics in your post, make sure Markdown+Itex is selected below and put your mathematics between dollar signs as usual. Only a subset of the usual TeX math commands are accepted: see here for a list.

  • (Help)