In mathematics, 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, for functions, a fixed point is an element that is mapped to itself by the function.
Formally, c is a fixed point of a function f if c belongs to both the domain and the codomain of f, and f(c) = c.
For example, if f is defined on the real numbers by
then 2 is a fixed point of f, because f(2) = 2.
Not all functions have fixed points: for example, f(x) = x + 1, has no fixed points, since x is never equal to x + 1 for any real number. In graphical terms, a fixed-point x means the point (x, f(x)) is on the line y = x, or in other words the graph of f has a point in common with that line.
In numerical analysis, 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 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 .
The notions of attracting fixed points, repelling fixed points, and periodic points are defined with respect to fixed-point iteration.
A fixed-point theorem is a result saying that at least one fixed point exists, under some general condition. [1]
For example, the Banach fixed-point theorem (1922) gives a general criterion guaranteeing that, if it is satisfied, fixed-point iteration will always converge to a fixed point.
The Brouwer fixed-point theorem (1911) says that any continuous function from the closed unit ball in n-dimensional Euclidean space to itself must have a fixed point, but it doesn't describe how to find the fixed point.
The Lefschetz fixed-point theorem (and the Nielsen fixed-point theorem) from algebraic topology give a way to count fixed points.
In algebra, 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 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.
A topological space is said to have the fixed point property (FPP) if for any continuous function
there exists such that .
The FPP is a topological invariant, i.e. is preserved by any homeomorphism. The FPP is also preserved by any retraction.
According to the Brouwer fixed-point theorem, every compact and convex subset of a Euclidean space 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. [2]
In domain theory, the notion and terminology of fixed points is generalized to a partial order. 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)[ citation needed ] of f is any p such that f(p) ≤ p. Analogously, a postfixed point of f is any p such that p ≤ f(p). [3] The opposite usage occasionally appears. [4] Malkis justifies the definition presented here as follows: "since f is before the inequality sign in the term f(x) ≤ x, such x is called a prefix point." [5] A fixed point is a point that is both a prefixpoint and a postfixpoint. Prefixpoints and postfixpoints have applications in theoretical computer science. [6]
In order theory, the least fixed point of a function from a partially ordered set (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 has a least fixpoint that coincides with its least prefixpoint (and similarly its greatest fixpoint coincides with its greatest postfixpoint). [7]
In combinatory logic for computer science, 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
In mathematical logic, 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 languages, in particular to Datalog.
This section needs additional citations for verification .(July 2018) |
In many fields, equilibria or stability are fundamental concepts that can be described in terms of fixed points. Some examples follow.
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 mapping a nonempty compact convex set to itself, there is a point such that . The simplest forms of Brouwer's theorem are for continuous functions from a closed interval in the real numbers to itself or from a closed disk to itself. A more general form than the latter is for continuous functions from a nonempty convex compact subset of Euclidean space to itself.
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., it includes all limiting values of points. For example, the open interval (0,1) would not be compact because it excludes the limiting values of 0 and 1, whereas the closed interval [0,1] would be compact. Similarly, the space of rational numbers is not compact, because it has infinitely many "punctures" corresponding to the irrational numbers, and the space of real numbers is not compact either, because it excludes the two limiting values and . However, the extended real number linewould be compact, since it contains both infinities. There are many ways to make this heuristic notion precise. These ways usually agree in a metric space, but may not be equivalent in other topological spaces.
In mathematics, a continuous function is a function such that a small variation of the argument induces a small variation of the value of the function. This implies there are no abrupt changes in value, known as discontinuities. More precisely, a function is continuous if arbitrarily small changes in its value can be assured by restricting to sufficiently small changes of its argument. A discontinuous function is a function that is not continuous. Until the 19th century, mathematicians largely relied on intuitive notions of continuity and considered only continuous functions. The epsilon–delta definition of a limit was introduced to formalize the definition of continuity.
In mathematics, the Banach fixed-point theorem is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certain self-maps of metric spaces, and provides a constructive method to find those fixed points. It can be understood as an abstract formulation of Picard's method of successive approximations. The theorem is named after Stefan Banach (1892–1945) who first stated it in 1922.
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 book Introduction to Metamathematics. A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr.
In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:
In mathematics, constructive analysis is mathematical analysis done according to some principles of constructive mathematics.
In mathematics, a closure operator on a set S is a function from the power set of S to itself that satisfies the following conditions for all sets
In mathematics, the barycentric subdivision is a standard way to subdivide a given simplex into smaller ones. Its extension on simplicial complexes is a canonical method to refine them. Therefore, the barycentric subdivision is an important tool in algebraic topology.
In computational complexity theory, the complexity class ELEMENTARY of elementary recursive functions is the union of the classes
In mathematics, a fixed-point theorem is a result saying that a function 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.
In mathematics, a path in a topological space is a continuous function from a closed interval into
In mathematics, the fixed-point index is a concept in topological fixed-point theory, and in particular Nielsen theory. The fixed-point index can be thought of as a multiplicity measurement for fixed points.
Axiomatic constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with "" and "" of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories.
In numerical analysis, fixed-point iteration is a method of computing fixed points of a function.
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 point. But another use is in order theory, where a partially ordered set P is said to have the fixed point property if every increasing function on P has a fixed point.
In proof theory, ordinal analysis assigns ordinals to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has a larger proof-theoretic ordinal than another it can often prove the consistency of the second theory.
In proof theory, a branch of mathematical logic, elementary function arithmetic (EFA), also called elementary arithmetic and exponential function arithmetic, is the system of arithmetic with the usual elementary properties of 0, 1, +, ×, , together with induction for formulas with bounded quantifiers.
In mathematics, structural Ramsey theory is a categorical generalisation of Ramsey theory, rooted in the idea that many important results of Ramsey theory have "similar" logical structures. The key observation is noting that these Ramsey-type theorems can be expressed as the assertion that a certain category has the Ramsey property.