nLab fixed point

Contents

Contents

Idea

A fixed point (or fixpoint) of an endofunction f:XXf \colon X \to X is an element xXx \in X such that f(x)=xf(x) = x.

More generally, if CC is a category with a terminal object 11 and an endomorphism f:XXf \colon X \to X, then a fixed point of ff is an element x:1Xx \colon 1 \to X such that fx=xf \circ x = x. More generally still, we can speak of the same notion but replacing global elements x:1Xx \colon 1 \to X by generalized elements x:UXx \colon U \to X, where again xx is a fixed point of f:XXf \colon X \to X if fx=xf \circ x = x.

Fixed points are also called invariants, in particular if they are joint fixed points of all the operations in a given monoid or group.

Such fixed points we discuss below in

The importance of fixed points all throughout mathematics is difficult to overstate. They are particularly important in analysis, topology, lattice theory, set theory, and category theory. Fixed points of endofunctors frequently arise as solutions to “recursive equations”, especially in the form of initial algebras and terminal coalgebras.

In category theory the concept of fixed points admits categorification: For example, if F:CCF \colon C \to C is an endofunctor, then an object cc of CC is called a “fixed point of the endofunctor” FF is there is an isomorphism F(c)cF(c) \cong c (although usually, a fixed point of a functor is an object together with a specified such isomorphism). These fixed points for endofunctors we discuss below in

See also at

In homotopy theory the concept of fixed point becomes that of

In stable homotopy theory it becomes the concept of

For further occurences in logic see also

Examples in analysis and topology

A typical application of fixed points in analysis is through the following general theorem:

Theorem

Suppose XX is an (inhabited) complete metric space with distance function dd and f:XXf \colon X \to X is a function with Lipschitz constant rr less than 11, i.e., d(f(x),f(y))rd(x,y)d(f(x), f(y)) \leq r \cdot d(x, y) for all x,yXx, y \in X. Then ff has a unique fixed point.

The proof is very easy: starting with an initial point x 0x_0, the sequence defined by x n+1=f(x n)x_{n+1} = f(x_n) is readily seen to be a Cauchy sequence which converges to some point xx. The sequence x n+1=f(x n)x_{n+1} = f(x_n) converges to both xx and f(x)f(x), so x=f(x)x = f(x). If xx and yy are fixed points, then 0d(x,y)=d(f(x),f(y))rd(x,y)0 \leq d(x, y) = d(f(x), f(y)) \leq r \cdot d(x, y), so

(1r)d(x,y)0(1-r)d(x, y) \leq 0

whence 0d(x,y)00 \leq d(x, y) \leq 0 and therefore x=yx = y.

By a suitable choice of space XX and endomorphism ff, this theorem can be used to establish existence and uniqueness of solutions of differential equations (this should be expanded upon).

In the case where XX is compact, we may weaken the condition d(f(x),f(y))rd(x,y)d(f(x), f(y)) \leq r d(x, y) for some uniform r<1r \lt 1, to merely d(f(x),f(y))<d(x,y)d(f(x), f(y)) \lt d(x, y) whenever xyx \neq y. To see this, use compactness to show that d(x,f(x))d(x, f(x)) attains a minimum value at some x 0x_0. Then f(x 0)=x 0f(x_0) = x_0, else d(f(x 0),f(f(x 0)))<d(x 0,f(x 0))d(f(x_0), f(f(x_0))) \lt d(x_0, f(x_0)). Hence there exists at least one fixed point, and only one since if x 0,y 0x_0, y_0 are different fixed points, then d(x 0,y 0)=d(f(x 0),f(y 0))<d(x 0,y 0)d(x_0, y_0) = d(f(x_0), f(y_0)) \lt d(x_0, y_0).

Examples for ordered sets

Knaster-Tarski theorem

Theorem

If LL is a complete lattice, then every monotone (i.e., order-preserving) map f:LLf \colon L \to L has a fixed point (in fact, the fixed points of ff form a complete lattice).

Proof

The algebras for the functor f:LLf \colon L \to L are elements xx such that f(x)xf(x) \leq x. Limits in Alg(L)Alg(L) are preserved and reflected by the forgetful functor or inclusion Alg(L)LAlg(L) \to L, hence Alg(L)Alg(L) is complete if LL is. In particular, Alg(L)Alg(L) has an initial object, and initial algebras are fixed points.

(In more down-to-earth terms, let tt be the infimum of A={x:f(x)x}A = \{x: f(x) \leq x\}. Then for every xAx \in A, we have f(t)f(x)xf(t) \leq f(x) \leq x, hence f(t)tf(t) \leq t. We therefore also have f(f(t))f(t)f(f(t)) \leq f(t), so that f(t)Af(t) \in A. But then it follows that tf(t)t \leq f(t), whence t=f(t)t = f(t). Clearly this tt is a least fixed point of ff.)

To show completeness of fix(f)fix(f), suppose given Sfix(f)S \subseteq fix(f), and let ss be the supremum of SS in LL. Then the principal upward-closed set ss \uparrow generated by ss is a complete lattice. Also, ff restricts to a map sss \uparrow \to s \uparrow (for if sxs \leq x, then pxp \leq x for all pSp \in S, whence p=f(p)f(x)p = f(p) \leq f(x) for all pSp \in S, so that sf(x)s \leq f(x)). The least fixed point of f:ssf: s \uparrow \to s \uparrow is the supremum of SS in fix(f)fix(f).

