Can someone help me understand Curry's paradox?

Question

I understand the general concept, that if you define a statement X such that X = X $\Rightarrow$ Y, you can prove that X is true regardless of Y so you can then prove any statement. What I don't quite understand is how one proves that X is true.

I have tried to prove it using the three main ways of proving an implication, contradiction, contrapositive, and direct, but the last two methods are unsatisfactory.

Contradiction:
Suppose X is true and Y is false.
Then X $\Rightarrow$ Y is false.
But X = X $\Rightarrow$ Y.
X cannot be both true and false. So X cannot be true when Y is false.
So X $\Rightarrow$ Y is true, so X is true.
QED

This way I understand and seems fine, what trips me up is direct and contrapositive, with direct assuming what you are trying to show and contrapositive showing that X is both true and false.

Direct:
Suppose X is true.
Then since X = X $\Rightarrow$ Y is true, and X is true, Y is true.
So X $\Rightarrow$ Y is true, and hence X is true.
QED

This seems to assume what we are trying to prove.

Contrapositive:
Suppose Y is false.
If X is true, then X $\Rightarrow$ Y is false.
But X = X $\Rightarrow$ Y so X is false.
X cannot be both true and false, so X is false.
Therefore X $\Rightarrow$ Y is true, so X is true.
QED

This is troubling because X has been shown to be both true and false.

I guess what I am asking is what is the accepted way to prove that a statement X = X $\Rightarrow$ Y is true to construct Curry's paradox, and why do some proof methods seem incorrect or contradictory?

Answer 1

First of all, $X \leftrightarrow (X \rightarrow Y)$ implies both $X$ and $Y$, and the whole point of the Curry Paradox is to show that $Y$ is true ... $X$ is just a 'helper'.

Second, you can show that $X \leftrightarrow (X \rightarrow Y)$ implies both $X$ and $Y$ in various ways:

First, truth-table:

\begin{array}{cc|c} X&Y&X \leftrightarrow (X \rightarrow Y)\\ \hline T&T&T\\ T&F&F\\ F&T&F\\ F&F&F\\ \end{array}

We see that $X \leftrightarrow (X \rightarrow Y)$ is only true in row 1 ... when $X$ and $Y$ are both true

Second, algebra:

$X \leftrightarrow (X \rightarrow Y) \overset{Equivalence}\Leftrightarrow$

$(X \rightarrow (X \rightarrow Y)) \land ((X \rightarrow Y) \rightarrow X) \overset{Implication}\Leftrightarrow$

$(\neg X \lor (\neg X \lor Y)) \land (\neg (\neg X \lor Y) \lor X) \overset{Association, DeMorgan}\Leftrightarrow$

$(\neg X \lor \neg X \lor Y) \land ((X \land \neg Y) \lor X) \overset{Idempotence, Absorption}\Leftrightarrow$

$(\neg X \lor Y) \land X \overset{Reduction}\Leftrightarrow$

$Y \land X$

Third, formal proof:

Answer 2

Both the "direct" and "contrapositive" arguments you gave work just as well as the "contradiction" argument.

The "direct" argument doesn't fall prey to assuming what you are trying to prove. It uses the structure that if we assume $A$ and prove $B$ from that assumption, we obtain $A \implies B$ assumption-free. Using this, we assume $X$ and prove $Y$ (dependent on assuming $X$). Thus we have $X \implies Y$ assumption-free. Then we get $X$ assumption-free by the equivalence of $X \implies Y$ and $X$ -- this is different from the original assumption of $X$ because now it is assumption-free.

The "contrapositive" argument doesn't show $X$ is both false and true. It shows $X$ is false under the assumption that $Y$ is false. This gives us $X \implies Y$ assumption-free, so $X$ is true assumption-free. Nowhere in the course of the argument is $X$ shown to be false assumption-free.