Editing Least fixed point

{{Short description|Smallest fixed point of a function from a poset}}
[[File:Puntos fijos.svg|thumb|150px|The function ''f''(''x'')&nbsp;=&nbsp;''x''<sup>2</sup>&nbsp;−&nbsp;4 has two fixed points, shown as the intersection with the blue line; its least one is at 1/2&nbsp;−&nbsp;{{sqrt|17}}/2.]]
In [[order theory]], a branch of [[mathematics]], the '''least fixed point''' ('''lfp''' or '''LFP''', sometimes also '''smallest fixed point''') of a [[function (mathematics)|function]] from a [[partially ordered set]] ("poset" for short)  to itself is the [[fixed point (mathematics)|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.

==Examples==
With the usual order on the [[real number]]s, the least fixed point of the real function ''f''(''x'') =&nbsp;''x''<sup>2</sup> is ''x''&nbsp;=&nbsp;0 (since the only other fixed point is 1 and 0&nbsp;<&nbsp;1). In contrast, ''f''(''x'') =&nbsp;''x''&nbsp;+&nbsp;1 has no fixed points at all, so has no least one, and ''f''(''x'') =&nbsp;''x'' has infinitely many fixed points, but has no least one.

Let <math>G = (V, A)</math> be a [[directed graph]] and <math>v</math> be a vertex. The [[set (mathematics)|set]] of vertices accessible from <math>v</math> can be defined as the  least fixed-point of the function <math>f: \wp(V) \to \wp(V)</math>, defined as <math>f(X) = \{ v \} \cup \{ x \in V: \text{ for some } w \in X \text{ there is an arc from } w \text{ to } x \} .</math>
The set of vertices which are co-accessible from <math>v</math> is defined by a similar least fix-point. The [[strongly connected component]] of <math>v</math> is the [[intersection (set theory)|intersection]] of those two least fixed-points.

Let <math>G = (V, \Sigma, R, S_0)</math> be a [[context-free grammar]]. The set <math>E</math> of symbols which produces the [[empty string]] <math>\varepsilon</math> can be obtained as the least fixed-point of the function <math>f: \wp(V) \to \wp(V)</math>, defined as <math>f ( X ) = \{ S \in  V: \; S \in X \text{ or } (S \to \varepsilon) \in R \text{ or } (S \to S^1 \dots S^n) \in R \text{ and } S^i \in X \text{, for all } i \}</math>, where <math>\wp(V)</math> denotes the [[power set]] of <math>V</math>.

==Applications==
Many [[fixed-point theorem]]s yield algorithms for locating the least fixed point. Least fixed points often have desirable properties that arbitrary fixed points do not.

===Denotational semantics===
{{main|Denotational semantics#Meanings of recursive programs}}
[[File:ScottDomain svg.svg|thumb|Partial order on <math>\mathbb{Z}_\bot</math>]]
In [[computer science]], the ''[[denotational semantics]]'' approach uses least fixed points to obtain from a given program text a corresponding mathematical function, called its semantics. To this end, an artificial mathematical object, <math>\bot</math>, is introduced, denoting the exceptional value "undefined".
Given e.g. the program datatype <code>int</code>, its mathematical counterpart is defined as <math>\mathbb{Z}_\bot = \mathbb{Z} \cup \{ \bot \} ;</math>
it is made a partially ordered set by defining <math>\bot \sqsubset n</math> for each <math>n \in \mathbb{Z}</math> and letting any two different members <math>n,m \in \mathbb{Z}</math> be uncomparable w.r.t. <math>\sqsubset</math>, see picture. 

The semantics of a program definition <code>int f(int n){...}</code> is some mathematical function <math>f: \mathbb{Z}_\bot \to \mathbb{Z}_\bot .</math> If the program definition <code>f</code> does not terminate for some input <code>n</code>, this can be expressed mathematically as <math>f(n) = \bot .</math> The set of all mathematical functions is made partially ordered by defining <math>f \sqsubseteq g</math> if, for each <math>n ,</math> the relation <math>f(n) \sqsubseteq g(n)</math> holds, that is, if <math>f(n)</math> is less defined or equal to <math>g(n) .</math> For example, the semantics of the expression <code>x+x/x</code> is less defined than that of <code>x+1</code>, since the former, but not the latter, maps <math>0</math> to <math>\bot ,</math> and they agree otherwise.

Given some program text <code>f</code>, its mathematical counterpart is obtained as least fixed point of some mapping from functions to functions that can be obtained by "translating" <code>f</code>.
For example, the [[C (programming language)|C]] definition 
<syntaxhighlight lang=c>int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); }</syntaxhighlight><!---keep on a single line, to emphasize analogy to F--->
is translated to a mapping 
:<math>F: (\mathbb{Z}_\bot \to \mathbb{Z}_\bot) \to (\mathbb{Z}_\bot \to \mathbb{Z}_\bot) ,</math> defined as <math>(F(f))(n) = \begin{cases} 1 & \text{if } n = 0, \\ n \cdot f(n-1) & \text{if } n \neq \bot \text{ and } n \neq 0, \\ \bot & \text{if } n = \bot. \\ \end{cases}</math> 
The mapping <math>F</math> is defined in a non-recursive way, although <code>fact</code> was defined recursively.
Under certain restrictions (see [[Kleene fixed-point theorem]]), which are met in the example, <math>F</math> necessarily has a least fixed point, <math>\operatorname{fact}</math>, that is <math>(F(\operatorname{fact}))(n) = \operatorname{fact}(n)</math> for all <math>n \in \mathbb{Z}_\bot</math>.<ref>{{cite book |url= |author1=C.A. Gunter |author2=D.S. Scott |contribution=Semantic Domains |pages=633&ndash;674 |isbn=0-444-88074-7 |editor=Jan van Leeuwen |title=Formal Models and Semantics |publisher=Elsevier |series=Handbook of Theoretical Computer Science |volume=B |year=1990}} Here: pp.&nbsp;636–638</ref> 
It is possible to show that 
:<math>\operatorname{fact}(n) = \begin{cases} n! & \text{if } n \geq 0, \\ \bot & \text{if } n < 0 \text{ or } n = \bot. \end{cases}</math> 

A larger fixed point of <math>F</math> is e.g. the function <math>\operatorname{fact}_0 ,</math> defined by 
:<math>\operatorname{fact}_0(n) = \begin{cases} n! & \text{if } n \geq 0, \\ 0 & \text{if } n < 0, \\ \bot & \text{if } n = \bot, \end{cases}</math> 
however, this function does not correctly reflect the behavior of the above program text for negative <math>n ;</math> e.g. the call <code>fact(-1)</code> will not terminate at all, let alone return <code>0</code>.
Only the ''least'' fixed point, <math>\operatorname{fact} ,</math> can reasonably be used as a mathematical program semantic.

===Descriptive complexity===
[[Neil Immerman|Immerman]]<ref>N. Immerman, Relational queries computable in polynomial time, Information and Control 68 (1–3) (1986) 86–104.</ref><ref>{{cite conference |last=Immerman |first=Neil |title=Relational Queries Computable in Polynomial Time |book-title=STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing |year=1982 |pages=147–152 |doi=10.1145/800070.802187}}  Revised version in ''Information and Control'', 68 (1986), 86–104.</ref>
and [[Moshe Y. Vardi|Vardi]]<ref>{{cite conference |last=Vardi |first=Moshe Y. |title=The Complexity of Relational Query Languages |book-title=STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing |year=1982 |pages=137–146 |doi=10.1145/800070.802186}}</ref>
independently showed the [[descriptive complexity]] result that the [[P (complexity)|polynomial-time computable properties]] of [[linear order|linearly ordered]] structures are definable in [[FO(LFP)]], i.e. in [[first-order logic]] with a least fixed point operator. However, FO(LFP) is too weak to express all polynomial-time properties of unordered structures (for instance that a structure has [[parity (mathematics)|even]] size).

==Greatest fixed points==
The greatest fixed point of a function can be defined analogously to the least fixed point, as the fixed point which is greater than any other fixed point, according to the order of the poset. In [[computer science]], greatest fixed points are much less commonly used than least fixed points. Specifically, the posets found in [[domain theory]] usually do not have a greatest element, hence for a given function, there may be multiple, mutually incomparable [[Maximal element|maximal]] fixed points, and the greatest fixed point of that function may not exist. To address this issue, the ''optimal fixed point'' has been defined as the most-defined fixed point compatible with all other fixed points. The optimal fixed point always exists, and is the greatest fixed point if the greatest fixed point exists. The optimal fixed point allows formal study of [[recursive]] and [[corecursive]] functions that do not converge with the least fixed point.<ref>{{cite book |last1=Charguéraud |first1=Arthur |chapter=The Optimal Fixed Point Combinator |title=Interactive Theorem Proving |series=Lecture Notes in Computer Science |date=2010 |volume=6172 |pages=195–210 |doi=10.1007/978-3-642-14052-5_15 |isbn=978-3-642-14051-8 |chapter-url=https://www.chargueraud.org/research/2010/fix/fix.pdf |access-date=30 October 2021}}</ref> Unfortunately, whereas [[Kleene's recursion theorem]] shows that the least fixed point is effectively computable, the optimal fixed point of a [[computable function]] may be a non-computable function.<ref>{{cite thesis |type=Ph.D. thesis |last1=Shamir |first1=Adi |title=The fixedpoints of recursive definitions |date=October 1976 |publisher=Weizmann Institute of Science |url=https://weizmann.primo.exlibrisgroup.com/permalink/972WIS_INST/1d4esio/alma990002185270203596 |oclc=884951223 |language=en}} Here: Example 12.1, pp. 12.2–3</ref>

== See also ==
*[[Knaster–Tarski theorem]]
*[[Fixed-point logic]]

==Notes==
{{reflist}}

==References==

* [[Neil Immerman|Immerman, Neil]].  ''[[Descriptive Complexity]]'', 1999, Springer-Verlag.
* [[Leonid Libkin|Libkin, Leonid]]. ''Elements of Finite Model Theory'', 2004, Springer.

[[Category:Order theory]]
[[Category:Fixed points (mathematics)]]