Skip to main content
computer-science economics mathematics psychology

​
Fixed point

​
Description

A point where input equals output under an operation: f(x) = x. Iterate the operation forever at the fixed point and the value doesn’t move. The diagnostic question — is there a value the operation leaves unchanged, and what does it tell us about the dynamics? — turns process descriptions into self-consistency conditions: “what value would have to be true for this operation to be self-consistent?” Fixed points come with a critical secondary property: stability. Attracting fixed points pull nearby points toward themselves under iteration (the Banach contraction-mapping theorem guarantees convergence in the contraction case); repelling fixed points push nearby points away under iteration. The same algebraic condition f(x) = x describes both — refuges and knife-edges — and the difference decides whether the fixed point is what the system actually settles to in practice. In computer science, fixed-point semantics is the foundation of how recursive programs mean what they mean: the meaning of a recursive function is the least fixed point of the corresponding function-of-functions.

​
Triggers

User-initiated: User describes iterative computations that “settle to” something, asks where a recursive definition’s meaning is anchored, or asks about a self-consistency condition. Vocabulary cues: “converges to,” “settles to,” “iterative,” “recursive,” “self-consistent,” “invariant under.” Agent-initiated: Agent encounters an iterated update process and considers what its long-run state is; or encounters a self-referential definition and considers what value makes it self-consistent. Candidate inference: “what is the fixed point; is it unique; is it attracting?” Vocabulary cues: “fixed point,” “f(x) = x,” “input equals output,” “self-referential,” “recursive definition,” “iterative convergence,” “Banach contraction,” “least fixed point,” “eigenvector.” Situation-shape signals: An iterative process or recursive definition whose long-run behavior is the load-bearing question. A self-consistency condition: “what value would have to be true for this to be coherent?” A search problem solved by repeated application of an operation. A best-response or equilibrium-existence question.

​
Exclusions

  • Non-iterative / one-shot operations — the framing requires applying the operation repeatedly (or considering self-consistency); a one-time function evaluation doesn’t have a fixed-point character.
  • Non-contracting operations without stability guarantees — Banach’s theorem assumes contraction; non-contracting iterations may diverge or oscillate. Asserting “this iterative process has a fixed point” without checking the conditions overpromises.
  • Pathological / discontinuous self-maps — Brouwer’s theorem assumes continuity; pathological maps may not have fixed points. The structural primitive still describes the question, but the existence guarantee is delicate.
  • Where the question is the path, not the destination — if the trajectory’s character is the load-bearing content (e.g., the texture of convergence, not just where it ends up), the fixed-point framing loses important information.

​
Structure

Internal structure of fixed-point: a table of its component slots and the concepts that fill them.

​
Relationships

Relationship neighborhood of fixed-point: a graph of the concepts it connects to and the concepts it is a part of.
  • equilibrium — an equilibrium in iterated-update form IS a fixed point — input equals output under the dynamics.
  • attractor — an attracting fixed point is the simplest kind of attractor — a point-attractor in iterated dynamics.
  • hysteresis — fixed points are state-determined-by-current-only, while hysteresis is the case where the state depends on the path taken to get there; a system with stable fixed points has its state determined by current input alone, but a hysteretic system has multiple coexisting fixed points and which one you’ve landed in matters. (hysteresis.md already references fixed-point.)
  • seeding — iterative computations converge to fixed points whose identity is determined by the seed when there are multiple basins; seed-sensitivity is fixed-point-multiplicity in disguise.

​
Examples

PageRank · computer-science

the dominant eigenvector of the link matrix; a fixed point of the link-following operation.

Nash equilibrium · economics

