Editing Fixed-point theorem

{{Short description|Condition for a mathematical function to map some value to itself}}
In [[mathematics]], a '''fixed-point theorem''' is a result saying that a [[function (mathematics)|function]] ''F'' will have at least one [[fixed point (mathematics)|fixed point]] (a point ''x'' for which ''F''(''x'') = ''x''), under some conditions on ''F'' that can be stated in general terms.<ref>{{cite book
 | editor     = Brown, R. F.
 | title      = Fixed Point Theory and Its Applications
 | year       = 1988
 | publisher  = American Mathematical Society
 | isbn       = 0-8218-5080-6
}}
</ref>

== In mathematical analysis ==
The [[Banach fixed-point theorem]] (1922) gives a general criterion guaranteeing that, if it is satisfied, the procedure of [[iteration|iterating]] a function yields a fixed point.<ref>{{cite book
 | author    = Giles, John R.
 | title     = Introduction to the Analysis of Metric Spaces
 | year      = 1987
 | publisher = Cambridge University Press
 | isbn      = 978-0-521-35928-3
}}</ref>

By contrast, the [[Brouwer fixed-point theorem]] (1911) is a non-[[Constructivism (mathematics)|constructive result]]: it says that any [[continuous function]] from the closed [[unit ball]] in ''n''-dimensional [[Euclidean space]] to itself must have a fixed point,<ref>Eberhard Zeidler, ''Applied Functional Analysis: main principles and their applications'', Springer, 1995.</ref> but it doesn't describe how to find the fixed point (see also [[Sperner's lemma]]).

For example, the [[cosine]] function is continuous in [−1,&nbsp;1] and maps it into [−1,&nbsp;1], and thus must have a fixed point. This is clear when examining a sketched graph of the cosine function; the fixed point occurs where the cosine curve ''y'' = cos(''x'') intersects the line ''y'' = ''x''. Numerically, the fixed point (known as the [[Dottie number]]) is approximately ''x'' = 0.73908513321516 (thus ''x'' = cos(''x'') for this value of ''x'').

The [[Lefschetz fixed-point theorem]]<ref>{{cite journal |author=Solomon Lefschetz |title=On the fixed point formula |journal=[[Annals of Mathematics|Ann. of Math.]] |year=1937 |volume=38 |pages=819–822 |doi=10.2307/1968838 |issue=4}}</ref> (and the [[Nielsen theory|Nielsen fixed-point theorem]])<ref>{{cite book
 | last1=Fenchel | first1=Werner | author1link=Werner Fenchel
 | last2=Nielsen | first2=Jakob | author2link=Jakob Nielsen (mathematician)
 | editor-last=Schmidt | editor-first=Asmus L.
 | title=Discontinuous groups of isometries in the hyperbolic plane
 | series=De Gruyter Studies in mathematics
 | volume=29
 | publisher=Walter de Gruyter & Co.
 | location=Berlin
 | year=2003
}}</ref> from [[algebraic topology]] is notable because it gives, in some sense, a way to count fixed points.

There are a number of generalisations to [[Banach fixed-point theorem]] and further; these are applied in [[Partial differential equation|PDE]] theory. See [[fixed-point theorems in infinite-dimensional spaces]].

The [[collage theorem]] in [[fractal compression]] proves that, for many images, there exists a relatively small description of a function that, when iteratively applied to any starting image, rapidly converges on the desired image.<ref>{{cite book
 | author     = Barnsley, Michael.
 | title      = Fractals Everywhere
 | url        = https://archive.org/details/fractalseverywhe0000barn
 | url-access = registration
 | year       = 1988
 | publisher  = Academic Press, Inc.
 | isbn       = 0-12-079062-9
}}</ref>

== In algebra and discrete mathematics ==

