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]

In natural language

A natural language version of Curry's paradox might be the following sentence:

If this sentence is true, then Santa Claus exists.

We need not believe, beforehand, that the sentence is true or that Santa Claus exists. But we can ask, hypothetically, if the sentence is true, then does Santa Claus exist?

If the sentence is true, then what it says is true, namely that if the sentence is true, then Santa Claus exists. Therefore the answer to the hypothetical question must be yes: Santa Claus does exist if the sentence is true. However, that is exactly what the sentence states: not that Santa Claus exists, but that he exists if the sentence is true, which is what the hypothetical answer just established. Therefore the sentence is true after all, and since we have established that Santa Claus exists if the sentence is true, and that it is true, it follows that Santa Claus must exist. Another approach at it is if you think, Santa Claus does not exist. Then, obviously, the sentence cannot be true; otherwise he would exist. So, it must be false. However, the original sentence could be rewritten as "If this sentence is false, then Santa Claus doesn't exist." Because we already assumed that Santa does not exist, and that the statement is false, this fits perfectly into the new sentence, making it true. This now states that it is not true that "Santa Claus doesn't exist." This, of course, leads us back to the original sentence being true. (One could also see this as an elaboration of the liar paradox.)

Since any claim can be substituted for "Santa Claus exists", including, for example, "Santa Claus does not exist", and the above argument will show that claim is true, there is a paradox.

In mathematical logic

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

tautology

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

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

X\ {\stackrel {\mathrm {def} }{=}}\ \left\{x\mid (x\in x)\to Y\right\}.

The proof proceeds:

{\begin{matrix}{\mbox{1.}}&(X\in X)\iff ((X\in X)\to Y)&{\mbox{definition of X}}\\{\mbox{2.}}&(X\in X)\to ((X\in X)\to Y)&{\mbox{from 1}}\\{\mbox{3.}}&(X\in X)\to Y&{\mbox{from 2, contraction}}\\{\mbox{4.}}&((X\in X)\to Y)\to (X\in X)&{\mbox{from 1}}\\{\mbox{5.}}&X\in X&{\mbox{from 3 and 4, modus ponens}}\\{\mbox{6.}}&Y&{\mbox{from 3 and 5, modus ponens}}\end{matrix}}

Again a particular case of this paradox is when Y is in fact a contradiction. Then X becomes $\scriptstyle \left\{x\mid (x\in x)\to (Z\wedge \neg Z)\right\}$ . This then implies that any x that is an element of x cannot be an element of X since this would imply $\scriptstyle (Z\wedge \neg Z)$ . Hence $\scriptstyle X=\left\{x\mid (x\notin x)\right\}$ , the set of all sets which do not contain themselves. This is exactly Russell's paradox.

Discussion

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

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");
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;
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
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 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.

Proposed solutions

In "Epimenides and Curry" (Analysis, vol. 46., no. 3), Laurence Goldstein relates Curry's paradox to the Epimenides paradox, proposing that each results from a particular kind of self-reference; namely, one that assigns conflicting truth-values to the same proposition.

In this case, this is disguised, but can be shown by means of material implication: the statement "X" is given as equal to "X implies Y", which is in turn equal to "not X or Y." That is, we can only identify these two statements if Y is true—otherwise we have defined X as equal to its own complement, which is obviously nonsensical; and so the paradox is resolved. Nevertheless, it should be emphasised that the paradox does not depend on interpreting the "if..then" as material implication, and the paradox can still occur if this particular account of the conditional is rejected.

Linear logic with its exponential operators removed disallows contraction and so does not admit this paradox.

References

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

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]" Relevant First-Order Logic LP# and Curry's Paradox http://front.math.ucdavis.edu/0804.4818

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

[1]