a profile of strategies where no player can improve unilaterally; structurally a fixed point of the best-response correspondence.
Tarski’s 1955 theorem established that any order-preserving (monotone) function on a complete lattice has a fixed point — and, more strongly, that the set of fixed points itself forms a complete lattice. This generalized the topological fixed-point results of Brouwer and Banach into a purely order-theoretic setting, requiring no metric or continuity assumptions.The result is foundational in denotational semantics (the least fixed point of a monotone operator on a domain gives the meaning of a recursive program), in static analysis (program properties as fixed points of abstract-interpretation operators), and anywhere a self-referential definition resolves by repeated approximation. Tarski showed that the abstract shape “the operation’s output equals its input” survives stripping away geometry — only the order matters.
guarantees a unique fixed point exists and iteration converges to it when the operation is a contraction.
every continuous self-map of a compact convex set has a fixed point; the existence machinery behind equilibrium proofs in economics.
Dana Scott and Christopher Strachey, “Toward a Mathematical Semantics for Computer Languages” (Programming Research Group Tech Monograph, 1971) — fixed-point semantics of recursive programs.
the meaning of a recursive program is the least fixed point of the program’s defining functional; Scott-Strachey theory.
Nash’s 1951 proof of equilibrium existence for non-cooperative games and the 1954 Arrow-Debreu proof of general-equilibrium existence in a competitive economy both turn on fixed-point theorems — Nash uses Kakutani’s set-valued generalization of Brouwer; Arrow-Debreu uses Kakutani in a similar way. The substantive economic claim (“an equilibrium exists”) is, in each case, recast as a topological claim (“a certain best-response correspondence has a fixed point”) and proved by appeal to abstract structure.This is a third-discipline confirmation of the same shape that arose in topology and analysis: equilibrium-as-stationarity is fixed-point existence. The economic content lives in setting up the best-response mapping; the existence of the equilibrium is essentially a corollary of the underlying mathematical theorem. The portability is striking — the same abstract result handles markets, games, and recursive program meaning.
Newton’s method, gradient descent, iterative linear-system solvers; all are fixed-point iterations.
John Nash, “Non-Cooperative Games” (Annals of Mathematics, 1951) — Nash equilibrium existence via Kakutani fixed-point theorem.
Kenneth Arrow and Gérard Debreu, “Existence of an Equilibrium for a Competitive Economy” (Econometrica, 1954) — general equilibrium existence.
Brouwer’s 1911 paper in Mathematische Annalen gave the first proof of what is now the topological cornerstone of fixed-point theory. Stated in modern terms: every continuous map from a compact convex set to itself has at least one fixed point — a point where input equals output, f(x) = x. Brouwer proved it for the n-ball (his “n-dimensional element”); because every non-empty compact convex subset of Euclidean space is homeomorphic to a closed n-ball, the result extends to that whole class.What makes this the load-bearing member of the fixed-point family is the kind of guarantee it gives. Banach’s contraction theorem also guarantees a fixed point, but only for contractions, and it tells you where (a unique point, reachable by iteration). Brouwer demands almost nothing — just continuity and a compact convex domain — and in exchange promises only existence: a fixed point is there somewhere, with no contraction assumption, no uniqueness, and no constructive recipe for finding it. The proof is non-constructive, which is exactly why it can underwrite situations where you cannot iterate your way to the answer.Inference: Brouwer is the right tool when you need to assert that a self-map has a resting point but have no contraction to lean on and no need to locate the point — only to know it exists. This is the existence machinery behind equilibrium proofs: Nash and Arrow–Debreu both establish that an economy or game has an equilibrium by showing the relevant best-response map is a continuous self-map of a compact convex set, then invoking Brouwer (or its set-valued cousin, Kakutani). The structural cost of the weak hypotheses is the weak conclusion — you learn that equilibrium exists, not which one obtains or how to compute it.
one of the most-used structural primitives in mathematics; the cross-discipline transfer to computer science (recursive definitions, denotational semantics, type theory) is canonical
factorial(n) = if n=0 then 1 else n * factorial(n-1); the function is the fixed point of a corresponding higher-order operation.
beliefs about oneself that are self-fulfilling at the social level often correspond to fixed points of the perception-behavior loop.
The PageRank algorithm, introduced in Brin and Page’s 1998 paper describing the prototype of Google, computed a page’s importance as the stationary distribution of a random walk over the web’s link graph. Mathematically, the rank vector is the eigenvector of the link-transition matrix associated with eigenvalue 1 — equivalently, the fixed point of the iteration that redistributes a page’s rank along its outgoing links.The algorithm computes the fixed point by power iteration: start with a uniform distribution, apply the transition operator repeatedly, watch the values converge. PageRank is a worked instance of the concept where the fixed-point property is the entire definition of the answer being sought — the rank a page “deserves” is precisely the value the redistribution operator leaves unchanged.
Banach’s 1922 paper — the published form of his doctoral dissertation — proved the contraction-mapping principle, the most operationally useful theorem in the fixed-point family. It states: if T is a contraction on a complete metric space (there is a constant k < 1 such that T pulls any two points closer by at least the factor k), then T has exactly one fixed point, and you reach it by iterating T from any starting point — the sequence x, T(x), T(T(x)), … converges to it.Set against Brouwer, the trade is reversed. Brouwer asks almost nothing of the map (continuity on a compact convex set) and gives almost nothing back (mere existence, possibly many points, no recipe). Banach asks for a stronger condition (the map must contract) and in return gives the strongest possible conclusion: existence, uniqueness, and a constructive algorithm with guaranteed convergence. The contraction hypothesis is what turns “a fixed point is there somewhere” into “here is the fixed point, and here is how to compute it to any precision.”Inference: Banach is the tool whenever an iterative process is contractive — and that condition is exactly what licenses the “just keep applying the operation until it stops moving” pattern. It unifies a large class of successive-approximation methods (Picard iteration for differential equations, Newton’s method near a root, value iteration in dynamic programming) under one guarantee. The practical diagnostic the concept warns about: before asserting “this iteration converges to a fixed point,” check that the map actually contracts. A non-contracting iteration may diverge or oscillate, and Banach gives you nothing in that regime — that is where you must fall back to a weaker existence result like Brouwer’s, paying for it with the loss of uniqueness and constructiveness.