Jump to content

Lawvere's fixed-point theorem

From Wikipedia, the free encyclopedia

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

It was first proven by William Lawvere in 1969.[3][4]

Statement

[edit]

Lawvere's theorem states that, for any Cartesian closed category and given an object in it, if there is a weakly point-surjective morphism from some object to the exponential object , then every endomorphism has a fixed point. That is, there exists a morphism (where is a terminal object in ) such that .

Applications

[edit]

The theorem's contrapositive is particularly useful in proving many results. It states that if there is an object in the category such that there is an endomorphism which has no fixed points, then there is no object with a weakly point-surjective map . Some important corollaries of this are:[2]

References

[edit]
  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. ^ a b 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.