nLab
fixed point

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

The same notion undergoes further generalization by 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 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).

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.

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

  • Brouwer’s theorem

  • Schauder

  • Kakutani

  • Tychonoff

  • Lefschetz

  • Atiyah-Singer; Wood’s Hole

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 an 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 f,gIf, g \in I, then fgIf \circ g \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 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.

Galois connections

Examples in set theory

  • 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 Adamek’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 kapa\kapa, 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(\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(β+1colim_{\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. (To be continued.)

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.

Todd: Here “idempotent” involves a coassociativity condition. To be related to structures over a modal operator, as at my web, or to diads a la Toby Kenney.

Domain theory

  • Adjunctions and adjoint equivalences

References

  • Claudio Hermida, Bart Jacobs, Structural induction and coinduction in a fibrational setting, Information and Computation 145 (1997), 107-152. (citeseer)

  • Michael Makkai and Robert Paré, Accessible Categories: The Foundations of Categorical Model Theory, Contemporary Mathematics 104, AMS (1989).

Revised on April 4, 2014 03:04:31 by Urs Schreiber (89.204.137.201)