In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a fixed-point theorem is a result saying that a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
''F'' will have at least one
fixed point (a point ''x'' for which ''F''(''x'') = ''x''), under some conditions on ''F'' that can be stated in general terms. Some authors claim that results of this kind are amongst the most generally useful in mathematics.
In mathematical analysis
The
Banach fixed-point theorem
In mathematics, the Banach fixed-point theorem (also known as the contraction mapping theorem or contractive mapping theorem) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certai ...
(1922) gives a general criterion guaranteeing that, if it is satisfied, the procedure of
iterating a function yields a fixed point.
By contrast, the
Brouwer fixed-point theorem
Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after L. E. J. (Bertus) Brouwer. It states that for any continuous function f mapping a compact convex set to itself there is a point x_0 such that f(x_0)=x_0. The simplest ...
(1911) is a non-
constructive result: it says that any
continuous function
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value ...
from the closed
unit ball
Unit may refer to:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* ''Unit'' (alb ...
in ''n''-dimensional
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
to itself must have a fixed point, but it doesn't describe how to find the fixed point (See also
Sperner's lemma
In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring (described below) of a triangulation of an ...
).
For example, the
cosine function is continuous in
ˆ’1,1and maps it into
ˆ’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 is approximately ''x'' = 0.73908513321516 (thus ''x'' = cos(''x'') for this value of ''x'').
The
Lefschetz fixed-point theorem
In mathematics, the Lefschetz fixed-point theorem is a formula that counts the fixed points of a continuous mapping from a compact topological space X to itself by means of traces of the induced mappings on the homology groups of X. It is named ...
(and the
Nielsen fixed-point theorem Nielsen theory is a branch of mathematical research with its origins in topological fixed-point theory. Its central ideas were developed by Danish mathematician Jakob Nielsen, and bear his name.
The theory developed in the study of the so-called ' ...
) from
algebraic topology
Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariant (mathematics), invariants that classification theorem, classify topological spaces up t ...
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
In mathematics, the Banach fixed-point theorem (also known as the contraction mapping theorem or contractive mapping theorem) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certai ...
and further; these are applied in
PDE theory. See
fixed-point theorems in infinite-dimensional spaces In mathematics, a number of fixed-point theorems in infinite-dimensional spaces generalise the Brouwer fixed-point theorem. They have applications, for example, to the proof of existence theorems for partial differential equations.
The first re ...
.
The
collage theorem
In mathematics, the collage theorem characterises an iterated function system whose attractor is close, relative to the Hausdorff metric, to a given set. The IFS described is composed of contractions whose images, as a collage or union when mapp ...
in
fractal compression
Fractal compression is a lossy compression method for digital images, based on fractals. The method is best suited for textures and natural images, relying on the fact that parts of an image often resemble other parts of the same image. Fractal a ...
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.
In algebra and discrete mathematics
The
Knaster–Tarski theorem states that any
order-preserving function
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...
on a
complete lattice
In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
has a fixed point, and indeed a ''smallest'' fixed point. See also
Bourbaki–Witt theorem In mathematics, the Bourbaki–Witt theorem in order theory, named after Nicolas Bourbaki and Ernst Witt, is a basic fixed point theorem for partially ordered sets. It states that if ''X'' is a non-empty chain complete poset, and
f : X \to X
su ...
.
The theorem has applications in
abstract interpretation
In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer prog ...
, a form of
static program analysis
In computer science, static program analysis (or static analysis) is the analysis of computer programs performed without executing them, in contrast with dynamic program analysis, which is performed on programs during their execution.
The term i ...
.
A common theme in
lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...
is to find fixed points of given lambda expressions. Every lambda expression has a fixed point, and a
fixed-point combinator
In mathematics and computer science in general, a '' fixed point'' of a function is a value that is mapped to itself by the function.
In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order fu ...
is a "function" which takes as input a lambda expression and produces as output a fixed point of that expression. An important fixed-point combinator is the
Y combinator
Y Combinator (YC) is an American technology startup accelerator launched in March 2005. It has been used to launch more than 3,000 companies, including Airbnb, Coinbase, Cruise, DoorDash, Dropbox, Instacart, Quora, PagerDuty, Reddit, Str ...
used to give
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
definitions.
In
denotational semantics
In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called ''denotations'' ...
of programming languages, a special case of the Knaster–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
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
, by applying
Kleene's recursion theorem
In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 b ...
. These results are not equivalent theorems; the Knaster–Tarski theorem is a much stronger result than what is used in denotational semantics. However, in light of the
Church–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
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
; the
fixed-point lemma for normal functions
The fixed-point lemma for normal functions is a basic result in axiomatic set theory stating that any normal function has arbitrarily large fixed points (Levy 1979: p. 117). It was first proved by Oswald Veblen in 1908.
Background and for ...
states that any continuous strictly increasing function from
ordinals to ordinals has one (and indeed many) fixed points.
Every
closure operator In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S
:
Closure operators are dete ...
on a
poset
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
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
Involution may refer to:
* Involute, a construction in the differential geometry of curves
* '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...
on a
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. Th ...
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
Parity may refer to:
* Parity (computing)
** Parity bit in computing, sets the parity of data for the purpose of error detection
** Parity flag in computing, indicates if the number of set bits is odd or even in the binary representation of the r ...
.
Don Zagier
Don Bernard Zagier (born 29 June 1951) is an American-German mathematician whose main area of work is number theory. He is currently one of the directors of the Max Planck Institute for Mathematics in Bonn, Germany. He was a professor at the ''Col ...
used these observations to give a one-sentence proof of
Fermat's theorem on sums of two squares
In additive number theory, Fermat's theorem on sums of two squares states that an odd prime ''p'' can be expressed as:
:p = x^2 + y^2,
with ''x'' and ''y'' integers, if and only if
:p \equiv 1 \pmod.
The prime numbers for which this is true ar ...
, 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.
[.]
List of fixed-point theorems
*
Atiyah–Bott fixed-point theorem
In mathematics, the Atiyah–Bott fixed-point theorem, proven by Michael Atiyah and Raoul Bott in the 1960s, is a general form of the Lefschetz fixed-point theorem for smooth manifolds ''M'', which uses an elliptic complex on ''M''. This is a sys ...
*
Banach fixed-point theorem
In mathematics, the Banach fixed-point theorem (also known as the contraction mapping theorem or contractive mapping theorem) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certai ...
*
Bekić's theorem
In computability theory, Bekić's theorem or Bekić's lemma is a theorem about fixed-points which allows splitting a mutual recursion into recursions on one variable at a time. It was created by Austrian Hans Bekić (1936-1982) in 1969, and publi ...
*
Borel fixed-point theorem
In mathematics, the Borel fixed-point theorem is a fixed-point theorem in algebraic geometry generalizing the Lie–Kolchin theorem. The result was proved by .
Statement
If ''G'' is a connected, solvable, linear algebraic group acting regularly ...
*
Bourbaki–Witt theorem In mathematics, the Bourbaki–Witt theorem in order theory, named after Nicolas Bourbaki and Ernst Witt, is a basic fixed point theorem for partially ordered sets. It states that if ''X'' is a non-empty chain complete poset, and
f : X \to X
su ...
*
Browder fixed-point theorem
*
Brouwer fixed-point theorem
Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after L. E. J. (Bertus) Brouwer. It states that for any continuous function f mapping a compact convex set to itself there is a point x_0 such that f(x_0)=x_0. The simplest ...
*
Caristi fixed-point theorem In mathematics, the Caristi fixed-point theorem (also known as the Caristi–Kirk fixed-point theorem) generalizes the Banach fixed-point theorem for maps of a complete metric space into itself. Caristi's fixed-point theorem modifies the ''ε''- va ...
*
Diagonal lemma
In mathematical logic, the diagonal lemma (also known as diagonalization lemma, self-reference lemma or fixed point theorem) establishes the existence of self-referential sentences in certain formal theories of the natural numbers—specificall ...
, also known as the fixed-point lemma, for producing self-referential sentences of
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
*
Discrete fixed-point theorem In discrete mathematics, a discrete fixed-point is a fixed-point for functions defined on finite sets, typically subsets of the integer grid \mathbb^n.
Discrete fixed-point theorems were developed by Iimura, Murota and Tamura, Chen and Deng and o ...
s
*
Earle-Hamilton fixed-point theorem
*
Fixed-point combinator
In mathematics and computer science in general, a '' fixed point'' of a function is a value that is mapped to itself by the function.
In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order fu ...
, which shows that every term in untyped
lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...
has a fixed point
*
Fixed-point lemma for normal functions
The fixed-point lemma for normal functions is a basic result in axiomatic set theory stating that any normal function has arbitrarily large fixed points (Levy 1979: p. 117). It was first proved by Oswald Veblen in 1908.
Background and for ...
*
Fixed-point property A mathematical object ''X'' has the fixed-point property if every suitably well-behaved mapping from ''X'' to itself has a fixed point. The term is most commonly used to describe topological spaces on which every continuous mapping has a fixed poi ...
*
Fixed-point theorems in infinite-dimensional spaces In mathematics, a number of fixed-point theorems in infinite-dimensional spaces generalise the Brouwer fixed-point theorem. They have applications, for example, to the proof of existence theorems for partial differential equations.
The first re ...
*
Injective metric space In metric geometry, an injective metric space, or equivalently a hyperconvex metric space, is a metric space with certain properties generalizing those of the real line and of L∞ distances in higher-dimensional vector spaces. These properties can ...
*
Kakutani fixed-point theorem
In mathematical analysis, the Kakutani fixed-point theorem is a fixed-point theorem for set-valued functions. It provides sufficient conditions for a set-valued function defined on a convex set, convex, compact set, compact subset of a Euclidean sp ...
*
Kleene fixed-point theorem
In the mathematical areas of order and lattice theory, the Kleene fixed-point theorem, named after American mathematician Stephen Cole Kleene, states the following:
:Kleene Fixed-Point Theorem. Suppose (L, \sqsubseteq) is a directed-complete pa ...
*
Knaster–Tarski theorem In the mathematics, mathematical areas of order theory, order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:
:''Let'' (''L'', ≤) ''be a complete lattice and let f : L → ...
*
Lefschetz fixed-point theorem
In mathematics, the Lefschetz fixed-point theorem is a formula that counts the fixed points of a continuous mapping from a compact topological space X to itself by means of traces of the induced mappings on the homology groups of X. It is named ...
*
Nielsen fixed-point theorem Nielsen theory is a branch of mathematical research with its origins in topological fixed-point theory. Its central ideas were developed by Danish mathematician Jakob Nielsen, and bear his name.
The theory developed in the study of the so-called ' ...
*
Poincaré–Birkhoff theorem
In symplectic topology and dynamical systems, Poincaré–Birkhoff theorem (also known as Poincaré–Birkhoff fixed point theorem and Poincaré's last geometric theorem) states that every area-preserving, orientation-preserving homeomorphism of a ...
proves the existence of two fixed points
*
Ryll-Nardzewski fixed-point theorem In functional analysis, a branch of mathematics, the Ryll-Nardzewski fixed-point theorem states that if E is a normed vector space and K is a nonempty convex subset of E that is compact under the weak topology, then every group (or equivalently: eve ...
*
Schauder fixed-point theorem The Schauder fixed-point theorem is an extension of the Brouwer fixed-point theorem to topological vector spaces, which may be of infinite dimension. It asserts that if K is a nonempty convex closed subset of a Hausdorff topological vector space V ...
*
Topological degree theory In mathematics, topological degree theory is a generalization of the winding number of a curve in the complex plane. It can be used to estimate the number of solutions of an equation, and is closely connected to fixed-point theory. When one solution ...
*
Tychonoff fixed-point theorem In mathematics, a number of fixed-point theorems in infinite-dimensional spaces generalise the Brouwer fixed-point theorem. They have applications, for example, to the proof of existence theorems for partial differential equations.
The first re ...
Footnotes
References
*
*
*
*
*
*
*
*{{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
Fixed Point Method
Closure operators
Iterative methods