Curry's paradox

The standard method for proving conditional sentences (sentences of the form "if A, then B") is called "conditional proof". In this method, in order to prove "if A, then B", first A is assumed and then with that assumption B is shown to be true.

To produce Curry's paradox, as described in the two steps above, apply this method to the sentence "if this sentence is true, then Germany borders China". Here A, "this sentence is true", refers to the overall sentence, while B is "Germany borders China". So, assuming A is the same as assuming "If A, then B". Therefore, in assuming A, we have assumed both A and "If A, then B". Therefore, B is true, by modus ponens, and we have proven "If this sentence is true, then 'Germany borders China' is true." in the usual way, by assuming the hypothesis and deriving the conclusion.

Now, because we have proved "If this sentence is true, then 'Germany borders China' is true", then we can again apply modus ponens, because we know that the claim "this sentence is true" is correct. In this way, we can deduce that Germany borders China.

The example in the previous section used unformalized, natural-language reasoning. Curry's paradox also occurs in some varieties of formal logic. In this context, it shows that if we assume there is a formal sentence (X → Y), where X itself is equivalent to (X → Y), then we can prove Y with a formal proof. One example of such a formal proof is as follows. For an explanation of the logic notation used in this section, refer to the list of logic symbols.

1. X := (X → Y)
   
   assumption, the starting point, equivalent to "If this sentence is true, then Y"
2. X → X
   
   law of identity
3. X → (X → Y)
   
   substitute right side of 2, since X is equivalent to X → Y by 1
4. X → Y
   
   from 3 by contraction
5. X
   
   substitute 4, by 1
6. Y
   
   from 5 and 4 by modus ponens

An alternative proof is via Peirce's law. If X = X → Y then (X → Y) → X. This together with Peirce's law ((X → Y) → X) → X and modus ponens implies X and subsequently Y (as in above proof).

Therefore, if Y is an unprovable statement in a formal system, there is no statement X in that system such that X is equivalent to the implication (X → Y). By contrast, the previous section shows that in natural (unformalized) language, for every natural language statement Y there is a natural language statement Z such that Z is equivalent to (Z → Y) in natural language. Namely, Z is "If this sentence is true then Y".

In specific cases where the classification of Y is already known, few steps are needed to reveal the contradiction. For example, when Y is "Germany borders China," it is known that Y is false.

1. X = (X → Y)
   
   assumption
2. X = (X → false)
   
   substitute known value of Y
3. X = (¬X ∨ false)
   
   implication
4. X = ¬X
   
   identity

Even if the underlying mathematical logic does not admit any self-referential sentences, certain forms of naive set theory are still vulnerable to Curry's paradox. In set theories that allow unrestricted comprehension, we can nevertheless prove any logical statement Y by examining the set

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

Assuming that both ${\displaystyle \in }$ and ${\displaystyle =}$ takes binding precedence over both ${\displaystyle \to }$ and ${\displaystyle \leftrightarrow }$, the proof proceeds as follows:

1. ${\displaystyle X=\left\{x\mid x\in x\to Y\right\}}$
   
   Definition of X
2. ${\displaystyle x=X\to (x\in x\leftrightarrow X\in X)}$
   
   Substitution of equal sets in membership
3. ${\displaystyle x=X\to ((x\in x\to Y)\leftrightarrow (X\in X\to Y))}$
   
   Addition of a consequent to both sides of a biconditional (from 2)
4. ${\displaystyle X\in X\leftrightarrow (X\in X\to Y)}$
   
   Law of concretion (from 1 and 3)
5. ${\displaystyle X\in X\to (X\in X\to Y)}$
   
   Biconditional elimination (from 4)
6. ${\displaystyle X\in X\to Y}$
   
   Contraction (from 5)
7. ${\displaystyle (X\in X\to Y)\to X\in X}$
   
   Biconditional elimination (from 4)
8. ${\displaystyle X\in X}$
   
   Modus ponens (from 6 and 7)
9. ${\displaystyle Y}$
   
   Modus ponens (from 8 and 6)

Step 4 is the only step invalid in a consistent set theory. In Zermelo–Fraenkel set theory, an extra hypothesis stating X is a set would be required, which is not provable in ZF or in its extension ZFC (with the axiom of choice).

Therefore, in a consistent set theory, the set ${\displaystyle \left\{x\mid x\in x\to Y\right\}}$ does not exist for false Y. This can be seen as a variant on Russell's paradox, but is not identical. 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. The existence of proofs like the one above shows that such a task is not so simple, because at least one of the deduction rules used in the proof above must be omitted or restricted.

Curry's paradox may be expressed in untyped lambda calculus, enriched by restricted minimal logic. To cope with the lambda calculus's syntactic restrictions, ${\displaystyle m}$ shall denote the implication function taking two parameters, that is, the lambda term ${\displaystyle ((mA)B)}$ shall be equivalent to the usual infix notation ${\displaystyle A\to B}$.

An arbitrary formula ${\displaystyle Z}$ can be proved by defining a lambda function ${\displaystyle N:=\lambda p.((mp)Z)}$, and ${\displaystyle X:=({\textsf {Y}}N)}$, where ${\displaystyle {\textsf {Y}}}$ denotes Curry's fixed-point combinator. Then ${\displaystyle X=(NX)=((mX)Z)}$ by definition of ${\displaystyle {\textsf {Y}}}$ and ${\displaystyle N}$, hence the above sentential logic proof can be duplicated in the calculus:[3][4][5]

$${\displaystyle {\begin{array}{cll}\vdash &((mX)X)&{\mbox{ by the minimal logic axiom }}A\to A\\\vdash &((mX)((mX)Z))&{\mbox{ since }}X=((mX)Z)\\\vdash &((mX)Z)&{\mbox{ by the theorem }}(A\to (A\to B))\vdash (A\to B){\mbox{ of minimal logic }}\\\vdash &X&{\mbox{ since }}X=((mX)Z)\\\vdash &Z&{\mbox{ by modus ponens }}A,(A\to B)\vdash B{\mbox{ from }}X{\mbox{ and }}((mX)Z)\\\end{array}}}$$

In simply typed lambda calculus, fixed-point combinators cannot be typed and hence are not admitted.

Curry's paradox may also be expressed in combinatory logic, which has equivalent expressive power to lambda calculus. Any lambda expression may be translated into combinatory logic, so a translation of the implementation of Curry's paradox in lambda calculus would suffice.

The above term ${\displaystyle X}$ translates to ${\displaystyle (r\ r)}$ in combinatory logic, where

$${\displaystyle r={\textsf {S}}\ ({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))\ ({\textsf {K}}Z);}$$

hence[6]

$${\displaystyle (r\ r)=((m(rr))\ Z).}$$

In the 1930s, Curry's paradox and the related Kleene–Rosser paradox played a major role in showing that formal logic systems based on self-recursive expressions are inconsistent. These include some versions of lambda calculus and combinatory logic.

Curry began with the Kleene–Rosser paradox[7] and deduced that the core problem could be expressed in this simpler Curry's paradox.[8][9] His conclusion may be stated as saying that combinatory logic and lambda calculus cannot be made consistent as deductive languages, while still allowing recursion.

In the study of illative (deductive) combinatory logic, Curry in 1941[10] recognized the implication of the paradox as implying that, without restrictions, the following properties of a combinatory logic are incompatible:

1. Combinatorial completeness. This means that an abstraction operator is definable (or primitive) in the system, which is a requirement on the expressive power of the system.
2. Deductive completeness. This is a requirement on derivability, namely, the principle that in a formal system with material implication and modus ponens, if Y is provable from the hypothesis X, then there is also a proof of X → Y.[11]

The origin of Alonzo Church's lambda calculus may have been, "How can you solve an equation, to provide a definition of a function?". This is expressed in this equivalence,

$${\displaystyle f\ x=y\iff f=\lambda x.y.}$$

This definition is valid if there is one and only one function ${\displaystyle f}$ that satisfies the equation ${\displaystyle f\ x=y}$, but invalid otherwise. This is the core of the problem that Stephen Cole Kleene and then Haskell Curry discovered with combinatory logic and Lambda calculus.

The situation may be compared to defining

$${\displaystyle y=x^{2}\iff x={\sqrt {y}}.}$$

This definition is fine as long as only positive values are allowed for the square root. In mathematics an existentially quantified variable may represent multiple values, but only one at a time. Existential quantification is the disjunction of many instances of an equation. In each equation is one value for the variable.

However, in mathematics, an expression with no free variables must have one and only one value. So ${\displaystyle {\sqrt {4}}}$ can only represent ${\displaystyle +2}$. However, there is no convenient way to restrict the lambda abstraction to one value or to assure that there is a value.

Lambda calculus allows recursion by passing the same function that is called as a parameter. This allows situations where ${\displaystyle f\ x=y}$ has multiple or no solutions for ${\displaystyle f}$.

Lambda calculus may be considered as part of mathematics if only lambda abstractions that represent a single solution to an equation are allowed. Other lambda abstractions are incorrect in mathematics.

Curry's paradox and other paradoxes arise in Lambda calculus because of the inconsistency of Lambda calculus considered as a deductive system. See also deductive lambda calculus.

Lambda calculus is a consistent theory in its own domain. However, it is not consistent to add the lambda abstraction definition to general mathematics. Lambda terms describe values from the lambda calculus domain. Each lambda term has a value in that domain.

When translating expressions from mathematics to lambda calculus, the domain of lambda calculus terms is not always isomorphic to the domain of the mathematical expressions. This lack of isomorphism is the source of the apparent contradictions.

There are many language constructs that implicitly invoke an equation that may have none or many solutions. The sound resolution to this problem is to syntactically link these expressions to an existentially quantified variable. The variable represents the multiple values in a way that is meaningful in common human reasoning, but is also valid in mathematics.

For example, a natural language that allows the Eval function is not mathematically consistent. But each call to Eval in that natural language may be translated into mathematics in a way that is consistent. The translation of Eval(s) into mathematics is

So where s = "Eval(s) → y",

If y is false, then the x = x → y is false, but this is a falsehood, not a paradox.

The existence of the variable x was implicit in the natural language. The variable x is created when the natural language is translated into mathematics. This allows us to use natural language, with natural semantics, while maintaining mathematical integrity.

The argument in formal logic starts with assuming the validity of naming (X → Y) as X. However, this is not a valid starting point. First we must deduce the validity of the naming. The following theorem is easily proved and represents such a naming:

$${\displaystyle \forall A,\exists X,X=A.}$$

In the above statement the formula A is named as X. Now attempt to instantiate the formula with (X → Y) for A. However, this is not possible, as the scope of ${\displaystyle \exists X}$ is inside the scope of ${\displaystyle \forall A}$. The order of the quantifiers may be reversed using Skolemization:

$${\displaystyle \exists f,\forall A,f(A)=A.}$$

However, now instantiation gives

$${\displaystyle f(X\to Y)=X\to Y,}$$

which is not the starting point for the proof and does not lead to a contradiction. There are no other instantiations for A that lead to the starting point of the paradox.

In Zermelo–Fraenkel set theory (ZFC), the axiom of unrestricted comprehension is replaced with a group of axioms that allow construction of sets. So Curry's paradox cannot be stated in ZFC. ZFC evolved in response to Russell's paradox.