The [[Knaster&ndash;Tarski theorem]] states that any [[monotonic|order-preserving function]] on a [[complete lattice]] has a fixed point, and indeed a ''smallest'' fixed point.<ref>{{cite journal | author=Alfred Tarski | url=http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1103044538 | title=A lattice-theoretical fixpoint theorem and its applications | journal = Pacific Journal of Mathematics | volume=5:2 | year=1955 | pages=285&ndash;309}}</ref> See also [[Bourbaki&ndash;Witt theorem]].

The theorem has applications in [[abstract interpretation]], a form of [[static program analysis]].

A common theme in [[lambda calculus]] is to find fixed points of given lambda expressions. Every lambda expression has a fixed point, and a [[fixed-point combinator]] is a "function" which takes as input a lambda expression and produces as output a fixed point of that expression.<ref>{{cite book|last=Peyton Jones|first=Simon L.|title=The Implementation of Functional Programming|year=1987|publisher=Prentice Hall International|url=http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/}}</ref> An important fixed-point combinator is the [[Fixed-point combinator#Y combinator|Y combinator]] used to give [[Recursion (computer science)|recursive]] definitions.

In [[denotational semantics]] of programming languages, a special case of the Knaster&ndash;Tarski theorem is used to establish the semantics of recursive definitions. While the fixed-point theorem is applied to the "same" function (from a logical point of view), the development of the theory is quite different.

The same definition of recursive function can be given, in [[computability theory]], by applying [[Kleene's recursion theorem]].<ref>Cutland, N.J., ''Computability: An introduction to recursive function theory'', Cambridge University Press, 1980. {{isbn|0-521-29465-7}}</ref> These results are not equivalent theorems; the Knaster&ndash;Tarski theorem is a much stronger result than what is used in denotational semantics.<ref>''The foundations of program verification'', 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, {{isbn|0-471-91282-4}}, Chapter 4; theorem 4.24, page 83, is what is used in denotational semantics, while Knaster&ndash;Tarski theorem is given to prove as exercise 4.3&ndash;5 on page 90.</ref> However, in light of the [[Church&ndash;Turing thesis]] their intuitive meaning is the same: a recursive function can be described as the least fixed point of a certain functional, mapping functions to functions.

The above technique of iterating a function to find a fixed point can also be used in [[set theory]]; the [[fixed-point lemma for normal functions]] states that any continuous strictly increasing function from [[ordinal number|ordinals]] to ordinals has one (and indeed many) fixed points.

Every [[closure operator]] on a [[poset]] has many fixed points; these are the "closed elements" with respect to the closure operator, and they are the main reason the closure operator was defined in the first place.

Every [[involution (mathematics)|involution]] on a [[finite set]] with an odd number of elements has a fixed point; more generally, for every involution on a finite set of elements, the number of elements and the number of fixed points have the same [[parity (mathematics)|parity]]. [[Don Zagier]] used these observations to give a one-sentence proof of [[Fermat's theorem on sums of two squares]], by describing two involutions on the same set of triples of integers, one of which can easily be shown to have only one fixed point and the other of which has a fixed point for each representation of a given prime (congruent to 1 mod 4) as a sum of two squares. Since the first involution has an odd number of fixed points, so does the second, and therefore there always exists a representation of the desired form.<ref>{{citation
 | last = Zagier | first = D. | authorlink = Don Zagier
 | doi = 10.2307/2323918
 | issue = 2
 | journal = [[American Mathematical Monthly]]
 | mr = 1041893
 | page = 144
 | title = A one-sentence proof that every prime ''p''&nbsp;≡&nbsp;1&nbsp;(mod&nbsp;4) is a sum of two squares
 | volume = 97
 | year = 1990
}}.</ref>

== List of fixed-point theorems ==
{{Div col|colwidth=25em}}
*[[Atiyah–Bott fixed-point theorem]]
*[[Banach fixed-point theorem]]
*[[Bekić's theorem]]
*[[Borel fixed-point theorem]]
*[[Bourbaki&ndash;Witt theorem]]
*[[Browder fixed-point theorem]]
*[[Brouwer fixed-point theorem]]
*[[Rothe's fixed-point theorem]]
*[[Caristi fixed-point theorem]]
*[[Diagonal lemma]], also known as the fixed-point lemma, for producing self-referential sentences of [[first-order logic]]
*[[Lawvere's fixed-point theorem]]
*[[Discrete fixed-point theorem]]s
*[[Earle-Hamilton fixed-point theorem]]
*[[Fixed-point combinator]], which shows that every term in untyped [[lambda calculus]] has a fixed point
*[[Fixed-point lemma for normal functions]]
*[[Fixed-point property]]
*[[Fixed-point theorems in infinite-dimensional spaces]]
*[[Injective metric space]]
*[[Kakutani fixed-point theorem]]
*[[Kleene fixed-point theorem]]
*[[Knaster–Tarski theorem]]
*[[Lefschetz fixed-point theorem]]
*[[Nielsen fixed-point theorem]]
*[[Poincaré–Birkhoff theorem]] proves the existence of two fixed points
*[[Ryll-Nardzewski fixed-point theorem]]
*[[Schauder fixed-point theorem]]
*[[Topological degree theory]]
*[[Tychonoff fixed-point theorem]]
{{div col end}}

== See also ==

* [[Trace formula (disambiguation)|Trace formula]]

== Footnotes ==
{{Reflist}}

== References ==
*{{cite book
 | author1    = Agarwal, Ravi P.
 | author2    = Meehan, Maria
 | author3    = O'Regan, Donal
 | title      = Fixed Point Theory and Applications
 | year       = 2001
 | publisher  = Cambridge University Press
 | isbn       = 0-521-80250-4
}}
*{{cite book
 | author1    = Aksoy, Asuman|author1-link=Asuman Aksoy
 | author2    = Khamsi, Mohamed A.
 | title      = Nonstandard Methods in fixed point theory
 | url        = https://archive.org/details/nonstandardmetho0000akso
 | url-access = registration
 | year       = 1990
 | publisher  = Springer Verlag
 | isbn       = 0-387-97364-8 
}}
*{{cite book
 | author     = Berinde, Vasile
 | title      = Iterative Approximation of Fixed Point
 | year       = 2005
 | publisher  = Springer Verlag
 | isbn       = 978-3-540-72233-5
}}
*{{cite book
 | author     = Border, Kim C.
 | title      = Fixed Point Theorems with Applications to Economics and Game Theory
 | year       = 1989
 | publisher  = Cambridge University Press
 | isbn       = 0-521-38808-2
}}
*{{cite book
 |author1=Kirk, William A. |author2=Goebel, Kazimierz | title      = Topics in Metric Fixed Point Theory
 | year       = 1990
 | publisher  = Cambridge University Press
 | isbn       = 0-521-38289-0
}}
*{{cite book
 |author1=Kirk, William A. |author2=Khamsi, Mohamed A. | title      = An Introduction to Metric Spaces and Fixed Point Theory
 | year       = 2001
 | publisher  = John Wiley, New York.
 | isbn         = 978-0-471-41825-2
}}
*{{cite book |author1=Kirk |first=William A. |author2=Sims |first2=Brailey |title=Handbook of Metric Fixed Point Theory |year=2001 |publisher=Springer-Verlag |isbn=0-7923-7073-2 |author-link2=Brailey Sims}}
*{{cite book |author1=Šaškin, Jurij A |author2=Minachin, Viktor |author3=Mackey, George W. |title=Fixed Points |year=1991 |publisher=American Mathematical Society |isbn=0-8218-9000-X |url-access=registration |url=https://archive.org/details/fixedpoints0002shas }}

==External links==
*[http://www.math-linux.com/spip.php?article60 Fixed Point Method]

{{Authority control}}

[[Category:Closure operators]]
[[Category:Fixed-point theorems| ]]
[[Category:Iterative methods]]