Fixed-point theorem: Difference between revisions

Revision as of 15:50, 25 November 2016

Latest revision as of 00:51, 3 February 2024

(44 intermediate revisions by 31 users not shown)

Line 1:

{{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

| authoreditor = Brown, R. F. (Ed.)

| title = Fixed Point Theory and Its Applications

| year = 1988

| publisher = American Mathematical Society

| isbn = 0-8218-5080-6

}}

}}</ref>

</ref> Results of this kind are amongst the most generally useful in mathematics.<ref>{{cite book

|author1=Dugundji, James |author2=Granas, Andrzej | title = Fixed Point Theory

| year = 2003

| publisher = Springer-Verlag

| isbn = 0-387-00173-5

}}</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|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 (Seesee also [[Sperner's lemma]]).

For example, the [[cosine]] function is continuous in [−1,&minusnbsp;1,1] and maps it into [−1,&minusnbsp;1, 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)

| first=Werner

| editor-last=Schmidt | editor-first=Asmus L.

| author1link=Werner Fenchel

| title=Discontinuous groups of isometries in the hyperbolic plane

| last2=Nielsen

| series=De Gruyter Studies in mathematics

| first2=Jakob

| volume=29

| author2link=Jakob Nielsen (mathematician)

| publisher=Walter de Gruyter & Co.

| editor-last=Schmidt

| ___location=Berlin

| editor-first=Asmus L.

| year = 2003

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

Line 48 ⟶ 39:

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

Line 63 ⟶ 56:

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

Line 78 ⟶ 71:

| 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]]

*[[Browder fixed pointBourbaki&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 fixpointfixed-point theorem]]

*[[Knaster–Tarski theorem]]

*[[Lefschetz fixed-point theorem]]

Line 98 ⟶ 101:

*[[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/>

== 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

Line 123 ⟶ 138:

| year = 2005

| publisher = Springer Verlag

| isbn = 978-3-540-72233-5

}}

*{{cite book

Line 130 ⟶ 145:

| year = 1989

| publisher = Cambridge University Press

| isbn = 0-521-38808-2

}}

*{{cite book

Line 136 ⟶ 151:

| year = 1990

| publisher = Cambridge University Press

| isbn = 0-521-38289-0

}}

*{{cite book

Line 144 ⟶ 159:

| 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

*{{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 }}

|author1=Kirk, William A. |author2=Sims, Brailey | title = Handbook of Metric Fixed Point Theory

| year = 2001

| publisher = Springer-Verlag

| isbn = 0-7923-7073-2

}}

*{{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

}}

==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]]