Misplaced Pages

In mathematics, Lawvere's fixed-point theorem is an important result in category theory. It is a broad abstract generalization of many diagonal arguments in mathematics and logic, such as Cantor's diagonal argument, Cantor's theorem, Russell's paradox, Gödel's first incompleteness theorem, Turing's solution to the Entscheidungsproblem, and Tarski's undefinability theorem.

It was first proven by William Lawvere in 1969.

Statement

Lawvere's theorem states that, for any Cartesian closed category ${\displaystyle \mathbf {C} }$ and given an object ${\displaystyle B}$ in it, if there is a weakly point-surjective morphism ${\displaystyle f}$ from some object ${\displaystyle A}$ to the exponential object ${\displaystyle B^{A}}$, then every endomorphism ${\displaystyle g:B\rightarrow B}$ has a fixed point. That is, there exists a morphism ${\displaystyle b:1\rightarrow B}$ (where ${\displaystyle 1}$ is a terminal object in ${\displaystyle \mathbf {C} }$ ) such that ${\displaystyle g\circ b=b}$.

Applications

The theorem's contrapositive is particularly useful in proving many results. It states that if there is an object ${\displaystyle B}$ in the category such that there is an endomorphism ${\displaystyle g:B\rightarrow B}$ which has no fixed points, then there is no object ${\displaystyle A}$ with a weakly point-surjective map ${\displaystyle f:A\rightarrow B^{A}}$. Some important corollaries of this are:

• Cantor's theorem
• Cantor's diagonal argument
• Diagonal lemma
• Russell's paradox
• Gödel's first incompleteness theorem
• Tarski's undefinability theorem
• Turing's proof
• Löb's paradox
• Roger's fixed-point theorem
• Rice's theorem

References

1. Soto-Andrade, Jorge; J. Varela, Francisco (1984). "Self-Reference and Fixed Points: A Discussion and an Extension of Lawvere's Theorem". Acta Applicandae Mathematicae. 2. doi:10.1007/BF01405490.
2. ^ Yanofsky, Noson (September 2003). "A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points". The Bulletin of Symbolic Logic. 9 (3): 362–386. arXiv:math/0305282. doi:10.2178/bsl/1058448677.
3. Lawvere, Francis William (1969). "Diagonal arguments and Cartesian closed categories". Category Theory, Homology Theory and their Applications II (Lecture Notes in Mathematics, vol 92). Berlin: Springer.
4. Lawvere, William (2006). "Diagonal arguments and cartesian closed categories with author commentary". Reprints in Theory and Applications of Categories (15): 1–13.

v t e Category theory
Key concepts Key concepts Category Abelian Additive Concrete Pre-abelian Preadditive Bicategory Adjoint functors CCC Commutative diagram End Exponential Functor Kan extension Morphism Natural transformation Universal property Yoneda lemma Universal constructions Limits Terminal objects Products Equalizers Kernels Pullbacks Inverse limit Colimits Initial objects Coproducts Coequalizers Cokernels and quotients Pushout Direct limit Algebraic categories Sets Relations Magmas Groups Abelian groups Rings (Fields) Modules (Vector spaces) Constructions on categories Free category Functor category Kleisli category Opposite category Quotient category Product category Comma category Subcategory
Higher category theory Key concepts Categorification Enriched category Higher-dimensional algebra Homotopy hypothesis Model category Simplex category String diagram Topos n-categories Weak n-categories Bicategory (pseudofunctor) Tricategory Tetracategory Kan complex ∞-groupoid ∞-topos Strict n-categories 2-category (2-functor) 3-category Categorified concepts 2-group 2-ring En-ring (Traced)(Symmetric) monoidal category n-group n-monoid
Category Outline Glossary

• Category theory
• Mathematical theorems