Kleene–Rosser paradox

From Wikipedia, the free encyclopedia

In mathematics, the Kleene–Rosser paradox is a paradox that shows that certain systems of formal logic are inconsistent, in particular the version of Haskell Curry's combinatory logic introduced in 1930, and Alonzo Church's original lambda calculus, introduced in 1932–1933, both originally intended as systems of formal logic. The paradox was exhibited by Stephen Kleene and J. B. Rosser in 1935.

The paradox

Kleene and Rosser were able to show that both systems are able to characterize and enumerate their provably total, definable number-theoretic functions, which enabled them to construct a term that essentially replicates Richard's paradox in formal language.

Curry later managed to identify the crucial ingredients of the calculi that allowed the construction of this paradox, and used this to construct a much simpler paradox, now known as Curry's paradox.

References

Andrea Cantini, "The inconsistency of certain formal logics", in the Paradoxes and Contemporary Logic entry of Stanford Encyclopedia of Philosophy (2007).
Kleene, S. C. & Rosser, J. B. (1935). "The inconsistency of certain formal logics". Annals of Mathematics. 36 (3): 630–636. doi:10.2307/1968646. JSTOR 1968646.

v t e Notable paradoxes
Philosophical	Analysis Buridan's bridge Dream argument Epicurean Fiction Fitch's knowability Free will Goodman's Hedonism Liberal Meno's Mere addition Moore's Newcomb's Nihilism Omnipotence Preface Rule-following Sorites Theseus' ship White horse Zeno's
Logical	Barber Berry Bhartrhari's Burali-Forti Court Crocodile Curry's Epimenides Free choice paradox Grelling–Nelson Kleene–Rosser Liar Card No-no Pinocchio Quine's Yablo's Opposite Day Paradoxes of set theory Richard's Russell's Socratic Hilbert's Hotel Temperature paradox Barbershop Catch-22 Chicken or the egg Drinker Entailment Lottery Plato's beard Raven Ross's Unexpected hanging "What the Tortoise Said to Achilles" Heat death paradox Olbers's paradox
Economic	Allais Antitrust Arrow information Bertrand Braess's Competition Income and fertility Downs–Thomson Easterlin Edgeworth Ellsberg European Gibson's Giffen good Icarus Jevons Leontief Lerner Lucas Mandeville's Mayfield's Metzler Plenty Productivity Prosperity Scitovsky Service recovery St. Petersburg Thrift Toil Tullock Value
Decision theory	Abilene Apportionment Alabama New states Population Arrow's Buridan's ass Chainstore Condorcet's Decision-making Downs Ellsberg Fenno's Fredkin's Green Hedgehog's Inventor's Kavka's toxin puzzle Morton's fork Navigation Newcomb's Parrondo's Preparedness Prevention Prisoner's dilemma Tolerance Willpower
List Category

This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.

Categories:

Hidden categories:

The paradox

See also

References