# Fixed point (mathematics)

{{#invoke:Hatnote|hatnote}}

In mathematics, a **fixed point** (sometimes shortened to **fixpoint**, also known as an **invariant point**) of a function is an element of the function's domain that is mapped to itself by the function. That is to say, *c* is a fixed point of the function *f*(*x*) if and only if *f*(*c*) = *c*. This means *f*(*f*(...*f*(*c*)...)) = *f ^{n}*(

*c*) =

*c*, an important terminating consideration when recursively computing

*f*. A set of fixed points is sometimes called a

*fixed set*.

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, if *f* is a function defined on the real numbers as *f*(*x*) = *x* + 1, then it has no fixed points, since *x* is never equal to *x* + 1 for any real number. In graphical terms, a fixed point 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.

Points which come back to the same value after a finite number of iterations of the function are known as periodic points; a fixed point is a periodic point with period equal to one. In projective geometry, a fixed point of a projectivity has been called a **double point**.^{[1]}

## Attractive fixed points

An *attractive fixed point* of a function *f* is a fixed point *x*_{0} of *f* such that for any value of *x* in the domain that is close enough to *x*_{0}, the iterated function sequence

converges to *x*_{0}. An expression of prerequisites and proof of the existence of such solution is given by the Banach fixed-point theorem.

The natural cosine function ("natural" means in radians, not degrees or other units) has exactly one fixed point, which is attractive. In this case, "close enough" is not a stringent criterion at all—to demonstrate this, start with *any* real number and repeatedly press the *cos* key on a calculator (checking first that the calculator is in "radians" mode). It eventually converges to about 0.739085133, which is a fixed point. That is where the graph of the cosine function intersects the line .

Not all fixed points are attractive: for example, *x* = 0 is a fixed point of the function *f*(*x*) = 2*x*, but iteration of this function for any value other than zero rapidly diverges. However, if the function *f* is continuously differentiable in an open neighbourhood of a fixed point *x*_{0}, and , attraction is guaranteed.

Attractive fixed points are a special case of a wider mathematical concept of attractors.

An attractive fixed point is said to be a *stable fixed point* if it is also Lyapunov stable.

A fixed point is said to be a *neutrally stable fixed point* if it is Lyapunov stable but not attracting. The center of a linear homogeneous differential equation of the second order is an example of a neutrally stable fixed point.

## Applications

In many fields, equilibria or stability are fundamental concepts that can be described in terms of fixed points. For example, in economics, a Nash equilibrium of a game is a fixed point of the game's best response correspondence. However, in physics, more precisely in the theory of phase transitions, *linearisation* near an *unstable* fixed point has led to Wilson's Nobel prize-winning work inventing the renormalization group, and to the mathematical explanation of the term "critical phenomenon".

In compilers, fixed point computations are used for program analysis, for example data-flow analysis which are often required to do code optimization.

The vector of PageRank values of all web pages is the fixed point of a linear transformation derived from the World Wide Web's link structure.

Logician Saul Kripke makes use of fixed points in his influential theory of truth. He shows how one can generate a partially defined truth predicate (one which remains undefined for problematic sentences like "This sentence is not true"), by recursively defining "truth" starting from the segment of a language which contains no occurrences of the word, and continuing until the process ceases to yield any newly well-defined sentences. (This will take a denumerable infinity of steps.) That is, for a language L, let 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-prime 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 which contains its *own* truth predicate.

The concept of fixed point can be used to define the convergence of a function.

## Topological fixed point property

{{#invoke:main|main}}
A topological space is said to have the *fixed point property* (briefly FPP) if for any continuous function

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

## Generalization to partial orders: prefixpoint and postfixpoint

The notion and terminology 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 **prefixpoint** (also spelled **pre-fixpoint**) of *f* is any *p* such that *f*(*p*) ≤ *p*. Analogously a **postfixpoint** (or **post-fixpoint**) of *f* is any *p* such that *p* ≤ *f*(*p*).^{[3]} One way to express the Knaster–Tarski theorem is to say that a monotone function on a complete lattice has a least fixpoint which coincides with its least prefixpoint (and similarly its greatest fixpoint coincides with its greatest postfixpoint). Prefixpoints and postfixpoints have applications in theoretical computer science.^{[4]}

## See also

- Eigenvector
- Equilibrium
- Attractor
- Stability theory
- Stationary point
- Normal form of Möbius transformation
- Invariant (mathematics)
- Fixed-point combinator
- Fixed point property
- Idempotent
- Fixed-point theorems
- Least fixed point and greatest fixed point
- Nielsen theory
- Sierpinski triangle
- Koenigs function
- Recurrence relation

## Notes

- ↑ H. S. M. Coxeter (1942)
*Non-Euclidean Geometry*, page 36, University of Toronto Press - ↑ Kinoshita, S. On Some Contractible Continua without Fixed Point Property.
*Fund. Math.***40**(1953), 96–98 - ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Yde Venema (2008) Lectures on the Modal μ-calculus