# Fixed point (mathematics)

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 *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 *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.

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. In projective geometry, a fixed point of a projectivity has been called a **double point**.[1]

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.

## 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 .[2]

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.

Multiple attractive points can be collected in an *attractive fixed set*.

## Applications

In many fields, equilibria or stability are fundamental concepts that can be described in terms of fixed points. Some examples follow.

- In economics, a Nash equilibrium of a game 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, 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."[3][4]

- Programming language compilers use fixed point computations for program analysis, for example in data-flow analysis, which is often required for code optimization. They are also the core concept used by the generic program analysis method abstract interpretation.[5]

- 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's link structure.

- The stationary distribution of a Markov chain is the fixed point of the one step transition probability function.

- 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 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.

## Topological fixed point property

A topological space is said to have the *fixed point property* (briefly 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.[6]

## 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*).[7] 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). Prefixpoints and postfixpoints have applications in theoretical computer science.[8]

## See also

## Notes

- Coxeter, H. S. M. (1942).
*Non-Euclidean Geometry*. University of Toronto Press. p. 36. - Weisstein, Eric W. "Dottie Number".
*Wolfram MathWorld*. Wolfram Research, Inc. Retrieved 23 July 2016. - https://journals.aps.org/prb/pdf/10.1103/PhysRevB.4.3174
- https://journals.aps.org/prb/pdf/10.1103/PhysRevB.4.3184
- https://www.di.ens.fr/~cousot/COUSOTpapers/POPL77.shtml
- Kinoshita, S. (1953). "On Some Contractible Continua without Fixed Point Property".
*Fund. Math.***40**(1): 96–98. ISSN 0016-2736. - B. A. Davey; H. A. Priestley (2002).
*Introduction to Lattices and Order*. Cambridge University Press. p. 182. ISBN 978-0-521-78451-1. - Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine