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 C {\displaystyle \mathbf {C} } and given an object B {\displaystyle B} in it, if there is a weakly point-surjective morphism f {\displaystyle f} from some object A {\displaystyle A} to the exponential object B A {\displaystyle B^{A}} , then every endomorphism g : B → B {\displaystyle g:B\rightarrow B} has a fixed point. That is, there exists a morphism b : 1 → B {\displaystyle b:1\rightarrow B} (where 1 {\displaystyle 1} is a terminal object in C {\displaystyle \mathbf {C} } ) such that g ∘ b = b {\displaystyle g\circ b=b} . This can be further generalized to a much broader class of categories. Let C {\displaystyle \mathbf {C} } be a category equipped with a functor ♯ : C × C → C {\displaystyle \sharp :\mathbf {C} \times \mathbf {C} \rightarrow \mathbf {C} } , a chosen object t {\displaystyle t} , and natural transformation δ : i d C ⇒ ♯ ∘ Δ C {\displaystyle \delta :id_{\mathbf {C} }\Rightarrow \sharp \circ \Delta _{C}} . Let F : A ♯ A → C {\displaystyle F:A\sharp A\rightarrow C} and σ : C → C {\displaystyle \sigma :C\rightarrow C} be morphisms in C {\displaystyle \mathbf {C} } such that, ∃ a 0 : t → A , ∀ a : t → A {\displaystyle \exists a_{0}:t\rightarrow A,\forall a:t\rightarrow A} , such that σ ∘ F ∘ δ A ∘ a = F ∘ ( a 0 ♯ a ) ∘ δ t {\displaystyle \sigma \circ F\circ \delta _{A}\circ a=F\circ (a_{0}\sharp a)\circ \delta _{t}} . Then the map c := F ∘ δ ∘ a 0 : t → C {\displaystyle c:=F\circ \delta \circ a_{0}:t\rightarrow C} satisfies σ ∘ c = c {\displaystyle \sigma \circ c=c} .
Applications The theorem's contrapositive is particularly useful in proving many results. It states that if there is an object B {\displaystyle B} in the category such that there is an endomorphism g : B → B {\displaystyle g:B\rightarrow B} that has no fixed points, then there is no object A {\displaystyle A} with a weakly point-surjective map f : A → B A {\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