A virtual corollary of this theorem is the Cantor-Schroeder-Bernstein theorem.

Pataraia’s theorem

The following significantly strengthens the Knaster-Tarski theorem, and is based on the notion of an ipo (inductive partial order; see Paul Taylor’s book), i.e., a poset with a bottom element and admitting joins of directed subsets.

Theorem

(Pataraia)
If LL is an ipo, then every monotone map f:LLf \colon L \to L has a (least) fixed point.

Proof

Consider the smallest SS among subsets of LL which contain \bot, are closed under ff, and closed under directed joins in LL. Then the restriction f:SSf \colon S \to S satisfies 1 Sf1_S \leq f, i.e., ff is inflationary. (For the set of all elements xLx \in L such that xf(x)x \leq f(x) is another such subset, so SS is contained in it.) Thus it suffices to show that every inflationary map on a poset SS with a bottom element and directed joins has a fixed point.

The collection II of inflationary monotone maps on SS is an ipo: its bottom element is 1 S1_S, and directed joins are computed pointwise. Moreover, II is itself directed: if g,hIg, h \in I, then ghIg \circ h \in I dominates them both. Thus the directed join tt of the collection exists; it is the maximal element tt of II. It follows that fttf \circ t \leq t, but also tftt \leq f \circ t since ff is inflationary. So ft=tf \circ t = t, and in particular t()St(\bot) \in S is a fixed point of ff.

This t()t(\bot) is a least fixed point of f:LLf: L \to L. For if xx is any fixed point, the downward-closed set LxL \downarrow x contains \bot, is closed under ff, and is closed under directed unions, and therefore SLxS \subseteq L \downarrow x. Hence t()St(\bot) \in S satisfies t()xt(\bot) \leq x.

One may mimic the last part of the proof of the Knaster-Tarski theorem to show that if LL is an ipo and ff is monotone, then fix(f)fix(f) (with the order inherited from LL) is also an ipo. Indeed, we have just seen fix(f)fix(f) has a bottom element, and if Afix(f)A \subseteq fix(f) is any directed subset, and s=sup(A)s = sup(A) is its sup in LL, then we may argue as we did for the Knaster-Tarski theorem that ff restricts to a monotone map on the ipo sLs \uparrow L, whence by Pataraia’s theorem it has a least fixed point, and this will be the sup of AA in fix(f)fix(f).

Galois connections

Examples in set theory

  • The identity function on a set SS is the unique function on SS such that every element in SS is a fixed point of said function.

  • In at least some of the “lower” levels of the hierarchy of countable ordinals, leading up to the Feferman-Schütte ordinal, fixed points of continuous operators on the first uncountable ordinal play a central role. More information may be found at countable ordinal.

  • Critical points of elementary embeddings (non-fixed points)

Examples in category theory

Initial algebras and final coalgebras

Various classical fixed-point theorems for monotone functions on posets can be “categorified” to give appropriate fixed-point theorems for endofunctors on categories. An example is that Kleene's fixed-point theorem generalizes to Adámek's fixed point theorem:

Theorem

