![Fixed point example](https://upload.wikimedia.org/wikipedia/commons/2/20/Fixed_point_example.svg)
A fixed point (sometimes shortened to fixpoint, also known as an invariant point) is a value that does not change under a given transformation. Specifically, 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 of 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 ...
is an element that is mapped to itself by the function.
In physics, the term fixed point can refer to a temperature that can be used as a reproducible reference point, usually defined by a
phase change
In chemistry, thermodynamics, and other related fields, a phase transition (or phase change) is the physical process of transition between one state of a medium and another. Commonly the term is used to refer to changes among the basic State of ...
or
triple point
In thermodynamics, the triple point of a substance is the temperature and pressure at which the three phases (gas, liquid, and solid) of that substance coexist in thermodynamic equilibrium.. It is that temperature and pressure at which the subli ...
.
Fixed point of a function
Formally, is a fixed point of a function if belongs to both the
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
and the
codomain
In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either the ...
of , and .
For example, if is defined on the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s by
then 2 is a fixed point of , because .
Not all functions have fixed points: for example, , has no fixed points, since is never equal to for any real number. In graphical terms, a fixed point means the point is on the line , or in other words the
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
of has a point in common with that line.
Fixed-point iteration
In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, ''fixed-point iteration'' is a method of computing fixed points of a function. Specifically, given a function
with the same domain and codomain, a point
in the domain of
, the fixed-point iteration is
which gives rise to the
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of
iterated function
In mathematics, an iterated function is a function (that is, a function from some set to itself) which is obtained by composing another function with itself a certain number of times. The process of repeatedly applying the same function is ...
applications
which is hoped to
converge
Converge may refer to:
* Converge (band), American hardcore punk band
* Converge (Baptist denomination), American national evangelical Baptist body
* Limit (mathematics)
* Converge ICT, internet service provider in the Philippines
*CONVERGE CFD s ...
to a point
. If
is continuous, then one can prove that the obtained
is a fixed point of
.
Points that come back to the same value after a finite number of
iterations
Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
of the function are called ''
periodic point In mathematics, in the study of iterated functions and dynamical systems, a periodic point of a function is a point which the system returns to after a certain number of function iterations or a certain amount of time.
Iterated functions
Given a ...
s''. A ''fixed point'' is a periodic point with period equal to one.
Fixed point of a group action
In
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary a ...
, for a group ''G'' acting on a set ''X'' with a
group action
In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphism ...
, ''x'' in ''X'' is said to be a fixed point of ''g'' if
.
The
fixed-point subgroup of an
automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
''f'' of a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
''G'' is the
subgroup
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgroup ...
of ''G'':
Similarly the
fixed-point subring In algebra, the fixed-point subring R^f of an automorphism ''f'' of a ring ''R'' is the subring of the fixed points of ''f'', that is,
:R^f = \.
More generally, if ''G'' is a group acting on ''R'', then the subring of ''R''
:R^G = \
is called th ...
of an
automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
''f'' of a
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
''R'' is the
subring
In mathematics, a subring of ''R'' is a subset of a ring that is itself a ring when binary operations of addition and multiplication on ''R'' are restricted to the subset, and which shares the same multiplicative identity as ''R''. For those wh ...
of the fixed points of ''f'', that is,
In
Galois theory
In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...
, the set of the fixed points of a set of
field automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
s is a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
called the
fixed field In algebra, the fixed-point subring R^f of an automorphism ''f'' of a ring ''R'' is the subring of the fixed points of ''f'', that is,
:R^f = \.
More generally, if ''G'' is a group acting on ''R'', then the subring of ''R''
:R^G = \
is called th ...
of the set of automorphisms.
Topological fixed point property
A
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...
is said to have the
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 ...
(FPP) if for 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 ...
:
there exists
such that
.
The FPP is a
topological invariant
In topology and related areas of mathematics, a topological property or topological invariant is a property of a topological space that is invariant under homeomorphisms. Alternatively, a topological property is a proper class of topological spaces ...
, i.e. is preserved by any
homeomorphism
In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphi ...
. The FPP is also preserved by any
retraction.
According to 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 ...
, every
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in British ...
and
convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytope ...
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of a
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 ...
has the FPP. Compactness alone does not imply the FPP and convexity is not even a topological property so it makes sense to ask how to topologically characterize the FPP. In 1932
Borsuk asked whether compactness together with
contractibility could be a necessary and sufficient condition for the FPP to hold. The problem was open for 20 years until the conjecture was disproved by Kinoshita who found an example of a compact contractible space without the FPP.
Fixed points of partial orders
In
domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer ...
, the notion and terminology of fixed points is generalized to a
partial order
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. A poset consists of a set together with a binary ...
. 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) of ''f'' is any ''p'' such that ''f''(''p'') ≤ ''p''. Analogously, a ''postfixed point'' of ''f'' is any ''p'' such that ''p'' ≤ ''f''(''p'').
The opposite usage occasionally appears.
A fixed point is a point that is both a prefixpoint and a postfixpoint. Prefixpoints and postfixpoints have applications in
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
.
Least fixed point
In
order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
, the
least fixed point
In order theory, a branch of mathematics, the least fixed point (lfp or LFP, sometimes also smallest fixed point) of a function from a partially ordered set to itself is the fixed point which is less than each other fixed point, according to the o ...
of 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 ...
from a
partially ordered set
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 ...
(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 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 → ...
is to say that a
monotone 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
least fixpoint
In order theory, a branch of mathematics, the least fixed point (lfp or LFP, sometimes also smallest fixed point) of a function from a partially ordered set to itself is the fixed point which is less than each other fixed point, according to the ...
that coincides with its least prefixpoint (and similarly its greatest fixpoint coincides with its greatest postfixpoint).
Fixed-point combinator
In
combinatory logic
Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of comput ...
for
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a fixed-point combinator is a
higher-order function
In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following:
* takes one or more functions as arguments (i.e. a procedural parameter, which is a parameter of a procedure that is itself ...
that returns a fixed point of its argument function, if one exists. Formally, if the function ''f'' has one or more fixed points, then
:
Fixed-point logics
In
mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
, fixed-point logics are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated by
descriptive complexity theory
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity cla ...
and their relationship to
database query language
Query languages, data query languages or database query languages (DQL) are computer languages used to make queries in databases and information systems. A well known example is the Structured Query Language (SQL).
Types
Broadly, query language ...
s, in particular to
Datalog
Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties ...
.
Fixed-point theorems
A fixed-point theorem is a result saying that at least one fixed point exists, under some general condition. Some authors claim that results of this kind are amongst the most generally useful in mathematics.
Applications
In many fields, equilibria or
stability
Stability may refer to:
Mathematics
*Stability theory, the study of the stability of solutions to differential equations and dynamical systems
**Asymptotic stability
**Linear stability
**Lyapunov stability
**Orbital stability
**Structural stabilit ...
are fundamental concepts that can be described in terms of fixed points. Some examples follow.
* In
projective geometry
In mathematics, projective geometry is the study of geometric properties that are invariant with respect to projective transformations. This means that, compared to elementary Euclidean geometry, projective geometry has a different setting, pro ...
, a fixed point of a
projectivity
In projective geometry, a homography is an isomorphism of projective spaces, induced by an isomorphism of the vector spaces from which the projective spaces derive. It is a bijection that maps lines to lines, and thus a collineation. In general, s ...
has been called a double point.
* In
economics
Economics () is the social science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services.
Economics focuses on the behaviour and intera ...
, a
Nash equilibrium
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
of a
game
A game is a structured form of play (activity), play, usually undertaken for enjoyment, entertainment or fun, and sometimes used as an educational tool. Many games are also considered to be work (such as professional players of spectator s ...
is a fixed point of the game's
best response correspondence.
John Nash exploited the
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 ...
for his seminal paper that won him the Nobel prize in economics.
* In
physics
Physics is the natural science that studies matter, its fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge which r ...
, more precisely in the
theory of phase transitions, ''linearisation'' near an ''unstable'' fixed point has led to
Wilson
Wilson may refer to:
People
* Wilson (name)
** List of people with given name Wilson
** List of people with surname Wilson
* Wilson (footballer, 1927–1998), Brazilian manager and defender
* Wilson (footballer, born 1984), full name Wilson Ro ...
's Nobel prize-winning work inventing the
renormalization group
In theoretical physics, the term renormalization group (RG) refers to a formal apparatus that allows systematic investigation of the changes of a physical system as viewed at different scales. In particle physics, it reflects the changes in the ...
, and to the mathematical explanation of the term "
critical phenomenon
In physics, critical phenomena is the collective name associated with the
physics of critical points. Most of them stem from the divergence of the
correlation length, but also the dynamics slows down. Critical phenomena include scaling relations ...
."
*
Programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
compilers
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
use fixed point computations for program analysis, for example in
data-flow analysis
In computing, dataflow is a broad concept, which has various meanings depending on the application and context. In the context of software architecture, data flow relates to stream processing or reactive programming.
Software architecture
Dataf ...
, which is often required for code
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
. They are also the core concept used by the generic program analysis method
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 ...
.
* In
type theory
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundat ...
, the
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 ...
allows definition of recursive functions in the
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 t ...
.
* The vector of
PageRank
PageRank (PR) is an algorithm used by Google Search to rank web pages in their search engine results. It is named after both the term "web page" and co-founder Larry Page. PageRank is a way of measuring the importance of website pages. According ...
values of all web pages is the fixed point of a
linear transformation
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pre ...
derived from the
World Wide Web
The World Wide Web (WWW), commonly known as the Web, is an information system enabling documents and other web resources to be accessed over the Internet.
Documents and downloadable media are made available to the network through web se ...
's link structure.
* The stationary distribution of a
Markov chain
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
is the fixed point of the one step transition probability function.
* Logician
Saul Kripke
Saul Aaron Kripke (; November 13, 1940 – September 15, 2022) was an American philosopher and logician in the analytic tradition. He was a Distinguished Professor of Philosophy at the Graduate Center of the City University of New York and emerit ...
makes use of fixed points in his influential theory of truth. He shows how one can generate a partially defined truth predicate (one that remains undefined for problematic sentences like "''This sentence is not true''"), by recursively defining "truth" starting from the segment of a language that contains no occurrences of the word, and continuing until the process ceases to yield any newly well-defined sentences. (This takes a
countable infinity
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
of steps.) That is, for a language L, let L′ (read "L-prime") be the language generated by adding to L, for each sentence S in L, the sentence "''S is true.''" A fixed point is reached when L′ is L; at this point sentences like "''This sentence is not true''" remain undefined, so, according to Kripke, the theory is suitable for a natural language that contains its ''own'' truth predicate.
See also
*
Cycles and fixed points
In mathematics, the cycles of a permutation ''π'' of a finite set S correspond bijectively to the orbits of the subgroup generated by ''π'' acting on ''S''. These orbits are subsets of S that can be written as , such that
: for , and .
The ...
of permutations
*
Eigenvector
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
*
Equilibrium
*
Fixed points of a Möbius transformation
*
Idempotence
Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
*
Infinite compositions of analytic functions
In mathematics, infinite compositions of analytic functions (ICAF) offer alternative formulations of analytic continued fractions, series, products and other infinite expansions, and the theory evolving from such compositions may shed light on the ...
*
Invariant (mathematics)
In mathematics, an invariant is a property of a mathematical object (or a class of mathematical objects) which remains unchanged after operations or transformations of a certain type are applied to the objects. The particular class of objects ...
Notes
{{reflist
External links
An Elegant Solution for Drawing a Fixed Point
Game theory