Curry's paradox

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.

It has also been called Löb's paradox after Martin Hugo Löb. [1]

Contents:
1. In natural language
2. In formal language
3. In naive set theory
4. Discussion
5. See also
6. References
7. External links
1. In natural language

Claims of the form "if A, then B" are called conditional claims. It is not necessary to believe the conclusion (B) to accept the conditional claim (if A, then B) as true. For instance, consider the following sentence:

If a man with flying reindeer has delivered presents to all the good children in the world in one night, then Santa Claus exists.

Imagine that a man with flying reindeer has, in fact, done this. Does Santa Claus exist, in that case? It would seem so. Therefore, without believing that Santa Claus exists, or that this scenario is even possible, it seems that we should agree that if a man with flying reindeer has delivered presents to all the good children in the world in one night, then Santa Claus exists, and so the above sentence is true.

Now consider this other sentence:

If this sentence is true, then Santa Claus exists.

As before, imagine that the antecedent is true - in this case, "this sentence is true". Does Santa Claus exist, in that case? Well, if the sentence is true, then what it says is true: namely that if the sentence is true, then Santa Claus exists. Therefore, without necessarily believing that Santa Claus exists, or that the sentence is true, it seems we should agree that if the sentence is true, then Santa Claus exists.

But then this means the sentence is true. So Santa Claus does exist. Furthermore we could substitute any claim at all for "Santa Claus exists". This is Curry's paradox.

2. In formal language

In formal languages, we sometimes interpret "If X then Y" as a material conditional. On this reading, it simply means "Y, or else not X". Here we would read the sentence as "Santa Claus exists, or this sentence is false". On this reading, Curry's paradox is simply a variant on the liar paradox. However, in natural language this is not usually what we mean by "If X then Y". For instance, "if 6*7=42, then the moon exists" is true as a material implication, but is generally not considered true in natural language, because the moon's existence does not seem to be related to this fact of arithmetic.

Nevertheless we arrived at paradox in natural language. In fact, not only did we arrive at a contradiction, but we were actually able to prove anything at all, without relying on such principles as the principle of explosion which are generally held to be false in accounts of natural language. Thus Curry's paradox poses an additional problem.

To arrive at this formally, let us denote by Y the proposition to prove, in this case "Santa Claus exists". Then, let X denote the statement that 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

rule of assumption, also called restatement of premise or of hypothesis

2. X → (X → Y)

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

3. X → Y

from 2 by contraction

4. X

substitute 3, since X = X → Y

5. Y

from 4 and 3 by modus ponens

3. 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



The proof proceeds:

This can be seen as a variant on Russell's paradox, but is in an important way more general. Some proposals for set theory have attempted to deal with Russell's paradox not by restricting the rule of comprehension, but by restricting the rules of logic so that it tolerates the contradictory nature of the set of all sets that are not members of themselves. This reasoning shows that such a task is not so simple, because again, we have not only a contradiction, but we have in fact proved any statement whatsoever, without recourse to the full apparatus of the propositional calculus.
4. 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 theorems is the observation that usually this can be done anyway; see Gödel number. The truth-predicate is generally not available, but in naive 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.

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.

The resolution of Curry's paradox is a contentious issue because resolutions (apart from trivial ones 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.

Linear logic disallows contraction and so does not admit this paradox directly, but one must remove its exponential operators, or else the paradox reappears in a modal form.
5. See also

* Richard's paradox
* Kleene-Rosser paradox

6. References

1. Barwise, Jon and John Etchemendy 1987: The Liar, p. 23. Oxford University Press.

7. External links

* The Stanford Encyclopedia of Philosophy: "Curry's Paradox" -- by J. C. Beall.
* Grossman, Jason, Australian National University: A Proof that Penguins Rule the Universe. A brief and entertaining discussion of Curry's paradox.

"[1]" "[2]" Relevant First-Order Logic LP# and Curry's Paradox http://front.math.ucdavis.edu/0804.4818