Let CC be a category with an initial object 00 and colimits of κ\kappa-directed diagrams for some regular cardinal κ\kappa, and suppose F:CCF \colon C \to C preserves κ\kappa-directed colimits. Then FF has an initial algebra (which by Lambek's theorem is a fixed point of FF).

Proof

Regarding κ\kappa as an ordinal {α<κ}\{\alpha \lt \kappa\} (hence a poset, hence a category), define a functor G:κCG \colon \kappa \to C recursively: on objects, put G()=0G(\emptyset) = 0, G(α+1)=F(G(α))G(\alpha + 1) = F(G(\alpha)), and G(β)=colim α<βG(α)G(\beta) = colim_{\alpha \lt \beta} G(\alpha) for β\beta a limit ordinal. On morphisms α<β\alpha \lt \beta,

  • G(<β)G(\emptyset \lt \beta) is the unique map 0G(β)0 \to G(\beta);

  • For β\beta a limit ordinal, G(α<β)G(\alpha \lt \beta) is a component of the cocone diagram that defines G(β)G(\beta) as a colimit;

  • G(α+1<β+1)=F(G(α<β))G(\alpha + 1 \lt \beta + 1) = F(G(\alpha \lt \beta));

  • For α\alpha a limit ordinal, G(α<β+1)G(\alpha \lt \beta + 1) is the unique map colim γ<αG(γ)G(β+1)colim_{\gamma \lt \alpha} G(\gamma) \to G(\beta +1) corresponding to the cocone from the diagram G|:αCG| \colon \alpha \to C to G(β+1)G(\beta+1).

By assumption, colimGcolim G exists in CC, and this colimit is preserved by FF. Thus we have an isomorphism F(colimG)colimGF(colim G) \cong colim G, affording an FF-algebra structure on colimGcolim G. If (x,θ:F(x)x)(x, \theta: F(x) \to x) is any algebra, then we define a cocone from GG to xx whose component at successor stages α+1\alpha + 1 is defined recursively as an evident composite

G(α+1)=F(G(α))F(x)θx,G(\alpha + 1) = F(G(\alpha)) \to F(x) \stackrel{\theta}{\to} x,

and whose component at limit stages α\alpha is the unique map G(α)xG(\alpha) \to x out of the colimit that is compatible with previous components G(β)xG(\beta) \to x, for β<α\beta \lt \alpha. It is readily seen that the map colimGxcolim G \to x, uniquely determined from the cocone GxG \to x, is the only possible algebra map.

A typical application is where CC is a κ\kappa-accessible category and F:CCF \colon C \to C is a κ\kappa-accessible functor. A concise statement is that accessible endofunctors on accessible categories with an initial object possess categorical fixed points (in fact, the fixed points form another accessible category with an initial object).

An arguably more elegant viewpoint on this is given in the following theorem and proof.

Theorem

Suppose CC is locally presentable, i.e., accessible and complete/cocomplete, and suppose F:CCF \colon C \to C is an accessible functor. Then the category of FF-algebras is also locally presentable. In particular, there exists an initial FF-algebra. Moreover, the category of fixed points, i.e., the category of FF-algebras XX for which the structure FXXF X \to X is an isomorphism is also locally presentable (in particular, cocomplete and complete).

Proof

Alg FAlg_F is an inserter construction, i.e., the data consisting of the evident 1-cell U:Alg FCU \colon Alg_F \to C and 2-cell FUUF \circ U \to U is universal among all such data in the 2-category CatCat. Since AccAcc is closed under 2-limits in CatCat such as inserters (see Makkai-Paré, theorem 5.1.6), the category Alg FAlg_F is accessible. It is also complete since CC is complete (being locally presentable) and the underlying functor U:Alg FFU \colon Alg_F \to F reflects limits. Since Alg FAlg_F is accessible and complete, it is also cocomplete, hence contains an initial object.

Similarly, the category of fixed points i:Fix(F)Ci \colon Fix(F) \to C is formed as an iso-inserter construction and is therefore accessible. If D:JFix(F)D \colon J \to Fix(F) is a diagram of fixed points and cOb(C)c \in Ob(C) is the colimit of iDi \circ D, then FF induces a functor (which we give the same name) F:cCcCF\colon c \downarrow C \to c \downarrow C, because for any object cdc \to d in cCc \downarrow C, we have a cocone iDFiDF(d)i \circ D \cong F \circ i \circ D \to F(d), factoring uniquely through an arrow cF(d)c \to F(d). Since cCc \downarrow C is a locally presentable category, the accessible functor FF acting on it has an initial algebra (cc,(cF(c))(cc))(c \to c', (c \to F(c')) \to (c \to c')), as we argued before. This is the colimit of DD in Fix(F)Fix(F), as is easily checked. Therefore Fix(F)Fix(F) is cocomplete and accessible.

Boundedness conditions, such as those given as hypotheses in the previous two theorems, are generally required to establish existence of categorical fixed points. The example of the covariant power-set functor on SetSet shows that a naive generalization of the Knaster-Tarski theorem from complete lattices to complete/cocomplete categories is hopelessly false.

Paul Taylor has built an elegant theory of locating certain initial algebras inside final coalgebras, via his notion of well-founded coalgebras. This too can be “categorified” (to be continued).

Fixed points of left exact idempotent endofunctors

Theorem (Paré, Rosebrugh, Wood)

Let EE be a topos, and let F:EEF \colon E \to E be a left-exact idempotent functor. Then the category of FF-coalgebras XX whose structure maps θ:XF(X)\theta \colon X \to F(X) are isomorphisms is a topos.

Here “idempotent” involves a coassociativity condition.

This theorem is a special case of a general theorem about categories of dialgebras for a diad?.

Todd: To be related to structures over a modal operator, as at my web, or to diads a la Toby Kenney.

Theorems

References

A version of the Knaster-Tarski fixed-point theorem is proved in constructive (and even predicative) set theory in

  • Giovanni Curi, On Tarski’s fixed point theorem, Proc. Amer. Math. Soc. 143 (2015), 4439-4455 doi:10.1090/proc/12569

as well as in dependent type theory in

  • Ian Ray, Tarski’s Least Fixed Point Theorem: A Type Theoretic Formulation (arXiv:2401.00841)

A relation to framed cobordism classes and fixed points:

  • Carlos Prieto, Fixed point theory and framed cobordism, Topol. Methods Nonlinear Anal. Volume 21, Number 1 (2003), 155-169. (Euclid)

  • Robert Paré, R. Rosebrugh and R. J. Wood, Idempotents in bicategories, Bulletin of the Australian Mathematical Society, Vol. 39, No. 3, 1989, pp. 421-434. [doi:10.1017/S0004972700003336]

  • Toby Kenney, Diads and their Application to Topoi, Applied Categorical Structures 17 (2009): 567-590.

Last revised on January 17, 2024 at 19:36:55. See the history of this page for a list of all contributions to it.