KNOWPIA
WELCOME TO KNOWPIA

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

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

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 .

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 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.^{[1]}

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*).^{[2]} The opposite usage occasionally appears.^{[3]} A fixed point is a point that is both a prefixpoint and a postfixpoint. Prefixpoints and postfixpoints have applications in theoretical computer science.^{[4]}

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).^{[5]}

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.

A fixed-point theorem is a result saying that at least one fixed point exists, under some general condition.^{[6]} Some authors claim that results of this kind are amongst the most generally useful in mathematics.^{[7]}

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**.^{[8]}^{[9]} - 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."^{[10]}^{[11]} - 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.
^{[12]} - 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.

**^**Kinoshita, S. (1953). "On Some Contractible Continua without Fixed Point Property".*Fund. Math.***40**(1): 96–98. doi:10.4064/fm-40-1-96-98. ISSN 0016-2736.**^**Smyth, Michael B.; Plotkin, Gordon D. (1982). "The Category-Theoretic Solution of Recursive Domain Equations" (PDF).*Proceedings, 18th IEEE Symposium on Foundations of Computer Science*. SIAM Journal of Computing (volume 11). pp. 761–783. doi:10.1137/0211062.**^**Patrick Cousot; Radhia Cousot (1979). "Constructive Versions of Tarski's Fixed Point Theorems" (PDF).*Pacific Journal of Mathematics*.**82**(1): 43–57. doi:10.2140/pjm.1979.82.43.**^**Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine**^**Yde Venema (2008) Lectures on the Modal μ-calculus Archived March 21, 2012, at the Wayback Machine**^**Brown, R. F., ed. (1988).*Fixed Point Theory and Its Applications*. American Mathematical Society. ISBN 0-8218-5080-6.**^**Dugundji, James; Granas, Andrzej (2003).*Fixed Point Theory*. Springer-Verlag. ISBN 0-387-00173-5.**^**Coxeter, H. S. M. (1942).*Non-Euclidean Geometry*. University of Toronto Press. p. 36.**^**G. B. Halsted (1906)*Synthetic Projective Geometry*, page 27**^**Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. I. Renormalization Group and the Kadanoff Scaling Picture".*Physical Review B*.**4**(9): 3174–3183. Bibcode:1971PhRvB...4.3174W. doi:10.1103/PhysRevB.4.3174.**^**Wilson, Kenneth G. (1971). "Renormalization Group and Critical Phenomena. II. Phase-Space Cell Analysis of Critical Behavior".*Physical Review B*.**4**(9): 3184–3205. Bibcode:1971PhRvB...4.3184W. doi:10.1103/PhysRevB.4.3184.**^**"P. Cousot & R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints".

- An Elegant Solution for Drawing a Fixed Point