Please wait a minute...

Frontiers of Philosophy in China

Front. Philos. China    2019, Vol. 14 Issue (3) : 490-510
Some Applications of Lawvere’s Fixpoint Theorem
LI Xi()
Department of Philosophy, Central South University, Changsha 410083, China
Download: PDF(801 KB)  
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

The famous diagonal argument plays a prominent role in set theory as well as in the proof of undecidability results in computability theory and incompleteness results in metamathematics. Lawvere (1969) brings to light the common schema among them through a pretty neat fixpoint theorem which generalizes the diagonal argument behind Cantor’s theorem and characterizes self-reference explicitly in category theory. Not until Yanofsky (2003) rephrases Lawvere’s fixpoint theorem using sets and functions, Lawvere’s work has been overlooked by logicians. This paper will continue Yanofsky’s work, and show more applications of Lawvere’s fixpoint theorem to demonstrate the ubiquity of the theorem. For example, this paper will use it to construct uncomputable real number, unnameable real number, partial recursive but not potentially recursive function, Berry paradox, and fast growing Busy Beaver function. Many interesting lambda fixpoint combinators can also be fitted into this schema. Both Curry’s Y combinator and Turing’s Θ combinator follow from Lawvere’s theorem, as well as their call-by-value versions. At last, it can be shown that the lambda calculus version of the fixpoint lemma also fits Lawvere’s schema.

Keywords paradox      fixpoint      diagonalization      combinator     
Issue Date: 14 October 2019
 Cite this article:   
LI Xi. Some Applications of Lawvere’s Fixpoint Theorem[J]. Front. Philos. China, 2019, 14(3): 490-510.
E-mail this article
E-mail Alert
Articles by authors
Related articles from Frontiers Journals
[1] CUI Xiaojiao. Paradoxes in the Textual Development of the Laozi: A Closer Examination of Chapters Eight and Twenty-Four[J]. Front. Philos. China, 2017, 12(3): 393-407.
[2] Alan Fox. A Process Interpretation of Daoist Thought[J]. Front. Philos. China, 2017, 12(1): 26-37.
[3] Mircea Dumitru. On Toleration, Charity, and Epistemic Fallibilism[J]. Front. Philos. China, 2016, 11(4): 671-679.
[4] XU Zhaoqing. On Kripke’s Dogmatism Paradox: A Logical Dynamical Analysis[J]. Front. Philos. China, 2015, 10(2): 298-310.
[5] Byeong-uk Yi. Numeral Classifiers and the White Horse Paradox[J]. Front. Philos. China, 2014, 9(4): 498-522.
[6] Bernard Linsky. Russell’s Paradox of Predicates[J]. Front. Philos. China, 2014, 9(1): 149-165.
[7] WANG Wenfang. Filtering Theories of Truth: Compositionality as a Criterion[J]. Front Phil Chin, 2013, 8(1): 156-170.
[8] WANG Wenfang. Against Classical Dialetheism[J]. Front Phil Chin, 2011, 6(3): 492-500.
[9] DUN Xinguo. Queries on Hempel's solution to the paradoxes of confirmation[J]. Front. Philos. China, 2007, 2(1): 131-139.
Full text