Editing Fixed point (mathematics) (section)

==Fixed points of partial orders ==

In [[domain theory]], the notion and terminology of fixed points is generalized to a [[partial order]]. Let ≤ be a partial order over a set ''X'' and let ''f'': ''X'' → ''X'' be a function over ''X''. Then a '''prefixed point''' (also spelled '''pre-fixed point''', sometimes shortened to '''prefixpoint''' or '''pre-fixpoint'''){{citation needed|reason=Give a source for each of the spellings.|date=October 2022}} of ''f'' is any ''p'' such that ''f''(''p'') ≤ ''p''. Analogously, a ''postfixed point''  of ''f'' is any ''p'' such that ''p'' ≤ ''f''(''p'').<ref name="SmythPlotkin1982">{{cite conference |last1=Smyth |first1=Michael B. |last2=Plotkin |first2=Gordon D. |date=1982 |title=The Category-Theoretic Solution of Recursive Domain Equations |url=https://homepages.inf.ed.ac.uk/gdp/publications/Category_Theoretic_Solution.pdf |publisher=SIAM Journal of Computing (volume 11) |pages=761–783 |doi=10.1137/0211062 |book-title=Proceedings, 18th IEEE Symposium on Foundations of Computer Science}}</ref>  The opposite usage occasionally appears.<ref name="CousotCousot1979">{{cite journal |author1=Patrick Cousot |author2=Radhia Cousot |year=1979 |title=Constructive Versions of Tarski's Fixed Point Theorems |url=http://www.di.ens.fr/~cousot/COUSOTpapers/publications.www/CousotCousot-PacJMath-82-1-1979.pdf |journal=[[Pacific Journal of Mathematics]] |volume=82 |issue=1 |pages=43–57 |doi=10.2140/pjm.1979.82.43}}</ref> Malkis justifies the definition presented here as follows: "since ''f'' is {{em|before}} the inequality sign in the term ''f''(''x'') ≤ ''x'', such ''x'' is called a {{em|pre}}fix point."<ref>{{cite book |last1=Malkis |first1=Alexander |date=2015 |chapter=Multithreaded-Cartesian Abstract Interpretation of Multithreaded Recursive Programs Is Polynomial |chapter-url=https://www.sec.in.tum.de/~malkis/Malkis-MultCartAbstIntOfMultRecProgIsPoly_techrep.pdf |title=Reachability Problems |series=Lecture Notes in Computer Science |volume=9328 |pages=114–127 |doi=10.1007/978-3-319-24537-9_11 |isbn=978-3-319-24536-2 |s2cid=17640585 |archive-url=https://web.archive.org/web/20220810075519/https://www.sec.in.tum.de/~malkis/Malkis-MultCartAbstIntOfMultRecProgIsPoly_techrep.pdf |archive-date=2022-08-10}}</ref> A fixed point is a point that is both a prefixpoint and a postfixpoint. Prefixpoints and postfixpoints have applications in [[theoretical computer science]].<ref>Yde Venema (2008) [http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf Lectures on the Modal μ-calculus] {{webarchive|url=https://web.archive.org/web/20120321162526/http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf|date=March 21, 2012}}</ref>

=== Least fixed point ===
{{Main|Least fixed point}}

In [[order theory]], the [[least fixed point]] of a [[function (mathematics)|function]] from a [[partially ordered set]] (poset) to itself is the fixed point which is less than each other fixed point, according to the order of the poset. A function need not have a least fixed point, but if it does then the least fixed point is unique.

One way to express the [[Knaster–Tarski theorem]] is to say that a [[monotone function]] on a [[complete lattice]] has a [[least fixed point]] that coincides with its least prefixpoint (and similarly its greatest fixed point coincides with its greatest postfixpoint).<ref>Yde Venema (2008) [http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf Lectures on the Modal μ-calculus] {{webarchive|url=https://web.archive.org/web/20120321162526/http://staff.science.uva.nl/~yde/teaching/ml/mu/mu2008.pdf|date=March 21, 2012}}</ref>