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 Curry's combinatory logic introduced in 1930, and 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 the Richard 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.

See also

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. 
Retrieved from "https://en.wikipedia.org/w/index.php?title=Kleene–Rosser_paradox&oldid=727610926"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Kleene–Rosser_paradox
This page is based on the copyrighted Wikipedia article "Kleene–Rosser paradox"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA