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 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 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 ...
.
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
* ...
and the
codomain 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 ...
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 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 manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods ...
, ''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 called ...
of
iterated function applications
which is hoped to
converge 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 of the function are called ''
periodic points''. 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 ...
, for a group ''G'' acting on a set ''X'' with a
group action , ''x'' in ''X'' is said to be a fixed point of ''g'' if
.
The
fixed-point subgroup of an
automorphism ''f'' of a
group ''G'' is the
subgroup of ''G'':
Similarly the
fixed-point subring of an
automorphism ''f'' of a
ring ''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 ...
of the fixed points of ''f'', that is,
In
Galois theory, the set of the fixed points of a set of
field automorphisms is a
field called the
fixed field 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 poin ...
is said to have the
fixed point property (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 val ...
:
there exists
such that
.
The FPP is a
topological invariant, 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 isom ...
. The FPP is also preserved by any
retraction.
According to the
Brouwer fixed-point theorem, 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 Britis ...
and
convex subset
In mathematics, set ''A'' is a subset of a set ''B'' if all 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 unequal, then ''A'' is a proper subset of ...
of a
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
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, 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
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 circumscribe the ...
.
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 of a
function 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. A poset consists of a set together with a binary ...
(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 is to say that a
monotone function 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 com ...
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 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 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 forma ...
, 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 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 languages ...
s, in particular to
Datalog.
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 are fundamental concepts that can be described in terms of fixed points. Some examples follow.
* In
projective geometry, a fixed point of a
projectivity has been called a double point.
* In
economics
Economics () is the social science that studies the production, distribution, and consumption of goods and services.
Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics anal ...
, 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, usually undertaken for entertainment or fun, and sometimes used as an educational tool. Many games are also considered to be work (such as professional players of spectator sports or games) or art (suc ...
is a fixed point of the game's
best response correspondence.
John Nash exploited the
Kakutani fixed-point theorem 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 ...
, 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 R ...
'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 t ...
, and to the mathematical explanation of the term "
critical phenomenon."
*
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 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
Dat ...
, which is often required for code
optimization. They are also the core concept used by the generic program analysis method
abstract interpretation.
* In
type theory, the
fixed-point combinator allows definition of recursive functions in the
untyped lambda calculus.
* The vector of
PageRank values of all web pages is the fixed point of a
linear transformation 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 ...
's link structure.
* The stationary distribution of a
Markov chain 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 e ...
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 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 of permutations
*
Eigenvector
*
Equilibrium
*
Fixed points of a Möbius transformation
*
Idempotence
*
Infinite compositions of analytic functions
*
Invariant (mathematics)
Notes
{{reflist
External links
An Elegant Solution for Drawing a Fixed Point
Game theory