Curry's paradox is a paradox that occurs in naive set theory or naive logics, and allows the derivation of an arbitrary sentence from a self-referring sentence and some apparently innocuous logical deduction rules. It is named after the logician Haskell Curry. Robert Boyles self-flowing flask fills itself in this diagram, but perpetual motion machines cannot exist (according to our present understanding of physics). ... In abstract mathematics, naive set theory1 was the first development of set theory, which was later to be framed more carefully as axiomatic set theory. ... Logic, from Classical Greek λόγος (logos), originally meaning the word, or what is spoken, (but coming to mean thought or reason) is most often said to be the study of criteria for the evaluation of arguments, although the exact definition of logic is a matter of controversy among philosophers. ... Haskell Brooks Curry (September 12, 1900, Millis, Massachusetts - September 1, 1982, State College, Pennsylvania) was an American mathematician and logician. ...

It has also been named Löb's paradox after Martin Hugo Löb.

In natural language

A natural language version of Curry's paradox might be a box which contains only a slip of paper stating the following: The term natural language is used to distinguish languages spoken and signed (by hand signals and facial expressions) by humans for general-purpose communication from constructs such as writing, computer-programming languages or the languages used in the study of formal logic, especially mathematical logic. ...

If everything in this box is true, then Santa Claus exists.

Suppose everything in the box is true. The slip says that if everything in the box is true, then Santa Claus exists. We are supposing that everything in the box is true, therefore we can conclude that Santa Claus exists. A common portrayal of Santa Claus. ...

We have found, then, that if we assume that everything in the box is true, then we can prove the existence of Santa Claus. But this is precisely what the slip was telling us, so the slip was right after all. Since it's the only thing in the box, that means everything in the box is, in fact, true. It follows therefore that Santa Claus exists.

There was nothing special about the clause "Santa Claus exists"; by this means, any proposition, whether true or not, may be proved.

In mathematical logic

Let us denote by Y the proposition to prove, in this case "Santa Claus exists". Then, let X denote the statement in the box, which asserts that Y follows from the truth of X. Mathematically, this can be written as X = (X → Y), and we see that X is defined in terms of itself. The proof proceeds:

1. X → X

identity

2. X → (X → Y) In logic, the law of identity states that A = A. Any reflexive relation upholds the law of identity; when discussing equality, the fact that A is A is a tautology. ...

substitute right side of 1, since X = X → Y

3. X → Y

from 2 by contraction

4. X In proof theory, a structural rule is an inference rule that does not refer to any logical connective, but instead operates on the judgements or sequents directly. ...

substitute 3, since X = X → Y

5. Y

from 4 and 3 by modus ponens

A particular case of this paradox is when Y is in fact a contradiction of the form Z∧¬Z. Then X becomes X = (X → (Z∧¬Z)). If the law of non-contradiction is accepted, then, from (X → (Z∧¬Z)), it follows that ¬X. Conversely, if the principle of explosion is accepted, and if ¬X, then from X anything follows, and in particular X → Z∧¬Z. Therefore X → Z∧¬Z is equivalent to ¬X. So X = ¬X, which is exactly the liar paradox. In Logic, Modus ponens (Latin: mode that affirms) is a valid, simple argument form (often abbreviated to MP): If P, then Q. P. Therefore, Q. or in logical operator notation: P → Q P ⊢ Q where ⊢ represents the logical assertion. ... In logic, the law of noncontradiction judges as false any proposition P asserting that both proposition Q and its denial, proposition not-Q, are true at the same time and in the same respect. In the words of Aristotle, One cannot say of something that it is and that it... (A ∧ ¬A)→ B Ex falso quodlibet, also known as ex contradictione (sequitur) quodlibet or the principle of explosion is the rule of classical logic that states that anything follows from a contradiction. ... In philosophy and logic, the liar paradox encompasses paradoxical statements such as: Analyzing the statement I am lying now, if what the speaker says is true, then the statement I am lying now is false, that means when the statement was said, the speaker was actually lying. ...

In naive set theory

Even if the underlying mathematical logic does not admit any self-referential sentence, in set theories which allow unrestricted comprehension, we can nevertheless prove any logical statement Y from the set In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of specification, or axiom schema of separation, or axiom schema of restricted comprehension, is a schema of axioms in Zermelo-Fraenkel set theory. ...

The proof proceeds:

Again a particular case of this paradox is when Y is in fact a contradiction. Then X becomes , which, similar to above, is equivalent to , the set of all sets which do not contain themselves. This is exactly Russell's paradox. Russells paradox (also known as Russells antinomy) is a paradox discovered by Bertrand Russell in 1901 which shows that the naive set theory of Frege is contradictory. ...

Discussion

Curry's paradox can be formulated in any language meeting certain conditions:

1. The language must contain an apparatus which lets it refer to, and talk about, its own sentences (such as quotation marks, names, or expressions like "this sentence");
2. The language must contain its own truth-predicate: that is, the language, call it "L", must contain a predicate meaning "true-in-L", and the ability to ascribe this predicate to any sentences;
3. The language must admit the rule of contraction, which roughly speaking means that a relevant hypothesis may be reused as many times as necessary; and
4. The language must of course admit the rules of identity ("if A, then A") and modus ponens (from "A", and "if A then B", conclude "B").

Various other sets of conditions are also possible. Natural languages nearly always contain all these features. Mathematical logic, on the other hand, generally does not countenance explicit reference to its own sentences, although the heart of Gödel's incompleteness theorem is the observation that usually this can be done anyway. The truth-predicate is generally not available, but in naïve set theory, this is arrived at through the unrestricted rule of comprehension. The rule of contraction is generally accepted, although linear logic (more precisely, linear logic without the exponential operators) does not admit the reasoning required for this paradox. La Vérité by the French painter Jules Joseph Lefebvre Common dictionary definitions of truth mention some form of accord with fact or reality. ... In proof theory, a structural rule is an inference rule that does not refer to any logical connective, but instead operates on the judgements or sequents directly. ... In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ... In formal number theory a Gödel numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a Gödel number (GN). ... In mathematical logic, linear logic is a type of substructural logic that denies the structural rules of weakening and contraction. ...

Note that unlike the liar paradox or Russell's paradox, this paradox does not depend on what model of negation is used, as it is completely negation-free. Thus paraconsistent logics can still be vulnerable to this, even if they are immune to the liar paradox. In logic, the law of noncontradiction judges as false any proposition P asserting that both proposition Q and its denial, proposition not-Q, are true at the same time and in the same respect. In the words of Aristotle, One cannot say of something that it is and that it... A paraconsistent logic is a non-trivial logic which allows inconsistencies. ...

The resolution of Curry's paradox is a contentious issue because nontrivial resolutions (such as disallowing X directly) are difficult and not intuitive. Logicians are undecided whether such sentences are somehow impermissible (and if so, how to banish them), or meaningless, or whether they are correct and reveal problems with the concept of truth itself (and if so, whether we should reject the concept of truth, or change it), or whether they can be rendered benign by a suitable account of their meanings.

External links

• http://luddite.cst.usyd.edu.au/cgi-bin/twiki/view/Jason/PenguinsRuleTheUniverse - A short discussion of Curry's paradox
• http://plato.stanford.edu/entries/curry-paradox/ - The Stanford Encyclopedia of Philosophy has an in-depth technical discussion.