Fixed Point

Definition

For an endofunctor $F:\mathcal{C}\to \mathcal{C}$, a fixed point is an object $X$ together with an isomorphism $f:F(X)\cong X$.

Disciussion

In the context of category theory, fixed points are characterized by the structure of algebras and coalgebras. While an arbitrary endofunctor may have many fixed points, two are of primary interest:

1. Initial $F$-algebra: The least fixed point, denoted $\mu F$.
2. Final $F$-coalgebra: The greatest fixed point, denoted $\nu F$.

Lambek’s Lemma

A fundamental result in the study of fixed points is Lambek’s Lemma, which states that if an endofunctor $F$ has an initial algebra $(\mu F,in)$, then the morphism $in:F(\mu F)\to \mu F$ is an isomorphism. Thus, every initial algebra is a fixed point. The dual holds for final coalgebras.

Domain Theory and Posets

In the context of a partially ordered set viewed as a category, a fixed point of a monotonic function $f$ is an element $x$ such that $f(x)=x$. The Knaster-Tarski theorem guarantees the existence of a complete lattice of fixed points if the underlying poset is a complete lattice.

References

Lambek, J. (1968). A fixedpoint theorem for complete categories. Mathematische Zeitschrift. Abramsky, S., & Jung, A. (1994). Domain Theory.